CODEWITHSUNDEEP
pythonalgorithmbacktrackingsudoku
KMG
KMG

Reputation: 1501

Why this sudoku solver return same board without solving anything?

I'm trying to write a simple python Sudoku solver that's implement backtracking which seems to not work at all and doesn't solve anything which I don't Know why. The Puzzle is supposed to have a solution I guess the problem is from the backtracking mechanism but I'm not sure at all Why such behavior could occur.

matric =[
    [7,8,0,4,0,0,1,2,0],
    [6,0,0,0,7,5,0,0,9],
    [0,0,0,6,0,1,0,7,8],
    [0,0,7,0,4,0,2,6,0],
    [0,0,1,0,5,0,9,3,0],
    [9,0,4,0,6,0,0,0,5],
    [0,7,0,3,0,0,0,1,2],
    [1,2,0,0,0,7,4,0,0],
    [0,4,9,2,0,6,0,0,7]
]

def is_possible(y: int, x: int, n: int) -> bool:

        # check row and column
    for i in range(9):
        if matric[y][i] == n:
            return False

    for i in range(9):
        if matric[i][x] == n:
            return False
    # check box
    new_x = x // 3 * 3
    new_y = y // 3 * 3
    for i in range(3):
        for j in range(3):
            if matric[new_y + i][new_x + j] == n:
                return False
    return True

def solve():
    global matric
    # Find a point
    for y in range(9):
        for x in range(9):
            if matric[y][x] == 0:   # found a point to solve
                for n in range(1, 10):   # Check numbers
                    if is_possible(y, x, n):
                        matric[y][x] = n
                        solve()         # Solve Next Point
                        matric[y][x] = 0    # Back track
                return
solve()
for x in matric:
    print(x)

Upvotes: 0

Views: 526

Answers (1)

trincot
trincot

Reputation: 350212

Your code always backtracks, even when it has found a solution. There is nothing in your code that says "hey, I found a solution, let's stop looking further". So after all possibilities have been scanned, you end up with a complete backtracked matrix. There is nothing else that this code can do: it will backtrack and set everything to zero. There is no if solved: announce the solution

What you can do

Let solve return a boolean: when it finds that the matrix is full, it should return True. If a recursive call returns True, then don't clear any cell! Instead, immediately return True. That way you will quickly backtrack out of the recursion tree, without changing anything in the matrix. The original caller will then find the matrix with the solution still in tact.

So:

def solve():
    global matric
    for y in range(9):
        for x in range(9):
            if matric[y][x] == 0:
                for n in range(1, 10):
                    if is_possible(y, x, n):
                        matric[y][x] = n
                        if solve():  # Did we find a solution?
                            return True  # Yes! Tell the caller!
                        matric[y][x] = 0  # Back track
                return False  # No way to fill this cell with a valid value
    return True  # Found no free cell, so this is a solved puzzle!

Be aware that although this algorithm may solve some puzzles, it will spend too much time on harder puzzles. To solve harder puzzles, you would need to add and maintain some more data structures to know which values can still be used in a cell, and which values still need to find a spot in a row, a column, or a block. This will give faster results than when you have to validate a placed value like you do now in is_possible.

Upvotes: 2

Related Questions