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.
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.
@@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.
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.
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.
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.
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.
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!
@@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.
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.
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.
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.
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.
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.
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.
in python, matrixs works the other way around. when you assing a X value to smth, you get it in a vertical line, not in a horizontal line. python has some tricks x)
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.
Got to say, this wasn't very well taught here. I didn't have a pre-existing understanding of recursion, and by the end of the video I had to pause on the function code and reverse engineer it to come to understanding. (In fact, I'm still looking back at it as I write this comment to make sure I get it) If the goal was to inspire study: okay. But if the goal was to teach: I don't think that happened. Anyone else who was left wanting, I'll try my hand: When there's a 0 in the list and the possible() test returns true, that 'possible' value is shoved in where the zero was, and the entire cycle starts again with this nested call to solve(). But now /that/ space in the grid is no longer a zero, so the first unknown value that this new call to solve() will find and try to populate is for the next zero in the list. The whole loop can have as many successful populations as it can get, all the way to the very last zero... But if that last zero can't be ANY of the possible values, then these nested calls to solve() start to unravel. If none of the values are possible in the current field that solve() is trying to solve for, then we return to the previous solve() call -- the one that was operating on the zero before the test that just failed. Having just fallen back out of it's call to solve(), the next line it processes is to set the value it had previously populated back to a zero. It then carries on trying the remaining possibilities in the range() for that empty space -- picking up from wherever it had left off. So if it had tried a 3, found success, called solve... but then solve() ultimately failed on some other space and return'd all the way back to it, it'll carry on trying a 4, then a 5, and so on. If 4-9 all fail, this call to solve() returns back to the preceding call -- aka: the previous unknown value. If it finds another possible match in the remaining range (4-9), it populates it and calls to solve() again. So it ends up moving forward and back, and forward and back, until it can get a successful match for the very last zero / the very last call to solve(). On that last call to solve(), all the numbers in the list will now be populated with non-zero values. So on this call, solve() will never try any possibles, and instead it will just cycle through all its for loops, and end by printing the grid() and asking for "More?" input. When you hit enter to tell it to continue, the entire umpteen-deep calls to solve() will all pick up from where they left off. The last zero will try any remaining possible values; if none found, return to the last zero; try remaining values; if found, call solve() again; etc. In this way, literally every possibility of every value ends up being checked, without wasting a single iteration repeating something that's already been tried. And if there's multiple possible solutions, all of them will be printed. So, when you hit Enter on the "More?" request... even though you may not get any other printed results, the program carries on testing every single possibility it hadn't already tried. -- The fact that this video was made, got me to understand recursion by studying this sample function on my own, in the absence of a through explanation. And often that's more valuable to a student in learning and retention. But the video didn't REALLY explain what was going on, and why, to the unfamiliar like I've just tried to here. And that means there's a barrier of entry placed on a potential student. They have to /want/ to understand enough to teach themselves. This is just my opinion, but I think computerphile should aim to use this space to teach, rather than to inspire learning.
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.
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 implemented this in C++ and found out that the easier sudoku problems are solved within seconds. But seeing that my code could solve sudoku in a matter of seconds, I became confident and googled the hardest sudoku problem and gave that for my computer to solve. It took my computer 55 minutes to solve that problem and I quickly became reminded of the limitations of my code. PS: My approach is a bit different from professor Thorsten's but it is backtracking nonetheless. I built that before watching this. My processor is an Intel Celeron R and I have 4 GB of memory, if any one is wondering.
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.
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
Am I the only viewer who can't get enough of the Professor's videos but quickly gets bored or irritated at other Computerphile presenters - and stops watching them? Why? Because the Professor is the antidote to the computer science lectures I attended in College where the lecturers took themselves and/or the subject matter too seriously.
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.
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
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.
@@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.
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))
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)
@@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.
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
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.
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?
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.
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
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,
At around 6:49, the line grid[y][x] = 0 looks to me like it's unreachable, because it would just start back all the way at the top of solve again, I also don't quite understand, because to me it seems like it should eventually get stuck where you've gotten yourself into a situation where nothing is possible to fill the 0 with, so it would just get stuck.
If there are no more empty spaces left on the grid (the solution is COMPLETE), then the first if function is not entered at all - this block is skipped over, and the print statement at the end executes. Assume that we do not have the input prompt line at the end. Once the solution is complete and the print statement has been executed, this is the latest element complete. We now go back through to the previous element and the line grid[y][x] = 0 is executed and other things happen - this is AFTER we have already printed the solution, so it has no effect on the output we see. Your thinking in your comment only applies within the CURRENT element of the stack. Imagine that the program has been running and halfway it hits a square where if possible(y,x,n) is FALSE (i.e. this cannot be the correct solution). What happens? The CURRENT element execution will end, but remember it will still need to go to the PREVIOUS element (the previous square it entered a value into). Once we are back in the previous element ONLY THEN does grid[y][x] = 0 execute. This will reset this square to 0 and iterate the inner for loop again, trying a different value. If NONE of the values work, then the square [y][x] stays equal to 0, the single return statement is hit, the current element ends and it tries the same thing with the previous square (in the previous element) again. If you start thinking about the running of the program it will get very complicated very quickly. You can also see that this is inefficient and would take a long time to compute, but as it is only a 9x9 sudoku solver then it does not matter in the grand scheme of things.
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.
It was fun to do the Klotski challenge, but it's more efficient to just brute force Klotski. It took me less than half a second to find all 25955 possible positions (counting every similar block as equal). The shortest solution has 116 single steps and every configuration can be reached in 137 steps. With recursion and backtracking, I got my solution in 2 seconds, but it required 3873 single steps (or 20928 steps when I forgot counting every similar block as equal).
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 .
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 have written Sudoku solver in CPP in my 2 year of university ... more than 10 years ago. And it it solve Sudoku in less than second on Pentium 3 @1.2Ghz notebook. I used brute force with recursion and 3 simple rules.
Backtracking is quite a complicated algorithm, so while Sudoku is fun it's better if you start with generating all possible combinations or permutations of a string. Once you get that, then Sudoko becomes actually really easy, because you only have 9 possible options.
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.
I use backtracking in C to find out all solutions. Each unfilled cell is a set created by the intersection sets of possible numbers in that column, in that row, and in that sub square. This can highly reduce the possibility of choice of numbers.
solve() didn't return anything for me, I have tried to write the same program with one of the puzzle I've found online. But this is not working for me. Can anybody plese help me solve this problem?
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.
far more efficient to find all possibles, fill in any square with only one possible number. Do that as much as you can, and if there are no one-possibles, then do this guessing algorithm.
Efficient? I doubt it. Coding time far exceeds running time, even if he didn’t take us through line by line. After a few million sudoku you might draw even...
You could eliminate candidates using clever tricks too, such as one of my favs (because its cheating) is to use the meta-knowledge that you fed it a puzzle that only had one solution to eliminate any candidates that results in a "unique rectangle".
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.
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.
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.
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
I put the exact same code into Python so I could mess around with it but it doesn't seem to work ... it is calling the function recursively (if I put a print statement as the first line after def it will print many, many times) but it never seems to reach the print(np.matrix(grid)) statement at the very end. Also, why does the grid variable not seem to get changed by the solve() function? If grid is global, shouldn't it be different after solve() runs? If I say print(np.matrix(grid)) after running solve I just get the original.
Its hard to understand with his accent, but he has a few DIY functions he built and added to his library & to @Alacritas' point, he's using Jupyter. He mentions this whole Soduku solver is a section in his book. Look him up and see if you can pick it up & walk through the process. Thats what I'm about to do.
@Theo van der Sluijs For me it was actually just because I inputted the original matrix incorrectly, seems that it was unsolvable. After I fixed that it worked as it should. I could send you the Jupyter notebook if you're really curious!
@@freshmilk980 Hey could you give link to this notebook, that be great. I tried doing u it but it didn't work I tried copying the code and it didn't work either.
Well, i'm having the same issue, but it is obviously clearing the entire array on its way back from the recursion,, everything below after the recursive solve() call gets triggers when the method bubbles back down, and therefore empties the array that it just solved, therefore there should be some kind of a conditional there that should decide if it actually should be emptied or if it should not be emptied, i haven't figured it out myself yet..
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.
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.
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.
I don't think I'd be able to come up with this solution. My first CS professor instilled an urge to always write efficient code, so I'd never even consider trying this approach lol
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 :)
The intuition (at least for me) is that the complexity of this solution is going to be off the scale even for a 9x9 problem, so it's quite surprising that it solves the puzzles quite successfully.
I started to learn python 3 days ago and I just finished a to create a sudoku solver yesterday, with just some basic loop and conditions. Using no import.
@@dylan-j-gerrits If you are a somewhat experienced software dev, which it sounds like you are, then moving from language to language is merely a change in syntax and operation. Object oriented principles don't care about your language as long as OOP is natively supported, neither does the concept of recursion for that matter, as long as your language supports nested method calls. So yeah, I believe the OP was referring to a beginner software developer rather than just python haha.
@@FreedomOfTħought : I am a beginner, not only in Python but overall. I've started to learn just a month ago, more or less, and doing a sudoku solver was the first thing I've created.
Took me a few minutes to really figure out what that code is doing. Normally with recursion, you'll do something like this if baseCase: return something else: change something call recursive function his code is run through a bunch of loops if the problem is not solved (ie. one of the values is 0) modify global variable with new guess recursively call the function revert the state of the global variable ( note: this works because the recursive calls have also reverted) return (note: this skips the later part of code that prints the solution else (note: he doesn't write else here, it just works - because we don't hit return in the previous code) print the solution It is cool in how concise the code is though. Edited: removed my wrong analysis.
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.
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
I remember he taught us a language called Coq - The amount of jokes he made was ridiculous lol
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
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.
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.
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.
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.
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.
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.
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.
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.
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
aaaaa the spaces before the colons
And this nested loops...
It hurts
@@OrgBrent And not having a space after commas. Not very pythonic
@@ekrem_dincel I get the spaces thing, but how else would you write the nested loops?
@@rudyorre you should find a better algorithm if possible.
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
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.
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.
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
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.
1:12 - "vot do vee do?"
SILENCE! VEE VIL AASK D'KVESHCHUNS!
Scooby dooby doo
haha
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!
He has so much more enthusiasm for computer science than 90% of my professors in the department. Lol.
6:45 that keyboard has seen war
Space bar certainly did
what about his whiteboard
shits scarred for life
Wow, it's not teaching, it's gossiping, motivating, soothing, relaxing.
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 built a sudoku solver in PowerShell, python and C++. But it couldn't solve the harder problems. Awesome video.
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.
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.
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.
3:08, shouldn't it be x = 2, y = 0?
in python, matrixs works the other way around. when you assing a X value to smth, you get it in a vertical line, not in a horizontal line. python has some tricks x)
@@FranciscoPereira-gc5xu in any grid, an x gives you a vertical line. OP is correct.
he used y to represents columns and x to represent rows. you could do vice versa. it doesn't really matter
y=2 and x=2 is correct, the grid is mislabeled.
The function is actually def possible (y,x,n), that's why they seem reversed
a function that calls itself? THIS CHANGES EVERYTHING
4:02 smooth af
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.
Got to say, this wasn't very well taught here. I didn't have a pre-existing understanding of recursion, and by the end of the video I had to pause on the function code and reverse engineer it to come to understanding. (In fact, I'm still looking back at it as I write this comment to make sure I get it)
If the goal was to inspire study: okay. But if the goal was to teach: I don't think that happened.
Anyone else who was left wanting, I'll try my hand: When there's a 0 in the list and the possible() test returns true, that 'possible' value is shoved in where the zero was, and the entire cycle starts again with this nested call to solve(). But now /that/ space in the grid is no longer a zero, so the first unknown value that this new call to solve() will find and try to populate is for the next zero in the list. The whole loop can have as many successful populations as it can get, all the way to the very last zero... But if that last zero can't be ANY of the possible values, then these nested calls to solve() start to unravel.
If none of the values are possible in the current field that solve() is trying to solve for, then we return to the previous solve() call -- the one that was operating on the zero before the test that just failed. Having just fallen back out of it's call to solve(), the next line it processes is to set the value it had previously populated back to a zero. It then carries on trying the remaining possibilities in the range() for that empty space -- picking up from wherever it had left off. So if it had tried a 3, found success, called solve... but then solve() ultimately failed on some other space and return'd all the way back to it, it'll carry on trying a 4, then a 5, and so on.
If 4-9 all fail, this call to solve() returns back to the preceding call -- aka: the previous unknown value. If it finds another possible match in the remaining range (4-9), it populates it and calls to solve() again. So it ends up moving forward and back, and forward and back, until it can get a successful match for the very last zero / the very last call to solve().
On that last call to solve(), all the numbers in the list will now be populated with non-zero values. So on this call, solve() will never try any possibles, and instead it will just cycle through all its for loops, and end by printing the grid() and asking for "More?" input.
When you hit enter to tell it to continue, the entire umpteen-deep calls to solve() will all pick up from where they left off. The last zero will try any remaining possible values; if none found, return to the last zero; try remaining values; if found, call solve() again; etc.
In this way, literally every possibility of every value ends up being checked, without wasting a single iteration repeating something that's already been tried. And if there's multiple possible solutions, all of them will be printed. So, when you hit Enter on the "More?" request... even though you may not get any other printed results, the program carries on testing every single possibility it hadn't already tried.
--
The fact that this video was made, got me to understand recursion by studying this sample function on my own, in the absence of a through explanation. And often that's more valuable to a student in learning and retention. But the video didn't REALLY explain what was going on, and why, to the unfamiliar like I've just tried to here. And that means there's a barrier of entry placed on a potential student. They have to /want/ to understand enough to teach themselves. This is just my opinion, but I think computerphile should aim to use this space to teach, rather than to inspire learning.
Thank you; this was the elaboration I was looking for.
Thanks a lot mate...really helpful!
Thank you! This was very helpful to me.
Thank you, I got it now :)
Thanks. I still don't think that I entirely comprehend the idea, but it's definitely starting to make more sense now.
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.
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 implemented this in C++ and found out that the easier sudoku problems are solved within seconds. But seeing that my code could solve sudoku in a matter of seconds, I became confident and googled the hardest sudoku problem and gave that for my computer to solve. It took my computer 55 minutes to solve that problem and I quickly became reminded of the limitations of my code. PS: My approach is a bit different from professor Thorsten's but it is backtracking nonetheless. I built that before watching this. My processor is an Intel Celeron R and I have 4 GB of memory, if any one is wondering.
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.
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?
Am I the only viewer who can't get enough of the Professor's videos but quickly gets bored or irritated at other Computerphile presenters - and stops watching them? Why? Because the Professor is the antidote to the computer science lectures I attended in College where the lecturers took themselves and/or the subject matter too seriously.
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.
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 😄
Wow. I really want to learn more under him. Beautifully explained everything. ❤️
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.
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.
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
_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.
"Once you understand it, it's quite simple"....That is the beauty of computer science
This is the kind of guy who teaches by doing
My favorite kind of teacher
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
i'm so intimidated by the ease he's talking about those hellish loops.
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!
I really like the, "and my challenge to you is to write...".
"The proof is left as an exercise to the reader"
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.
LEGEND!
10 minutes on this and was able to understand backtracking...
Dude ur profile pic made me throw my phone against the wall
Love yt recommendations. I have been watching for 1 min and was subscribed already.
The cooking animation was amazing ... and made me laugh^^
Haha yes
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 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.
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
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,
The homework is to create a python script using that solver and "back tracking" to generate new "1 possibility" sudoku grids.
I'm hobby Python programer and Sudoku solver was my first "real" project fee months ago. I really love Python!!! :)
So this is what Steve Wozniak do after leaving Apple
At around 6:49, the line grid[y][x] = 0 looks to me like it's unreachable, because it would just start back all the way at the top of solve again, I also don't quite understand, because to me it seems like it should eventually get stuck where you've gotten yourself into a situation where nothing is possible to fill the 0 with, so it would just get stuck.
i am confused there too. Can you reply my message if you find any solutions?
If there are no more empty spaces left on the grid (the solution is COMPLETE), then the first if function is not entered at all - this block is skipped over, and the print statement at the end executes. Assume that we do not have the input prompt line at the end. Once the solution is complete and the print statement has been executed, this is the latest element complete. We now go back through to the previous element and the line grid[y][x] = 0 is executed and other things happen - this is AFTER we have already printed the solution, so it has no effect on the output we see.
Your thinking in your comment only applies within the CURRENT element of the stack.
Imagine that the program has been running and halfway it hits a square where if possible(y,x,n) is FALSE (i.e. this cannot be the correct solution). What happens? The CURRENT element execution will end, but remember it will still need to go to the PREVIOUS element (the previous square it entered a value into). Once we are back in the previous element ONLY THEN does grid[y][x] = 0 execute. This will reset this square to 0 and iterate the inner for loop again, trying a different value. If NONE of the values work, then the square [y][x] stays equal to 0, the single return statement is hit, the current element ends and it tries the same thing with the previous square (in the previous element) again.
If you start thinking about the running of the program it will get very complicated very quickly. You can also see that this is inefficient and would take a long time to compute, but as it is only a 9x9 sudoku solver then it does not matter in the grand scheme of things.
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
REALLY be wanting to fix that phone cord.
Glad I'm not the only one. 👍
Ur so funny guy
Please do a follow up on Knuth's dancing links algo.
It was fun to do the Klotski challenge, but it's more efficient to just brute force Klotski. It took me less than half a second to find all 25955 possible positions (counting every similar block as equal). The shortest solution has 116 single steps and every configuration can be reached in 137 steps.
With recursion and backtracking, I got my solution in 2 seconds, but it required 3873 single steps (or 20928 steps when I forgot counting every similar block as equal).
Hey, I just did the challange aswell and found that every configuration can be reached in 167 steps, instead of 137
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 .
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 dig this speaker. Pretty chill one. And interesting topics too :)
I have written Sudoku solver in CPP in my 2 year of university ... more than 10 years ago. And it it solve Sudoku in less than second on Pentium 3 @1.2Ghz notebook. I used brute force with recursion and 3 simple rules.
I still don't quite understand the reason for "grid[y][x] = 0" at 6:14 if anyone could explain, it would be much appreciated.
Backtracking is quite a complicated algorithm, so while Sudoku is fun it's better if you start with generating all possible combinations or permutations of a string. Once you get that, then Sudoko becomes actually really easy, because you only have 9 possible options.
I programmed my own sudoku solver last week, was fun.
He makes coding on light mode less weird
Great teacher, fun and entertaining for super tough concepts. Such an elegant solution too.
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.
I use backtracking in C to find out all solutions. Each unfilled cell is a set created by the intersection sets of possible numbers in that column, in that row, and in that sub square. This can highly reduce the possibility of choice of numbers.
solve() didn't return anything for me, I have tried to write the same program with one of the puzzle I've found online. But this is not working for me. Can anybody plese help me solve this problem?
same
It’s not meant to do you mean it doesn’t print anything??
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.
far more efficient to find all possibles, fill in any square with only one possible number. Do that as much as you can, and if there are no one-possibles, then do this guessing algorithm.
Yeah, but with modern computers that's negligible on a 9x9 grid.
Efficient? I doubt it. Coding time far exceeds running time, even if he didn’t take us through line by line. After a few million sudoku you might draw even...
You could eliminate candidates using clever tricks too, such as one of my favs (because its cheating) is to use the meta-knowledge that you fed it a puzzle that only had one solution to eliminate any candidates that results in a "unique rectangle".
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.
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
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
I put the exact same code into Python so I could mess around with it but it doesn't seem to work ... it is calling the function recursively (if I put a print statement as the first line after def it will print many, many times) but it never seems to reach the print(np.matrix(grid)) statement at the very end.
Also, why does the grid variable not seem to get changed by the solve() function? If grid is global, shouldn't it be different after solve() runs? If I say print(np.matrix(grid)) after running solve I just get the original.
I haven't checked, but maybe because it's all made in Jupyter and not run in the normal Python terminal. Did you try it in Jupyter?
Its hard to understand with his accent, but he has a few DIY functions he built and added to his library & to @Alacritas' point, he's using Jupyter. He mentions this whole Soduku solver is a section in his book. Look him up and see if you can pick it up & walk through the process. Thats what I'm about to do.
@Theo van der Sluijs For me it was actually just because I inputted the original matrix incorrectly, seems that it was unsolvable. After I fixed that it worked as it should. I could send you the Jupyter notebook if you're really curious!
@@freshmilk980 Hey could you give link to this notebook, that be great. I tried doing u it but it didn't work I tried copying the code and it didn't work either.
Well, i'm having the same issue, but it is obviously clearing the entire array on its way back from the recursion,, everything below after the recursive solve() call gets triggers when the method bubbles back down, and therefore empties the array that it just solved, therefore there should be some kind of a conditional there that should decide if it actually should be emptied or if it should not be emptied, i haven't figured it out myself yet..
Pure brute force 🙂 never stops to amaze me, how far brute force can get you.
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.
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.
I don't think I'd be able to come up with this solution. My first CS professor instilled an urge to always write efficient code, so I'd never even consider trying this approach lol
what? why not. what would you have tried?
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 :)
This guy wants to save me 15% on my car insurance.
goated video. I used to hate recursion in general but I appreciated the caliber of backtracking because of this video
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...
The intuition (at least for me) is that the complexity of this solution is going to be off the scale even for a 9x9 problem, so it's quite surprising that it solves the puzzles quite successfully.
Instead of importing numpy, how about :
for row in grid:
print(row)
" ".join(row)
Otherwise you'd print "[1, 2, 0, 3, ...]"
Or just use pprint
????
For r, row in enumerate(grid):
For c, cell in enumerate(row):
Print(cell)
@@rensaito9009 Why are you wasting CPU-cycles for `enumerate`?
use print("
".join(" ".join(str(x) for x in y) for y in grid)) for efficiency, printing many lines wastes more time than joining them beforehand
This video helped me a lot understand a different way of using recursion
Python Beginner: print("Hello World!")
Beginner: AYE
Thorsten: Let's make a Python Sudoku Solver, not a problem
Beginner: ...
I started to learn python 3 days ago and I just finished a to create a sudoku solver yesterday, with just some basic loop and conditions.
Using no import.
I can fluently program in python and starting to move into python but i made that joke because i have a friend who only knows the print function
@@dylan-j-gerrits If you are a somewhat experienced software dev, which it sounds like you are, then moving from language to language is merely a change in syntax and operation. Object oriented principles don't care about your language as long as OOP is natively supported, neither does the concept of recursion for that matter, as long as your language supports nested method calls.
So yeah, I believe the OP was referring to a beginner software developer rather than just python haha.
@@FreedomOfTħought : I am a beginner, not only in Python but overall. I've started to learn just a month ago, more or less, and doing a sudoku solver was the first thing I've created.
@@dylan-j-gerrits then you're a prodigy I guess. i have 4 years experience and yet can't do this sh*t
Took me a few minutes to really figure out what that code is doing. Normally with recursion, you'll do something like this
if baseCase:
return something
else:
change something
call recursive function
his code is
run through a bunch of loops
if the problem is not solved (ie. one of the values is 0)
modify global variable with new guess
recursively call the function
revert the state of the global variable ( note: this works because the recursive calls have also reverted)
return (note: this skips the later part of code that prints the solution
else (note: he doesn't write else here, it just works - because we don't hit return in the previous code)
print the solution
It is cool in how concise the code is though. Edited: removed my wrong analysis.
There's not a lot of industry applications for a Sudoku Solver. Is that why you say "Most industry would not allow it"?
@@lacascadaobregon Nope I was just wrong in my original comment. Using these type of passed through variables is totally fine.
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.