Sudoku is a great way to pass some time, especially on a long flight. However, we don’t think the airlines will let [Sanahm] board with his sudoku-solving robot. The basic machine looks like a 2D plotter made with aluminum extrusion, with the addition of a Raspberry Pi and a camera. The machine can read a sudoku puzzle, solve it, and then fill in the puzzle with a pen. Unlike humans, it should never need to erase its work.
The software uses OpenCV to process the camera data, find the grid, and the cells provided by the puzzle. TensorFlow recognizes the numbers. From there, it is all just math to solve the puzzle. Once solved, the plotter part of the robot takes over and fills in the blanks. After all that, this seems like the easy part.
There’s no video, but the original post has an image of the machine doing its thing. The repository has all the information about the electronics, mechanical construction, and the firmware.
We remember a similar project done with Lego Mindstorms. If you need help getting OpenCV on the Raspberry Pi, we’ve talked about that before, too.
Oh no! The robot is committing sudoku!
It would be super cool to watch it in the order that it figures things out, instead of solving the whole puzzle and then filling them all in.
That was exactly my first thought. It would be much more interesting.
This is pretty cool. I have an original Houston Instruments Hi-Plot (X and Y steppers and a pen lift solenoid in a nice case – letter sized) sitting here and this is a perfect application.
By the way, in my lackadaisical campaign to put the people back in METS, I have to bring up “Sudoku are digital puzzles that computers can solve automatically because they obey some simple mathematical rules.” I mean aside from it saying that computers obey simple rules where I think from context you mean Sudoku obeys simple rules. Someone developed the algorithm and wrote the program. I would think that to hackers, that process of creating the solution finder is more interesting than the mechanization.
On that line, isn’t it fair to say that the person who wrote the program has solved all possible Sudoku puzzles? Provided there is a proof that the program is correct?
lol Just do it!
A Sudoku solving program is one of the most fun code to write as it has a real DUH moment.
My first code more or less emulated the way I personally do the puzzle and it was very wordy and tedious.
For me the DUH moment was when I realized that the 3 rules of positioning can be converted to rules of symmetry and translocation just like the Rubik cube. Once you realize that you can start with a simple solved puzzle and map the array to the known elements of the actual puzzle using the rules above and in doing so you end up re-mapping the unknown elements as well.
For extra points you can make the whole code into one single recursive function.
Or you could just write a brute force algorithm that just blindly tries all combinations, applies the rules, and breaks out when they pass.
The approach you outlined is elegant, but only works on high-quality input data sets (such as published puzzles), which have exactly one solution.
If the input is incomplete (under-constrained, with multiple solutions) this approach would seem to only find one of them.
Consider the puzzle fragment below, where only the top row, and top left grid are populated as shown:.
123456789
456
789
This (under-constrained) partial board has thousands of solutions.
I wrote a recursive Sudoku solving function that works in two phases.
The first phase applies simple deduction to determine which blank cells have only one possible value, after eliminating the other values already occurring in the regions (row, column, 3×3 grid) that include the cell.
This first phase is enough to solve simpler puzzles.
The second phase uses a brute force approach. When all remaining blank cells have multiple possible candidate values, save the current board as a “forking” point, pick a cell with the minimum number of candidate choices, and tentatively assign the next candidate value to the cell . Then (recursively) call Solve again, in a depth-first traversal of the tree of choices. A tree branch terminates when either a solution is reached, or it is impossible to chose a digit without duplication in a row, column, or grid. If digit duplication is unavoidable, it means that an earlier forking choice (or the initial puzzle configuration itself) was incorrect.
Consider this –
456123789
123
789
If I translate 123 for 456 then it is the same as your example.
In fact you can transpose and translate to create every permutation from one solution. ie – Like the Rubik cube there is only one solution from which every other state is derived. However with this puzzle there is also transposition which is like pealing all the stickers off a Rubik cube and then refitting them with only one color per side. Technically the cube is then different but by the symmetry of it’s logic it is still the same.
When I coded for the above case, the code worked in parallel fashion even though executing sequentially due to being processor based (VHDL would be fully parallel). Because of it’s parallel nature there is no “first” solution so in the case of an under constrained matrix it would simply return some elements as “indeterminate”.
Consider this –
123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678
By simply swapping rows and columns you can create every other possible permutation. From memory I brought it down to a lesser number of swap functions and the result is that the known numbers form a Karnaugh map of the swaps needed to complete the puzzle.
I understand how you can create any possible permutation from a single solved puzzle. My point was that I did not see how this approach would allow you to enumerate all possible solutions, for the (admittedly degenerate) case of puzzles that have multiple solutions.
My code was also to make puzzles.
While it is possible to return a Boolean formula for multiple solutions, I didn’t bother with this as any puzzle that has more than one solution is considered an invalid puzzle.
I think recognise the frame of an old ABC 3D printer, given how useless I found the machine to be at 3D printing this looks like the first useful adaptation of the device I have seen. Much kudos.
“Sudoku is a great way to pass some time, especially on a long flight.”
You’re a man after my own heart, Al. Every flight I’ve taken for the past 10 years, my first stop after going through security is the stereotypical book-and-magazine store that exists in every airport, to get the latest Sudoku and Sudoku-variant magazine and a pack of pencils.
very impressive to be fair. For something more challenging, how about getting a computer to solve the Times crossword (the proper, cryptic one)?