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
- Normalize grid by comparing the set of possible values for each
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.