Shahzad Bhatti Welcome to my ramblings and rants!

April 2, 2006

Sudoku Solver in Ruby

Filed under: Computing — admin @ 10:37 pm

Sudoku Solver in Ruby
This weekend I spent a couple of hours to write a simple solver for Sudoku
puzzles in Ruby. Despite Here is how the algorithm works:

  • Create a matrix of 9×9
  • Initialize each cell in 9×9 matrix with all possible values, which will
    be 1..9.
  • Load partial solution from a data file specified by the user. The data
    file stores number in simple lines, where each number is separated by
    space and empty cells are represented by 0. For example:

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

  • Loop – while sudoku puzzle is not solved
    • Normalize grid by comparing the set of possible values for each
      unsolved cell against values in its row, column and minigrid
      and remove those values from the set of possible values.
    • If there are no remaining unsolved cells remaining then quit.
    • Sort grid cells by least number of possible values. This means that
      solved cells will come up first, followed by cells with only two,three
      or four possible values.
    • Pick the cell that is not yet solved and select a number from its
      set of possible values.
    • Go back to loop

Here is complete source code or download it directly from http://bhatti.plexobject.com/sudoku_solver.rb.

  1 #
  2 # == Synopsis
  3 # sudoku_solver.rb solves Sudoku Puzzles.
  4 #
  5 # == Usage
  6 #    ruby sudoku_solver.rb  [ -h | --help ] [ -v | -- verbose ] [ -f | --file inputfile ]
  7 #    The input file stores Sudoku puzzle. Separate each number by a space
  8 #    in the file and use 0 for empty cells.
  9 #
 10 # == Author
 11 #  Shahzad Bhatti
 12 #
 13 # == Copyright
 14 #   None, whatsover.
 15 #
 16 require 'optparse'
 17 require 'rdoc/usage'
 18 require "benchmark"
 19 include Benchmark
 20 
 21 #
 22 ### Cell represents a single cell in the in the Soduku matrix, i.e., there
 23 ### will be 9 cells in a row of matrix and 9 cells in column.
 24 #
 25 class Cell
 26   include Comparable
 27   attr_reader :id
 28 
 29   public
 30   def initialize(id, min, max)
 31     @id = id
 32     @possible_numbers = []
 33     fill(min, max)
 34   end
 35 
 36   #
 37   ### fills internal array values with all possible values
 38   #
 39   def fill(min, max)
 40     for i in 0 ... max
 41       @possible_numbers[i] = i+min
 42     end
 43   end
 44 
 45   #
 46   ### allows sorting based on number of possibilities
 47   ### this will be used so that we sort cells by reducing number of
 48   ### possibilities.
 49   #
 50   def <=>(other)
 51     size <=> other.size
 52   end
 53 
 54   #
 55   ### accessor array
 56   #
 57   def [](indice)
 58     @possible_numbers[indice]
 59   end
 60 
 61   #
 62   ### return number of possible values
 63   #
 64   def size
 65     @possible_numbers.length
 66   end
 67 
 68   #
 69   ### pick any number randomly from the set of possible values
 70   #
 71   def pick_any
 72     num = random_number
 73     if (num < 0)
 74       num = 0
 75     else
 76       num = num % @possible_numbers.length
 77     end
 78     @possible_numbers = [@possible_numbers[num]] if (!solved?)
 79   end
 80 
 81   #
 82   ### settor array operator
 83   #
 84   def set(value)
 85     raise ArgumentError if (value == nil || value.length == 0)
 86     @possible_numbers = value if (value[0] > 0)
 87   end
 88 
 89   #
 90   ### return array of possible values for this cell
 91   #
 92   def get
 93     @possible_numbers
 94   end
 95 
 96   #
 97   ### remove solved solutions from possible values
 98   #
 99   def remove(already_solved)
