+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: building a sudoku solver (/thread-35081.html)
building a sudoku solver - usercat123 - Sep-27-2021
Hi,
For some reason, a call to solve_sudoku() will not print the solved sudoku, "test" is not even printed and I don't see why. Can anyone help me?
import numpy as np
def possible(x,y,n):
for i in range(9):
if grid[i][y] == n or grid[x][i] == n:
return False
x0 = x // 3
y0 = y // 3
for i in range(3):
for j in range(3):
if grid[x0+i][y0+j] == n:
return False
return True
def solve_sudoku():
for i in range(9):
for j in range(9):
if grid[i][j] == 0:
for n in range(1,10):
if possible(i,j,n):
grid[i][j] = n
solve_sudoku()
grid[i][j] = 0
return
print("test")
print(np.matrix(grid))
def main():
global grid
grid = [
[3,0,0,8,0,0,0,0,1],
[0,0,0,0,0,2,0,0,0],
[0,4,1,5,0,0,8,3,0],
[0,2,0,0,0,1,0,0,0],
[8,5,0,4,0,3,0,1,7],
[0,0,0,7,0,0,0,2,0],
[0,8,5,0,0,9,7,4,0],
[0,0,0,1,0,0,0,0,0],
[9,0,0,0,0,7,0,0,6]
]
solve_sudoku()
if __name__ == '__main__':
main()
RE: building a sudoku solver - deanhystad - Sep-27-2021
This is an odd solver. Took me a while to see how it works.
"test" is only printed if you solve the puzzle. Your solver cannot solve the puzzle because there is an error in "possible()"
RE: building a sudoku solver - usercat123 - Sep-27-2021
(Sep-27-2021, 03:32 PM)deanhystad Wrote: "test" will never be printed. The function contains a return that prevents every reaching the print command.
It doesn't matter though, because your program has a lot of errors. You recursively call the solver, but you don't pass any information so no progress is made. It just starts over from the beginning. The return is in the wrong place so your program gives gives up after solving the first cell. The solver doesn't return a status, so even if you did find a solution the program would continue running trying to find a solution.
But return is within the scope of
if grid[i][j] == 0:so it should only return after the recursion has finished right? And for the last case - where every square is not 0 - the statement
if grid[i][j] == 0:is ignored entirely and instead print should be called?
RE: building a sudoku solver - deanhystad - Sep-27-2021
I edited my early response because I found the bug, but by then you had replied. Look at the part in possible where you check if n is in the square containing x,y. That is where you have a bug.
RE: building a sudoku solver - usercat123 - Sep-28-2021
I'm too dumb to spot the bug, can you tell me whats wrong?
RE: building a sudoku solver - deanhystad - Sep-28-2021
Almost 90% of the time you are looking at the wrong part of the grid when doing this test:
for i in range(3):
for j in range(3):
if grid[x0+i][y0+j] == n:
return False Try different values for x and y and see what you get x0 and y0. For example, what is x0 when x is 5? What should X0 be?
RE: building a sudoku solver - usercat123 - Oct-01-2021
Thanks I overlooked that one. On another note, I have now expanded with a sudoku generator. First, I want to generate a valid sudoku but I have made a mistake while doing so. Here is the updated code. Can you spot it (again...)? A index out of range exception is thrown when executing place_random
import numpy as np
import random
def possible(x,y,n):
if grid[x][y] != 0:
return False
for i in range(9):
if grid[i][y] == n or grid[x][i] == n:
return False
x0 = (x // 3)*3
y0 = (y // 3)*3
for i in range(3):
for j in range(3):
if grid[x0+i][y0+j] == n:
return False
return True
def solve_sudoku():
for i in range(9):
for j in range(9):
if grid[i][j] == 0:
for n in range(1,10):
if possible(i,j,n):
grid[i][j] = n
solve_sudoku()
grid[i][j] = 0
return
print(np.matrix(grid))
def place_random(x,y):
n = random.sample(range(1,10),9)
i = 0
while not possible(x,y,n[i]):
i += 1
grid[x][y] = n[i]
def generate_sudoku():
global grid
for i in range(9):
for j in range(9):
place_random(i,j)
print(np.matrix(grid))
def main():
global grid
grid = [[0]*9]*9
"""
grid = [
[3,0,0,8,0,0,0,0,1],
[0,0,0,0,0,2,0,0,0],
[0,4,1,5,0,0,8,3,0],
[0,2,0,0,0,1,0,0,0],
[8,5,0,4,0,3,0,1,7],
[0,0,0,7,0,0,0,2,0],
[0,8,5,0,0,9,7,4,0],
[0,0,0,1,0,0,0,0,0],
[9,0,0,0,0,7,0,0,6]
]
"""
generate_sudoku()
if __name__ == '__main__':
main()
RE: building a sudoku solver - deanhystad - Oct-01-2021
The loop in place_random() ends when it finds a number that can be placed in the cell, but what happens if there are no valid numbers?
def place_random(x,y):
n = random.sample(range(1,10),9)
i = 0
while not possible(x,y,n[i]): # <- What is the value for i if there are no possible solutions for this cell?
i += 1
grid[x][y] = n[i]This is ugly code anyway. Why are you using while?def place_random(x, y):
for n in random.sample(range(1, 10), 9)
if possible(x, y, n):
grid[x][y] = n
return True
return FalseReturns True if the cell is filled, else False.Not that it matters much since you cannot generate sudoku puzzles using your approach. Most of the puzzles your generator makes will end up being invalid. You will need to make a backtracking algorithm similar to your solver that backs up when it encounters an invalid puzzle and tries again.