You should come back to this and implement some set theory strategies. One of the more common ones nowadays is the Phistomafel ring. But set theory in general is a great way to solve those tough sudokus.
I've recently discovered your channel. As other comments said, it's very underrated. Hope the algorithm notes it. Probably you are already aware of Sudokus variants (arrow, thermos, killer cages, anti-knights, ...), that could be nice if you wanted to continue down the rabbit hole. For those interested on these puzzles, I recommend "Cracking the Cryptic" channel. Thanks for the great content!
Yes, I was thinking about trying those. Need to try those myself as a human first. I already have Killer and Jigsaw versions in my Steam library, waiting.
When I was tasked with making a program like this, I implemented only up to minding naked/hidden pairs and proceeded to brute force. But even then my main improvement was to make a guess in a cell with as few options as possible and see how it plays out, in order to minimize the use of guesses. It seems to me that this approach, while not being identical, is pretty similar to the links/colors approach, which starts sounding like representing the consequences of an educated guess
Yea eventually it's hard to tell the difference between educated guess. In a sense it's really just "try a cell, see if it has any conflicts. If yes, eliminate that option"
There actually is a type of "brute forcing" that's human-viable and is commonly used by speed solvers in competitions. It's called "bifurcation" when you do your brute force method only on cells where there are two candidates left. Rather than true brute force where you guess one cell, then guess the next cell, then guess the next cell etc., you only need to make a guess between two numbers and then you continue solving the puzzle using all the other standard techniques. Also, it surprised me that 3D Medusa/brute force was necessary for so many puzzles. There must have been some simpler but more elegant logic intended for these puzzles. Great video and channel. You just need a little luck with the TH-cam algorithm and your channel will grow massively!
I think there is a name for the method you are describing, Don't remember the name - chain something or other. It is quite intuitive, actully, but requires good concentration skills.
@@GamesComputersPlay There are techniques such as Alternating Inference Chains (which I don't really understand) that use pair cells, but bifurcation is less formal. You just pick one of two values and see how far it takes you, backtracking if it fails. I guess the two techniques are closely related, though AIC is more like "logic" and bifurcation is more like "educated guessing". I had no idea sudoku was so complex until I started watching Cracking the Cryptic. If this project has got you more interested in sudoku check them out! They're puzzle experts and even they think 3D Medusa is too complicated for humans (such a cool name though)
@@GamesComputersPlay There are also various advanced methods named "forcing chains". You can also try out many algorithms interactively with SudokuWiki's solver: www.sudokuwiki.org/sudoku.htm
Wow, great presentation and really interesting video :) You really deserve more views and the fact that i got this recommended hopefully means others will too :D As someone who was trying to at least code simple elimination once, this was extra interesting to see 👀
You can also just hand the rules to a general purpose logic solver like Z3. It'll still end up backtracking the hard ones, but it'll do it more magically.
Really really hoping for a part two of this video, there has been some recent new strategies discovered, for example set theory. i think those could be very fun to implement and see how many more puzzles they could solve (also i’d be very interested to learn more about the struggles you had implementing the rules, and how you solved them)
Thanks, although I don't think a second one is ever coming. What I found is that those "cool" methods can be used on an ever smaller number of sudokus. In fact, using only a few + bruteforce seems to be the most efficient way to solve sudokus on average. I do, however, want to explore the sudoku generation one day.
Fantastic video from a fantastic channel, definitely subscribing after this one. Only thing I'd change is a cosmetic update to have the computer mark the squares in the order it solved them, instead of just top to bottom left to right, y'know? Would look more pleasing. But! Function is more important than form, you did a great job.
Now that you mentioned that, yes, it would make more interesting picture. The reason it is as it is, from programming perspective it was two almost completely separate pieces of code...
@@GamesComputersPlay Makes perfect sense! There's always a reason behind stuff, and it probably would have ended up being slower if you actually implemented it the way I suggested. Excellent content though, and thank you for posting it!
The incomplete tic tac toe game among the sketches in 0:18 is actually resolved. I think it's safe to assume that X went first by going middle, in which case it's O's turn (but if O went first, it would be X's move and a one move win by placing the X in the upper left corner). O must block in upper left corner to prevent X from winning on its turn, also setting up a position where X always loses giving itself options to win by completing 3 symbols in the top row or the left column. X can block only one of them on ist turn, allowing O to secure a win on its next move by completing the other row/column with his symbol. I have no idea why I noticed it, analysed it and wrote this comment, but i did. If you read this, thank you and have a great day!
I actually remember drawing this. I may be retro-conning right now, and it was totally random, but I think I meant the position captured where Crosses start first then noughts made a mistake of going side, not corner. After that they are doomed - crosses win on the next move. Great day to you too and thanks for watching!
Do you have a way to determine the efficiency of a given strategy? Like applying the brute force method after reaching a solid state in the puzzle using other methods? I'd imagine after simple elimination it would take significantly fewer random insertions to solve high level puzzles, roughly how many brute force iterations would you save with the most complex methods? That is how a human would solve the puzzles that those methods "failed" at.
I'm here before your channel blows up and rises in popularity. Also, if you could solve sudokus way faster than before, you'd also be closer to a cure for cancer, because both of these problems have the same NP-complete difficulty
*in discrete polynomial time, assuming you are talking about protein folding, which I am not sure of the problem class, but I assume is of NP-complete or higher (exponential??)
Hey! How did you combine the algorithms? Were each of the attempts purely following one algorithm, or dod you use the next one at the point where the previous attempts couldnt make any further progress? In that case, could it be that after a latter algorithm made some more progress, an earlier one could comlete the puzzle from that point? Just wondering about your method and what the 'this approach yields this many results' means. Cool vid tho regardless ^^
So, they all are applied in that order you see in the video. If there is no outcome from the algorythm (no candidate were removed), program proceeds to the next algorithm. As long as the algorythm gets any updates (even 1 candidate removed), program resets everything and goes back to algoritm N1 (simple elimination). This repeats until the last algorithm fails, then brute force.
You should watch some Cracking the Cryptic and revisit this subject. All of their solves are done live by a human. All puzzles are hand crafted. They've published some solves that require set theory and geometry strategies. Here's the first in that series where they explain it for the first time: th-cam.com/video/ZLcey7qiXv8/w-d-xo.html They've done some since that require different variations of the technique with different shapes and such.
I think I watched a few of their videos while making that video. I can be wrong here, but from what I gather you can create a tough puzzle for a human (meaning no backtracking/bruteforce) or a tough puzzle for machine (meaning simple backtracking). As far as I know, algorithms that does backtracking + some human techniques will crack pretty much anything in milliseconds. Anyway, I do admire people who are good at sudokus - especially those who do it with just pen and paper. When I reserached various sudoku techniques - I was really impressed how elaborate and creative they are!
Could you share that medium sudoku that required you to use 3d medusa? I'm very curious about it. I'm pretty sure that it was number 57 on your spreadsheet
Sure: 701030004090000080580029000000090206034008000000000730050700010640000003000006400 Ran the program again, yes, there was Medusa there somewhere. I also tested it in the sudoku grader (here:www.sudokuwiki.org/sudoku.htm), got a "Very Hard Grade"
How well does an algorithm work where it tries each non-brute force strategy until it gets stuck then moves on with the solved bit saved to the next strategy instead of starting fresh? Are there any puzzles that cannot be solved this way?
The general problem of Sudoku puzzles is an NP complete, so while some puzzles may be solvable with more trivial methods, more difficult puzzles will have to be solved by searching the solution space (aka “brute force”).
There come a day when it is not longer frowned upon. I will be ready, feet, socks and sandals. With a heart full of vindication and a single tear in my eye.
Cool video, and thank you for shareing your code :) ... and useing variable names like i or j is the most evil the codeing community came up with ... I try to avoid useing them... they make understanding what is going on harder then it could be.
1. I plead guilty to my code being far from perfect. I do try to work on that and if you compare some later code (connect4, for example), it is way more cleaner than something I wrote in the beginning. Sudoku code is still quite messy I must say. I tried to tidy up the general structure of the program, but inside functions it is textbook terrible - with one-letter variables and weird conditions that have minimal comments. 2. Having said that, I do want to defend i and j (and, occasionally, k). It is just like saying: I am interting over something, the number does not mean much, just a sequence number of what I am iterating over. And I think it works just fine, if used rationally.
@@GamesComputersPlay thanks for your answer. First of all it wasnt my goal to start a discussion, just wanted to share my frustration XD. And im not sure if i can agree with your point 3. Useing i, j, k... is just lazyness There are ALWAYS "better" names ... A good friend of mine said ... good code doesnt need comments to understand what is going on ... And i think useing this "idea" as reminder helps a lot by trying to improve readability...
What did you find about Sudokus with multiple solutions? Did you let brute force run to find all solutions or did you stop it as soon as it found a solution?
I don't remember exactly, but I think I assumed that there would be only one solution - otherwise such sudoku is not "legal", right? So, yes, brute force method would just stop as soon as the solution is found.
I think you may be using an old version of the program. './samples/universe1.png' is one of the files that were used to read the screen of the "Sudoku Universe" game. Generalized Sudoku Solver, currenttly published on Git (github.com/gamescomputersplay/sudoku-solver), doesn't have that - it supposed to solve sudokus from the text string. (You can see a few sample in the end of the file). If you do want to try it with the old version after all and make it work with Sudoku Universe - I can send over those png files, but I can't promise they'll work (most probably they won't), they are specific to the screen settings. You might need to get into the internal workings of the program to make it work.
Well, it might be not that super easy - when I wrote it I didn't think about easy reconfiguration for other platforms. But if you are not afraid to get into the code, figure out what it does and change it, this is what you will need to do: - in the set_version function you neet to set up coordinates of all the cells, left, right, top, bottom sides in 4 arrays. (this function was designed to easily switch between various sudoku platforms, but I only implemented 2 and abandoned it). - in "samples" folder you need to have picture samples of the numbers you'll have on a screen. Alternatevely, if you dont want to mess with the number recognition, and just looking to solution to a particular sudoku, you can use solve_from_line function - just pass in a string with numbers / zeros. Sorry again for super messy code - it isn't finished product in any way, it's just some bits of code for those who are curious how the result was achieved.
@@GamesComputersPlay Thank you for the reply! It's a useful algorithm for solving the Set Cover problem. Using a reduction, it can be applied to sudoku, and solves the problem in a small enough polynomial time. Could be a useful topic for a video!
Those puzzle rankings should be re-calculated based on how many strategies have to be used to solve it. Also, couldn't you just go straight to the backtracking strategy and be done with it?
So if you care about efficiency (and I assume you do) - is going right to backtracking the best way to solve a sudoku, generally? The answer is in my other Sudoku-related video: "Backtracking or Logic?": th-cam.com/video/8kKlEnBxa5M/w-d-xo.html
Thanks, but flattering as it may be, I am pretty sure I am not. While it does solves most Sudokus in seconds, any half-decent comiped-based solver will beat my python implementation by 100 times, for sure.
![BOWKYLION - วิงวอน (ex-change) [Official MV]](http://i.ytimg.com/vi/cLdnZWDaO-w/mqdefault.jpg)
THis channel is very underrated, can't wait until you have many more subs
Aaaaaaand now he does
You should come back to this and implement some set theory strategies. One of the more common ones nowadays is the Phistomafel ring. But set theory in general is a great way to solve those tough sudokus.
I've recently discovered your channel. As other comments said, it's very underrated. Hope the algorithm notes it.
Probably you are already aware of Sudokus variants (arrow, thermos, killer cages, anti-knights, ...), that could be nice if you wanted to continue down the rabbit hole. For those interested on these puzzles, I recommend "Cracking the Cryptic" channel.
Thanks for the great content!
Yes, I was thinking about trying those. Need to try those myself as a human first. I already have Killer and Jigsaw versions in my Steam library, waiting.
When I was tasked with making a program like this, I implemented only up to minding naked/hidden pairs and proceeded to brute force. But even then my main improvement was to make a guess in a cell with as few options as possible and see how it plays out, in order to minimize the use of guesses. It seems to me that this approach, while not being identical, is pretty similar to the links/colors approach, which starts sounding like representing the consequences of an educated guess
Yea eventually it's hard to tell the difference between educated guess. In a sense it's really just "try a cell, see if it has any conflicts. If yes, eliminate that option"
There actually is a type of "brute forcing" that's human-viable and is commonly used by speed solvers in competitions. It's called "bifurcation" when you do your brute force method only on cells where there are two candidates left. Rather than true brute force where you guess one cell, then guess the next cell, then guess the next cell etc., you only need to make a guess between two numbers and then you continue solving the puzzle using all the other standard techniques.
Also, it surprised me that 3D Medusa/brute force was necessary for so many puzzles. There must have been some simpler but more elegant logic intended for these puzzles.
Great video and channel. You just need a little luck with the TH-cam algorithm and your channel will grow massively!
I think there is a name for the method you are describing, Don't remember the name - chain something or other. It is quite intuitive, actully, but requires good concentration skills.
@@GamesComputersPlay There are techniques such as Alternating Inference Chains (which I don't really understand) that use pair cells, but bifurcation is less formal. You just pick one of two values and see how far it takes you, backtracking if it fails. I guess the two techniques are closely related, though AIC is more like "logic" and bifurcation is more like "educated guessing".
I had no idea sudoku was so complex until I started watching Cracking the Cryptic. If this project has got you more interested in sudoku check them out! They're puzzle experts and even they think 3D Medusa is too complicated for humans (such a cool name though)
@@GamesComputersPlay There are also various advanced methods named "forcing chains". You can also try out many algorithms interactively with SudokuWiki's solver: www.sudokuwiki.org/sudoku.htm
@@MisterM2402 alternating inference chains is another name for what this video refers to as “X cycles”
It would be cool to see an animation representing each strategy as your program uses them
Very informative and a great way to go through the solving process
Wow, great presentation and really interesting video :)
You really deserve more views and the fact that i got this recommended hopefully means others will too :D
As someone who was trying to at least code simple elimination once, this was extra interesting to see 👀
Glad you liked it, Sudoku is indeed a great excersice for coding.
agree
I just stumbled across you… I’m loving these
You can also just hand the rules to a general purpose logic solver like Z3. It'll still end up backtracking the hard ones, but it'll do it more magically.
Really really hoping for a part two of this video, there has been some recent new strategies discovered, for example set theory. i think those could be very fun to implement and see how many more puzzles they could solve (also i’d be very interested to learn more about the struggles you had implementing the rules, and how you solved them)
Thanks, although I don't think a second one is ever coming. What I found is that those "cool" methods can be used on an ever smaller number of sudokus. In fact, using only a few + bruteforce seems to be the most efficient way to solve sudokus on average.
I do, however, want to explore the sudoku generation one day.
Fantastic video from a fantastic channel, definitely subscribing after this one.
Only thing I'd change is a cosmetic update to have the computer mark the squares in the order it solved them, instead of just top to bottom left to right, y'know? Would look more pleasing.
But! Function is more important than form, you did a great job.
Now that you mentioned that, yes, it would make more interesting picture.
The reason it is as it is, from programming perspective it was two almost completely separate pieces of code...
@@GamesComputersPlay Makes perfect sense! There's always a reason behind stuff, and it probably would have ended up being slower if you actually implemented it the way I suggested. Excellent content though, and thank you for posting it!
The incomplete tic tac toe game among the sketches in 0:18 is actually resolved. I think it's safe to assume that X went first by going middle, in which case it's O's turn (but if O went first, it would be X's move and a one move win by placing the X in the upper left corner). O must block in upper left corner to prevent X from winning on its turn, also setting up a position where X always loses giving itself options to win by completing 3 symbols in the top row or the left column. X can block only one of them on ist turn, allowing O to secure a win on its next move by completing the other row/column with his symbol.
I have no idea why I noticed it, analysed it and wrote this comment, but i did. If you read this, thank you and have a great day!
I actually remember drawing this. I may be retro-conning right now, and it was totally random, but I think I meant the position captured where Crosses start first then noughts made a mistake of going side, not corner. After that they are doomed - crosses win on the next move.
Great day to you too and thanks for watching!
Do you have a way to determine the efficiency of a given strategy? Like applying the brute force method after reaching a solid state in the puzzle using other methods? I'd imagine after simple elimination it would take significantly fewer random insertions to solve high level puzzles, roughly how many brute force iterations would you save with the most complex methods? That is how a human would solve the puzzles that those methods "failed" at.
Video quality is great , nice upload👍
I LIKE SOCKS AND SANDALS TOO MY DUDE
Further version of the solver
Strategies:
1. Simple Elimination
2. Hidden Singles
3. CSP
4. Intersection
5. X-Wing
6. Coloring
7. Y-wing
8. Swordfish
9. XYZ Wing
10. X-Cycles
11. XY-Chains
12. 3D Medusa
13. Unique Rectangles
14. Subset Exclusion
15. Grouped X-Cycles
16. Alter. Inference Chains
17. Sue-de-Coq
18. Almost Locked Sets
19. Bowman's Bingo
20. Brute Force
(Of course, I know 10 strategies are enough be efficient.)
I'm here before your channel blows up and rises in popularity. Also, if you could solve sudokus way faster than before, you'd also be closer to a cure for cancer, because both of these problems have the same NP-complete difficulty
*in discrete polynomial time, assuming you are talking about protein folding, which I am not sure of the problem class, but I assume is of NP-complete or higher (exponential??)
What in the world is that Medium 57 puzzle? o.O
Hey!
How did you combine the algorithms?
Were each of the attempts purely following one algorithm, or dod you use the next one at the point where the previous attempts couldnt make any further progress?
In that case, could it be that after a latter algorithm made some more progress, an earlier one could comlete the puzzle from that point?
Just wondering about your method and what the 'this approach yields this many results' means.
Cool vid tho regardless ^^
So, they all are applied in that order you see in the video.
If there is no outcome from the algorythm (no candidate were removed), program proceeds to the next algorithm.
As long as the algorythm gets any updates (even 1 candidate removed), program resets everything and goes back to algoritm N1 (simple elimination).
This repeats until the last algorithm fails, then brute force.
You should watch some Cracking the Cryptic and revisit this subject. All of their solves are done live by a human. All puzzles are hand crafted. They've published some solves that require set theory and geometry strategies. Here's the first in that series where they explain it for the first time: th-cam.com/video/ZLcey7qiXv8/w-d-xo.html They've done some since that require different variations of the technique with different shapes and such.
I think I watched a few of their videos while making that video.
I can be wrong here, but from what I gather you can create a tough puzzle for a human (meaning no backtracking/bruteforce) or a tough puzzle for machine (meaning simple backtracking).
As far as I know, algorithms that does backtracking + some human techniques will crack pretty much anything in milliseconds.
Anyway, I do admire people who are good at sudokus - especially those who do it with just pen and paper. When I reserached various sudoku techniques - I was really impressed how elaborate and creative they are!
Could you share that medium sudoku that required you to use 3d medusa? I'm very curious about it. I'm pretty sure that it was number 57 on your spreadsheet
Sure: 701030004090000080580029000000090206034008000000000730050700010640000003000006400
Ran the program again, yes, there was Medusa there somewhere.
I also tested it in the sudoku grader (here:www.sudokuwiki.org/sudoku.htm), got a "Very Hard Grade"
How well does an algorithm work where it tries each non-brute force strategy until it gets stuck then moves on with the solved bit saved to the next strategy instead of starting fresh? Are there any puzzles that cannot be solved this way?
The general problem of Sudoku puzzles is an NP complete, so while some puzzles may be solvable with more trivial methods, more difficult puzzles will have to be solved by searching the solution space (aka “brute force”).
yay for socks in sandals
There come a day when it is not longer frowned upon. I will be ready, feet, socks and sandals. With a heart full of vindication and a single tear in my eye.
Computers are like made for sudoku
thats how computers check for data errors
Cool video, and thank you for shareing your code :) ... and useing variable names like i or j is the most evil the codeing community came up with ...
I try to avoid useing them... they make understanding what is going on harder then it could be.
1. I plead guilty to my code being far from perfect. I do try to work on that and if you compare some later code (connect4, for example), it is way more cleaner than something I wrote in the beginning.
Sudoku code is still quite messy I must say. I tried to tidy up the general structure of the program, but inside functions it is textbook terrible - with one-letter variables and weird conditions that have minimal comments.
2. Having said that, I do want to defend i and j (and, occasionally, k). It is just like saying: I am interting over something, the number does not mean much, just a sequence number of what I am iterating over. And I think it works just fine, if used rationally.
@@GamesComputersPlay thanks for your answer.
First of all it wasnt my goal to start a discussion, just wanted to share my frustration XD.
And im not sure if i can agree with your point 3. Useing i, j, k... is just lazyness
There are ALWAYS "better" names ...
A good friend of mine said ... good code doesnt need comments to understand what is going on ...
And i think useing this "idea" as reminder helps a lot by trying to improve readability...
What did you find about Sudokus with multiple solutions? Did you let brute force run to find all solutions or did you stop it as soon as it found a solution?
I don't remember exactly, but I think I assumed that there would be only one solution - otherwise such sudoku is not "legal", right? So, yes, brute force method would just stop as soon as the solution is found.
And seems nobody mentioned SAT solver as universal solution for all sudoku-like puzzles
I've opened a wikipedia page about it and was out of my depth right around the beginning of second sentence... :)
3:31 missed opportunity to say "from 1 to 9" lol
haha, nice one.
Hi, I downloaded the python file, but it wants to open './samples/universe1.png'. Can you please tell me were I can download this file?
I think you may be using an old version of the program.
'./samples/universe1.png' is one of the files that were used to read the screen of the "Sudoku Universe" game.
Generalized Sudoku Solver, currenttly published on Git (github.com/gamescomputersplay/sudoku-solver), doesn't have that - it supposed to solve sudokus from the text string. (You can see a few sample in the end of the file).
If you do want to try it with the old version after all and make it work with Sudoku Universe - I can send over those png files, but I can't promise they'll work (most probably they won't), they are specific to the screen settings. You might need to get into the internal workings of the program to make it work.
Can AI solve Nonograms? Probably yes. How fast would it be?
how to tranfer the code to our game and run it so that it can actually work on my pc?
Well, it might be not that super easy - when I wrote it I didn't think about easy reconfiguration for other platforms.
But if you are not afraid to get into the code, figure out what it does and change it, this is what you will need to do:
- in the set_version function you neet to set up coordinates of all the cells, left, right, top, bottom sides in 4 arrays. (this function was designed to easily switch between various sudoku platforms, but I only implemented 2 and abandoned it).
- in "samples" folder you need to have picture samples of the numbers you'll have on a screen.
Alternatevely, if you dont want to mess with the number recognition, and just looking to solution to a particular sudoku, you can use solve_from_line function - just pass in a string with numbers / zeros.
Sorry again for super messy code - it isn't finished product in any way, it's just some bits of code for those who are curious how the result was achieved.
Can you write a Python script to get people to stop calling it "Suduko"
They do? Can't say I heard it this way, where I am from people quite correctly call them "sudoku", or to be more precise "судоку".
That or "Suduku", drives me nuts!
Why didn't you use Knuth's Algorithm X?
Hm, I haven't heard about that one.
Just googled it, something to look into. I particularly like the name "dancing links".
@@GamesComputersPlay Thank you for the reply! It's a useful algorithm for solving the Set Cover problem. Using a reduction, it can be applied to sudoku, and solves the problem in a small enough polynomial time. Could be a useful topic for a video!
What the hell was up with puzzle 57, and why was it in MEDIUM?
It's like a sudoku version of the character from "Nobody".
Isn’t solving sudoku puzzles an NP problem?
I am pretty sure it isn't, I think it's just a P problem.
But I have not enough mathematial skills to prove it.
Those puzzle rankings should be re-calculated based on how many strategies have to be used to solve it.
Also, couldn't you just go straight to the backtracking strategy and be done with it?
So if you care about efficiency (and I assume you do) - is going right to backtracking the best way to solve a sudoku, generally?
The answer is in my other Sudoku-related video: "Backtracking or Logic?": th-cam.com/video/8kKlEnBxa5M/w-d-xo.html
my mom nearly has a 10k win streak on sudoku
You hold the TAS world record for this game and you don't even know it
Thanks, but flattering as it may be, I am pretty sure I am not.
While it does solves most Sudokus in seconds, any half-decent comiped-based solver will beat my python implementation by 100 times, for sure.
In Russia they write code only in IDLE
Haha, in Soviet Russia Dark Mode switches you.
Haven't switched me yet, as you can see.
chris prat 😂😂