Coding a Sudoku solver in Python using recursion/backtracking

Показать описание

Learn how to code a Sudoku puzzle solver in Python! In this tutorial, I explain how recursion/backtracking work in order to solve a Sudoku puzzle input.

In this video, I go over the steps necessary to use recursion to solve the input. Basically, the steps we need to follow are: determine where the next guess should go, place a guess between 1-9, then attempt to solve by recursively calling the mutating function. If the function solves the puzzle, then we are done. Otherwise, we reset our guess and guess another number.

At the end, we've literally tried every single combination of numbers on the board, through the backtracking process, so if we haven't reached a solution, then we know that our puzzle is unsolvable.

Of course, this is not a very "intelligent" solution in the sense that we have to try all the various combinations. There is probably a more optimized solution out there that can solve the problem in fewer steps. This is a good exercise to try! If you think your solution is good, you can make a pull request on github or just DM me your solution. I might include it in the github (with credits to you ofc).

Feel free to leave any questions.

Thanks for watching everyone!
~~~~~~~~~~~~~~~~~~~~~~~~

Рекомендации по теме

Комментарии

If you want to take it a step further, try coming up with an algorithm to solve the sudoku more intelligently (basically right now we're iterating through every combination til we find one that works. but there are definitely better ways that would require less time/steps). Send your solution to me/make a pull request if you've found one, and I may feature it on github!

Subscribe and follow me on insta/twitter: @kylieyying :)

KylieYYing

This is one of the best videos on this topic. I like that you use x in list for validation and list comprehension for building the columns. For some Sudokus you could continue after the first solution. There might be others, but that's considered a weak Sudoku.

alexanderpoplawski

Best explanation of sudoku recursive backtracking I've seen.. and I've been searching!

sergiobost

When I spend my day off watching, and enjoying, videos like this, I suspect that confirms what I've always known... I'm a nerd.

I wouldn't want it any other way.

:)

Thanks Kylie.

MrEdwardCollins

my version

'''
Define the isValid() function,
which checks if num can be place in
the cell indicated by row and col
'''

def isValid( board, row, col, num):
#check row
for i in range(9):
if board[row][i] == num:
return False
#check col
for j in range(9):
if board[i][col] == num:
return False
#get top-left corner
c_row = row - row % 3
c_col = col - col % 3

#check 3x3 square
for i in range(c_row, c_row+3):
for j in range(c_col, c_col+3):
if board[i][j] == num:
return False

#return True if none of the cases above returns False
return True
'''
Define the solveBoard() function,
which solves the sudoku board recursively
'''

def solveBoard(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if isValid(board, i, j, num):
board[i][j] = num
result = solveBoard(board)
if result:
return True
else:
board[i][j]= 0
return False
return True #no empty cell found

mylist = []

for i in range(9):
input first " +str(i)+ " row of board: ")))

if solveBoard(mylist):
print("Yes")
else:
print("No")

saqibraja

Great explanation!! I was thinking for lines 32 to 34, where a check is being made for a number guess being repeated in a column, that for loop could be used to check every column value. This way, no extra space has to be allocated. Considering that the number of rows and columns is fixed in this case, I think the current code is alright. Otherwise, I highly appreciate your sharing of understanding and please continue to do so.

abhinavl

Thanks for the video! I'm working on a sudoku generator but kept getting infinite loops. After a lot of digging, I realized Python was making impossible puzzles and got stuck halfway while making them since it had no way of determining if the puzzles were solvable.

LordTails

Thanks for making this fantastic tutorial video! Learned a lot and appreciate your efforts!

Just a small thing. When the program reaches the Step 6 (if none of the numbers that we try work...), it does not mean the puzzle is unsolvable. It means all numbers tried won't work for this cell. In this case the program will recursively go back to the previous state and continue. This can be seen by put a print statement right before the "return False" statement.

alanz

Such a well detailed and lucid explanation, thanks a lot

softwareengineer

I recognize the new set up.
Love the way you explain the concepts.

Looking forward for new and *quick* posts. 😅❤️❤️

zchamdawala

Wow, you got a nicest way to explain source code :)

codedoctor

I'm no programmer in any way but I have an idea to possibly speed up the run time.
As first stage filling each square on the board with 1-9 as "available guesses", then to check for each col/row/3x3 if there are any repetitions in available guesses. if there is non, then you have found a positive correct for sure. now, you need this to go back and check the board from the beginning until "board before last check" = "board after". so you have utilized all of the "simple information". That way you are left with way fewer options for the resource intensive "dumb guessing" you are left with at the end.
(I hope it's explained sort of well, the logic is the most basic "human solving method", but I tried to somewhat translate to computer logic in words. It's probably way more complex to write but it might be faster. unfortunately currently I don't have the tools to check myself)

eitamr

Her thought process makes me feel like i still have a long way to go

glansingColt

Please make a course on "Professional data structure and algorithm"
I want to learn more about it

chakmadeveloper

this is perfect 👌 you explain it really well! i‘ve been meaning to get back into working with python and this was perfect timing plus who doesn‘t love sudoku!

Gthefray