Backtracking with Killer Sudoku

Question

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 07 '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 07 '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 07 '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 07 '12 at 16:02
Did I give you the right answer on that Visitor question? :) — Robert Harvey, Jul 29 '16 at 15:37
Actually yes, thank you about that. I deleted my post because I felt like the question was too dumb. I thought of the answer myself before and imagined it would not work for some reason :) — Cydonia7, Jul 30 '16 at 17:29

Karl Bielefeldt · Accepted Answer · 2012-05-07T20:19:55.383

3

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

edited May 07 '12 at 20:19

answered May 07 '12 at 18:20

Karl Bielefeldt

146,727
38
279
479

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 07 '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 07 '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 09 '12 at 15:56
Are you looping through all the unsolved cells, not just the first one? – Karl Bielefeldt May 09 '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

score 1 · Answer 2 · answered May 08 '12 at 02:30

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.

score 0 · Answer 3 · answered May 08 '12 at 09:36

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

Backtracking with Killer Sudoku

3 Answers3