class Sudoku
Sudoku.rb
Created on September 23, 2013
Public Class Methods
new(*args)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 20 def initialize (*args) @total_iterations = 0 @max_iterations = 100000 @debug = false @cells = Array.new(9) { Array.new(9) } if args.size==1 (0..8).each { |row| if args[0][row].is_a?(String) (0..8).each { |col| val = args[0][row][col] if /[0-9]/.match(val) @cells[row][col] = Cell.new(val.to_i) else @cells[row][col] = Cell.new() end } end } elsif args.size==0 (0..8).each { |row| (0..8).each { |col| @cells[row][col] = Cell.new() } } end unless self.validate_sudoku raise Exception.new('Sudoku entered appears to be invalid.') end end
Public Instance Methods
add_possible_value(row, col, val)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 71 def add_possible_value(row, col, val) @cells[row][col].add_possible_value(val) end
check_col_value(row, col, val)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 286 def check_col_value(row, col, val) result = true (0..8).each { |r| if r!=row if @cells[r][col].get_fixed_value()==val result = false end end } result end
check_matrix_value(row, col, val)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 298 def check_matrix_value(row, col, val) result = true row_start = (row/3).floor * 3 col_start = (col/3).floor * 3 (row_start..row_start+2).each { |y| (col_start..col_start+2).each { |x| unless row==y and col==x if @cells[y][x].get_fixed_value()==val result = false end end } } result end
check_row_value(row, col, val)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 274 def check_row_value(row, col, val) result = true (0..8).each { |current_column| if current_column!=col if @cells[row][current_column].get_fixed_value()==val result = false end end } result end
compute_possible_values()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 248 def compute_possible_values (0..8).each { |r| (0..8).each { |c| if @cells[r][c].get_fixed_value()<=0 @cells[r][c].reset_possible_values() (1..9).each { |possible_value| if check_row_value(r, c, possible_value) and check_col_value(r, c, possible_value) and check_matrix_value(r, c, possible_value) add_possible_value(r, c, possible_value) end } if @cells[r][c].get_possible_values().count==1 fixed_val = @cells[r][c].get_possible_values()[0] @cells[r][c].set_fixed_value(fixed_val) print_debug 'Resetting possible values...' @cells[r][c].reset_possible_values() elsif @cells[r][c].get_possible_values().count>1 @cells[r][c].set_fixed_value(-1) end end } } end
copy()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 342 def copy s = Sudoku.new() (0..8).each { |r| (0..8).each { |c| copied_cell = @cells[r][c].copy s.set_cells(r, c, copied_cell) } } s.set_max_iterations(@max_iterations) s.set_total_iterations(@total_iterations) s.set_debug(@debug) s end
count_fixed_cells()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 130 def count_fixed_cells fixed_cell_count=0 @cells.each() do |row| row.each() do |cell| fixed_cell_count = fixed_cell_count + 1 if cell.get_fixed_value != -1 end end fixed_cell_count end
dump_known_cells_str()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 464 def dump_known_cells_str result = '\n' for row in (0..8) (0..8).each do |col| if @cells[row][col].get_fixed_value() > 0 val = @cells[row][col].get_fixed_value() else val = ' ' end result+='%3s ' % val if col == 2 or col == 5 result+= '| ' end end if row==2 or row==5 result+= '\n----------------------------------------\n' else result+= '\n' end end result end
dump_to_str()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 437 def dump_to_str if @debug print '\n' (0..8).each { |row| (0..8).each { |col| printf(' %3s | ' % @cells[row][col].get_fixed_value()) if col == 2 or col == 5 print '| ' end } print '\n' (0..8).each { |col| array = @cells[row][col].get_possible_values() if array==[] array = '--' end printf(' %10s ' % array) if col == 2 or col == 5 print '| ' end } print '\n\n' } end end
find_col_implied_values()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 177 def find_col_implied_values (1..9).each { |i| (0..8).each { |c| fixed_count = 0 variable_count = 0 temp_row = -1 temp_col = -1 (0..8).each { |r| if @cells[r][c].get_fixed_value()==i fixed_count+=1 end (0..@cells[r][c].get_possible_values().count).each { |j| if @cells[r][c].get_possible_values()[j]==i variable_count+=1 temp_row = r temp_col = c end } } if (fixed_count==0) and (variable_count==1) @cells[temp_row][temp_col].set_fixed_value(i) end if fixed_count>1 raise('Duplicate fixed value in column check. Make sure you entered correct values.') end } } end
find_matrix_implied_values()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 209 def find_matrix_implied_values # In each sub-matrix we check for implied values (i) one at a time... [0, 3, 6].each { |row_start| [0, 3, 6].each { |col_start| (1..9).each { |i| temp_row = 0 temp_col = 0 fixed_count = 0 variable_count = 0 (row_start..row_start+2).each { |r| (col_start..col_start+2).each { |c| if @cells[r][c].get_fixed_value()==i fixed_count+=1 end (0..@cells[r][c].get_possible_values().count).each { |j| if @cells[r][c].get_possible_values()[j]==i variable_count+=1 temp_row = r temp_col = c end } } } if (fixed_count==0) and (variable_count==1) @cells[temp_row][temp_col].set_fixed_value(i) end if fixed_count>1 raise('Duplicate fixed value in matrix check. Make sure you entered correct values.') end } } } end
find_row_implied_values()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 141 def find_row_implied_values (1..9).each { |i| (0..8).each { |r| fixed_count = 0 variable_count = 0 temp_row = -1 temp_col = -1 (0..8).each { |c| # Start by counting up fixed values for the given number i. (e.g. How many of i do we have?) if @cells[r][c].get_fixed_value()==i fixed_count+=1 end # We are checking to see if there is only one i in the possible values for this row. # If so, then we will set the fixed value in the cell contains it. (0..@cells[r][c].get_possible_values().count).each { |j| if @cells[r][c].get_possible_values()[j]==i variable_count+=1 temp_row = r temp_col = c end } } if (fixed_count==0) and (variable_count==1) @cells[temp_row][temp_col].set_fixed_value(i) end if fixed_count>1 raise('Duplicate fixed values in row check. Make sure you entered correct values.') end } } end
get_cells()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 51 def get_cells @cells end
get_fixed_value(row, col)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 59 def get_fixed_value(row, col) @cells[row][col].get_fixed_value() end
get_possible_values(row, col)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 75 def get_possible_values(row, col) @cells[row][col].get_possible_values end
get_total_iterations()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 79 def get_total_iterations @total_iterations end
print_debug(message)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 488 def print_debug(message) if @debug puts message + '\n' end end
recurse()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 314 def recurse recurse = copy() (2..9).each { |guesses| (0..8).each { |r| (0..8).each { |c| if (recurse.get_possible_values(r, c).count==guesses) #Staring with cells that have the fewest to solve. (0..recurse.get_possible_values(r, c).count).each { |j| unless recurse.get_possible_values(r, c)[j].nil? print_debug '\nStarting recursion with (%s,%s) set to %s\n' % [r, c, recurse.get_possible_values(r, c)[j]] recurse.set_fixed_value(r, c, recurse.get_possible_values(r, c)[j]) print_debug('Recursion starting...') recurse, iterations = recurse.solve @total_iterations = @total_iterations + iterations if recurse!=nil return recurse else recurse = copy() end end } end } } } print_debug('Dead end found.\n') nil end
set_cells(row, col, cell)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 55 def set_cells(row, col, cell) @cells[row][col]=cell end
set_debug(b)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 433 def set_debug(b) @debug = b end
set_fixed_value(row, col, val)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 63 def set_fixed_value(row, col, val) @cells[row][col].set_fixed_value(val) end
set_max_iterations(iterations)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 12 def set_max_iterations(iterations) @max_iterations=iterations end
set_possible_values(row, col, vals)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 67 def set_possible_values(row, col, vals) @cells[row][col].set_possible_values(vals) end
set_total_iterations(iterations)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 16 def set_total_iterations(iterations) @total_iterations = iterations end
solve()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 83 def solve iteration=0 no_progress_count = 0 print_debug 'Max Iterations = %s' % @max_iterations while @solved_cell_count!=81 iteration+=1 @total_iterations+=1 print_debug 'Iteration: %s SolvedCells: %s\n' % [iteration, @solved_cell_count] print_debug dump_known_cells_str compute_possible_values() begin if validate_sudoku() find_row_implied_values() find_col_implied_values() find_matrix_implied_values() else return nil, @total_iterations end rescue Exception => error print_debug '\nValidation Error: %s\n' % error @solved_cell_count=count_fixed_cells() return nil, @total_iterations end if @max_iterations > 0 and @total_iterations > @max_iterations print_debug 'Total Iterations... %s\n' % @total_iterations print_debug 'This is just taking too long\n' raise Exception.new('Solution taking too long!\n\n') end if @solved_cell_count==count_fixed_cells() no_progress_count+=1 if no_progress_count>9 print_debug ('We''re not making progress here!') solution = recurse() return solution, @total_iterations end else no_progress_count=0 @solved_cell_count=count_fixed_cells() end end return self, @total_iterations end
validate_column(c)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 395 def validate_column(c) (1..9).each { |i| found_count = 0 (0..8).each { |r| if @cells[r][c].get_fixed_value()==i found_count+=1 end } if found_count>1 raise Exception.new('Row invalid. Canceling') end } true end
validate_matrix(r, c)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 412 def validate_matrix(r, c) (1..9).each { |i| found_count=0 row_start = (r/3).floor * 3 col_start = (c/3).floor * 3 (row_start..row_start+2).each { |y| (col_start..col_start+2).each { |x| if @cells[y][x].get_fixed_value()==i found_count+=1 end } } if found_count>1 raise Exception.new('Matrix invalid! Canceling.') end } true end
validate_row(r)
click to toggle source
# File lib/phg_sudoku_solver.rb, line 378 def validate_row(r) (1..9).each { |i| found_count=0 (0..8).each { |c| if @cells[r][c].get_fixed_value()==i found_count+=1 end } if found_count>1 raise Exception.new('Row invalid %s. Canceling' % r) end } true end
validate_sudoku()
click to toggle source
# File lib/phg_sudoku_solver.rb, line 356 def validate_sudoku results = true begin (0..8).each { |r| validate_row(r) } (0..8).each { |c| validate_column(c) } [0, 3, 6].each { |r| [0, 3, 6].each { |c| validate_matrix(r, c) } } rescue Exception => error results = false end results end