Jun-27-2022, 12:46 PM
(This post was last modified: Jun-27-2022, 12:46 PM by 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
I like this better
if col == M: row += 1 col = 0 if (row == M): return TrueBut 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.