Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
share|improve this question
    
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. –  Skydreamer 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. –  Skydreamer May 7 '12 at 16:02
add comment

3 Answers

up vote 3 down vote accepted

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
share|improve this answer
    
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. –  Skydreamer 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. –  Skydreamer 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 ! –  Skydreamer May 10 '12 at 10:52
add comment

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
share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.