Python Forum
Sudoku Solver in Python - Can someone explain this code ?
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Sudoku Solver in Python - Can someone explain this code ?
#1
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.
Reply
#2
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?
Sig:
>>> import this

The UNIX philosophy: "Do one thing, and do it well."

"The danger of computers becoming like humans is not as great as the danger of humans becoming like computers." :~ Konrad Zuse

"Everything should be made as simple as possible, but not simpler." :~ Albert Einstein
Reply
#3
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.
Reply
#4
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.[Image: lzlLd4k]

Attached Files

Thumbnail(s)
   
Reply
#5
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.
Reply
#6
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
Reply
#7
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.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  [split] Explain the python code in this definition Led_Zeppelin 1 711 Jan-13-2023, 10:20 PM
Last Post: deanhystad
  I am new to python and Could someone please explain how this below code is working? kartheekdas 2 971 Dec-19-2022, 05:24 PM
Last Post: kartheekdas
  Explain the python code in this definition Led_Zeppelin 1 1,059 Oct-27-2022, 04:04 AM
Last Post: deanhystad
  Can someone explain this small snippet of code like I am a 5 year old? PythonNPC 3 1,201 Apr-08-2022, 05:54 PM
Last Post: deanhystad
  Could you explain each part of the code? Tsushida 2 1,466 Mar-20-2022, 08:19 AM
Last Post: Larz60+
  Sudoku Solver, please help to solve a problem. AdithyaR 5 2,043 Oct-28-2021, 03:15 PM
Last Post: deanhystad
  building a sudoku solver usercat123 7 2,693 Oct-01-2021, 08:57 PM
Last Post: deanhystad
  What is the run time complexity of this code and please explain? samlee916 2 2,257 Nov-06-2020, 02:37 PM
Last Post: deanhystad
  poplib - parsing message body, could somebody please help explain this code t4keheart 2 2,248 Oct-12-2020, 01:59 PM
Last Post: t4keheart
  unable to use result of solver in another function ross1993hall 0 1,379 Aug-10-2020, 10:29 AM
Last Post: ross1993hall

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020