I'm working on algos in python and tried to implement python sudoku solver. After many tries I've decided to look for the solution and decided to use the one listed here
I've tried to play with the code and modify it to accept a local variable sudoku instead of the global one, however it seems like my code solves the sudoku and then replaces the solved sudoku with the unsolved one probably due to the recursion modification.
Here is my modified code:
#Forming the Puzzle Grid
def form_grid(puzzle_string):
global grid
print('The Sudoku Problem')
for i in range(0, len(puzzle_string), 9):
row = puzzle_string[i:i 9]
temp = []
for block in row:
temp.append(int(block))
grid.append(temp)
printGrid()
Function to print the Grid
#Function to print the grid
def printGrid():
global grid
for row in grid:
print(row)
#Function to check if a digit can be placed in the given block
def possible(grid,row,col,digit):
for i in range(0,9):
if grid[row][i] == digit:
return False
for i in range(0,9):
if grid[i][col] == digit:
return False
square_row = (row//3)*3
square_col = (col//3)*3
for i in range(0,3):
for j in range(0,3):
if grid[square_row i][square_col j] == digit:
return False
return True
def solve(grid):
for row in range(9):
for col in range(9):
if grid[row][col] == 0:
for digit in range(1,10):
if possible(grid, row,col,digit):
grid[row][col] = digit
solve(grid)
grid[row][col] = 0 #Backtrack step
return grid
puzzle_string = "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
solve(form_grid(puzzle_string))
Can't figure out how to modify the code to accept the sudoku as a parameter while returning the correct result, I've also tried to check for validity in every cal such as:
if 0 not in grid.flatten():
return grid
but that yielded the same result
CodePudding user response：
The main problem is that you were assigning the current cell always back to 0 and checked all possible digits regardless of the result of the recursive solve. you should check if the recursive solve is valid and decide what would be the next step.
The following is a small fix to your code. First, solve should return bool (i.e., True or False) as the pointer to grid remains the same, so you ddon't really need to return it. Then you should use the recursive call to check if a valid solution was found. If not, continue to the next digit, and if you checked all digits, assign 0 back to the current cell and return False. Otherwise (if a valid solution was found) return True.
def solve(grid):
for row in range(9):
for col in range(9):
if grid[row][col] == 0:
valid = False
for digit in range(1, 10):
if possible(grid, row,col,digit):
grid[row][col] = digit
if solve(grid):
return True
grid[row][col] = 0 # Backtrack step
return False
return True
puzzle_string = "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
grid = form_grid(puzzle_string)
printGrid()
solve(grid)
print()
printGrid()
BTW, there were few bugs in your code, such as relating to a global grid but not initializing it anywhere.
Also, solve is not very efficient as in each recursive call you are searching for the next empty cell. Currently is just a 9X9 grid, so it would be fast anyway, but for generalization, or just as a principal, a better way to use the recursive call is that solve would receive the row and col of the next position to check.
Finally, it might be better to remove the global grid and just return it from the form_grid function. the same for printGrid that should get the grid to print. The following is a version with the mentioned modifications:
#Forming the Puzzle Grid
def form_grid(puzzle_string):
grid = []
print('The Sudoku Problem')
for i in range(0, len(puzzle_string), 9):
row = puzzle_string[i:i 9]
temp = []
for block in row:
temp.append(int(block))
grid.append(temp)
return grid
#Function to print the grid
def printGrid(grid):
for row in grid:
print(row)
print()
#Function to check if a digit can be placed in the given block
def possible(grid, row, col, digit):
for i in range(0, 9):
if grid[row][i] == digit:
return False
for i in range(0, 9):
if grid[i][col] == digit:
return False
square_row = (row // 3) * 3
square_col = (col // 3) * 3
for i in range(0, 3):
for j in range(0, 3):
if grid[square_row i][square_col j] == digit:
return False
return True
def get_next_position(current_row, current_col):
if current_col == 8:
if current_row == 8:
return None, None
return current_row 1, 0
return current_row, current_col 1
def solve(grid, row, col):
if row is None:
return True
next_row, next_col = get_next_position(row, col)
if grid[row][col] != 0:
return solve(grid, next_row, next_col)
for digit in range(1, 10):
if possible(grid, row, col, digit):
grid[row][col] = digit
if solve(grid, next_row, next_col):
return True
grid[row][col] = 0
return False
puzzle_string = "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
grid = form_grid(puzzle_string)
print("Initial grid")
printGrid(grid)
is_solved = solve(grid, 0, 0)
print(f"Solved: {is_solved}")
print("Solved grid")
printGrid(grid)
CodePudding user response：
You could take the following steps:
- Remove the global variable and all
globalstatements - Turn your functions into methods of a new
Sudokuclass - Make
from_gridthe constructor of that class, i.e. name it__init__ - Define
self.grid = []in this constructor. This waygridis an instance member, so it is separate for each instance you create ofSudoku - Remove all
gridfunction parameters, but addselfas the first parameter of all these methods, and make sure to referenceself.gridwhere ever you need access to the grid solvehas an algorithmic problem: it returnsgridwhen it has already backtracked a working "move". Instead makesolvesuch that it returns a boolean:Truewhen the solution is found, andFalseif not, and make sure it does not clear any moves when a solution is found, and does not try any alternatives. That wayself.gridwill have the solution.
Here are those things implemented, with a few other cosmetic changes:
class Sudoku:
def __init__(self, puzzle_string):
self.grid = [
list(map(int, puzzle_string[i:i 9]))
for i in range(0, len(puzzle_string), 9)
]
#Function to print the grid
def printGrid(self):
for row in self.grid:
print(row)
#Function to check if a digit can be placed in the given block
def possible(self, row, col, digit):
if digit in self.grid[row]:
return False
for i in range(0,9):
if self.grid[i][col] == digit:
return False
square_row = (row//3)*3
square_col = (col//3)*3
for i in range(0,3):
for j in range(0,3):
if self.grid[square_row i][square_col j] == digit:
return False
return True
def solve(self):
for row in range(9):
for col in range(9):
if self.grid[row][col] == 0:
for digit in range(1,10):
if self.possible(row, col, digit):
self.grid[row][col] = digit
if self.solve():
return True
self.grid[row][col] = 0 #Backtrack step
return False
return True
puzzle_string = "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
puzzle = Sudoku(puzzle_string)
print('The Sudoku Problem:')
puzzle.printGrid()
puzzle.solve()
if puzzle.solve():
print("Solved:")
puzzle.printGrid()
else:
print("Sorry, no solution found")