This puzzle is composed of five regular 9x9 puzzles that are interconnected and you can't solve either of them alone, meaning that you need to be solving all five of them at the same time and use intermediate results from one puzzle to get an intermediate result for another puzzle that this puzzle is connected with. It sounded like a good challenge so I started working on it. After two or three nights I realized that I made a mistake!! Ughhh. I erased everything I had solved and started from scratch. After another few nights I found another problem, got turned off by this puzzle and put it away.
I came across the puzzle once again when my wife and I returned to Slovakia this winter. I found the puzzle in the apartment and, being a person who likes challenges and doesn't get turned off my failures for too long, I decided to erase everything and this time be very careful and solve the puzzle once and for all.
After about two evenings I found something I didn't want to see. An error!!! It was hard to believe it, but there it was. I tried to fix it, but if you don't spot an error in a sudoku puzzle early enough, you'll spend more time fixing it than if you started from scratch.
Do you think I felt like starting from scratch? No! But I couldn't let this be. So since I had 10 or so days off during the Christmas break (thanks Sun!!!), I decided to use my brain in a more productive way and to write a small program that would solve the puzzle for me.
Given my interest in Ruby and JRuby and the type of problem I was about to solve, the language choice was an easy one to make.
A few days later I had a script that solved the puzzle for me within 1.07 seconds. Ya! You heard right! Solved not in a few evenings but in just a little more than one second.
Top Left:
718|956|324
452|387|619
936|142|587
-----------
341|528|796
695|713|842
287|694|153
-----------
523|461|978
869|275|431
174|839|265
Top Right:
635|428|971
214|679|853
897|531|426
-----------
976|382|514
152|764|389
348|915|267
-----------
463|857|192
529|146|738
781|293|645
Bottom Left:
728|154|396
194|836|752
653|279|184
-----------
519|368|427
346|725|918
872|491|563
-----------
231|987|645
467|512|839
985|643|271
Bottom Right:
215|849|637
348|627|591
976|153|824
-----------
869|431|752
154|972|368
732|568|149
-----------
521|796|483
483|215|976
697|384|215
Center:
978|215|463
431|678|529
265|439|781
-----------
813|754|692
649|382|157
527|961|834
-----------
396|847|215
752|196|348
184|523|976
Lessons learned: "automate automate automate!" and "Don't work hard, but work smart!" :)
The algorithm is very simple. The model is based on the simplest unit - a cell which is part of a row, column and a square. Each puzzle consists of 9 columns, 9 rows and 9 squares. Cells are flexible enough to be part of more than one square, row or a column at a time, so I can have cells that are present in more than one puzzle at a time. With a flexible model like this, all that the program needs to do is to use some basic rules to eliminate candidates and determine cell values. This type of solver is often referred to as human-style solver, because it uses the same techniques used by humans.
If anyone is interested in having a look at the source code it can be downloaded from here: multi_sudoku_solver.rb. A word of warning - the code is not cleaned up nor documented. This was just a fun project that I worked on, and the fact that I achieved what I set out to achieve was a good enough milestone to call this project done.
After this experience I don't feel like solving sudoku puzzles any more. They are just a repetitious problems that are well suited for automated solution. Most importantly - I actually had more fun writing the program than I had with solving the puzzle :).
2 comments:
Nice, will check your code later. The thing I really like on sudoku is how difficult you can get without the need of pen and paper - keeping all the numbers in your mind. That's when it gets really interesting.
Interesting with the extra challenge. I have difficulty with solving the single 9x9 case. I too wrote a program to solve Sudoku puzzles. My program is in C with a recursive implementation of a brute-force with backtracking method. Not so clever or exciting but I like how programs can solve problems.
What turned out to be interesting for me is how I applied my Sudoku solver to generate Sudoku solutions boards (starting with a blank board) from which I generated Sudoku puzzles for my website http://this1that1whatever.com/miscellany/sudoku/.
Now I'm getting more interested in learning ways to solve Sudoku with my own brain. However, I need to spend time on building my website.
Post a Comment