Python Sudoku Solver - Computerphile
Vložit
- čas přidán 11. 02. 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.
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
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'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.
Does he have his own CZcams channel? I really enjoy the way he talks about problems. Makes them seem much easier than they really are.
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.
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.
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.
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
The time when Targaryens not using Dragons anymore, They are using Python..
6:45 that keyboard has seen war
Space bar certainly did
what about his whiteboard
shits scarred for life
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 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 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!
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 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.
1:12 - "vot do vee do?"
SILENCE! VEE VIL AASK D'KVESHCHUNS!
Scooby dooby doo
haha
He has so much more enthusiasm for computer science than 90% of my professors in the department. Lol.
Wow. I really want to learn more under him. Beautifully explained everything. ❤️
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
Great teacher, fun and entertaining for super tough concepts. Such an elegant solution too.
Love yt recommendations. I have been watching for 1 min and was subscribed already.
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.
a function that calls itself? THIS CHANGES EVERYTHING
Simple and elegant solution. I love it!
_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.
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.
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
This video helped me a lot understand a different way of using recursion
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.
I built a sudoku solver in PowerShell, python and C++. But it couldn't solve the harder problems. Awesome video.
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.
Beautiful solution. Bravo!
Wow, it's not teaching, it's gossiping, motivating, soothing, relaxing.
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.
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 :)
This guy is off the hook!
Spectacular!
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 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
4:02 smooth af
This beautifull man just made me understand backtracking... Thank you!
Woah, there has to be more such videos!
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.
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
I'm hobby Python programer and Sudoku solver was my first "real" project fee months ago. I really love Python!!! :)
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'm so intimidated by the ease he's talking about those hellish loops.
This is the kind of guy who teaches by doing
My favorite kind of teacher
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.
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 cooking animation was amazing ... and made me laugh^^
Haha yes
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 just recently learned python, this video was pretty fun
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 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 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.
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.
Thank you for that demo
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!
LEGEND!
10 minutes on this and was able to understand backtracking...
Dude ur profile pic made me throw my phone against the wall
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!
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.
"Once you understand it, it's quite simple"....That is the beauty of computer science
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
I programmed my own sudoku solver last week, was fun.
This amazing please do more videos in Python
I really like the, "and my challenge to you is to write...".
"The proof is left as an exercise to the reader"
hay everyone 2d list output easy mode -> print(*listvar, sep='
') !!!best thing EVER changed my life
Another one
from pprint import pprint
pprint (grid)
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?
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 😄
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
So this is what Steve Wozniak do after leaving Apple
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.
The code is complete and perfect
This guy wants to save me 15% on my car insurance.
He makes coding on light mode less weird
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?
Cracking stuff. I think I understand what's happening here. I'm going to test it out!
I dig this speaker. Pretty chill one. And interesting topics too :)
Please do a follow up on Knuth's dancing links algo.
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!
awesome! pls upload more videos like this!
The homework is to create a python script using that solver and "back tracking" to generate new "1 possibility" sudoku grids.
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
I love his videos ♥️
Love this man
REALLY be wanting to fix that phone cord.
Glad I'm not the only one. 👍
Ur so funny guy
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.
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.
Grüße und ein Danke an dich, Thorsten :)
7:31 Italy Map 😂
Lol
I don't get it
@@iuppiterzeus9663 just look the map of italy and you will understand
Not really. Where's the upper part.
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.
love this guy
good explanation thank you so much
Why has no one mentioned that the Scientist from Independence Day is now doing coding videos on Sudoku?
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
Really helpful. Thanks!
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.