I think this could be made even more diabolic/difficult: Instead of having to solve the sudokus traditionally one by one, you need the (partial) solution of some singular fields from different sudokus to solve the next sudoku partially (but not complete), which helps to solve the next one partially (and so on) until you have large chain of partially solved sudokus (which you can't solve completely). Now imagine multiple of these chains with different, randomly selected start-sudokus (which you have to find first). Only when you have solved all these chains as far as possible the will meet e.g. at the central sudoku, where you can finally solve the first sudoku completely. Only after all of this work you can propagate back through these partially solved sudokus and solve those as well. I think in theory these chains could even cross themselves and go back and forth so that you could be forced to solve all sudokus partially before being able to complete the first one.
@@renderthegreatskycity Why. We got things to do, places to be. -O3 gets a program that runs several times faster. If you're like me running a program that takes weeks on 1000 cores, we ain't got time to not pass optimizer flags.
I love your videos! This video reminds me of this activity I do. At school, during math class, I grab some Graph paper for my later classes. Then I draw perfect mazes. Not with algorithms or anything, just with my human brain.
Try using Wave Function Collapse, it goes like: >Every cell has entropy (how many valid states it can have) >Choose cell with lowest entropy and choose a random VALID state >Update all cells >If one cell has 0 entropy, backtrack or start all over again >Repeat This is also used for procedural world generation but can also be used for sudoku This is all simplified, the actual algorithm is a little more complex
@@development_placeholder-ym4hhIt's the same premise but with the addition of entropy based prioritization which significantly decreases the chance of backtracking
@@development_placeholder-ym4hhIt's slightly better than what he did in the video, because you choose cells with low entropy, and you check if any cell has no options at every step
you could make the megapuzzle even harder by removing hints until the computer manages to generate two solutions to the puzzle; in general the ideal puzzle should have a correlation between very distant subgrids so that you have to solve them all together.
Python can be optimized for performance with some libraries, I haven't seen a lot of people bother with it Personally I just stick to Python for quick programs & C when I got to do something serious
python function calls are very expensive. he probably did something very bad in python solution though, because python is usually 5x slower than c++ if we exclude input/output
so you can probably make it harder bc if each sudoku can already be solved individually, then the information from the other solved sudokus can make solving the connected one easier. what you need is for the sudokus only to be solvable with the information from an adjoining one (starting with the central one). in other words, generate your sudokus using a completed square from the previous puzzle in addition to random numbers, and then test that it still comes up as hard or harder :)
@Green-Code love your videos. It helps me through several blocks. You could name it probably productivity block. I was particularly interested if you commissioned someone to do your avatar. I really want to get back into art and making simple animated caricatures and your animations look amazing!
A few months ago I randomly tried to make an optimized sudoku solver program. I got as far as implementing 2 easy techniques which until now I thought were clever. Then I got distracted. I may not be ready for this.
I'm new to coding and I wanted to know how he visualised all the algorithms and all in his videos for e.g. in the sorting video he visualised all the different types of sorting, does he use python or a different program for it?
Maybe this is a dumb question - but where the puzzles intersect, you get a chain of 5 3x3 sections in a row, meaning there are rows that have 15 numbers in them. Do the sudoku rules of no repeats only apply per 9x9 segment? As in, you can have repeats in the 15 number row so long as they dont repeat in each 9x9 square?
so when I solve one sudoku in the grid, it yields additional clues to the ones it intersects with by corner squares, so they become easier, don't they?
You don't even have to solve it, even just filling in 1 number in the intersecting corners would already help out. The center 'diabolical' sudoku gets waaaay easier as you get extra 4 sudoku's helping you out on those corners
I wonder how that data set was formatted. A rough calculation suggests that 10M puzzles should take up around 782MB of space, given that each puzzle should take no more than 82 bytes, 81 for each cell, 0 denoting an empty cell, 1-9 for the actual numbers, then the newline character, assuming *nix line endings. I'd guess that there was some sort of UUID generated per puzzle, because otherwise the storage should have been half or less what you mentioned. Of course, the storage could be further reduced by denoting each cell as a 4-bit value. Anything further would require using compression, but it's easier to not require decompression to handle a data set. As for writing a puzzle solver, It's better to employ multiple algorithms with each pass. Take all the single holes first, then cross lines to eliminate notes, then single possibles from the notes, and so on. I would leave the sequential guessing with backtracking method for last, if it's even needed at all.
You could represent the puzzle as a single number (with 81 digits). Such a number could be stored in a 270 Bit number. If we keep a single byte character as a separator, each Sudoku takes up 278 bits (34.75 Bytes). For 10M puzzles this would need only 332MB Storing each cell as a 4bit number (and a single byte separator) would require 332 Bits (41.5 Bytes) per Sudoku and 396MB for 10M
@@SonOfNerd Yeah, if you still really want to avoid compression, though I'd argue at that point that compression would probably be easier. However, I'd rather take the hit and eat nearly a gig of space.
A: That is not usually how multi-sudoku grids work. You don't solve one and move on to the next. Each individual grid has multiple solutions but the whole puzzle has a unique one. For example, you may need to partially solve grid 1, 2, 3 and 4 in order to solve grid 5. You shouldn't generate single sudokus and then link them together. You should generate a single puzzle. I get it's not the goal of this particular exercise but I thought I'd mention it. B: Your backtracking algorithm is very primitive. You should learn about the Dancing Links algorithm. It is much more efficient in solving sudokus. C: In order to test a solver, you don't need to download millions of puzzles. You can solve the same puzzle over and over.
re: C, if that puzzle happens to be easier or harder than the average sudoku, the time you get won't really be representative of how fast the solver is on average. A larger sample size is better
hypothetically if the fastest sudoku master Wang Shiyao, from China could solve a sudoku every 5 minutes then 300s * 4810 = 1,443,000 seconds to complete or 24,050 minutes, ~400.833.. hours or ~16.7018889 days, aka ~2 weeks 2 days 16 hours 50 minutes and 168 milliseconds straight without break.
So if I were to isolate a 9x9 grid from your biggest puzzle (except the central one), it wouldn't be solvable. Right? I'm also worried that we may be able to use simple techniques to get a digit in the overlapping region that sidesteps the need for the harder techniques one needs to use in order to solve the puzzles in isolation.
@@med_boussalem Manims main thing is morphing and transformation of vector graphics, which isn't really shown in the video. I'm positive he's doing "3D" stuff in the video editor and pygame for visualizing the software aspects. My guess is based on a pygame import I spotted in the script. It would also fit the visuals. Would nice to have official confirmation though ;D
I love the idea but it’s technically not following the rules of sudoku anymore, when two of them connect at a corner, there’s 3 colums and 3 rows through the middle each with 21 numbers in, making them impossible to solve with 9 digits, an equally large and recursive sudoku could’ve been made in a different shape however
I'm not completely sure but I think I've seen that video, and it's just satire. The joke is that the digital version wouldn't even work like that, so it is just 'ha ha younger generation don't understand how to not use technology'.
Suggestion: I absolutely love your random ass content, like this kinda shit is absolutely perfect for me, but can you also provide your sources which u used to learn about the specific video's content?
hey though your game development is good enough. but even then i find hard to make a train traffic control game of my self. where i have freedom to add track, signals, swithces, deadends and platforms. and not only to interlock them but to also make a schedule of trains all in just a file size of 4mb or less, only with pyqt5 or pygame. can you make one?
So your backtracking is basically just a sat solver. It would be interesting to compare your algorithm and a typical sat solver in a race to solve the biggest sudoku
Go to brilliant.org/GreenCode/ to learn more about Computer Science with a free 30-day trial and 20% off the premium subscription!
Where can i find the sodoku? I wanna try to solve it. Btw the discord link doesnt work
yeah, yeah, we get it, get Brilliant, WHICH I ALREADY DID, get Brilliant, get Brilliant, get Brilliant, everybody knows Brilliant now, so BRUH.
You should do a sudoku, but with all 300000+ unicode characters, instead of the usual 9 digits.
wait... thats actually not a bad idea. ill try to do it in rust
Eternalis sudoku
What’s the 10th one?
@@PhilTaylorsCaravan 1234567890- 10 numbers
@@PhilTaylorsCaravanprob 0
Cant wait to see Cracking The Cryptic trying this one
Scrolled down to find this comment
@@XEqualsPenguinjust wanted to comment the same, but found this
Sudoku Desert Bus
He could turn it into a series
I think this could be made even more diabolic/difficult:
Instead of having to solve the sudokus traditionally one by one, you need the (partial) solution of some singular fields from different sudokus to solve the next sudoku partially (but not complete), which helps to solve the next one partially (and so on) until you have large chain of partially solved sudokus (which you can't solve completely).
Now imagine multiple of these chains with different, randomly selected start-sudokus (which you have to find first). Only when you have solved all these chains as far as possible the will meet e.g. at the central sudoku, where you can finally solve the first sudoku completely.
Only after all of this work you can propagate back through these partially solved sudokus and solve those as well.
I think in theory these chains could even cross themselves and go back and forth so that you could be forced to solve all sudokus partially before being able to complete the first one.
That sounds diabolical but also could be fun if its is not that big
8:16 Why do the extreme techniques sound like attacks that the secret boss uses
Like bro what the hell is a "Death Blossom" that sounds sick as hell
fr
Trying to implement techniques like exocet, death blossoms, fireworks, or Phistomefel Ring is literally torture
Yea and then you got the easy techniques like "Naked singles"
@@theexplainer1576 i was around for the phistomefels rings discovery, there were some beautiful constructed sudokus with it
Just yesterday night I started watching Cracking the Cryptic, and now you upload this, maybe the algorithm is telling me something.
3:23 should've tried assembly
Cyber-serial killer in disguise
6:30 this is actually a really smart way for people to not skip the sponsor part, because they will be interested in the soduko solver
no -O3/-Ofast flag passed to compiler makes me sad
Same
@@renderthegreatskycity Why. We got things to do, places to be. -O3 gets a program that runs several times faster. If you're like me running a program that takes weeks on 1000 cores, we ain't got time to not pass optimizer flags.
@@IsYitzach FRFR
At this rate, we might as well start using OpenMP or Cuda or smthn. We gotta pick up the pace.
@@IsYitzach thats the point, in the video he DIDNT pass the flags, he is sad because of that
Also no more advanced optimization flags like -mavx, -mfma, -mavx512f, -march=x86-64-v3 (or v4) nor -mx32.
you should consider sending it to Cracking the Cryptic. they're a great sudoku channel
@Green-Code
It’s amazing to see how coding can bring even the most complex challenges to life
I love your videos! This video reminds me of this activity I do. At school, during math class, I grab some Graph paper for my later classes. Then I draw perfect mazes. Not with algorithms or anything, just with my human brain.
Try using Wave Function Collapse, it goes like:
>Every cell has entropy (how many valid states it can have)
>Choose cell with lowest entropy and choose a random VALID state
>Update all cells
>If one cell has 0 entropy, backtrack or start all over again
>Repeat
This is also used for procedural world generation but can also be used for sudoku
This is all simplified, the actual algorithm is a little more complex
This is quite literally just recursive backtracking. the same thing he did in the video.
@@development_placeholder-ym4hh nooooooooooooooo?
@@development_placeholder-ym4hhIt's the same premise but with the addition of entropy based prioritization which significantly decreases the chance of backtracking
You can still do better with things like arc consistancy. Or arc consistancy for the full thing. This will detect a wrong number earlier.
@@development_placeholder-ym4hhIt's slightly better than what he did in the video, because you choose cells with low entropy, and you check if any cell has no options at every step
you could make the megapuzzle even harder by removing hints until the computer manages to generate two solutions to the puzzle; in general the ideal puzzle should have a correlation between very distant subgrids so that you have to solve them all together.
We need to get Cracking the Cryptic on that final sudoku ^^
Yeah
This deserves to break youtube algorithm. Happy to see a new coder in my sub list!
Oh my goodness I love sudoku so much I need this video.
I love all your videos bro, please keep it up! The projects are always interesting and I enjoy your humor. Cheers to the new year!
Love your videos man, so interesting and well paced
wooow the comparison of 7 hours python vs 1.4 minutes in cpp is crazy. But was the python code optimized for performance?
Python can be optimized for performance with some libraries, I haven't seen a lot of people bother with it
Personally I just stick to Python for quick programs & C when I got to do something serious
well, c++ code wasn't neither
python function calls are very expensive. he probably did something very bad in python solution though, because python is usually 5x slower than c++ if we exclude input/output
Probably nested for loops in Python should use list comprehension so the loops run in c instead
@@deamit6225 lol it wouldn't help backtracking relies on nested loops, that's basically all it is n nested loops
I hope cracking the cryptic has seen this. Would love to see thw series of videos solcing the giant puzzle
1:53 “And Boom! It turns into a completely different Sudoku puzzle!”
This is cool! btw, what did you use for generating your images or rendering them in c++?
We need a 10 part Cracking the Cryptic video on this 🗣️🔥
5:45 Matching two STANDARD sudoku is easy. If the common part is 3x3 or smaller - you can change numbers in one of them to fit the other
Great video 👍
The quality and efford of the videos increase radical
Love this video and channel, keep it up!
Instead of each puzzle sharing ceritan boxes, you should make it so that each box is in a row and colomb of 3, just in a weird shape.
so you can probably make it harder bc if each sudoku can already be solved individually, then the information from the other solved sudokus can make solving the connected one easier. what you need is for the sudokus only to be solvable with the information from an adjoining one (starting with the central one). in other words, generate your sudokus using a completed square from the previous puzzle in addition to random numbers, and then test that it still comes up as hard or harder :)
You're alive????
He was busy cooking The World's Biggest Sudoku
Now I'm just expecting one of those sudoku challenge solving channels to make a multiple part series on solving this one...
Look mama this green guy is alive😂😂
YESSSSSS NEW GREENCODE VIDEO WHOOOOO
never fails to surprise us
1:50 isnt it better to first check if there are any spots that can fill only one number ?
I made a script that first did that and then did backtracking and on some boards it did make a big difference
@Green-Code love your videos. It helps me through several blocks. You could name it probably productivity block. I was particularly interested if you commissioned someone to do your avatar. I really want to get back into art and making simple animated caricatures and your animations look amazing!
Can’t wait for more videos
A few months ago I randomly tried to make an optimized sudoku solver program. I got as far as implementing 2 easy techniques which until now I thought were clever. Then I got distracted. I may not be ready for this.
Where did you learn how to code and what language do you code in? Love the vids by the way keep it up
Bro first of all how are u even alive.
2nd great work man love ur work please do not stop u inspire me to do my work no matter how hard it is
Thank u
Ages ago I've done a sudoku solver in excel (yes, VBA) and find out recursive is not the best aproach
GreenCode posts, I watch. That simple
Hahahahaha
Without "with Code", I initially thought you created Sudoku with rocks.
There is a sudoku called the catterdokupillar which is made by humans and have some cool variants, also c# could do it better
Doesn't glueing sudokus together make them less hard? In the sense that hints can be shared across puzzles
Anyways very cool what you did!
Yes, but that’s how you can connect multiple sudokus into one puzzle
Would say more time consuming than hard. Would like to see you implement other rules you would see on cracking the cryptic's channel
Next you should try to make a bigger one where as many as possible are diabolical grade.
I'm new to coding and I wanted to know how he visualised all the algorithms and all in his videos for e.g. in the sorting video he visualised all the different types of sorting, does he use python or a different program for it?
You are crazy insane 😱
Maybe this is a dumb question - but where the puzzles intersect, you get a chain of 5 3x3 sections in a row, meaning there are rows that have 15 numbers in them. Do the sudoku rules of no repeats only apply per 9x9 segment? As in, you can have repeats in the 15 number row so long as they dont repeat in each 9x9 square?
i love this!!
4:16 to make a billion dollar game you need a bit of lua an idea and some luck 😂
Great content 😊
I think wave function collapse is way more effective than recursive backtracking.
green bro how did you learn to code , im about to enter college this year and want to learn coding too , could you plz provide a roadmap?
Maybe for the next video: solving some grids using IA ?
so when I solve one sudoku in the grid, it yields additional clues to the ones it intersects with by corner squares, so they become easier, don't they?
You don't even have to solve it, even just filling in 1 number in the intersecting corners would already help out.
The center 'diabolical' sudoku gets waaaay easier as you get extra 4 sudoku's helping you out on those corners
Could you release the giant sudoku png file? Would love to try to solve it without using a program
oh wait I'm dumb, the sudoku is on patreon
I wonder how that data set was formatted. A rough calculation suggests that 10M puzzles should take up around 782MB of space, given that each puzzle should take no more than 82 bytes, 81 for each cell, 0 denoting an empty cell, 1-9 for the actual numbers, then the newline character, assuming *nix line endings. I'd guess that there was some sort of UUID generated per puzzle, because otherwise the storage should have been half or less what you mentioned. Of course, the storage could be further reduced by denoting each cell as a 4-bit value. Anything further would require using compression, but it's easier to not require decompression to handle a data set.
As for writing a puzzle solver, It's better to employ multiple algorithms with each pass. Take all the single holes first, then cross lines to eliminate notes, then single possibles from the notes, and so on. I would leave the sequential guessing with backtracking method for last, if it's even needed at all.
You could represent the puzzle as a single number (with 81 digits). Such a number could be stored in a 270 Bit number.
If we keep a single byte character as a separator, each Sudoku takes up 278 bits (34.75 Bytes). For 10M puzzles this would need only 332MB
Storing each cell as a 4bit number (and a single byte separator) would require 332 Bits (41.5 Bytes) per Sudoku and 396MB for 10M
@@SonOfNerd Yeah, if you still really want to avoid compression, though I'd argue at that point that compression would probably be easier. However, I'd rather take the hit and eat nearly a gig of space.
you should upload it to a website and let people solve it
Hey awesome video can you solve it using Wave Function Collapse Cool concept to try solving or making procedural maps using this concept
Lv ur videos
I ENJOYED
i want to solve this sudoke where can i find it?
guts
Phenomenal!
A: That is not usually how multi-sudoku grids work. You don't solve one and move on to the next. Each individual grid has multiple solutions but the whole puzzle has a unique one.
For example, you may need to partially solve grid 1, 2, 3 and 4 in order to solve grid 5. You shouldn't generate single sudokus and then link them together. You should generate a single puzzle. I get it's not the goal of this particular exercise but I thought I'd mention it.
B: Your backtracking algorithm is very primitive. You should learn about the Dancing Links algorithm. It is much more efficient in solving sudokus.
C: In order to test a solver, you don't need to download millions of puzzles. You can solve the same puzzle over and over.
re: C, if that puzzle happens to be easier or harder than the average sudoku, the time you get won't really be representative of how fast the solver is on average. A larger sample size is better
i love you and your videos >
Next video solving the world's hardest sudoku using worlds slowest modern programming language ☠️☠️
For this to be harder, You shout not always start with the center sudoku 👿
A more difficult would be if you need to partial solve some to actully get th solution
make it a mmos
a massivly multiplayer online sudoku ;)
Hey can u share the big sudoku in the description or something
hypothetically if the fastest sudoku master Wang Shiyao, from China could solve a sudoku every 5 minutes then 300s * 4810 = 1,443,000 seconds to complete or 24,050 minutes, ~400.833.. hours or ~16.7018889 days, aka ~2 weeks 2 days 16 hours 50 minutes and 168 milliseconds straight without break.
I guess you are working with a space of states... Are you using any heuristic for optimising the time it takes? Or just a brute force algorithm?
So if I were to isolate a 9x9 grid from your biggest puzzle (except the central one), it wouldn't be solvable. Right?
I'm also worried that we may be able to use simple techniques to get a digit in the overlapping region that sidesteps the need for the harder techniques one needs to use in order to solve the puzzles in isolation.
Did you make it so that two interconnected sudokus have unique solutions only in interconnected state and cant be solved separately?
[How] Do you ensure that the next puzzle is still hard after the previous puzzle provides a full 3x3 section filled out for it?
What lib are you using for animation and graphics ?
I'm pretty sure he uses Pygame for the programmatic visuals
@OxibanCraft I find it pretty similar to manim ( the same model used by 3blue1brown )
@@med_boussalem Manims main thing is morphing and transformation of vector graphics, which isn't really shown in the video. I'm positive he's doing "3D" stuff in the video editor and pygame for visualizing the software aspects. My guess is based on a pygame import I spotted in the script. It would also fit the visuals. Would nice to have official confirmation though ;D
Bro one video on gen ai please 🎉
Anyone have any machine learning projects ideas or your projects?
I want to do for my college project
How long did it take to solve the beast with a backtracker?
Maybe you could make a competition for the fastest solver.
loved your video, how do you create this green and black png files of the sudoku?, it looks so good
this feels like a true chaotic evil 😈 I love it 😏
I love the idea but it’s technically not following the rules of sudoku anymore, when two of them connect at a corner, there’s 3 colums and 3 rows through the middle each with 21 numbers in, making them impossible to solve with 9 digits, an equally large and recursive sudoku could’ve been made in a different shape however
hence it's not the larger sudoku but the large array of interconected sudokus
Roughly 15 seconds, not 10 😢
im beating atleast 100 of the sudoku's in this before i die
LOL, how did you get from 9 million sudokus to 10 million sudokus? 😂
what compile options did you use for the C++ sudoku solver?
Is that a digital hungry hungry hippos?! Now I feel like a boomer because that didn't need to be digital, just have a normal hippo game
I'm not completely sure but I think I've seen that video, and it's just satire. The joke is that the digital version wouldn't even work like that, so it is just 'ha ha younger generation don't understand how to not use technology'.
some people go to pub , some on tinder after a break up me green code channel.
Suggestion: I absolutely love your random ass content, like this kinda shit is absolutely perfect for me, but can you also provide your sources which u used to learn about the specific video's content?
He mentioned a few in the most cryptographically secure place imaginable. The description!
Can you please make a tutorial for us? We also want to do such projects! 😇
how do you do the green thingy i waned to try making a scramble word puzzle from scratch so it might help me being a nice guy and its funny
How can i find github link your code repositories?
bro didnt even compile the c++ code with -O3 and -march=native 😭😭😭😭
Bro made the umbrella corp logo
hey though your game development is good enough. but even then i find hard to make a train traffic control game of my self. where i have freedom to add track, signals, swithces, deadends and platforms. and not only to interlock them but to also make a schedule of trains all in just a file size of 4mb or less, only with pyqt5 or pygame. can you make one?
Times said sudoku: infinity
So your backtracking is basically just a sat solver. It would be interesting to compare your algorithm and a typical sat solver in a race to solve the biggest sudoku
Where is the sudoku???? I whant to try it ..