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 ?
#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


Messages In This Thread
RE: Sudoku Solver in Python - Can someone explain this code ? - by deanhystad - Jun-27-2022, 12:46 PM

Possibly Related Threads…
Thread Author Replies Views Last Post
  [split] Explain the python code in this definition Led_Zeppelin 1 753 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 1,026 Dec-19-2022, 05:24 PM
Last Post: kartheekdas
  Explain the python code in this definition Led_Zeppelin 1 1,109 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,255 Apr-08-2022, 05:54 PM
Last Post: deanhystad
  Could you explain each part of the code? Tsushida 2 1,527 Mar-20-2022, 08:19 AM
Last Post: Larz60+
  Sudoku Solver, please help to solve a problem. AdithyaR 5 2,145 Oct-28-2021, 03:15 PM
Last Post: deanhystad
  building a sudoku solver usercat123 7 2,782 Oct-01-2021, 08:57 PM
Last Post: deanhystad
  What is the run time complexity of this code and please explain? samlee916 2 2,309 Nov-06-2020, 02:37 PM
Last Post: deanhystad
  poplib - parsing message body, could somebody please help explain this code t4keheart 2 2,310 Oct-12-2020, 01:59 PM
Last Post: t4keheart
  unable to use result of solver in another function ross1993hall 0 1,422 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