My penance is countless hours of painful debugging. Despite these shortcomings, this program still seems to work OK................. Writing Jet Sudoku has been an ongoing project for well over a decade. It was a natural fit for me because I enjoy both computer programming and solving sudoku puzzles. It has been both challenging and frustrating but continues to be an ongoing process that will most likely never end. First of all, why the name JET SUDOKU? I spent quite a bit of time searching for a cool, catchy name. I found that most of them have already been used (Sudoku-cabana, Sudoku-topia, Sudoku-phrenia, Sudoku-whatever). I gave up looking for a really cool name and just threw out JET SUDOKU (hastily) and now I'm stuck with it. Oh well. What's in a name. I wish it was more cool but it is what it is. I started this project with several priorities in mind:
As far a sharing source code, I have included the code for analyzing and generating puzzles. The code for the GUI (graphical user interface) works well as you can see but the source code is a mess! Also the source code for the individual solving techniques is a mess. I haven't shared that code out of shear embarrassment. The code for puzzle generating is clean and is here for those who want to check it out. Click HERE to download the source code. The file is SUDOKU.BAS which is a text file viewable with most text editors (notepad, wordpad, etc). It can probably be tweaked to run with VB.NET and other BASIC languages, I'll leave that part up to the reader. CREATING NEW SUDOKU PUZZLES Creating new sudoku puzzles has four priorities, two manditory and two optional. These are:
It is a simple task to randomly add numbers to a blank grid. The challenge is that the puzzle must be tested for validity when each new number is added. I discovered early on that starting with blank grid (ie. no known solution) was a bad idea. A much better approach is to start with a solved puzzle and work backwards. This takes care of priority #1. If the solved puzzle is valid, it will be impossible to create an insolvable puzzle. Priority #2 gets a bit more complicated. How do you verify that a puzzle has only one unique solution? I posed this question in some reputable sudoku forums and started some interesting dialog. The best solution appears to be what I call BI-DIRECTIONAL BRUTE FORCE. I have also read about other techniques such as solving with bruce force, then rotating or flipping the puzzle and solving it again. This method has been proven to be faulty in detecting multisolution puzzles. I have tested the bi-directional method extensively and have yet to see it fail. Click here for details about brute force. So now that we have the tools to prove puzzle validty, let's create some puzzles! GENERATING A NEW SOLVED PUZZLE So where does one obtain a completed puzzle to begn with? There are authors who suggest starting with a known completed puzzle and altering it by rotating and/or flipping the puzzle followed by renumbering the digits. This might be Ok but I take exception to it. With the staggering number of possible puzzles (6,670,903,752,021,072,936,960 according to Wikipedia), why start with one that already exists? My opinion is that we should start from scratch with every puzzle. How does one create a new solved puzzle? It isn't as easy as it sounds. Take a blank grid and start randomly plugging in numbers until you've filled in all 81 numbers. Obviously you must avoid conflicts in any house (row, column, or box). Doing this randomly, you will encounter a dead end greater than 99.9% of the time (try it). Fortunately, doing this in a computer program allows a 99.9% failure rate to be acceptable. A new solved puzzle can be produced in less than a second. Still, there are ways to make the process more efficient. Here are my three ways of creating new solutions.
With our new solved puzzle in hand, we have two approaches to create a new sudoku puzzle:
The second method starts with a blank grid and sequentially reveals cells. The process is repeated until only one solution is possible. The downside is that the brute force method is using a small number of givens (it doesn't even try until there are at least 18 givens). This method is illustrated in the SUDOKU.BAS module in Sub CreatePuzzleFromSolutionAlt(MySolution As String, MyPuzzle As String). It is shown only for interest but it is not recommended. PUZZLE DIFFICULTY The first question is "what determines a puzzles difficulty?". There is considerable debate about this issue. My personal opinion is that difficulty is dependent upon the solving techniques required to solve it. A puzzle that requires use of an XY-Wing at some point would be a very difficult puzzle. A puzzle that is solved by all naked singles would be ridiculously easy. But who gets to decide whether a swordfish is more difficult that a finned X-Wing or a turbot fish? In Jet Sudoku, puzzles are assigned difficulty levels based on my own arbitrary assessment. They can be EASY (all naked singles doubles and triples), MEDIUM (throw in a few locked candidates) ,HARD (hidden doubles, hidden triples, X-Wing and unique corners), VERY HARD (finned anything, swordfish, jellyfish, xy wing xyz wing, quads) or DIABOLICAL (everything else, chains, trial and error). These are purely my own. If there is an accepted standard out there somewhere in the sudoku world, I'll be glad to incorporate it into JS. Regardless of the this contraversy, how does one create a puzzle that requires on XY-Wing to solve it? Creating new sudoku puzzles with specific degrees of difficulty has been very disappointing. It boils down to creating a large batch of puzzles, testing them all for level of difficulty, and selecting the desired puzzles from the batch. There should be a better way but I've yet to find it. If you know of one, email me at jumpindoc@gmail.com and tell me about it. You'll be my hero (or heroine) forever! VISUALLY PLEASING PUZZLES I have toyed with this a bit but not extensively. Its low on my priority list but I realize its important to many. In the SUDOKU.BAS file, there is a subroutine called Sub CreatePuzzleFromSolutionByPairs(MyPuzzle As String, PairsOnly As Boolean). Notice the boolean option PairsOnly. This subroutine sequentially blanks cells to create the puzzle. When PairsOnly is true, cells are blanked in pairs that are mirror images of each other. So top left cell would be the mirror image of bottom right cell. The process is repeated until it is not possible to blank any more cells without creating a multi-solution puzzle. The result is a symmetrical puzzle. The downside to this method is that the puzzles tend to be easy to solve, usually all naked singles. Conversely, when PairsOnly is false, difficulty can be anywhere from EASY to DIABOLICAL. When running Jet Sudoku, PairsOnly will be TRUE when pressing F11 and FALSE when pressing ALT+F11. Got any ideas? Everything here is ready to tweak. None of it is cast in stone. I'm always looking for ways to improve JS. New algorithms and solving techniques, ideas, comments, criticisms, are all welcome. Drop me an email at: jumpindoc@gmail.com |