I'm developing a Killer Sudoku solver for a school project. I've programmed 10 human strategies showing what they are doing in order to be the most educational possible.
It can solve hard Killer Sudokus right now but my teacher proposed that I use backtracking to solve every possible grid.
I've been trying for one week searching for general resources on backtracking or resources based on Sudoku... The fact is that with Killer Sudoku, you can't just say a cell has a solution without relying on zones and on what the previously written cells imply on zones and possibilities everywhere.
What I'd like to do is something which applies all my strategies everytime it suggests a number to be more efficient and return the only solution.
But to apply strategies, we need a copy of the grid right ? So I can clone my objects totally using some methods and I can apply my strategies using another method.
What would be the structure for this function ?
PS: I've tried several times to write some code and everytime the solution returned was incorrect. (The grid can easily be checked for validity)
It was something like this :
def bt(sudoku) if sudoku.valid? then true else sudoku2 = sudoku.clone sudoku2.first_cell_not_solved.possibilities.each do |p| sudoku2.first_cell_not_solved.solution = p end sudoku2.apply_all_strategies if sudoku.completed? return sudoku.valid? else bt(sudoku2) end end end