100     return if (already_solved == nil || already_solved.length == 0)
101     new_values = []
102     for i in 0 ... @possible_numbers.length
103       @possible_numbers.delete_at(i) if (already_solved.include?(@possible_numbers[i]))
104     end
105   end
106 
107   #
108   ### returns true if solved
109   #
110   def solved?()
111     return @possible_numbers.length == 1
112   end
113 
114   #
115   ### stringified array
116   #
117   def to_s
118     buffer = ""
119     for i in 0 ... @possible_numbers.length
120       buffer += @possible_numbers[i].to_s
121     end
122     buffer
123   end
124   #
125   ### generates a random number
126   #
127 
128   private
129   def random_number
130     t = Time.now.to_f / (Time.now.to_f % Time.now.to_i)
131     random_seed = t * 1103515245 + 12345;
132     num = Integer((random_seed / 65536) % 32768)
133   end
134 end
135 
136 #
137 ### A general purpose class to represent multi-dimensional arrays in Ruby
138 #
139 class MultiDimensionalArray
140   #
141   ### multi-dimensional array object
142   #
143   def initialize(*dimensions)
144     @dimensions = Array.new(dimensions.length)
145     @factors = Array.new(dimensions.length)
146     product = 1
147     i = dimensions.length - 1
148     while i >= 0
149       @dimensions[i] = dimensions[i]
150       @factors[i] = product
151       product *= @dimensions[i]
152       i -= 1
153     end
154     @data = Array.new(product)
155   end
156   #
157   ### find offset from Array
158   #
159   def getOffset(indices)
160     raise IndexError if indices.length != @dimensions.length
161     offset = 0
162     for i in 0 ... @dimensions.length
163       if indices[i] < 0 or indices[i] >= @dimensions[i]
164         raise IndexError
165       end
166       offset += @factors[i] * indices[i]
167     end
168     return offset
169   end
170 
171   #
172   ### accessor array
173   #
174   def [](*indices)
175     @data[self.getOffset(indices)]
176   end
177 
178   #
179   ### setter array
180   #
181   def []=(*indicesAndValue)
182     value = indicesAndValue.pop
183     @data[self.getOffset(indicesAndValue)] = value
184   end
185 
186   #
187   ### stringified object
188   #
189   def to_s
190     @data
191   end
192 end
193 
194 #
195 ### This class stores entire Sudoku matrix or matrix, where each cell
196 ### is initialized with partial solution specified by the user (from file).
197 #
198 class Matrix
199   MIN_NUMBER = 1
200   MAX_NUMBER = 9
201 
202   include Comparable
203   attr_reader :cells
204   attr_reader :dims
205   attr_reader :mini_dims
206 
207   public
208   #
209   ### constructor that initializes Sudoku matrix 9x9
210   #
211   def initialize(dims=MAX_NUMBER)
212     @dims = dims
213     @mini_dims = Math.sqrt(dims)
214     @cells = MultiDimensionalArray.new(dims, dims)
215     for i in 0 ... dims
216       for j in 0 ... dims
217         @cells[i, j] = Cell.new(i*dims+j, MIN_NUMBER, MAX_NUMBER)
218       end
219     end
220   end
221 
222   #
223   ### accessor array operator
224   #
225   def [](i, j)
226     @cells[i, j]
227   end
228 
229   #
230   ### return array of solved numbers for given row and column
231   #
232   def get_solved_numbers(row, col)
233     solved = []
234     for i in 0 ... dims
235       solved.push(@cells[row, i][0]) if (@cells[row, i].solved?)
236       solved.push(@cells[i, col][0]) if (@cells[i, col].solved?)
237     end
238     mini = mini_matrix_for_row(row, col)
239     for i in 0 ... mini.dims
240       for j in 0 ... mini.dims
241         solved.push(mini.cells[i, j][0]) if (mini.cells[i, j].solved?)
242       end
243     end
244     solved
245   end
246 
247   #
248   ### settor array operator
249   #
250   def []=(i, j, value)
251     @cells[i, j] = value
252   end
253 
254   #
255   ### return sorted array of cells by reducing possibilities
256   #
257   def as_sorted_array
258     arr = []
259     for i in 0 ... dims
260       for j in 0 ... dims
261         arr.push(@cells[i, j])
262       end
263     end
264     arr.sort
265   end
266 
267   #
268   ### return all cells in a given row
269   #
270   def get_solved_cells_for_row(row)
271     arr = []
272     for i in 0 ... dims
273       arr.push(@cells[row, i]) if (@cells[row, i].solved?)
274     end
275     arr.sort
276   end
277 
278   #
279   ### return all cells in a given row
280   #
281   def get_solved_cells_for_column(col)
282     arr = []
283     for i in 0 ... dims
284       arr.push(@cells[i, col]) if (@cells[i, col].solved?)
285     end
286     arr.sort
287   end
288 
289   #
290   ### This method checks whether the matrix follows Sudoku's rules
291   #
292   def valid?()
293     for i in 0 ... dims
294       arr = get_solved_cells_for_row(i)
295       return false if (duplicates_cells?(arr))
296       arr = get_solved_cells_for_column(i)
297       return false if (duplicates_cells?(arr))
298       arr = get_solved_mini_matrix(i)
299       return false if (duplicates_cells?(arr))
300     end
301     true
302   end
303 
304   #
305   ### This method normalizes the matrix by checking value in each cell that is
306   ### not yet solved and comparing it against all possible values for its
307   ### row and column. Basically, it means that if any of possible numbers
308   ### for that cell exist in its row, column or minimatrix, then that number
309   ### will be removed from possible values.
310   #
311   def normalize()
312     is_solved = true
313     for i in 0 ... @dims
314       for j in 0 ... @dims
315         if (!@cells[i, j].solved?)
316           already_solved = get_solved_numbers(i, j)
317           @cells[i, j].remove(already_solved)
318           is_solved = false
319         end
320       end
321     end
322     is_solved
323   end
324 
325   #
326   ### returns mini matrix
327   #
328   #     [0,0][0,1][0,2]         [0,3][0,4][0,5]         [0,6][0,7][0,8]
329   #     [1,0][1,1][1,2]         [1,3][1,4][1,5]         [1,6][1,7][1,8]
330   #     [2,0][2,1][2,2]         [2,3][2,4][2,5]         [2,6][2,7][2,8]
331   #
332   #     [3,0][3,1][3,2]         [3,3][3,4][3,5]         [3,6][3,7][3,8]
333   #     [4,0][4,1][4,2]         [4,3][4,4][4,5]         [4,6][4,7][4,8]
334   #     [5,0][5,1][5,2]         [5,3][5,4][5,5]         [5,6][5,7][5,8]
335   #
336   #     [6,0][6,1][6,2]         [6,3][6,4][6,5]         [6,6][6,7][6,8]
337   #     [7,0][7,1][7,2]         [7,3][7,4][7,5]         [7,6][7,7][7,8]
338   #     [8,0][8,1][8,2]         [8,3][8,4][8,5]         [8,6][8,7][8,8]
339   #
340   # matrixs are number left to right and top to bottom
341   #
342   def mini_matrix_for_row(row, col)
343     row = Integer(row / @mini_dims)
344     col = Integer(col / @mini_dims)
345     mini_matrix(Integer(row*@mini_dims+col))
346   end
347   #
348   ### returns mini matrix by number
349   #
350   def mini_matrix(num)
351     start_row = Integer(num/@mini_dims) * @mini_dims
352     start_col = Integer(num % @mini_dims * @mini_dims)
353     mini_cells = Matrix.new(@mini_dims)
354     for i in 0 ... @mini_dims
355       for j in 0 ... @mini_dims
356         row = Integer(start_row+i)
357         col = Integer(start_col+j)
358         mini_cells[i, j] =  @cells[row, col]
359       end
360     end
361     mini_cells
362   end
363 
364   #
365   ### returns solved cell values for given mini matrix
366   #
367   def get_solved_mini_matrix(num)
368     arr = []
369     mini = mini_matrix(num)
370     for i in 0 ... mini.dims
371       for j in 0 ... mini.dims
372         arr.push(mini.cells[i, j]) if (@cells[i, j].solved?)
373       end
374     end
375     arr.sort
376   end
377 
378   #
379   ### stringified object
380   #
381   def to_s
382     buffer = ""
383     for i in 0 ... @dims
384       for j in 0 ... @dims
385         buffer += @cells[i, j].to_s + " "
386       end
387       buffer += "rn"
388     end
389     buffer
390   end
391 
392   private
393   def duplicates_cells?(arr)
394     count = Hash.new(0)
395     arr.each { |box|
396       count[box[0]] += 1        # this is only possible with Fixnum
397     }
398     duplicates = false
399     count.each { |key, value|
400       duplicates = true if (value > 1)
401     }
402     duplicates
403   end
404 end
405 
406 #
407 ### This is the real workhorse class that solves Sudoku puzzle.
408 #
409 class Solver
410   attr_reader :matrix
411   attr_reader :data_file
412   attr_reader :verbose
413 
414   public
415   #
416   ### default constructor
417   #
418   def initialize
419     @verbose = false
420     @opts = OptionParser.new
421     @opts.on("-h", "--help") { RDoc::usage }
422     @opts.on("-v", "--verbose") { @verbose = true}
423     @opts.on("-f", "--file FILENAME") {|arg| @data_file = arg}
424     @opts.parse(ARGV) rescue RDoc::usage('usage')
425     die("!!!!!!!!!!! No file specified !!!!!!!!") if @data_file == nil
426     die("!!!!!!!!!!! No such file #{@data_file} !!!!!!!!") if !File.exist?(@data_file)
427     load
428   end
429 
430   #
431   ### Loads partial solution from the file specified by the user.
432   #
433   def load
434     row = 0
435     @matrix = Matrix.new
436     File.open(@data_file, "r") do |file|
437       while line = file.gets
438         next if line =~ /^s*#/
439         nums = line.chomp.split(/[ trn,;:]/)
440         for col in 0 ... nums.length
441           @matrix[row, col].set([Integer(nums[col])])
442         end
443         row = row+1
444       end
445     end
446   end
447 
448   #
449   ### This is the main method for solving Sudoku puzzle. Here is the algorithm:
450   ### - initialize matrix where each cell has 1..9 possible values
451   ### - load partial solution from user's file
452   ### - after loading some of cells will be initialized with user's
453   ###           specified solution value and other will be remain untouched.
454   ### - while not solved
455   ###   - normalize matrix by comparing set of possible values for each
456   ###           unsolved cell against values in its row, column and minimatrix
457   ###           and remove those values from the set of possible values.
458   ###   - if there are no remaining unsolved cells remaining then quit.
459   ###   - sort matrix by least number of possible values. This means that solved
460   ###           cells will come up first.
461   ###   - pick any cell that is not yet solved and select a number from its
462   ###           set of possible values.
463   ###   - go back to loop
464   ###
465   #
466   def solve
467     moves = 0
468     started = Time.now
469     bm(1) do |x|
470       x.report("BM:") {
471         while (!@matrix.normalize())
472           moves += try_solve
473           puts "After try #{moves} moves:n#{@matrix}" if (@verbose)
474         end
475       }
476     end
477     elapsed = (Time.now - started).to_f
478     puts "Solution: after #{moves} moves in #{elapsed}:n#{@matrix}"
479   end
480 
481   private
482   #
483   ### Tries to solve puzzle by first sorting the matrix by least number of
484   ### possible values and then picking any number randomly from the cell
485   ### that is not yet solved.
486   #
487   def try_solve
488     moves = 0
489     sorted = @matrix.as_sorted_array
490     sorted.each do |cell|
491       next if cell.solved?
492       puts "before picking cell #{cell.id} with possible values #{cell}" if (@verbose)
493       prev = cell.get
494       cell.pick_any
495       if (@matrix.valid?)
496         puts "after picking random cell #{cell.id}: with value #{cell}" if (@verbose)
497         return moves
498       end
499 
500       #
501       prev.each do |num|
502         cell.set([num])
503         moves += 1
504         if (@matrix.valid?)
505           puts "after (#{moves}) picking cell #{cell.id}: with value #{cell}" if (@verbose)
506           return moves
507         end
508       end
509       puts "failed to validate after (#{moves}) picking cell #{cell.id}: with value #{cell}" if (@verbose)
510       cell.set(prev)
511     end
512     moves
513   end
514   #
515   ### class method to exit if input arguments are incorrect.
516   #
517   def die(msg = "")
518     puts msg
519     RDoc::usage
520     exit
521   end
522 end
523 
524 Solver.new.solve

Usage:

ruby -w sudoku_solver.rb -v –file your-file

Benchmark: Here is benchmark results for above puzzle

        user     system      total        real
 BM:  8.762000   0.000000   8.762000 (  8.903000)
 Solution: after 771 moves in 8.903:
 9 6 3 1 2 4 7 5 8
 1 7 8 3 7 5 6 2 9
 2 5 5 6 8 9 4 3 1
 8 2 1 4 3 7 5 9 6
 4 9 6 8 5 2 3 1 7
 7 3 5 9 6 1 2 8 4
 5 1 9 7 4 3 8 6 2
 3 8 7 2 1 6 9 4 5
 6 4 2 5 9 8 1 7 3

Future: Note this solution provides one solution, however it can be
easily extended using some backtracking techniques (similar to
some Chess solvers) to provide multiple solutions. By the way, if you
rerun the program with same data, you will see different solutions to
the same problem.

No Comments

No comments yet.

RSS feed for comments on this post. TrackBack URL

Sorry, the comment form is closed at this time.

Powered by WordPress