Code: github.com/kying18/sudoku 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 :)
I don't have the code for it or anything, but what if instead of filling in the empty cells in order, we first filled in all 9 1's, then all 9 2's, and so on? My claim is that this would cause the algorithm to fail (and therefore backtrack) as fast as possible. This may be inconsequential for a sudoku of size n=3, but for larger n I suspect this would shave magnitudes off the runtime.
Yeah that could potentially work.. I was also thinking maybe doing some type of check for the blank space that has the most information at each recursive step, instead of grabbing the first point we see... that help decrease the top level iterations
Sort sub groups into a group list, with 9 rows, then the 9 columns, then the 9 blocks. Makes iterating and unitetesting easier as each file appears exactly 3 times.
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.
Well... I just ran across another video explaining the backtracking method. The video is 5 minutes long and the code fits on the screen. Just saying...
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.
I'm not that good at reading code but it helped me by thinking how it "should" work. Somehow the algorithm must remember where it stopped guessing the last time. Otherwise it would make the same mistake over again when the recursion rolls back. It can't begin from 1-9. Thankfully it doesn't. The beauty of this is that when you roll back it continues to iterate where it stopped the last time. If the previous guess was 6 it continues with 7.
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.
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.
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.
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): mylist.append(str(input("Please input first " +str(i)+ " row of board: "))) if solveBoard(mylist): print("Yes") else: print("No")
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)
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!
Yor explaination is quite nice! Just one thing how do enter that code into the computer while your hands are off of the keyboard as you explain things???😉😉😉
Kylie first recoreded herself writing out the suduko solver code without any sound, then, as she replayed her recording she is then able to talk without any distractions such as, trying to talk and type on her keyboard. Add in some clever editing and you have what you see in her video.
Great video... I just don't get why the value of "example_puzzle" changes so that when it's printed on the last line of the code it shows the solved puzzle.
Hey nice tutorial! Thank you for your work. But I need to ask question. what's that if __name__ = "main"? what does it do and why you needed it? I removed that part and it still works.
yep, it'll still work. that if statement is good practice for when you start building projects with multiple files. i explain this here: th-cam.com/video/G8ns2HxpM0U/w-d-xo.html
Must be a valid puzzle -- plus, "with one unique solution" (should probably have been clarified). However, you could save the solution and continue the recursion beyond that point; and, if another solution arises, let the program inform that such solution is not unique.
Hello! Could you please tell me what terminal/interface is this? I am completely green in coding and when I download newest Python, it opens up as command prompt only. Thank you!
It's called VS Code, you can know more about it here: Visual Studio Code - code.visualstudio.com I think this is a great tutorial to get stated with it: VSCode Tutorial For Beginners - th-cam.com/video/ORrELERGIHs/w-d-xo.html
Love the video. You are clearly very intelligent (and cute :P). one thing that kinda bugged me was the amount of comments you have... Its too much and makes the code harder to read. While comments are useful there shouldn't be more comments than code imo. I'm Nitpicking otherwise a great video
I don't get how THAT recursion call works, it's hurting my brain quite a bit, but how does 'if solve_sudoku(puzzle): return True' recursively call the solve puzzle function? and how do you know where to indent your backtracking line?
The most unintelligent method of solving a sudoku is "trying all of possible combinations and then choosing the right one". That's crap. That's not really fun.
Thanks for letting me know. I think in this video, I really wanted to teach recursion. It's pretty difficult to incorporate much more logic from there. In addition, if you think about it, humans playing sudoku also pretty much try all the combos in their head, but just make the combinations fail faster so they end up trying less.
@@KylieYYing yes, you're probably right. Sorry for my angry remark earlier. Just been thinking about writing the sudoku solving code in Python myself. Pretty much via "guess" function, trying to go without recursion. But still haven't finished it, really. So, been rather annoyed at myself. Thanks for your answer.
I think you don't understand this solution. It actually finds a path to the solution and reroutes at any obstacle. It does not try all possible combinations with multiple violations of the puzzle.
![ลองสุ่มไอโฟน 990 โกงมั้ย? [ โกงมั้ยครับ ep.101 ] | DOM](http://i.ytimg.com/vi/bfsWe0j492k/mqdefault.jpg)
Code: github.com/kying18/sudoku
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 :)
I don't have the code for it or anything, but what if instead of filling in the empty cells in order, we first filled in all 9 1's, then all 9 2's, and so on? My claim is that this would cause the algorithm to fail (and therefore backtrack) as fast as possible. This may be inconsequential for a sudoku of size n=3, but for larger n I suspect this would shave magnitudes off the runtime.
Yeah that could potentially work.. I was also thinking maybe doing some type of check for the blank space that has the most information at each recursive step, instead of grabbing the first point we see... that help decrease the top level iterations
@@KylieYYing th-cam.com/video/G_UYXzGuqvM/w-d-xo.html
@@KylieYYing Is there a way to be sure whether the puzzle given by user is solvable?
Sort sub groups into a group list, with 9 rows, then the 9 columns, then the 9 blocks. Makes iterating and unitetesting easier as each file appears exactly 3 times.
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.
Best explanation of sudoku recursive backtracking I've seen.. and I've been searching!
Well... I just ran across another video explaining the backtracking method. The video is 5 minutes long and the code fits on the screen.
Just saying...
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.
I'm not that good at reading code but it helped me by thinking how it "should" work. Somehow the algorithm must remember where it stopped guessing the last time. Otherwise it would make the same mistake over again when the recursion rolls back. It can't begin from 1-9. Thankfully it doesn't. The beauty of this is that when you roll back it continues to iterate where it stopped the last time. If the previous guess was 6 it continues with 7.
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.
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.
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.
Such a well detailed and lucid explanation, thanks a lot
Her thought process makes me feel like i still have a long way to go
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):
mylist.append(str(input("Please input first " +str(i)+ " row of board: ")))
if solveBoard(mylist):
print("Yes")
else:
print("No")
I recognize the new set up.
Love the way you explain the concepts.
Looking forward for new and *quick* posts. 😅❤️❤️
Great video, the explenation was great, keep it up!
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)
Wow , you got a nicest way to explain source code :)
Please make a course on "Professional data structure and algorithm"
I want to learn more about it
Hey you . . . we need more . . . get it!!!!! mooooore . . . the pace and attitude are great . . . I am learning and enjoying 🥰😘😍😎🤩
Best sudoku backtracking video, really nice work.
Very nicely explained! Great job this should have a ton more views please keep up the great work!!
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!
most underrated tut on sudoku..was crying all day imao !! thanks!!!
Going to give this a try, but not sure if this is ideal for a beginner at Python.
Hi Kylie, v nice!, is this DFS backtracking?
Yor explaination is quite nice! Just one thing how do enter that code into the computer while your hands are off of the keyboard as you explain things???😉😉😉
Kylie first recoreded herself writing out the suduko solver code without any sound, then, as she replayed her recording she is then able to talk without any distractions such as, trying to talk and type on her keyboard. Add in some clever editing and you have what you see in her video.
That was excellent, I followed your lead and implemented this in Rust (I am a terrible Rust programmer, but finally got it to work :-). Thank you !
Your video is so easy to understand.
Hi I liked the video, can I ask you how did you learn python ? school or books or online ? Thanks
Best video of all time imo
Great video... I just don't get why the value of "example_puzzle" changes so that when it's printed on the last line of the code it shows the solved puzzle.
U got a subscriber from 🇹🇷
Hey nice tutorial! Thank you for your work. But I need to ask question. what's that if __name__ = "main"? what does it do and why you needed it? I removed that part and it still works.
yep, it'll still work. that if statement is good practice for when you start building projects with multiple files. i explain this here: th-cam.com/video/G8ns2HxpM0U/w-d-xo.html
Nice backtracking example.
Thanks! This really helped me get a better understanding of this topic. Hopefully it'll be enough for finals tomorrow
Must be a valid puzzle -- plus, "with one unique solution" (should probably have been clarified). However, you could save the solution and continue the recursion beyond that point; and, if another solution arises, let the program inform that such solution is not unique.
It's easily understandable
If possible can you recomend top python books for beginners. Thanks
Joma Tech also did the same exact thing
Hello!
Could you please tell me what terminal/interface is this? I am completely green in coding and when I download newest Python, it opens up as command prompt only.
Thank you!
It's called VS Code, you can know more about it here: Visual Studio Code - code.visualstudio.com
I think this is a great tutorial to get stated with it: VSCode Tutorial For Beginners - th-cam.com/video/ORrELERGIHs/w-d-xo.html
Amazing explanation! Thank you!
What level of complexity would this algorithm be?
Both space and time will be O(n^2)
pretty neat, and lucid!
Excellent. great as always.
Love your videos ....👍👌👌
How do we call does blue lines on left side
can u plz explain why in line 8 we r checking the empty cell with "-1"??
7:17 how is that technique called in Python?, thanks
List comprehension
How long was it running? O(9^81) is not promising
i love this channel. very helpful!
How would you change this to make it valid for a 2x3 sudoku puzzle?
But if we return only true how to get the result? How to grab the puzzle?
Love you from India
Getting the triangles could be also done with Mod und compare only the starting points where mod3==0
What a cool fuckin program dude nice job
would converting the puzzle to a matrix make it easier?
Thank you so much Kylie ♥
This is a great explanation!
thank you Mulann!!!
This was helpful !! Thanks :)
This is awesome!!!!
Fine job!!!
YOU ARE THE BEST!
why this code isn't working on expert level?
I love you !
I copied this and ran it and it doesn't seem to work
she is so cute that at minute 2:30 she can write code without using her hands
She's recorded it before and is teaching us again.
@@ayman4490 th-cam.com/video/G_UYXzGuqvM/w-d-xo.html
Wow thanks a ton
Thank!
Love the video. You are clearly very intelligent (and cute :P). one thing that kinda bugged me was the amount of comments you have... Its too much and makes the code harder to read. While comments are useful there shouldn't be more comments than code imo.
I'm Nitpicking otherwise a great video
It doesn't work with me
Hmm...u copy Joma or Joma copy u?
すごい
Beauty
I don't get how THAT recursion call works, it's hurting my brain quite a bit, but how does 'if solve_sudoku(puzzle): return True' recursively call the solve puzzle function?
and how do you know where to indent your backtracking line?
Change the name of the video🙃🙃, it should be valid sudoku instead of sudoku solver
yo recursion does make your brain hurt!
How I feel about recursion sometimes: 🥴🥴🥴
Don't you mind to socialise with me?
I just did this, except I used java
Me too, except half the desktops had the wrong client version and it failed.
The most unintelligent method of solving a sudoku is "trying all of possible combinations and then choosing the right one". That's crap. That's not really fun.
Thanks for letting me know. I think in this video, I really wanted to teach recursion. It's pretty difficult to incorporate much more logic from there. In addition, if you think about it, humans playing sudoku also pretty much try all the combos in their head, but just make the combinations fail faster so they end up trying less.
@@KylieYYing yes, you're probably right. Sorry for my angry remark earlier. Just been thinking about writing the sudoku solving code in Python myself. Pretty much via "guess" function, trying to go without recursion. But still haven't finished it, really. So, been rather annoyed at myself. Thanks for your answer.
I think you don't understand this solution. It actually finds a path to the solution and reroutes at any obstacle. It does not try all possible combinations with multiple violations of the puzzle.
Backtracking woohoooo😌
Hello my wealing girls friends ?
Will you b my friend