Excel Formulas Based Sudoku Solver

| 6 Comments | 0 TrackBacks

About four years ago, I created an interesting Sudoku Solver. It was unique because rather than use brute force VBA to determine every possible combination of numbers to solve a given puzzle, it used recognized human logical techniques that had been developed for the Sudoku game by enthusiasts worldwide. Techniques such as Intersection Removal, Hidden Quads, and Naked Pairs. And to top it off, these logical techniques were executed by formulas, with the heavy lifting done by named formulas using bitwise operations. I alluded to this game solver back in January when I posted 5 And 3 Is 1. Today, I'm finally sharing it with you.

 
sudoku_solver_excelhero.com.gif
Above is an animated GIF of my Sudoku Solver in action. It does use VBA, but not for solving a puzzle, just for updating the display and moving the game forward. What's nice about this implimentation is that it is interactive and can be used to learn the various human logic techniques that when mastered can solve these puzzles efficiently.

The techniques that are currently supported are Naked Singles, Hidden Singles, Naked Pairs, Hidden Pairs, Naked Triples,  Hidden Triples, Naked Quads, Hidden Quads, and Intersection Removal. I had planeed to add X-Wing, Turbot Fish, Y-Wing, Sword-Fish, Jelly Fish, and X-Wing Pairs, but sadly never found the time. Perhaps a budding Excel Hero will. The project is open-ended so any number of logical techniques could in theory be added.

I'll warn you that the logic gets a little complex. I'm sure my formulas could be improved upon. The project was done as a proof of concept and not as a production piece. However, there is a lot here that can be learned from advanced named formulas to VBA to conditional formatting.

To run the solver, just click on the Search button. The program will test the puzzle to see if any of the logical techniques in its arsenal will work. When it finds one, it stops and highlights the technique and the affected squares. This is how you learn. To continue, just click on Search again. This iterative process continues until either the puzzle is solved or the current roster of techniques cannot advance the puzzle solution further. Surprisingly most puzzles published can be solved with this limited list of techniques.

The small numbers are candidates for the larger square immediately to their right.

You will notice a sheet named "z." On that sheet is a collection of puzzles that you can try. Most can be solved by this program. Some cannot. Just copy the 81 numeral string to the clipboard and then switch back to the Game sheet and click the Import button. Paste the string in the dialog and click OK. You can import any Sudoku puzzle this way; it just needs to be in the standard 81 numeral format.

On the bottom-right corner you will find a section entitled Show Candidates. Clicking on any of the colors there will highlight the respective candidates on the game board.

The program goes out of its way to protect itself and password protects the Game worksheet on every move. The password it just the numeral "1". Tear into this. I guarantee you will learn a lot.

I've tested it in Excel 2002, 2007, and 2010. Please let me know what you think.

Here is the file.


Enhanced by Zemanta

If you liked this article, please share it!



Your Ad Here

No TrackBacks

TrackBack URL: http://www.excelhero.com/cgi-bin/mt/mt-tb.cgi/62

6 Comments

Perhaps I get too much spam, but I'll bet this is the only legitimate use of "Found Naked Singles" on the entire internet.

@Dick -

I wondered who would pick up on that. I'm glad it was you!

Regards,
Daniel Ferry
excelhero.com

rhanks for secret
www.sudoku-maroc.ma

This was an interesting post to read. I have seen a few sudoku puzzle solvers. But this one seems to still keep the fun in it. thanks

Have you seen or can you make puzzles bigger than 36x36? Biggest one I find online is ...

http://sudoku-puzzles.merschat.com

This is extremely impressive, but I found a problem with it.

While trying to solve this puzzle:

000300920000000010900170600070040002460205071800030050004027008080000000017008000

It finds the Naked Quad quickly, which I was impressed by, but then it hangs.

In box 8 the only candidates for 4 are in column 4, but it does not take the 4 out of column 4 in box 2, which is needed to unlock the hidden tripple.

Leave a comment

About this Entry

This page contains a single entry by Daniel Ferry published on July 13, 2010 3:08 PM.

Excel Optical Illusions Week #21 was the previous entry in this blog.

Excel Partial Match Database Lookup is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.