Actually it uses the brutal backtrack method. Try fill a number in one cell, then recursively call itself, if it works, continue, then return, try another, until it fills all the 81 cells. I made some changes based on the original code, the major changes once the solver find the solution then exit the loop, while in the original code the program will continue loop until the end, I compare my changes with the original code, the total times executed and execution time both drops about 50%.
Here is my modified code:
class SudokuSolverThe logic is really simple: first reads the puzzle, construct the one dimension array.
def initialize(puzzle)
@@p = puzzle.split(//)
end
#Algorithm to solve the sudoku puzzle
def solver
#81 times for each block in the puzzle
81.times do |j|
next if @@p[j].to_i!=0
candidatesArray = getCandidates(j)
candidatesArray.each do |v|
@@p[j]=v.to_s
foundAll = solver
if(foundAll == true)
return true
end
end
# finished trying all the candidates, backtrack
@@p[j]=0
return false
end
return true
end
def getCandidates(j)
Array array = [1,2,3,4,5,6,7,8,9]
row = j/9 *9
col = j%9
#find the cells with the same row
9.times do |k|
m = @@p[row+k].to_i
if(m)
array.delete(m)
end
end
#find the cells in the same column
9.times do |k|
m = @@p[k*9 + col].to_i
if(m)
array.delete(m)
end
end
#find the cells in the same sub cube
start_row = j/27 * 3
start_col = j%9/3 * 3
3.times do |t|
3.times do |l|
m = @@p[(start_row + t)*9 + start_col + l].to_i
if(m)
array.delete(m)
end
end
end
return array
end
def printResult
puts "\n\nThe Solution is:\n"
print "+-----------------------------+\n|"
1.upto(81) do |x|
print " #{@@p[x-1]} "
if x%3==0 and x%9 !=0
print "|"
end
if x%9==0 and x%81 !=0
print"|\n|-----------------------------|\n|"
end
if x%81==0
puts "|"
end
end
puts "+-----------------------------+"
end
end
question = "000700390090500000300240800700900200000000000003007008004026007000005060026001000"
answer = SudokuSolver.new(question)
puts "\n\n\nSolving puzzle, wait one moment..."
answer.solver
answer.printResult
The key is in Solver method:
From 81 cells, pick one empty cell, calculate the candidate numbers of this cell,
Pick one number, fill the cell,
Recusively call itself, continue try to fill another empty cell.
If the program could not find the candidate for the cell, or the program iterate all the cell’s candidate number, then erase the number, backtrack;
If the program fills all the 81 cells, return true
The algorithm of getCanidates(j) is easy:
Build an array of 1-9
Find each cell with the same row, erase the number in the cell from the array;
Find each cell with the same column, erase the number in the cell from the array;
Find each cell with the same sub block, erase the number in the cell from the array.
The left in the array are candidates
From this code, I understand more about the backtrack and recursive method. This code belongs to the depth-first backtrack search.
Donald Knuth’s Dancing Link algorithm is quite interesting, there are lots of articles and blog about using it solving the SuDoKu. But right now for me it is really hard to understand.
For SuDoKu, there are following thins to do in future:
1. Implement the SuDoKu solver using Dancing Link algorithm
2. Find out the algorithm of SuDoKu Generator, like how to generate a puzzle based on difficulty, and how to find out there is only one solution.
3. How to implement an algorithm that simulate human's solving logic?
Here are several link about dancing link and SoDuKu:
Dancing Link C implementation
Dancing link for Java
Donald Knuth Home page
Donald Knuth's Dancing links paper(pdf)
