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.