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)

## No comments:

## Post a Comment