Code Kata: SuDoKu Solver

This week I am interested in the Sudoku puzzle, I am thinking how to use program to solve the SuDoKu. I almost spent a week for it. At first I was inspired the a book called “Wicked Cool Ruby Scripts”in chapter 5, it provides a ruby source code for the SuDoKu solver. I spent two days to understand the code. The problem is the book does not describe the algorithm in details, and I don’t know how to debug the ruby code in TextMate. So it took me a longer time to finally understand the whole logic.

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 SudokuSolver
  
  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 logic is really simple: first reads the puzzle, construct the one dimension array.
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)