Sudoku is easy to understand: a 9x9 grid, 81 cells, in which every row, column, and 3x3 box must contain digits 1 through 9. Simple enough, but with enormous possibilities. If one were to write a little program to generate all possible 9x9 grids with all possible combinations of 9 digits in each of the 81 cells, it would have to generate 9^81 (9 to the 81st power) grids (that's a number with 78 digits). I did in fact write such a simple program over 15 years ago. But to complete the task within my lifetime, even on a powerful 5 gHz machine generating, very generously, one grid per 10 processor ticks or 500 million grids per second, the program would have to have started running a 62-digit number of years ago. I think that's well before God created Earth.

Now, there are considerably fewer than 9^81 valid Sudoku grids. My program needn't try all 9 digits for all 81 cells. If I made the logic a bit more complex, it could generate only valid Sudokus without wasting processor time on invalid ones. Taking just the top row, for example: there are 9^9 or 387,420,489 possible combinations of digits 1 - 9 for those 9 cells. But there are only 9! (nine factorial), or 362,880 combinations of 9 digits in which each digit occurs exactly once (a valid Sudoku row). So, for example, for a given cell in the row, if there were already a 2, 3, 5 and 8 in other cells in the same row, my program need only try the remaining digits 1, 4, 6, 7, and 9. It could therefore solve the row in a fraction of processing repetitions, or loops.

Applying this to the whole Sudoku grid is a bit more complex, because every cell in the 9x9 grid is a member of exactly 3 groups of 9 cells: one row, one column, and one 3x3 box. The improved logic would have to take this into account. I did so by moving to assembly language and using bitwise operations AND, OR, and XOR to make valid digit selection more intelligent and efficient for each cell, in relation to each of the 3 groups to which that cell belongs. Also, the order in which my program looked at each cell needn't be a row-by-row scan. I settled on this order: [a1-a9, b1-b3, c1-c3, b4-b9, c4-c9, d1-i1, d2-i2, d3-i3, d4-d9, e4-e9, f4-f9, g4-g9, h4-h9, i4-i9] as a way to optimize the smart formation of valid groups with a minimum of looping.

Moreover, for any given valid Sudoku grid, there exist many derivations which may look different, but are logically the same Sudoku. For example, you could swap the first two rows, putting the second row on top, and the first row below it. Each row retains its own contents and validity. Each column in the Sudoku also retains its validity, since no digit has moved from one column to another. Every 3x3 box is likewise still valid. You could do the same thing with the 2nd and 3rd rows. There are in fact 6 distinct ways in which the first 3 rows can be arranged without disturbing the Sudoku's validity nor changing its uniqueness. Note that you could not swap one of the first 3 rows with any of the lower 6 rows, since that would involve moving cells between different 3x3 boxes, altering their contents and their validity. But you could swap rows 4 through 6 in six ways, and rows 7 through 9 as well, resulting in 6 x 6 x 6 = 216 ways the 9 rows could be swapped without changing the Sudoku's validity or uniqueness. In the same way, you could also swap any two tiers, or groups of 3 rows. Since there are six ways the 3 tiers can be arranged, we now have 216 x 6 = 1,296 arrangements of rows and tiers of rows that are all logically the same Sudoku. For any one of these 1,296 arrangements of rows and tiers, we can also swap columns and groups of 3 columns. Then we could rotate the entire 9x9 grid 90° for an entirely different arrangement which is still the same valid Sudoku. (Note that rotating the 9x9 grid 180° gives us the same grid as one of the row and column variations, and so would not count as a new arrangement. Similarly, rotating it 270° would be the same as rotating it 90° together with one of the row and column variations.) Finally, we can swap the nine digits with each other, for example changing each '1' in the Sudoku to a '4', each '8' to a '3', etc. There are 9! (nine factorial) or 362,880 ways that the nine digits 1 through 9 can be swapped. Putting all this together, there are 1,296 x 1,296 x 2 x 362,880 = 1,218,998,108,160 ways any given valid Sudoku can be arranged to look different while remaining the same logically. This is pretty much in concordance with the mathematicians at Technology Review, who have used their computers to determine that there are 6,670,903,752,021,072,936,960 possible valid sudoku grids but only 5,472,730,538 unique Sudokus.

Together with some other improvements, after a few weeks my program was a little more complex, but alot more efficient. It was generating almost one million valid Sudoku grids per second on my old 500 mHz machine. There were still duplicate morphs being generated, but this was now fast enough to generate all possible valid Sudokus in a couple weeks or so of continuous running. More to the point, this same improved logic was able to work on a partially filled grid, i.e, a Sudoku puzzle. As noted in the previous article, a Sudoku with 60 or fewer empty cells is exponentially faster to analyze.

But this introduces a new layer of complexity, in that for every complete Sudoku grid there exist an immense number of partially complete grids, composed of filled and empty cells. Some of these partially complete grids may be true single-solution Sudoku puzzles, that can only resolve to one unique complete Sudoku. Others may pertain to more than one complete grid, that is, they may have multiple solutions. Still other partial grids may be unsolvable; there exists no way to fill in the empty cells to obtain a valid complete Sudoku grid.

Limiting ourselves to the first category: for any given single-solution Sudoku, there may exist a huge number of paths to solve it. At any one step along the way, you may be able to solve any number of different cells, using a variety of strategies. Solve one of those cells, and now you have a different puzzle, one that is probably easier to solve. Solve a different cell, and you now have a slightly different Sudoku, perhaps harder to solve, not easier!

I don't know how to calculate this additional complexity: how many incomplete grids exist, how many of these are single-solution Sudokus, and how many different ways there may be to solve them. I suspect the total number may be of a similar or greater magnitude as in the first paragraph above, virtually impossible to compute all possibilities exhaustively.

Well, OK. You may well question why a retired geek would spend so much time chasing such an unattainable goal. What can I say? Am content to have developed my program to the point where it seems to be able to analyze, if not all, at least the vast majority of the aforementioned enormous possibilities. To repeat: if you disagree with my boast, if you find a problem, or if you ever come across another analyzer that performs like my Sudoku Analyzer, be sure to let me know.

When you press the buttons 'Analyze', 'Hint', 'Peek', or 'Solve', the Sudoku Analyzer sends a small Ajax packet to the server. The 'X' in A.J.A.X. in this case stands for 'executable', a program that runs on the hosting server at cyberjerry.info as a native BSD excutable or binary. The binary performs the requested task and sends another small packet back to your computer to complete the Ajax transaction. This program is written in C and assembly, compiled on the server using gcc, for maximum execution speed. (Sudoku analysis would run way too slowly in a scripting language.) The original and core part of the program, written in assembly, solves the Sudoku by means of simple and fast bitwise AND, OR, and XOR instructions in tightly coded repetitive loops. Its task is to solve the Sudoku grid, or exhaust all possibilities in trying to solve it. Upon finding one solution, it continues to repetitively loop, looking for additional solutions. It can thus report back to the C program whether the particular grid has one solution, multiple solutions, or no solution. Its secondary task is to construct the array used to make the Elimination Grid.

This simple but efficient assembly solver routine could (almost always) perform its task very quickly. Given an empty or nearly empty grid, even the fastest binary program would take too much time to try all possibilities, but it could continue to generate multiple solutions (as many as a million or more per second) until the calling C program said, "Enough!". When given a grid with several cells filled in and therefore fewer cells to solve, it could exhaust all possibilities in exponentially less time. Where it would take several days to find all the solutions for an empty grid, it could do the same in a couple seconds - less than one second on a fast web server - for a grid that had 60 or fewer empty cells. It could then report definitively to the C program that the grid had exactly one solution, multiple solutions, or no solution. The C program could then use this information to begin to analyze the grid and, in the case of a single solution Sudoku, could help the human operator with step by step hints. Thus was born the Sudoku Analyzer.

The middle range was a bit problematic, where the grid had between 8 and 20 cells filled in. Depending upon how the 8 to 20 cells were configured, they might in some cases prevent the assembly routine from generating solutions quickly. At the same time, so many unsolved cells meant that the assembly routine would repetitively loop exponentially more times trying to exhaust all possibilities, and the server would likely kill the program for taking too much processor time. None of the problematic grids tested were valid single-solution Sudokus; they either had no solution or multiple solutions. Or so I thought. So, a few years ago, to avoid the server timeout error, I added a loop counter, telling the assembly routine to quit if it had found no solution after 120 million loops, at which point the C program would report that the grid had "no solution, or too many to analyze."

This assembly solver routine has been the focus of my attention for the past several weeks. Written about 15 years ago, it was the first part of what eventually became the online Sudoku Analyzer. In the interim years I continued to make improvements and fix bugs in the interactive web page, and the server-side C program's analysis and hint logic, but the assembly routine remained mostly unchanged. Then, as noted in the previous blog article, Señor Manuel Navarro De La Hoz of Colombia sent me something I had never found: a single-solution Sudoku with only 17 cells filled in. For the reasons mentioned above, my assembly routine could not solve it nor exhaust all possibilities within the loop limit constraints. And I knew what I had to do: I had to go back to the beginning, and make the assembly language solver routine run smarter and faster.

The new assembly routine is more complex and more analytical than the old one. Rather than trying to solve every grid the same simple way, it examines the grid and ranks its unsolved cells and groups of cells according their possible valid contents. Similarly, rather than always trying the digits 1 through 9 in numerical order, it ranks the digits in an order more likely to produce valid results quickly. Finally, upon testing my new logic, it became apparent that extending the loop limit beyond a few million loops had very little impact. So my new routine tries to complete its work in under 8 million loops. If it fails, it might try a different order of digits and cells, then another, then another. 99.77% of the time it now does all its work with less than 20,000 loops, and should never make more than 20 million loops, even in worst cases, so the server should never complain that it is consuming too much processor time.

Since the above involves radical changes to the core assembly routine, this marks a major new release number for the Sudoku Analyzer, version 3.0.000. At this same version level, there are a few minor changes to the C portion of the server-side binary and to the client-side interface. One new feature you may notice is that, above the Elimination Grid, you may now click 'Stats' to see how many loops and how much time the binary is taking each time it is called. The overall Ajax time is there for reference; the new changes affect only the speed and efficiency of the server-side binary. I have no control over the Ajax process, which depends upon your connection speed and that of all the servers that pass the small Ajax packet back and forth between your computer and the server at cyberjerry.info.

Now, with all due respect to Señor Navarro, and with humble gratitude for his astute and successful answer to my Challenge, I am in no way relinquishing my Sudoku Analyzer's claim to be the best on the web. It was already the best, and now, thanks to Señor Navarro, it is even better. The website where he found the Sudoku that had my Analyzer (temporarily) stumped was nothing more than a collection of canned Sudoku grids and their final solutions. No step by step hints, no analysis, nothing.

As I compose this blog article, am also running a program on my home computer to generate Sudokus in various configurations of filled and empty cells, to continue testing my new logic. At this moment, this program has generated around 90 million grids, all of which the new logic is handling without failing, and without taking too much time. That's not to say that the Sudoku Analyzer is now without flaws, nor that 3.0.000 will be its final version. But if you find a problem, or if you ever come across another analyzer that performs like my Sudoku Analyzer, be sure to let me know.

A few days ago, an astute visitor* to the CyberJerry Sudoku page successfully responded to the Sudoku Challenge, the first CyberJerry visitor to do so. He found the Sudoku grid pictured which the Analyzer couldn't solve, and told me (in Spanish) how to solve it:

este sudoku lo saque de la pagina https://www.sudoku-online.org de categoria sudoku extremo #717, y su analizar dice que no tiene una solución, sin embargo por metodo analitico encuentro que F6 = 4 debido al 4 de E3 y el 4 de G5, tambien encuentro que I9 = 5 debido al 5 de D8 y al 5 de H4, al colocar estos dos números, ahora si dice que tiene solución única lo anterior esta pasando

Now that it's more and more difficult to find Sudoku grids that the CyberJerry Sudoku Analyzer (the 'Analyzer') can't analyze step by step, the great Sudoku Challenge is also becoming more difficult. To help out a bit, below are four Sudoku grids that the Analyzer can't analyze step by step. You just have to figure out how to solve one of these analytically (no guesswork) to qualify as a successful Sudoku Challenger. Click on any of the grids to bring it up in the Analyzer. Both it and you should be able to solve several cells. But at some point, the Analyzer gets stuck and can't give a hint. Can your brain keep analyzing beyond that point, and solve the puzzle? If so, click on the (read article)

A recent round of minor enhancements and corrections has made the CyberJerry Sudoku Analyzer capable of analyzing increasingly tough Sudokus. Two results: the "New Puzzle" control now offers a "Genius" level, and the "Hint" feature may offer extremely complex hints, containing many interdependent sub-steps of a variety of advanced strategies. The added focus on complex Sudokus has had another unforeseen result: the possibility of encountering what I call the "Unavoidable Avoidable Rectangle". (Not being able to find any mention of the phenomenon in any other website, I claim the right to assign this name to it.) Let me explain: (read article)

This blog article serves as both another bug report and as a candidate for the Sudoku Challenge .

This time, the Sudoku Analyzer cannot solve the Sudoku step-by-step. It should be able to. This is a known bug, recently discovered by yours truly, and which yours truly is working on, and hope to have fixed soon.

In the meantime, if you think you can solve this Sudoku analytically (no guesswork), (read article)

This Sudoku puzzle has me scratching my head.

The Sudoku Analyzer solves it step by step, giving clues along the way. Which is to say, it is not one of those occasional Sudokus which can only be solved in trial-end-error guesswork manner. But at a couple points, the Sudoku Analyzer gives very complex hints where simple hints are possible. This is not according to design. Then, in at least one very complex hint, several secondary hint steps are omitted, without which the complex hint is incomplete.

What's especially baffling is that these (read article)