Build a Brute-Force Sudoku Solver!
ฝัง
- เผยแพร่เมื่อ 22 มิ.ย. 2024
- Sudoku - A popular puzzle game that has also gained interest among programmers due to its logical nature.
Today, we learn how to use a recursive method to solve a puzzle with brute force. While no guessing is actually required to solve a Sudoku puzzle, the method we see here takes an elegant approach to guessing, deriving solutions in a very short amount of time.
= Links and Downloads =
WinSudoku - sourceforge.net/projects/wins...
Full sudoku client that also lets you generate puzzles
Download the code here - drive.google.com/drive/folder...
= Contents =
0:47 Rules of Sudoku
2:06 Part 1 - Architecture
-→ 2:29 Solving Strategies
-→ 3:16 Psuedocode (explaination focusing on the recursion)
6:42 Part 2 - Programming the Basics
-→ 7:21 Converting the board to mutable lists
-→ 9:07 Building the solve() function which checks every cell
-→ 10:33 Function for getting the possible values in a cell
---→ 11:48 Brief digression to look at Python comprehensions and sets
---→ 14:54 Return to writing getPossibilities()
---→ 17:10 Discussion on how to extract 3x3 squares
---→ 20:51 Testing the getPossibilities() function
-→ 22:06 Making the solve() function loop and solve as much as it can
-→ 23:22 I fix some bugs and provide a new board
-→ 24:00 Writing a printBoard() function
25:50 Part 3 - Getting started with the recursive solution
-→ 26:36 Writing isComplete() to check if the game is complete
-→ 27:56 Finding a cell to guess with
-→ 28:56 Starting to write the recursive step
-→ 29:38 Rolling back bad guesses with copy.deepcopy()
-→ 30:50 Detecting contradictions
-→ 32:46 We're done! Now testing
34:15 Conclusion
= 0612 TV =
0612 TV, a sub-project of NERDfirst.net, is an educational TH-cam channel. Started in 2008, we have now covered a wide range of topics, from areas such as Programming, Algorithms and Computing Theories, Computer Graphics, Photography, and Specialized Guides for using software such as FFMPEG, Deshaker, GIMP and more!
Enjoy your stay, and don't hesitate to drop me a comment or a personal message to my inbox =) If you like my work, don't forget to subscribe!
Like what you see? Buy me a coffee → www.nerdfirst.net/donate/
0612 TV Official Writeup: nerdfirst.net/0612tv
More about me: about.me/lcc0612
Official Twitter: / 0612tv
= NERDfirst =
NERDfirst is a project allowing me to go above and beyond TH-cam videos into areas like app and game development. It will also contain the official 0612 TV blog and other resources.
Watch this space, and keep your eyes peeled on this channel for more updates! nerdfirst.net/
-----
Disclaimer: Please note that any information is provided on this channel in good faith, but I cannot guarantee 100% accuracy / correctness on all content. Contributors to this channel are not to be held responsible for any possible outcomes from your use of the information.
![เก่งแต่ลับหลัง (FINSTA) - ส้ม มารี (Zom Marie) Ft. Punch 4EVE [Official MV]](http://i.ytimg.com/vi/OOolBU2aC70/mqdefault.jpg)
![[FULL EP.69] #เอิร์นจิรวรรณ เปิดบ้านหมื่นล้านทุกมุม ครั้งแรก! l เคหสถานบานปลาย l One Playground](http://i.ytimg.com/vi/_J4_nw8c64o/mqdefault.jpg)
This is a terrific, clear, step-by-step tutorial on the backtracking method. Your solution is unique in using deepcopy and sets. Lots of people post their code online but I like how you take a step, test your code and print your progress as you go along. You're a great teacher!
Hello and thank you very much for your comment, and for your shoutouts on Twitter! Really appreciate your kind words, and I'm glad you've enjoyed the video =)
I like your way of explaining the code.Thanks for sharing the code
You're welcome! Very happy to be of help =)
Great job ! thank you ! i learned a lot with this video.
Hello and thank you very much for your comment! Glad to be of help =)
Very clear and interested, well done :)
Hello and thank you for your comment! Glad you got the recursion problem fixed as well =)
amazing tutorial
Hello and thank you very much for your comment! Glad you liked the video =)
Thank you so much
You're welcome! Glad to be of help.
hey, how would you make adjustments to the code if its a 10x10 sudoku with 2x5 squares ?i can't seem to make it work when im slicing the squares to find out the current position, i used chars from 0-9
Hello and thank you for your comment! The logic holds exactly as long as the Sudoku rules aren't changed. The only difference is, when you're looking for squares, you can't divide by 3 as I've done. Use 2 and 5 instead for both the division and modulo operations.
Have you ever heard of the book Sodoku Programming with C? Besides the brute-force solution it gives you 10 or so more algorithms to solve the puzzle. I haven't read it myself but I heard it was a good read.
Hello and thank you very much for your comment! I haven't heard of the book, no. This method in the video was based entirely on intuition! More a fun showcase of recursion than anything.
Nice
Hello and thank you for your comment! Glad you liked the video =)
Thanks
You're welcome! Glad to be of help :)
wow who is this guy? is he a descendant from hong kong?
no offense. this solution is so beautiful and the explanation is perfect. thansk
Hello and thank you for your comment! I am the guy =) I'm from Singapore though.
Hey, I know that this is a year old, but I just stumbled onto your channel.
But I was wondering if you could sort these set of numbers out numerically?
If that's possible that would be cool if you could help me out?
Thanks
Hello and thank you for your comment! Do you mean you wish to perform sorting operations and would like to know of techniques to do so? If that's what you mean, you may want to consider my sorting algorithms series from a long time back: th-cam.com/play/PLJse9iV6Reqg-IffRqjxebaPg0zaPxWlt.html
I'll be sure to go through and check them out
Thanks for the help
How fast is the code? Good explaination btw
Hello and thank you for your comment! Because this is a brute-force algorithm, it is considered highly inefficient. However in terms of real world time it's not bad! Even challenging puzzles can be solved in seconds.
Actually I wanted to add difficulty levels to it....so that it generates a Sudoku as per difficulty level...can you help me in this...
Hello and thank you for your comment! The code given already randomly generates sudoku puzzles if you leave the grid completely empty.
You'll have to write some extra code to continue from there, but you can always take away squares, and everytime you do that, check and confirm that the final answer only allows one unique value for that square... Actually it's a little bit involved now that I think about it!
manually i solved sudoku with brute force. It works even extreme ones. Use Brute force on twins..
Hello and thank you for your comment! Yeah, you definitely can! Though of course some would say this violates the spirit of the puzzle :)
I have a kind of dumb question I guess.
If you've iterated through each item in each row haven't you also iterated through all the columns technically ?
for val in board[i] :
possibilities -= set(val)
psuedo-iteration :
i00, i01, i02, i03 .. etc
i10, i11, i12, i13, ...etc
Isn't that going through each row and thus each column ??
Maybe I'm just being Semantic and need a taste of Occams Razor...
wait it;s because you have to narrow down the possibilities if you have numerous empty spaces in each row. Duh
Hello and thank you for your comment! If I'm understanding you correctly, then the answer is no - You haven't iterated through all the columns!
You see, a 2D array is actually an array of arrays, ie. The outer array holds rows, and each row is an array which contains the columns within that row. (If that isn't clear, check out this video I did on this subject: th-cam.com/video/8ErEH_fJ44k/w-d-xo.html).
So when you loop through the row, you'll only ever get rows, but not the items inside the rows (ie. The "columns") until you poke further into that with a second loop. To use your notation for the iteration, you'd actually get:
i[0][all of 0 to 9]
i[1][all of 0 to 9]
i[2][all of 0 to 9] etc
@@NERDfirst Thanks a ton for taking the time for responding! Will you be doing any more tutorials soon? I've been learning through your channel!
You're welcome! More videos definitely coming :)
When you wrote if len(possibilities) == 1:
board[i][j] == possibilities[0]
and then you ran the program for test at 21:36 it returned ['8','7','6'] which I thought the len of possibilities is 3 now. How does it work? len(possibilities) == 1:
is equal to 1 ? what is that mean ?
Hello and thank you for your comment! These two bits of code are not really linked to each other.
At 21:36, I ran the program to test for possibilities at position (2,2) only, to get the values [8,7,6].
The part with the length check is in the nested loops, which will run the getPossibilities() function for every possible square. So, in English, what the solve() function (as shown at 21:59) is doing is this:
For every square on the board, getPossibilities() on that square. If there is only one possible value for that square, fill in that number into the square (because that's the correct value!)
@@NERDfirst Thank you very much. I enjoyed a lot learning from this video .
Can you please explain this in C#? i'd be very grateful...
Hello and thank you for your comment! I'm afraid I don't use C#. Though to be honest I'd have hoped that the concepts here are clear enough to be implemented in any language with understanding of the underlying concepts. Let me know if you're having problems with any of the concepts and I'll see how I can guide you.
I ended up with an unsolved puzzle
Hello and thank you for your comment! Sounds like some debugging is needed then! This is a pretty complex program so there are many places for things to go wrong.