Writing Sudoku Solver wih Python

Question

Here is my Sudoku Solver written in python language, When I run this program there seems to be a problem with in Update function and Solve function.

No matter how much time I look over and move the codes around, I seem to have no luck

Can anyone Help me?

---

import copy


def display (A):

    if A:
        for i in range (9):
            for j in range (9):
                if type (A[i][j]) == type ([]): print A[i][j][0],
                else: print A[i][j]
            print
        print
    else: print A

def has_conflict(A):

    for i in range(9):
        for j in range(9):
            for (x,y) in get_neighbors(i,j):
                if len(A[i][j])==1 and A[i][j]==A[x][y]: return True
    return False


def get_neighbors(x,y):

    neighbors = []
    for i in range(3):
        for j in range(3):
            a = 3*(x / 3)+i
            b = 3*(y / 3)+j
            if (x,y) != (a,b):
                neighbors += [(a,b)]

    for i in range(9):
        if (x,y) != (x,i) and (x,i) not in neighbors:
            neighbors += [(x,i)]
        if (x,y) != (i,y) and (i,y) not in neighbors:
            neighbors += [(i,y)]

    return neighbors



def update(A,x,y,value):

    B = copy.deepcopy(A)
    B[x][y] = [value]
    for (i,j) in get_neighbors(x,y):
        if B[i][j] == B[x][y]:
            if len(B[i][j]) > 1: B[i][j].remove(value)
            else: return [] 
    if has_conflict(B) == True: return []
    else: return B


def solve(A):

    for x in range (9):
        for y in range(9):
            if len(A[x][y]) == 1: return A[x][y]
            if len(A[x][y]) > 1:
                lst = update(A,x,y,A[x][y])
                if len(lst[x][y]) > 1: solve(lst)
                if lst == []: return []
                if len(lst[x][y]) == 1: return lst
            else: return A[x][y]    



A=[]

infile = open('puzzle1.txt','r')

for i in range(9):

        A += [[]]
        for j in range(9):
            num = int(infile.read(2))
            if num: A[i] += [[num]]
            else: A[i] += [[1,2,3,4,5,6,7,8,9]]

for i in range(9):

        for j in range(9):
            if len(A[i][j])==1: A = update(A, i, j, A[i][j][0])
            if A == []: break
        if A==[]: break

if A<>[]: A = solve(A)

display(A)

---

Here are some puzzles:

Puzzle 1

0 0 0 2 6 0 7 0 1
6 8 0 0 7 0 0 9 0
1 9 0 0 0 4 5 0 0
8 2 0 1 0 0 0 4 0
0 0 4 6 0 2 9 0 0
0 5 0 0 0 3 0 2 8
0 0 9 3 0 0 0 7 4
0 4 0 0 5 0 0 3 6
7 0 3 0 1 8 0 0 0

Puzzle 2

1 0 0 4 8 9 0 0 6
7 3 0 0 0 0 0 4 0
0 0 0 0 0 1 2 9 5
0 0 7 1 2 0 6 0 0
5 0 0 7 0 3 0 0 8
0 0 6 0 9 5 7 0 0
9 1 4 6 0 0 0 0 0
0 2 0 0 0 0 0 3 7
8 0 0 5 1 2 0 0 4

Puzzle 3

0 2 0 6 0 8 0 0 0
5 8 0 0 0 9 7 0 0
0 0 0 0 4 0 0 0 0
3 7 0 0 0 0 5 0 0
6 0 0 0 0 0 0 0 4
0 0 8 0 0 0 0 1 3
0 0 0 0 2 0 0 0 0
0 0 9 8 0 0 0 3 6
0 0 0 3 0 6 0 9 0

---

Answer 1

Solving sudoku need some bruteforcing method, I dont see those in your codes.

I also tried to do before, but finally I saw norvig's codes, its just working perfect.

and ended up with learning his codes finally.

Answer 2

If you want to stabilize your code, then write small test cases for each function which make sure that they work correctly.

In your case, run a puzzle, and determine which field is wrong. Then guess which function might produce the wrong output. Call it with the input to see what it really does. Repeat for every bug you find.

[EDIT] The module unittest is your friend.

Answer 3

I would avoid things like "move the codes around". This is called "Programming by Coincidence" (see The Pragmatic Programmer). Programming like this won't make you a better programmer.

Instead, you should take out a paper and pencil, and start thinking how things should work. Then, read the code and carefully write what it actually does. Only when you understand, go back to the computer terminal.

Answer 4

I'd like to help you in a way that you can write the actual code, so here is some explanation, and some pseudo-code.

Those sudoku solvers that don't mimic human deduction logic are bruteforce-based. Basically, you'll need a backtrack algorithm. You have your has_conflict method, which checks whether the candidate is ok at first look. Then you write the backtrack algorithm like this:

Solve(s):
    Pick a candidate.
    Does it have a conflict? If yes, go back, and pick another one.
    No more empty cells? Then cool, return True.
    Have you run out of candidates? Then it cant be solved, return False.

    At this point, it seems ok. So call Solve(s) again, lets see how it works 
    out with the new candidate.
    If Solve returned false, then after all it was a bad candidate. Go
    back to picking another one.
    If Solve returned True, then you solved the sudoku!

The main idea here is that if your guess was wrong, despite not having a conflict at first look, then a confliction will reveal itself somewhere deeper in the call tree.

The original sudokus have only one solution. You can extend this method to different solutions for sudokus that have them by trying any candidates despite the return value of Solve (but that will be very slow with this approach).

There's a nice trick to find out if a sudoku has more than one solutions. First try the candidates in natural order in every call of solve. Then try them backwards. Then do these two steps again, but this time run the algorithm from the last cell of the sudoku, stepping backwards. If these four solutions are identical, then it has only one solution. Unfortunately I don't have a formal proof, but it seemed to work all the time. I tried to prove it, but I'm not that great with graphs.