Sudoku Solver in Python - Can someone explain this code ?

[qwemx]

M = 9
def puzzle(a):
    for i in range(M):
        for j in range(M):
            print(a[i][j],end = " ")
        print()
def solve(grid, row, col, num):
    for x in range(9):
        if grid[row][x] == num:
            return False
             
    for x in range(9):
        if grid[x][col] == num:
            return False
 
 
    startRow = row - row % 3
    startCol = col - col % 3
    for i in range(3):
        for j in range(3):
            if grid[i + startRow][j + startCol] == num:
                return False
    return True
 
def Suduko(grid, row, col):
 
    if (row == M - 1 and col == M):
        return True
    if col == M:
        row += 1
        col = 0
    if grid[row][col] > 0:
        return Suduko(grid, row, col + 1)
    for num in range(1, M + 1, 1): 
     
        if solve(grid, row, col, num):
         
            grid[row][col] = num
            if Suduko(grid, row, col + 1):
                return True
        grid[row][col] = 0
    return False
 
'''0 means the cells where no value is assigned'''
grid = [[2, 5, 0, 0, 3, 0, 9, 0, 1],
        [0, 1, 0, 0, 0, 4, 0, 0, 0],
    [4, 0, 7, 0, 0, 0, 2, 0, 8],
    [0, 0, 5, 2, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 9, 8, 1, 0, 0],
    [0, 4, 0, 0, 0, 3, 0, 0, 0],
    [0, 0, 0, 3, 6, 0, 0, 7, 2],
    [0, 7, 0, 0, 0, 0, 0, 0, 3],
    [9, 0, 3, 0, 0, 0, 6, 0, 4]]
 
if (Suduko(grid, 0, 0)):
    puzzle(grid)
else:
    print("Solution does not exist:(")

Can someone help me how the code is working - this is from the below webpage - suduko solver.
There are no comments in the code - so can someone explain what each segment is doing

https://www.askpython.com/python/example...-in-python

Yoriz write Jun-23-2022, 11:51 AM:
Please post all code, output and errors (in their entirety) between their respective tags. Refer to BBCode help topic on how to post. Use the "Preview Post" button to make sure the code is presented as you expect before hitting the "Post Reply/Thread" button.

[rob101]

That's a very nice bit of coding.

There's a full explanation of what the script is doing on the page that you linked: "Steps to solve the sudoku puzzle in Python"

I've found that one of the best way to learn Python, is to study code such as this and work out what each line of code does.

What part of the code are you stuck on?

[deanhystad]

Nearly all sudoku solvers work the same way.

Try yo put a number in the first open box.
If successful move on to the next open box. If not, undo the last box and try a different number.

It annoys me that sudoku solvers arrange values in rows and columns. The puzzle is drawn that way, but storing values in a 2D array just makes the code more complicared. It is easier if the puzzle is flattened out into an 81 element 1D list.

[qwemx]

def Suduko(grid, row, col):
 
    if (row == M - 1 and col == M):
        return True
    if col == M:
        row += 1
        col = 0
    if grid[row][col] > 0:
        return Suduko(grid, row, col + 1)
    for num in range(1, M + 1, 1): 
     
        if solve(grid, row, col, num):
         
            grid[row][col] = num            
            if Suduko(grid, row, col + 1):
                return True
        grid[row][col] = 0
    return False

I am not sure if we are using row=0 and col=0 as starting or row=1,col=1 as starting
In this code the Row = 8 and Col=9 because M=9
so if we see the picture attached.

suduko rows and column

so we still have one more Row left at the bottom - how will that be processes?


so basically we have two functions suduko and solve
I am trying to study what exactly each doing.

[deanhystad]

The range for both rows and columns is 0 through 8. The if statement is testing if you finished twe last row. You could test "if row == M" and place it after the "if col == M" test.

[qwemx]

The last box to check will be row and column will be both ROW(M-1) &COL(M-1) which will be 8th Row and 8th Column if they start from 0,0 but in the code it is M-1 and M

[deanhystad]

The code does not check if you reached the last box, it checks if you passed the last box. The last box is [8][8]. The next box could be thought of as [8][9] or [9][8] or [9][0].

I like this better

    if col == M:
        row += 1
        col = 0
    if (row == M):
        return True

But I still don't like that very much. Keeping track of rows and columns just adds complication to the algorithm. Why not make the board a len 81 list instead of nine len 9 lists? I would write the solver like this:

def print_puzzle(puzzle):
    """Pretty print the puzzle"""
    for r in range(0, 81, 9):
        row = puzzle[r:r+9]
        print(" | ".join([" ".join(row[i:i+3]) for i in range(3)]))
        if r in (18, 45):
            print("------+-------+------")

def choices(puzzle, index):
    """Return list of values that can be placed in puzzle[index]"""
    # Get used row and column values
    r = index // 9
    c = index % 9
    used = puzzle[r*9:(r+1)*9] + [puzzle[i] for i in range(c, 81, 9)]

    # Get values in the same "square" as puzzle[index]
    upperleft = r // 3 * 27 + c // 3 * 3
    for i in range(upperleft, upperleft+27, 9):
        used += puzzle[i:i+3]

    # Return choices that are not in the row, column or square.
    used = set(used)
    return [n for n in "123456789" if not n in used]


def solve(puzzle, index=0):
    """Recursive sudoku solver"""
    if index >= len(puzzle):
        # All the boxes are filled in.  We won!
        return True

    if puzzle[index] != " ":
        # Box is filled in.  Move on to next box
        return solve(puzzle, index+1)

    for n in choices(puzzle, index):
        puzzle[index] = n
        if solve(puzzle, index+1):
            return True
        puzzle[index] = " "
    return False

puzzle = list("25  3 9 1 1   4   4 7   2 8  52         981   4   3      36  72 7      39 3   6 4")

if solve(puzzle):
    print_puzzle(puzzle)
else:
    print("Solution does not exist:(")

Using a 1D list makes it easier to identify when the puzzle is solved and what should be the next cell to solve. Making the choices characters instead of numbers makes it easier to do a pretty print because I don't have to convert to the cell values to strings. Finally, I think it makes more sense to loop through values that can be placed in the cell than it does to try every value and test if it is an invalid choice. It should eliminate millions of operations.