kying18 / sudoku Goto Github PK
View Code? Open in Web Editor NEWSudoku solver using backtracking
Sudoku solver using backtracking
Hi,
Thanks for this example and the video.
I try to understand how this work.
I understand the logic of backtracking, but i don't understand how in the code you go back in positions.
I have try to use breakpoint() and see how it works but i'm confused.
(Pdb) c
guess: 9
row: 0 , col: 8
> /Dev/sandbox/python_sudoku_solver/sudoku.py(77)solve_sudoku()
-> puzzle[row][col] = -1 # reset the guess
(Pdb) c
> /Dev/sandbox/python_sudoku_solver/sudoku.py(76)solve_sudoku()
-> breakpoint()
(Pdb) c
guess: 3
row: 0 , col: 7
> /Dev/sandbox/python_sudoku_solver/sudoku.py(77)solve_sudoku()
-> puzzle[row][col] = -1 # reset the guess
When i reach guess = 9 on row: 0, col: 8, i set it back to -1 (puzzle[row][col] = -1).
But how do i go back to row:0 col:7 ?
Please help me understand.
Regards
Heyo,
I try to learn Phyton at the moment and I have started to work through your video tutorials.
I am currently stuck at the sudoku solver.
I have implemented it (My helper functions are a little different than yours, but essentially work the same way)
The code has run in a RecursionError it first:
RecursionError: maximum recursion depth exceeded in comparison
But after amping the recursion limit to 5000 (from originally 1000) this error does not occur anymore.
Now there is no error at all. I have put in an integer which just counts up and is printed in the console so I can see after how many iterations the script terminates. Currently it is at 2128 in my IDE and 2129 in my console. My guess is that the OS terminates it, but I am not certain.
I work on a Windows Machine and use Phyton 3.10.4.
I have attached the code I have written.
Have a nice day!
from pprint import pprint
def find_next_empty(puzzle):
#finds next row, col on the puzzle that is not filled yet -->rep with -1
for r in range (9):
for c in range(9):
if puzzle[r][c]==-1:
return r, c
else:
continue
return None, None
def is_valid(puzzle, guess, row, col):
#Checks if the guess is valid by checking row, column and matrix.
for r in range(9):#Check if there is the number guess already in the row (col is static)
if puzzle[r][col]==guess:
return False
for c in range(9):#Check if there is the number guess already in the col (row is static)
if puzzle[row][c]==guess:
return False
#I have also to check the 3x3 matrix for the same number
#I can check row and col and use their index to determine the representative 3x3 Matrix
#Representing them with CAPS
ROW=None
COL=None
try:#This could be simplified, but I find it easier to read it in several if statements
#Generates ROW
if row in range(3):
ROW=0
elif row in range(3,6):
ROW=1
elif row in range(6,9):
ROW=2
else:
print(f"{row} is not a valid input for row")
raise ValueError
#Generates COL
if col in range(3):
COL=0
elif col in range(3,6):
COL=1
elif col in range(6,9):
COL=2
else:
print(f"{col} is not a valid input for col")
raise ValueError
except ValueError:
return False
#I still have to check the matrix, but now I know which one I have to check
#Generate the Matrix as a list and use a second variable to see if there is the guess
#Making it a list because I do not need to know if it is lower, higer or left or right
Mat=[]
for r in range(3):
for c in range(3):
Mat.append(puzzle[ROW+r][COL+c])
if guess in Mat:
return False
return True
def solve_sudoku(puzzle, i):
#solve sudoku using backtracking!
#puzzle is a list of lists, where each inner list represents a row in our puzzle
#return whether a solution exists
#mutates puzzle to be the solution (if solution exists)
print(i)
i+=1
#step 1: choose somewhere on the puzzle to make a guess
#Because we essentially brute force the puzzle, we can choose the first free entry in puzzle and start with 1
row, col = find_next_empty(puzzle)
#Step 1.1: if there is nowhere left, then we are done because we only allowed valid inputs
if row is None:
pprint(puzzle)#Printing the found solution
return True
#Step 2: if there is a place to put a number, then make a guess between 1 and 9
for guess in range(1,10):
#Step 3: Check if guess is valid
if is_valid(puzzle, guess, row, col):
puzzle[row][col]=guess
#Now we have a modified puzzle which we will iterate
#Step 4: Iterate
if solve_sudoku(puzzle, i):
return True
#Step 5. Turns out that the guess was shit. So we count up and start again till we have no numbers left
else:
puzzle[row][col]=-1#reset the guess (should not be necessary, but just in case)
continue
#Step 6: If we have tried every combination and did not solve puzzle, then this solver was not able to solve it and will return false.
#We can assume that this puzzle is not solveable
return False
if __name__=='__main__':
import sys
import threading
print(sys.getrecursionlimit())
i =1
sys.setrecursionlimit(50000)
threading.stack_size(10**8)
example_board = [
[3, 9, -1, -1, 5, -1, -1, -1, -1],
[-1, -1, -1, 2, -1, -1, -1, -1, 5],
[-1, -1, -1, 7, 1, 9, -1, 8, -1],
[-1, 5, -1, -1, 6, 8, -1, -1, -1],
[2, -1, 6, -1, -1, 3, -1, -1, -1],
[-1, -1, -1, -1, -1, -1, -1, -1, 4],
[5, -1, -1, -1, -1, -1, -1, -1, -1],
[6, 7, -1, 1, -1, 5, -1, 4, -1],
[1, -1, 9, -1, -1, -1, 2, -1, -1]
]
pprint(example_board)
print(solve_sudoku(example_board, i))
Hi! thank you so much for your helpful tutorial. I have noticed that when I run the code with a sudoku puzzle that is already wrong (for example there is already two of the same digits in one row) it freezes.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.