first-go-at-sudoku-solver.rb

#!/usr/bin/env ruby

# construct the array of possibilities
def construct_board(board)
  unknown_count = 0

  board.each_with_index do |row, row_index|
    row.each_with_index do |cell_value, column_index|
      if cell_value.nil?
        board[row_index][column_index] = (1..9).to_a
        unknown_count += 1
      end
    end
  end

  return board, unknown_count
end

def solve_function(board, prior_unknown_count)
  board.each_with_index do |row, row_index|
    row.each_with_index do |cell_value, column_index|
      if cell_value.is_a?(Integer)
        # filter rows
        row.each_with_index do |filter_cell_value, filter_column_index|
          next if filter_cell_value.is_a?(Integer)
          filter_cell_value.delete(cell_value)
        end

        # filter columns
        board.each do |filter_row_values|
          next if filter_row_values[column_index].is_a?(Integer)
          filter_row_values[column_index].delete(cell_value)
        end

        # filter blocks
        row_block_start, column_block_start = ((row_index / 3.to_f).floor * 3), ((column_index / 3.to_f).floor * 3)
        row_block_start.upto(row_block_start + 2) do |filter_row_index|
          column_block_start.upto(column_block_start + 2) do |filter_column_index|
            next if board[filter_row_index][filter_column_index].is_a?(Integer)
            board[filter_row_index][filter_column_index].delete(cell_value)
          end
        end
      end
    end
  end

  unknown_count = 0
  guesses = []
  # assign for squares where only one possibility exists
  board.each_with_index do |row, row_index|
    row.each_with_index do |cell, column_index|
      if cell.is_a?(Array) && cell.length == 0
        raise "Dead end"
      elsif cell.is_a?(Array)
        guesses << {length: cell.length, row: row_index, column: column_index}
        unknown_count += 1
      end
    end
  end

  puts [prior_unknown_count, unknown_count].inspect

  # guess
  if unknown_count == 0
    puts "Solved"

    board.each do |row|
      puts row.join(" ")
    end

    exit
  elsif prior_unknown_count == unknown_count
    puts "We are going to start guessing."

    guesses.sort_by { |g| g[:length] }.each do |guess|
      board[guess[:row]][guess[:column]].each do |guess_value|
        guess_board = board
        guess_board[guess[:row]][guess[:column]] = guess_value
        solve_function(guess_board, unknown_count)
      end
    end
  else
    puts "Unknown count: #{unknown_count}"
    solve_function(board, unknown_count)
  end
end

puzzle = [
            [  5,   3, nil, nil,   7, nil, nil, nil, nil],
            [  6, nil, nil,   1,   9,   5, nil, nil, nil],
            [nil,   9,   8, nil, nil, nil, nil,   6, nil],
            [  8, nil, nil, nil,   6, nil, nil, nil,   3],
            [  4, nil, nil,   8, nil,   3, nil, nil,   1],
            [  7, nil, nil, nil,   2, nil, nil, nil,   6],
            [nil,   6, nil, nil, nil, nil,   2,   8, nil],
            [nil, nil, nil,   4,   1,   9, nil, nil,   5],
            [nil, nil, nil, nil,   8, nil, nil,   7,   9]
]

puzzle, unknown_count = construct_board(puzzle)
puts unknown_count.inspect
solve_function(puzzle, unknown_count)