Re: [QUIZ] Sodoku Solver (#43) [SOLUTION]

> My strategy was to build an array of the possible moves for every row,
> every column and every 3x3 block, then take their intersection.  I
> believe some other authors have already posted this concept; I'm only
> posting because I appear to be the only person to do it using array
> subtraction.  :-)  I find the intersection that has the fewest options
> available to it, and iterate over those choices, using recursion to
> solve the rest of the board.  

Ahem... Mine used array subtraction too. Sorry.

--- SNIP (class Options) ----

  def calculate_options_at( row, col )
    ( 
      [1, 2, 3, 4, 5, 6, 7, 8, 9] -
      board.row( row ) - 
      board.col( col ) - 
      board.region( 
        board.get_region_num( row, col ) 
      )
    )
  end

--- SNIP -----

I actually worked on this before the Sudoku challenge even came up. I
think, based on your e-mail, it uses the same recursive algorithm that
you do, but I haven't verified that yet.

Also, there's less idiomatic Ruby here than there could / should be.
After re-reading this code I realize that some of these methods can be
reduced to one-liners.

Here it is (Download at http://muthanna.com/ruby-sudoku.tar.gz).

#!/usr/bin/env ruby

=begin rdoc
The Ruby Sudoku Solver

Mohit Muthanna Cheppudira <[e-mail]>

Sudoku, Japanese,  sometimes spelled Su Doku, 
is a placement puzzle, also known as Number Place in the 
United States. The aim of the puzzle is to enter a numeral 
from 1 through 9 in each cell of a grid, most frequently a 
9 grid made up of 3ラ3 subgrids (called "regions"), starting 
with various numerals given in some cells (the "givens"). Each 
row, column and region must contain only one instance of each 
numeral.

To Learn more about Sudoku, visit the great Wikipedia.

This implementation of the Sudoku solver uses an educated brute
force approach. By educated brute-force, I mean the solver:

* Narrows down options available in the empty places
* Fills in cells that have only one option
* For cells that have more than one option:
  * Try each one, then recurse (Narrow down, fill-in, etc.).

This file consists of five classes:

* Line: Represents a set of 9 cells. This could be a Row, a
Column, or a Region.

* Options: Represents a set of valid options for a cell. This is 
meant to be used as a workspace or scratch-pad for the Solver.

* Board: Represents the 9x9 Sudoku board. Has helper methods
to access cells, rows, columns and regions.

* Csv: Utility class used to load boards from CSV files.

* Solver: Our educated brute-force solver.
=end

module Sudoku


=begin rdoc

A Sudoku Line is basically an array that is
1-indexed. A Line could be a complete row, column or region.

=end

class Line < Array

=begin rdoc
This class variable represents the set of digits that
are valid in a Sudoku cell.
=end

  @@valid_digits = [1, 2, 3, 4, 5, 6, 7, 8, 9] 

=begin rdoc
We overload the [] operator so that the cells are
indexed from 1 till 9, instead of 0 till 8.
=end

  def []( num )
    at( num - 1 )
  end

=begin rdoc
The to_s method is called by other methods that
need a string representation of the class. E.g., puts()
 
In this case, the code:

   line = Line.new << 0 << 1 << 4 << 5
   puts line
  
Displays:
  
  0, 1, 4, 5
=end

  def to_s
    self.join( ", " )
  end

=begin
This method returns a list of missing digits
in the line.
=end

  def missing_digits
    return @@valid_digits - self
  end

=begin
Check if the Line or Region is
valid, i.e., has unique digits between
1 and 9, and has no zeros.

This method is used by the Solver to determine
if the solution is correct.
=end

  def valid?
    digits = Array.new

    # Navigate each cell:
    (1..9).each do |value|

      # Invalid if any zeros.
      return false if self[value] == 0 

      # Invalid if duplicate.
      if digits[self[value]] == true 
        return false
      else 
        # First occurrence. Log it.
        digits[self[value]] = true
      end
    end

    # Valid Line.
    return true
  end
end

=begin rdoc
This class defines a basic 9 x 9 Sudoku
board. The board is subdivided into smaller
3 x 3 regions. These regions are numbered
from 1 to 9 as so: Top to Bottom, Left to Right.

e.g., Top Left is Region 1
      The region beneath 1 (row 4, col 1) is 2
      Top Middle is Region 4.

      You get the picture.
=end

class Board
  def initialize( board = nil )
    if board == nil
      reset
    else
      # Our copy constructor. In ruby all variables are
      # references to classes. Copies have to be 
      # explicit. 
      reset
      board.each {|row, col, val| self[row,col] = val}
    end
  end

=begin rdoc
Our board is represented by a two-dimensional 9x9 array.
=end

  def reset
    @board = Array.new( 9 ) { Array.new( 9, 0 ) }
  end

=begin rdoc
Cells in this board can be referenced with this method. Uses row, col; not x, y.
A bit retarded, but works.
=end

  def []( row, col )
    return @board[col-1][row-1]
  end

  def []=( row, col, val )
    return (@board[col-1][row-1] = val)
  end

=begin
Draw up a simple ASCII Sudoku board.
=end

  def to_s
    string = "    1  2  3  4  5  6  7  8  9\n"
    string += "  +--------------------------\n"
    filled_in = 0

    (1..9).each do |r| 
      row( r ).each { |cell| filled_in += 1 unless cell == 0 }
      string += r.to_s + " | " + row( r ).to_s + "\n"
    end

    return string + "Filled: #{filled_in} / 81\n"
  end

  def row( row_num )
    r = Line.new
    (1..9).each { |c| r << self[ row_num, c ] }

    return r
  end

  def col( col_num )
    return Line.new( @board[ col_num - 1] )
  end

=begin
Return a region (class Line) of cells determined
by a region number. The regions are numbered incrementally
top to bottom, left to right. So the cell at row 2, column
2 is at region 1; 5, 5 is region 5; 7, 4 is region 8.
=end
  def region( region_num )
    region = Line.new

    start_row = ((( (region_num - 1) % 3 )) * 3) + 1
    start_col = (((region_num - 1) / 3) * 3) + 1

    (start_row..start_row + 2).each do |row|
      (start_col..start_col + 2).each do |col|
        region << self[row, col]
      end
    end

    return region
  end

=begin
Return a region number given a row and column.
=end
  def get_region_num( row, col )
    region_row = ( (row - 1) / 3 ) + 1
    region_col = ( (col - 1) / 3 ) + 1

    region_num = region_row + ( 3 * (region_col - 1))
  end

=begin
Used to iterate through each cell on the board.
=end
  def each
    (1..9).each do |row|
      (1..9).each do |col|
        yield row, col, self[row, col]
      end
    end
  end

=begin rdoc
Go through each row, column and region to 
determine if the board is valid.
=end

  def valid?
    (1..9).each do |line|
      return false if (
        !row( line ).valid? ||
        !col( line ).valid? ||
        !region( line ).valid? 
        )
    end

    return true
  end

end

=begin
This class loads a Sudoku board from a CSV file, A sample
board would look like this:

# Sample Board

0,0,0,0,2,3,4,0,0
0,6,3,0,9,8,0,0,0
4,0,0,5,0,0,0,0,0
0,2,5,0,8,0,0,7,3
0,1,0,0,0,0,0,5,0
6,4,0,0,5,0,1,9,0
0,0,0,0,0,5,0,0,8
0,0,0,9,7,0,3,6,0
0,0,6,8,3,0,0,0,0

Blank lines and lines beginning with hashes (#) are
ignored.

You can also save to CSV files by generating a 
string via the to_s method.
=end

class Csv
  def initialize( board = nil )
    if board == nil
      @board = Board.new
    else
      @board = board
    end
  end

  def load( file_name )
    File.open( file_name, "r" ) do |file|
      row = 1

      while line = file.gets

        # Strip out all comments and
        # blank lines.
        line.chomp!
        next if line =~ /^\s*#/
        next if line =~ /^\s*$/

        col = 1
        line.split(",").each do |value|
          @board[row, col] = value.to_i
          col += 1
        end

        row += 1
      end
    end

    @board
  end

=begin rdoc
Generate a CSV string representing the board.
=end
  def to_s
    string = ""

    (1..9).each do |r| 
      string += @board.row( r ).to_s + "\n"
    end

    return string 
  end
end

=begin
This class is represents a set of options for Sudoku cells. It's
simply a three dimensional array.
=end

class Options
  def initialize
    @options = Array.new( 9 ) { Array.new( 9 ) { Array.new } }
  end

  def []( row, col )
    return @options[col-1][row-1]
  end
  
  def []=( row, col, val )
    return (@options[col-1][row-1] = val)
  end

  def to_s
    string = ""

    (1..9).each do |row|
      (1..9).each do |col|
        string += self[row, col].join(",") + ":"
      end
      string += "\n"
    end

    string
  end 
end

=begin
Our Edumicated Brute-Force Sudoku Solver.
=end

class Solver
  
  attr_accessor :board, :options

  def initialize( board=nil )
    if board
      @board = board
    else 
      @board = Board.new
    end    
    
    @options = Options.new
  end

=begin rdoc
This method returns a list of digits that are valid inside
a specific cell. It works by subtracting the set of cells
in the specific row, column and region from a full-line, i.e,
[1, 2, 3, 4, 5, 6, 7, 8, 9].
=end

  def calculate_options_at( row, col )
    ( 
      [1, 2, 3, 4, 5, 6, 7, 8, 9] -
      board.row( row ) - 
      board.col( col ) - 
      board.region( 
        board.get_region_num( row, col ) 
      )
    )
  end

=begin rdoc
This method navigates through each cell in the board,
calculating a set of options for the cell. For cells
that have just one available option:

  * Set the cell with the available option.
  * Recalculate options.

If no options could be calculated, we hit a dead-end; return
false.
=end

  def calculate_options
    again = true
    have_options = false

    while again
      again = false
      self.options = Options.new

      # Navigate each cell...
      board.each do |row, col, value|

        # If the cell is empty...
        if value == 0
          
          # Set the options for the cell
          options[ row, col ] += calculate_options_at( row, col )
        end

        # How many options do we have?
        number_of_options = options[row, col].length

        # We had atleast one option; set return code.
        have_options = true if number_of_options > 0

        # Only one option here, reflect it on the
        # board.
        if number_of_options == 1
          board[row, col] = options[row, col][0]
          again = true
        end
      end
    end

    have_options
  end

=begin rdoc
Our solve algorithm. 
=end
  def brute_force

    # First narrow the board down.
    calculate_options

    # Navigate each cell
    board.each do |row, col, value|

      # If we see and empty cell:
      if value == 0

        # Navigate each option
        options[row, col].each do |an_option|

          # Save the state of the board, this is
          # necessary because calculate_options()
          # mangles the board.
          old_board = Board.new( board )
           
          # Try this option
          board[row, col] = an_option

          # Recurse
          return true if brute_force
         
          # No solution. Revert to saved board
          # and try the next option.
          @board = old_board
        end

        break
      end

    end

    # Did we solve it?
    return true if board.valid? 
    false
  end

  def solve
    brute_force
  end
end

=begin rdoc
Example code using this library. Reads a Sudoku-board file 
from the command-line and solves it.
=end

def Sudoku.main
  puts "Ruby Sudoku Solver - 12 Aug 2005"
  puts "Mohit Muthanna Cheppudira <[e-mail]>"
  puts

  unless ARGV[0]
    puts "Usage: #{$0} filename"
    exit
  end

  # Load the board directly into the Solver.
  solver = Solver.new( Csv.new().load( ARGV[0] ))

  # Display the unsolved board.
  puts "Problem:"
  puts solver.board
  
  if solver.solve
    puts "\nSolution:"
  else
    puts "\nNo Solution. Best match:"
  end

  # Display the final board.
  puts solver.board
end

Sudoku.main

end