# Backtracking with Killer Sudoku

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
``````
• Not sure what you mean by strategies. Could you give us an example? – Neil May 7 '12 at 15:41
• It takes the grid and try to remove possibilities and find solutions using logic. For example, looking for uniq numbers in a row. – Cydonia7 May 7 '12 at 15:43
• I think I understand your question now. Unfortunately, I don't know Ruby, but it seems to me that you need to organize it (beyond 3x3 groups and 1x9 groups) by the sum groups and keep track of "guaranteed" numbers in that group. For each number in that group, you need to include the addition info that that number should really belong there or if it simply belongs inside that grouping (to make it sum properly). – Neil May 7 '12 at 15:53
• The whole "addition" info is available in the sudoku object so that is not really a problem I think. My strategies already remove many possibilities using the other cells including all this checking, that's why I wanted a way to use them without modifying the whole grid, but still getting the solution after. I don't expect an answer as ruby but even as pseudo-code would be nice, just to see the backbone of what I should do. – Cydonia7 May 7 '12 at 16:02
• Did I give you the right answer on that Visitor question? :) – Robert Harvey Jul 29 '16 at 15:37

Where you have `sudoku2.first_cell_not_solved.set_first_possibility_as_solution`, you actually need to be looping through all possibilities on the first cell not solved, then loop through all possibilities on the second cell not solved, etc. Each time you see if choosing that possibility produces a solution by applying your strategies. If it doesn't, you undo (i.e. backtrack) that possibility and choose the next one. By only ever choosing the first possibility, your example code doesn't actually do any backtracking.

This kind of brute force algorithm has the potential to take a very, very long time. The trick is choosing the right cell to go first. For example, choosing a cell with only two possibilities will likely produce a result faster than choosing a cell that's wide open. Also, you're likely to solve the same sub-puzzles many times, so some sort of memoization is usually very helpful.

Edit: something like this (forgive any ruby mistakes, I don't know the language):

``````def bt(sudoku)
if sudoku.completed? then
return sudoku.valid?
else
sudoku.first_cell_not_solved.possibilities.each do |p|
sudoku2 = sudoku.clone
sudoku2.first_cell_not_solved.solution = p
sudoku2.apply_all_strategies
if bt(sudoku2)
sudoku = sudoku2
true
end
end
end
false
end
``````
• I did the loop in the true code I tried in fact... Forgot it in the main post. The problem here is to undo all the changes, I think I must clone sudoku2 and copy it to sudoku only if a solution is found and then it should be good. I'll try to code it again hoping it won't do anything wrong... But I don't think my mistake's here because I tried various ways to backtrack. – Cydonia7 May 7 '12 at 19:32
• You need to do the `clone` inside the loop. That way each time through the loop, doing the new clone undoes all the changes from the loop. You also need to return false if you make it through the loop without finding anything. See my edit. – Karl Bielefeldt May 7 '12 at 20:19
• It works but for a very hard grid, the solution found was incorrect (10 in a cell) so I added this constraint to the valid? method and now it says that the grid has no solution while there's one. – Cydonia7 May 9 '12 at 15:56
• Are you looping through all the unsolved cells, not just the first one? – Karl Bielefeldt May 9 '12 at 17:23
• It was a small error in the grid... My mistake. Thank you for all your help ! – Cydonia7 May 10 '12 at 10:52

It's actually easier to write an exhaustive backtracking program than it is to solve a specific Sudoku puzzle. The algorithm is pretty simple. You don't need to clone the grid.

``````value[i] = 0 for i in 0..totalCells-1;
int currentCell = 0;

while (currentCell != totalCells) {
++value[currentCell];
if (value[currentCell] > 9) {
value[currentCell] = 0; // erase
--currentCell; // backtrack
if (currentCell < 0) throw new UnsolvableSudokuException();
} else if (!anyConstraintViolated) {
++currentCell; // advance to next cell
}
}
``````

You might think this would run for a long time but even with a slower language like Perl this algorithm solves regular Sudoku in a couple of seconds.

An alternative to cloning would be to use the memento pattern.

``````def bt(sudoku)
if !sudoku.valid?
throw Exception()
if sudoku.completed? then
true
else
memento = sudoku.dump
sudoku.first_cell_not_solved.possibilities.each do |p|
sudoku.first_cell_not_solved.solution = p
sudoku.apply_all_strategies
if sudoku.valid? and bt(sudoku)
return true
sudoku.restore(memento)
end
false
end
end
``````