0
votes

I'm trying to use backtracking to make a Sudoku solver. When I work through the code by hand it works perfectly but when I run it I get empty cells in my return solution. I've spent such a ridiculous amount of time trying to fix it but I can't even figure out where exactly its going wrong. I'm fairly certain my function for checking cell solutions is correct. Here's the code:

import numpy as np

board = np.array([[0, 0, 0, 8, 4, 0, 0, 0, 3],
                  [0, 7, 5, 0, 0, 0, 0, 0, 0],
                  [0, 4, 3, 0, 0, 6, 0, 0, 0],
                  [0, 0, 7, 0, 0, 8, 4, 9, 0],
                  [0, 0, 0, 9, 3, 1, 0, 0, 0],
                  [0, 5, 2, 7, 0, 0, 8, 0, 0],
                  [0, 0, 0, 2, 0, 0, 3, 4, 0],
                  [0, 0, 0, 0, 0, 0, 6, 2, 0],
                  [2, 0, 0, 0, 7, 3, 0, 0, 0]])

#check if input is viable solution for a cell
def isSolution(row, col, n):
    #return 0 for false (not a possible solution)
    #return 1 for true (possible solution)
    a = 0
    for i in range(0,9):
        if(board[row,i] == n):
            a += 1
        if(board[i,col] == n):
            a += 1
    h = (1 - (2 * ((row % 3) != 0)))
    i = (1 - (2 * ((col % 3) != 0)))
    j = (2 - (row % 3)**2)
    k = (2 - (col % 3)**2)
    if(board[row + h, col + i] == n):
        a += 1
    elif(board[row + h, col + k] == n):
        a += 1
    elif(board[row + j, col + i] == n):
        a += 1
    elif(board[row + j, col + k] == n):
        a += 1
    if(a == 0):
        return 1
    else:
        return 0

def solve():
    for row in range(0, 9):
        for col in range(0,9):
            if(board[row,col] == 0):
                for n in range(1, 10):
                    if(isSolution(row, col, n) == 1):
                        board[row,col] = n
                        print(board)
                        solve()
                        board[row,col] = 0

                return


#main
solve()

Please help if you can I'm trying to get better at python and feel like I've hit a wall here

1
Note that you should return True or False rather than 0 or 1, and that you don't need to increment a when you find an incompatibility: just immediately return False, and return True at the end of your function if you managed to arrive to that point. - Thierry Lathuille
You never test that you have found the solution (when you reach the end of the innerest loop while col == row == 8), so you find it, and go on trying other solutions. - Thierry Lathuille
A nested list is likely to be as fast or faster than an array, since you are indexing individual elements. Also pay close attention to when the board is modified inplace versus copied. - hpaulj

1 Answers

0
votes

Expanding comment of Thierry Lathuille

def solve():
    for row in range(0, 9):
        for col in range(0,9):
            if(board[row,col] == 0):
                for n in range(1, 10):
                    if(isSolution(row, col, n) == 1):
                        board[row,col] = n
                        # print(board)
                        if (board != 0).all():
                            raise StopIteration
                        solve()
                        board[row,col] = 0

                return


#main
try:
    solve()
except StopIteration:
    print(board)