Python recursive backtracking suduko solver

Question

I am writing a recursive backtracking algorithm for a suduko solver. It seems it is terrible at suduko.

Code:

def recursiveBacktrack(board):
  if(checkEntireBoard(board)):
    return board
  else:
    for node in board:
      if(node.val == "."):
        for val in (1,2,3,4,5,6,7,8,9):
           if(checkNodeConstraintsOk(board, node, val)):
             node.val = val
             posNewBoard = recursiveBacktrack(board)
             if(posNewBoard != None):
               return posNewBoard
             else:
              node.val = "."
         return None

boards are made up of node objects. Each node object has a (x,y) for the board, a value that is either a number or a period for no assignment, and a square value (what suduko square it is in).

I know for a fact that both my methods checkEntireBoard and checkNodeConstraintsOk work. checkEntireBoard checks to see if the board is solved properly and checkNodeConstraintsOk checks to see if I were to set the given node to the given value on the given board if the constraints of the suduko game hold true.

For some reason I think my algorithm above is not working properly (see output below), I have followed the pseudocode for recursive backtracking exactly and can find no error. So I would have to figure the error lies with my low knowledge of python.

------------------------------
7  5  9  | .  4  .  | .  .  .  
6  8  .  | 5  .  .  | .  4  .  
.  3  .  | 2  .  9  | 5  .  .  
------------------------------
5  6  .  | 1  .  .  | 9  .  .  
.  .  3  | .  .  .  | 1  .  .  
.  .  1  | .  .  6  | .  3  7  
------------------------------
.  .  5  | 3  .  7  | .  9  .  
.  7  .  | .  .  8  | .  5  3  
.  .  .  | .  6  .  | 7  2  1  
------------------------------

Found Solution 
------------------------------
7  5  9  | 1  4  2  | 3  4  5  
6  8  1  | 5  3  4  | 2  4  6  
2  3  3  | 2  5  9  | 5  1  7  
------------------------------
5  6  2  | 1  1  3  | 9  5  4  
1  3  3  | 2  4  5  | 1  6  8  
4  5  1  | 6  7  6  | 1  3  7  
------------------------------
3  1  5  | 3  2  7  | 4  9  9  
5  7  4  | 3  6  8  | 7  5  3  
6  2  7  | 4  6  1  | 7  2  1  
------------------------------

If the error does not show up in my backtracking algorithm I will end up opening a code review on codereview.stack. But from what I have seen the problem lies above.

EDIT

def checkEntireBoard(board):
  for node in board:
    if(node.val == "."):
      return False
    if(not checkNodeConstraintsOk(board, node, node.val)):
      return False
  return True

def checkNodeConstraintsOk(board, inNode, posVal):
  val = posVal
  for node in board:
    if(node != inNode and node.val == val):
      if(node.x == inNode.x or node.y == inNode.y or node.sqr == inNode.sqr):
        return False
  return True

EDIT2

Solved thanks Peter

Found Solution 
------------------------------
7  5  9  | 6  4  3  | 8  1  2  
6  8  2  | 5  7  1  | 3  4  9  
1  3  4  | 2  8  9  | 5  7  6  
------------------------------
5  6  7  | 1  3  2  | 9  8  4  
8  2  3  | 7  9  4  | 1  6  5  
9  4  1  | 8  5  6  | 2  3  7  
------------------------------
4  1  5  | 3  2  7  | 6  9  8  
2  7  6  | 9  1  8  | 4  5  3  
3  9  8  | 4  6  5  | 7  2  1  
------------------------------

Can you give us your checkEntireBoard and checkNodeConstraintsOk functions so people can debug your code? Because it sure looks like checkNodeConstraintsOk is returning True in cases where it shouldn;t. — abarnert
For checking the node constraints I went like this. We only care about nodes with the same value as us, and we don't care about ourselves because it will obviously have the same value. So if we find a node that has the same value, and shares a x, y, or square value with us then we cannot make the assignment of posVal to inNode — user1311286
By the way, "terrible at Sudoku" is an ambiguous term. Sure, it gets the wrong answers, but it probably gets them a lot faster than a correct algorithm, and it doesn't know it's gotten them wrong, and most humans in that situation would be happy. :) — abarnert
Anyway, this still isn't enough to run and debug your code, and it still seems quite possible that the error is in the code you haven't shown us. We really need an SSCCE to help. — abarnert
If my theory isn't the problem, it would still be a good idea to show how board and its known nodes get created. — Peter DeGlopper

Peter DeGlopper Peter DeGlopper · Accepted Answer · 2013-10-23T22:46:52

Check the type of your initial node values. If they're getting initialized with, say, val = "1" instead of val = 1 then your checkNodeConstraintsOk function won't spot the conflict because the values won't be equal. I see that none of the incorrect values in your example conflict with one added by your recursive backtracker, just the starting values, so I suspect this is the problem.

Python recursive backtracking suduko solver

1 Answers