Python Sudoku Solver - Computerphile
Вставка
- Опубліковано 11 лют 2020
- Fun comes in many forms - playing puzzles, or writing programs that solve the puzzles for you. Professor Thorsten Altenkirch on a recursive Sudoku solver.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
Once you understand recursion you can understand recursion
I see what you did there
I see what you did there
@@violet_flower Yeah sure I'll explain deadlocks to you right after I've explained deadlocks to you
But where is the edge case?
@@harbl2479 I was thinking that too. It seems like it's taken care of by simply working through the nested for loops, which continues even after it found a solution. This has the advantage of finding all solutions if there are any, which there shouldn't be if the puzzle was constructed properly.
You make it sound straightforward, but in ORDER to understand recursion, you need to understand recursion.
1:38 wow he was able to say "recursion" without even moving his mouth, that's the real trick
It's easy if you try it.
now everyone is trying it out
I've literally watched it 10 times now and I'm still amazed.
His lips utilize a very efficient algorithm
That comment made me laugh so hard. xD
It must ba a joy having him as teacher, he is so chill and methodical.
When he's your teacher you don't get subtitles, so it can be tricky
Amen
I'm sad
@@RobertMilesAI exactly
Robert Miles he's perfectly understandable without subtitles imo
It's more fun to write a solver/ generator than it is to do the puzzles by hand
A+ (now write it in Rust ;-) )
@@recklessroges Now Brainf*ck 😉
(It's is a real programming language)
@@garethevans9789 Piet?
Making a solver is also kind of a puzzle :p
@@garethevans9789 I refuse to believe anyone is so masochistic as to write a program for extensively handling a two-dimension array in Brainfuck. Like, I'm sure one exists somewhere, but it was almost certainly written in C and then run through a converter.
I really like Thorsten, he seems like a good guy.
eh kills sodukus and doesnt afraid of anything
he's awesome. he has that excitement for maths like a young person, and explains in a way to help others.
Yeah I love this guy.
he ist verry deutsch
Kinda reminds me of a bond villain.
aaaaa the spaces before the colons
And this nested loops...
It hurts
@@OrgBrent And not having a space after commas. Not very pythonic
@@ekremdincel1505 I get the spaces thing, but how else would you write the nested loops?
@@rudyorre you should find a better algorithm if possible.
For those who wanted to learn more about this. The problem of solving sudoku can be generalized to a problem called Constraint Satisfaction Problem (CSP), CSP includes things from puzzle solving to real world problem like planning and scheduling.
True. It mostly uses AllDiff constraints to solve the problem.Which states that all the variables must have different values.
The Dancing Links algorithm, by Knuth, is one of the most beautiful algos I have ever seen. It works by abstracting away from the sudoku itself, and translating all the constraints into a matrix form, on witch you can apply a backtracking algorithm, in order to find a subset of lines with exactly one non-zero value in each column. The advantage is that it treats all constraints as equal.
You should absolutely do a video on solving Sudoku with Dancing Links. Moreover, you can show that by generalizing a problem, you can use exactly the same algorithm for Sudoku, Pentominos, Soma cube and many others.
Does he have his own UA-cam channel? I really enjoy the way he talks about problems. Makes them seem much easier than they really are.
This is O(scary)
I'm literally crying from seeing this approach
i mean this aproach is almost brute force
Not for a normal 9x9 sudoku. NP-hard means it gets way harder once you _increase_ the size. For example, 16x16 sudoku would probably take longer to solve, but a 9x9 should be doable in just a few milliseconds.
How did this not hit the recursion depth limit?
@@TaylorLopez412 you can set the recursion limit iirc
I was actually contemplating on making a sudoku solver myself as practice or not, but then seeing how it's done is just way too fun.
Dear Thorsten, I was your student and enjoy this video. As a Chinese, I want to tell that the later game is called Huarongdao. (华容道), The story is about a general of a kingdom escaping from a losing battle. I have some fun when I was a child with it.
6:45 that keyboard has seen war
Space bar certainly did
what about his whiteboard
shits scarred for life
The time when Targaryens not using Dragons anymore, They are using Python..
As someone who's learning Python I'm excited to try this project. I've learned to build my first LogisticRegression model, so I'm excited to to continue making progress.
You can use the built-in pprint function (from pprint import pprint) to pretty print data
That is a separate library in the deployments I'm familiar with.
@@rucker69 I guess he means it's part of the standard library.
@@Kuchenrolle it looks like the original was edited
1:12 - "vot do vee do?"
SILENCE! VEE VIL AASK D'KVESHCHUNS!
Scooby dooby doo
haha
I remember i made my own sudoku solver in my late teens. I don't remember much but i remember part of it would track POSSIBLE numbers for each square. This video brought back a bit of my memory when i saw "possible" in the code.
At one time I wanted to learn java, so I wrote a sudoku solver in Java, with a gui to input the puzzle.
The principles of solving were basically the same as the python version, but Thorstens version were more elegantly written.
4:02 smooth af
For my final project in pic10C (programming in computing) at Uni, I tried to finally write a program in c++ to generate Sudokus using specified seeds. I had tried to write this program three times previously: once in c++, then in python, then again in c++ and of course the last attempt in c++. It's amazing just how complicated it becomes trying to generate Sudokus.
You'd think the logic would be simple enough: put a number there if it can go there; but the issue is the framework you have to move in: columns, rows, and blocks. You find that numbers being in cells is only a suffucient condition to block a number from potentially going in a cell. In fact, potential numbers in potential cells can affect OTHER cells potential numbers, and the issue just compounds from there!
I have couple ideas, I'll try to remember to test them
@@Henrix1998 One of the ideas I came up with (which was ultimately insufficient but which might be improvable though I've not worked on this project for about a year) to surmount this problem was this concept of cell "families" which were empty cells in a block, row, or column whose mutual potentials were the source of the exclusion of those numbers outside the family in that block, row, or column. I remember getting the first layer of this idea working but it needed to "shrink" as cells in families were assigned numbers which I never solved in time. Typing this out it reads like a non-issue but for whatever reason the difficulty of doing what I was doing shot up.
i also wrote a sudoku generator. my approach was to first: generate a list of the most "primitive" sudokus possible and store that list, then use that list to create the sudokus.
with "primitive" sudoku i mean a special set of sudokus with which i can create any legal sudoku. i create a new sudoku out of a primitive by several transformations like:
flipping,
rotating,
switching numbers with each other (like switching all 1s to 2s, all 2s to 5s and all 5s to 1s)
switching rows within blocks
switching rows of blocks
and more.
the important thing is doing any of the transformations on a valid sudoku will give a new valid sudoku.
and to get that list of the most primitive sudoku i basically just brute-forced all sudokus, checked if they were legal, then check if i already stored this sudoku or any of its transformations, if not then store this as a new primitive sudoku.
you only have to generate that list once on your computer, then you can use that to generate new sudokus really fast on any machine.
Wouldn't it be exactly the same as solving a sudoku, with the only two key differences being that
1) you start with an empty board, and
2) you don't check whether 1-9 can fit in a cell in numerical order, but random
How about this for generation:
Create a complete and legal board
Remove a number and solve()
Keep repeating until the board has more than one solution
Put back the last removed number
I'm not sure if this would make for nice puzzles, though. It will probably _depend_ on backtracking, which humans don't really like. I prefer to deduce or infer solutions.
This is really a clever little algorith for the problem. It's a bit too simple for my taste because it only prints out the solution while the solve() recursion is still running. After solve() is completed, the grid is in the state from the beginning again and the solution is lost. I slightly modified it by adding a returnvalue to solve() and some evaluation to keep the final result in the variable grid[ ][ ]. A while back I began programming a sudoku solver that should replicate the exact way I solve a sudoku on paper. It's still not finished because it struggles with the extra hard Sudokus. I like these Computerphile videos.
He explains everything well, except for the part "grid [y] [x] = 0". I had to take some time to realize that this part is actually connected to the input part where the program stops and not just sets the cell value back to zero right after finding the answer)
I still struggle to understand that part
@@weejohntee this took me a while. Thing is solve() has 3 different outcomes: 1. No empty cell found (the sudoku is solved) -> before the function finishes (and leads to grid[y][x] = 0) it prints the array. 2. The possible() function returns false and not all numbers (1-9) were tried already OR the possible() function returns false and no number fits in the cell. In the first case it checks possible() with the next number, in the second case (3) it returns the solve() function before the the whole sudoku was finished and sets no number for this cell. The previous solve() call in the recursion now finishes its own solve call, and sets the cell before also 0. BUT in this case maybe not all numbers(1-9) were tried so it could try again with another. Only when all numbers were tried, the solve() returns and then checks the previous solve() call (bottom up in the recursion). But maybe in the end the solve() function can't find an empty cell anymore. Then the whole thing gets printed before all the recursions collapse and go bottom up (--> clear the array) again.
@@Anaximander29A thanks for the explanation
Great teacher, fun and entertaining for super tough concepts. Such an elegant solution too.
I would like to watch your follow-up video about Knuth’s algorithm x and dancing links, considering a sudoku solver as a constraint satisfaction problem :)
I’ve tried to code it myself using my own logic on solving sudokus. It is far more complicated and frustrating to code, and this is where the beauty of his method resides.
I feel you, after 5 attempts i finally succeeded using logic, i spent way too much time on it though
Wow. I really want to learn more under him. Beautifully explained everything. ❤️
Some time ago I was making a sudoku solver for fun. But I did the "like human" approach. Specifically, I made it try various techniques. This also nicely doubled as a puzzle difficulty checker. Instead of just looking at how many cells were pre-filled (most of publications I checked do that), it checked what techniques were required to progress.
But I got bored before I could finish it so it would solve the "hardest sudoku puzzle" without guessing.
Is it possible for you to enable automatically generated captions? They work perfectly on Numberphile channel!
I am convinced I am not the only one who would appreciate this. I often watch your videos at night and I cannot enable sound because that would disturb my roommates :(
btw. I love your videos. Great content as always!
I did one years ago, I made a 3 dimesional array, 10 values for each square (10th value holds the solved value). The user could enter numbers interactively. When a number was inserted it registered the number across the row, column and block, thus reducing the possibilities in each square. Then it checked the whole grid, and if there was only one possibility in a particular square, it got filled in. Then it recursed. If it failed to fill in another square, it went back to waiting for the user to fill in another number. It would normally reach a tipping point where all the numbers got filled in.
Worth mentioning is that sudoku is part of a family of problems called 'exact cover' problems which are NP hard. In the family are problems such as nonograms and the eight queens problem. Would be cool to see sudoku generalized as an exact cover problem and solved that way.
Thank you for the efficient explanation! Does Thorsten Altenkirch’s name appear in the description notes? I am looking forward to reading the book he alludes to: Conceptual Programming with Python.
He has so much more enthusiasm for computer science than 90% of my professors in the department. Lol.
I built a sudoku solver in PowerShell, python and C++. But it couldn't solve the harder problems. Awesome video.
a function that calls itself? THIS CHANGES EVERYTHING
I'm hobby Python programer and Sudoku solver was my first "real" project fee months ago. I really love Python!!! :)
I would smoke weed with this guy
Teo Ionut me too, and I don’t even smoke
Teo where do you find weed in Bucharest?
@@evolutionsimplified noapte buna
He lowkey looks like a gangsta or a drug lord turned programmer 😂
I think I'd have to have smoked weed to understand this guy!
_cries in PEP8_
Lol
Every video with this guy
Searched through the comments for this before starting the video.
the think that hurts me the most is not using numpy's nicer features, for ex, the possible() function could have been this:
def possible(x, y, value):
return np.all((grid[y, ...] != value) + (grid[..., x] != value))
@@proud22beme, looks like that's only the column and row rules, you missed the 3x3 square rule.
Many years ago now, i.e. very shortly after Sudoku arrived in Norway, I wrote a solver for it. For a quick & dirty program like this I used Perl. The obvious method was to use recursion with pruning and backtracking since a brute force approach would be far too slow. My solver sorts all the open cells by the number of possible numbers to put there, this means that I always enter any forced values first, then when I can't see any more of these I will try the cells with two possible values, then 3, 4 etc.
The key to make it fast was to have a compact grid representation so that I could pass it along on the recursive calls, I used a 9-bit bitmap for each cell, so each time I place a digit I also cross out that bit from cells in the same column or row. The alternative is to clean up during backtracking but in that case the bitmap updates take a lot of time so it is better to simply make a local copy for each call.
The obvious next stage was to use the solver to evaluate the difficulty of randomly generated sudokus, I gave this program to my parents for Christmas so that they could print out a pair of new puzzles each time they wanted to have a solving race. I used the number and size of the N-way splits needed in the solver as a proxy for difficulty and this worked very well.
Love yt recommendations. I have been watching for 1 min and was subscribed already.
I wrote a similar solver in MATLAB using recursion but I searched through the puzzle to find the element with the least number of possible values which minimises the number of calls to the function.
Wow, it's not teaching, it's gossiping, motivating, soothing, relaxing.
there is one little trick to improve the the solver by magnitudes, iterate over all fields and find the one with the least possible values according to the 3 constraints (row, colom, box)
if you feel fance only try those values (but it just reduces runtime costs by some small amount)
that way you have much less guessing and the search tree almost collapses to a list
could you elaborate, please?
I did something similar in python last year (as a college freshman). It's really cool seeing how my sloppy self taught code/sudoku logic (not using brute force/guess and check) compares to a legitimate build.
This is the kind of guy who teaches by doing
My favorite kind of teacher
i'm so intimidated by the ease he's talking about those hellish loops.
Simple and elegant solution. I love it!
Recursion is easy to understand at high level but hard if you actually think in detail. When I wrote a Sudoku solver I used a more human approach. I first added those that were certain and used recursion only when there were alternatives,
I can just imagine this guy as Hitchhiker's Guide to the Galaxy character.
I like your comment, but at this moment it has 42 likes, so I won't put another one there, it would ruin the "answer".
@@Nilslos can't help it now
President Zaphod
"Once you understand it, it's quite simple"....That is the beauty of computer science
For anyone interested: If you want an easy way to go the constraint solving route, for example because you want to solve this for larger N where the running time becomes restrictive, you can model your sudoku problem in a constraint programming language such as MiniZinc and solve it using a constraint solver. Sudoku is actually part of the MiniZinc tutorial
Constraint programming is the way to solve this without reinventing the wheel 😄
I didnt do it this. But I did a sudoku verifier in C instead. It was quite interesting because you can use threads to check the puzzle from rows, columns, and each individual square.
Prof: This is my sudoku solution.
Interviewer: Now do it in O(-1) complexity
Prof:
Vstro its O(1) because the n is always 9
The homework is to create a python script using that solver and "back tracking" to generate new "1 possibility" sudoku grids.
This video helped me a lot understand a different way of using recursion
This guy is off the hook!
Spectacular!
If anyone is confused how the resetting to 0 isn't called everytime: note where the print statement is! It gets called only in the case, that on some recursion level deep down, there is no more empty cell! After the full algorithm has finished, all the initially empty cells are indeed back to 0.
Nice! Thank you
The cooking animation was amazing ... and made me laugh^^
Haha yes
I tried copying this with a blank starting grid with all zeros and thought it wasn't working, but then realized it was just taking forever to loop through everything! Great video, got me thinking.
😆😆😆
I wrote a sudoku solver that ran on an arduino spitting each new addition to the grid as a load of serial prints. I didn’t use the brute force recursive approach but instead tried to replicate the methods I found on a website devoted to solving sudoku. I think it taught me allot
Why did you run on an arduino? I'm just curious
Nuno Ricardo Serafim because at the time it was the only programming language / environment that I was familiar with!
REALLY be wanting to fix that phone cord.
Glad I'm not the only one. 👍
Ur so funny guy
LEGEND!
10 minutes on this and was able to understand backtracking...
Dude ur profile pic made me throw my phone against the wall
This beautifull man just made me understand backtracking... Thank you!
Dear Professor Thorsten Altenkirch, Thanks a lot for the video and the solution. What I don't understand is how your algorithm manages find multiple solutions for a single puzzle? What would be different for it to return just one solution? I was wondering if the looping of potential possible values in solve() creates a Tree (data structure) of potential valid solutions for solve() to recursively step through? Is that it? Sorry if the question is uber-silly.
I really like the, "and my challenge to you is to write...".
"The proof is left as an exercise to the reader"
Really liked this one, the solution is so elegant
not really its about as brute force as it gets
why does it continue to print other solutions, even after its out of loop? plz help
@@bugodi327 No it's not as brute force as it gets. The as brute force as it gets would be to generate all the possible sudokus and check for each one if it was vaild.
My job is in the health industry and I have very little idea about other domains. I've recently just been looking at computer science online. This is insane for me. There are universes of things in life I have no idea existed.
Talk more about conways life.
I have watched every video about it and i am just so curious about simple laws and infinite repetitions to create physical effects and mathematical phenomena!
Because all* maths can be made into a complex computer with parts that move and interact using laws of the universe to create physical effects and mathematical phenomena!
Please do a follow up on Knuth's dancing links algo.
Interesting solution.
I wrote a Solver a few years ago that replicated the way that humans would attempt to solve it. It would be interesting to see a speed comparison between this method (recursion) compared to my solution. I suspect that with a simple puzzle as presented here that the recursion method would be comparable, but it would be interesting to see how it would deal with a harder puzzle.
Yeah, this one looks like a brute-force try 9^81~ish possibilities until one of them doesn't fail.
Bro the code in this video is O(scary)
Because I didn't have anything better to do (read avoiding responsibilities), I copied the code presented here and wrapped the same timing method around the solve function. For the puzzle presented here, on the same hardware, my solver completed it in 0.003 seconds (I'm aware that there will be slop in python timing) and this recursive solution took 0.09 seconds.
I then fed them both a hard puzzle (as pulled from an Australian Newspaper which had 24 values entered - compared to 29 in the video). Mine took 0.005 seconds (so not much slower compared to the easier puzzle), but the recursive solver took 0.8 seconds, so significantly slower.
@@band-o-lear Code from this video can be significantly improved: when an empty cell is found Code start from the very beginning to looking for another empty cell. But if continue from the "current" position (there are no empty cells before) - it will be much faster.
who can golf the fastest solver
The most easy explanation for recursion trick is calculation for ! (factorial). And understanding of it is like a splash in brain! And you start to make magic, like in this video. Thanks!
Great video! Worth mentioning that after all solutions are found grid will return to its original form as a side effect of grid[y][x]=0 (which can also be a feature).
If i dont want this, how can i prevent it? An idea was to put it in an if statement, that checks if all rows sum to 45 and then not execute grid[x][y] = 0. Or maybe use numpy to check if there are any zeroes left? Would there be a more elegant solution?
hay everyone 2d list output easy mode -> print(*listvar, sep='
') !!!best thing EVER changed my life
Another one
from pprint import pprint
pprint (grid)
I dig this speaker. Pretty chill one. And interesting topics too :)
Woah, there has to be more such videos!
Try building a MILP solver. Really quite interesting, particularly to extend it for other variants.
I was reading Steven Skiena's "Algorithm Design Manual" and according to him, this kind of sudoku solution for backtracking suffers from choosing the empty squares suboptimally. It seems like the best way would be to try the most-constrained-empty-squares first, rather than simply looping empty squares from top left corner to the bottom right corner. Most constrained empty square is those squares on the board which have the least possible (guessable) values in them. So instead of recursing from a square which has [1,2,4,6] as possible guessses, focus on starting from a square which has only two possible if that is available on the board. It makes it a bit tricky to code the backtracking but it seems in principle it should prune the search tree quite a bit.
Of course the purpose of this video was not to present an efficient algorithm, but to explain recursion/backtracking on an example. I doubt an efficient algorithm would use recursion or backtracking... I guess it would solve the constraint problem. But on topic: The tricky part in the code comes after you invoke solve()... when you return ,where are you in the tree of all possibilities? What to do next? That's what makes this video so valuable. Thanks a lot....
@@QContinuuum I'm not disagreeing in principle but I just wanted to point it out for benefit of all viewers. I reckon that DFS brute force with backtrack would still be effective for regular sudokus. Assuming properly formed sudokus with 17 or more clues (with singular answer). There are allegedly some other type of methods like simulated annnealing which use random guessing somehow to solve the sudoku fast. But in principle DFS brute force with backtracking will always succeed in solving sudoku given enough time. In terms of other known sudoku algorithms there is dancing links/algorithm X by Donald Knuth, but I'm not too familiar with its time complexity or how efficient it supposedly is.
I didn't understand what for the line after the call for the recursion func?
the line grid[y][x] = 0?
because, if i call the function, it will start over, and if i finished, i will not enter the if statement..
as i understand it, it goes like this:
find a number that is possible in the next empty position (on the first call, this will be the first empty position).
now taking the position as filled with that chosen number, again find a number that is possible in the next empty position. repeat this process until all positions are filled.
if we can’t find a possible number for a given position we made a mistake somewhere and the lowest recursive call returns.
this return within the lowest recursive call will lead the next higher call to reset its position as empty and loop to the next value between 1 and 9, repeating the process.
if the loop can’t find a possible value for the empty position, it too will return, leading the next higher call to reset its position as empty. repeat for each layer.
It's fine as a method of teaching Python, which is of course what is for. Brute force type solutions are pretty inelegant though. There are lots of algorithms that can be applied to solve Sukudu logically. The normal ones apply ever more complex ones in sequence in the same way as one does solving Sukudu manually.
I once wrote one that (I think) was hugely elegant in that each square was its own object and monitored every other square (and combination of squares) that could affect it, changing its own "opinion" of what it could be as other squares did the same. It couldn't solve hugely complex puzzles (which brute force aways will) but it was fun to watch it "think" and it was very fast.
Beautiful solution. Bravo!
Hi! Does anyone knows why if I end the function with return(A) (I'm not using global) instead of using print(A), it delivers None? Also, why "input("More")" on the function makes it to generate other solutions? Thanks!
To your second question:
It will run through the function, and then back to the previous recursion, set that cell to 0, keep finding if another number is possible.
If there is another solution eventually, then print and input(“More?”)
If not, return
He makes coding on light mode less weird
Would it be quicker for each node (square) to know what it cant be and then auto solve itself if it has enough data? I believe this will be especially better when there are mostly completed puzzles instead of cycling through randomly it knows easy notes to complete and will help with completing future nodes.
Interesting video but really needed the white board and working though an example sudoku, (just a couple of numbers) to show the recursion and backtrack. The X and Y variables are local to their own solve() function which means that when you return out of a solve() you are in the last square that you previously filled.
That puzzle is called The Setting Sun, its on my list for VB
When I originally wrote one of these, I looped through and filled in values that I knew had to be correct, because I was counting the numbers in rows, columns, and boxes and if there was only one solution, put it in. It ended up solving about 90~99% of sudoku puzzles on its own, with no further complicated logic. Just counting up what it couldn’t be, and if there is only one could be left, it knew what had to go there.
This solution is pretty interesting and elegant in that it does not actually need any special constraint logic to do the solving, which is neat, but I think filling in the table with “MUST BE” values first might speed up the amount of backtracking necessary. But then, as mentioned, this way solves nearly all the puzzles I came across. But at least this would be an interesting combination solver, that only deferred this backtracking logic to get around complicated constraint heuristics.
puellanivis definitely a way to optimise the solving progess but i don’t think it’s necessary here. We don’t have so many combinations that the backtracking would need to go through. Any modern cpu can solve it in fractions of a second or whatever. However if we look at chess we definitely need more than plain backtracking and with example of Go to even be applicable in real time we need deep learning
1) why is professor's runtime significantly shorter than mine? Did his buffer save the answer? He got output almost instantly
2) is there a "smarter" way to solve this w/o implementing a O(N^2) / nested-loop method? Thank you
This kind of sudoku solver is sort of my version of a Hello world program. I write it in every (or at least most) programming language I learn since it’s nice practice that covers the simple syntax and passing by reference (note my disdain for the global variable used here).
So far done in C++, Python, Rust and I even used it for a test assembly program for an assembler/emulator we made in a system software course.
Rest assured, your disdain has been noted.
So this is what Steve Wozniak do after leaving Apple
I spent a week on a sudoku solver then this video comes along and makes my code look like it was written by a 5y year old :(
Edit: my program does solve the problem within a similar amount of time so at least its not too bad.
Keep going though?
That's amazing! You got to solve it for yourself, spoiler-free :)
And then you got to see how someone else did it, so you could compare notes!
Did you solve it the same way?
Don't worry about your code looking like a kid wrote it. It will improve if you keep at it. You never really notice it though, before you go back and look at some code you wrote a couple of years ago. Fun!
So make sure you put copy of your code in its current state in a durable place. You may thank yourself in the future :)
@@chixulub The main difference in our programs is that I generated an entire possible solution filling in all the squares and then went through it row/column/3x3 and then tossed out the result if an inconsistency was found. rather than his approach of going through each square one by one. I think its called breadth first vs. depth first.
I also tried to implement some logic that uses human tricks to solve sudokus like the hidden/naked pairs trick, but its kind of difficult to program it efficiently. I got stuck trying to avoid quadruple for loops with tons of if statements. Maybe I'll go back to it later.
for the last point I've been using github for offsite storage. Not really the sites intended use since no one will ever see or use the code, but its a really nice place to keep things organized.
This is elegantly simple and effectively illustrates backtracking. However, it is still a brute-force solution and back in my day, when computers were orders of magnitude slower, we would have lost marks for a solution like this. Glad he reflected on this near the end.
Same over here - I completely thought through the rules of the game and had an intermediate step before the recursion which would solve the field according to those rules. Which makes it a lot more complicated.
You guys should include a link to the jupyter notebook in the description of videos like this.
One of ze best vizeos!
Further to clearify the input('More?') thing:
When he prints the matrix we just end one of those recursion steps. The others a still to come.
If we get a solution let's say in the n-th step we still have not evaluated N-n steps. The input('More?') just halts the process till someone presses enter. Then it is possible that none or more times in the last N-n steps we get further solutions.
So the answers is, we do not initiate something when pressing 'Enter' to the question 'More?', we just proceed.
Realizing the topic is just back-tracking here, this algorithm is inefficient for difficult puzzles. I found it more efficient when I wrote similar code to work the most obvious cells first (the ones with fewer potential solutions). I greatly reduced the time to solve the most complicated puzzles.
On my smart phone I play on the EXPERT mode, 1-3 games just before I go to sleep. It usually takes me 10-12 minutes to complete a game without any errors.
I totally agree with you. That what came in my mind first. I thought it was not the perfect one for expert sudoku puzzles, because it will take more time .
From the notes on his whiteboard it seems he is taking the MIT Programming with Categories course :)))
Are you kidding me? Altenkirch does research on Homotopy Type Theory, he doesn't need to take any course. He eats Category Theory for breakfast.
In any case he'd be giving the course...
I programmed my own sudoku solver last week, was fun.
Pure brute force 🙂 never stops to amaze me, how far brute force can get you.
I'm dying thinking about the time complexity... What's the lowest it can be here?
How does adding the "input()" function at the end give you a different result. Wouldn't the algorithm always find the same solution? I don't get it. Someone help please
@8:38
say when solve() was filling the grid cell at position (0,6)i.e 1st row and 7th col.
solve() filled the 1, then recursed and filled all of the empty cells in the grid.
printing happens after last cell is processed (8,8) i.e if it is empty then it is filled.
and here input() function has paused the execution of the program and waits for the user to press enter.
when user presses enter. it starts backtracking...
It back-tracks and reaches to recursion call which filled 1at (0,6) position.
it removes 1 from the cell and tries with other numbers.
here when it tries with 9 it got one more solution...
The input function is just there to give the user a pause between the possible grids. Imagine if a puzzle had 16 possible solutions. If the program printed them all out without that input function inbetween them then you would need to scroll up to see each of the solutions. The input function lets you see the solutions one at a time.
Thank you for that demo
To make it solve more like a human, you could get it to list the number of "possible" numbers in each currently blank space, and to try the possibilities of each of the lowest.
You could then assign a difficulty to the problem, by asking it what the largest number of possibles was at any step, and the maximum number of steps it had to go through to check the correct number. I'd also imagine this is a little more computationally efficient, since it works on the "easier" numbers first. I don't think it'd be hard to get it to keep working from concurrent steps too. My preference here would be to write it in Haskell without for-loops :)