Introduction
Su Doku is a number puzzle which seems to have originated in 1979 but which from November 2004 has begun appearing on the puzzle pages of most newspapers and magazines.
The basis is a 9x9 grid which is further subdivided into 3x3 squares, as shown in figure 1.
Figure 1 - A blank Su Doku grid
The puzzle starts with a number of the squares already filled in - eg figure 2.
Figure 2 - Partly completed Su Doku grid
Your task is to fill in all the blank squares such that each row, each column and each 3x3 block with a thicker outline contains each of the digits from 1 to 9 only once, as in figure 3.
Figure 3 - The completed grid
The difficulty of puzzles is rated from 'easy' to 'fiendish', partly determined by how many squares are filled in initially, usually from 40 down to 25, although the arrangement of the initial numbers also affects the difficulty.
A properly constructed puzzle should have just a single correct solution and it is usually possible to deduce the correct value for each square without needing to guess. It is believed that the absolute minimum number of initially filled-in squares for a puzzle to have a single solution is 17.
Apparently the number of different completed 9x9 Su Doku grids meeting the requirement of each row, column and 3x3 subsquare containing the digits 1-9 is 6,670,903,752,021,072,936,960, so enthusiasts are not likely to run out of puzzles to solve.
Su Doku on the hp 39g+ Graphing Calculator
Solving Su Doku puzzles is fiddly but can be done by accurately following a set of instructions and remembering pieces of information, and is therefore ideal for solving by a computer.
The program SuDoku is a solver that runs on the hp 39g+ calculator. It is quite slow but has solved all the puzzles it has been given. It only solves the original 9x9 grid pattern puzzles, not some of the other variations which are occasionally seen.
Loading SuDoku
Copy the files SUDOKU00.000, HP39DIR.000 and HP39DIR.CUR to an empty directory on a PC, start the HP39G Connectivity program and point it to the directory holding the three files.
The Su Doku solver program consists of a single file, SuDoku, which should be downloaded from the computer into the PROGRAM catalog part of the hp 39g+'s memory using the RECV option on the calculator.
(Originally a second file was used as a subroutine to reduce the overall size of the program, but I found that after it had been called about 100 times it stopped with an error message. I believe this is a bug in the operating system of the calculator. The subroutine has now been incorporated into the main program.)
Running SuDoku
Run SuDoku from the PROGRAM catalog. Once it has compiled its title appears on the screen and a 9x9 grid is drawn. You are then invited to enter the digits already supplied in the puzzle. The screen is shown in figure 4.
Figure 4 - Digit entry screen, with some already entered.
The 3x3 blocks have a solid border and the individual squares a dotted border. The current square is highlighted in solid black. The keys used to enter the digits are:
- The cursor keys move the highlighted square as expected, with wraparound at all edges.
- The digit keys 1 - 9 put that digit into the current square, overwriting anything already there.
- Pressing 0 (zero) deletes the digit in the current square. Used for correcting mistakes if the square should really be blank.
- (-), the sign change key, moves the highlight on to the next square. Any of the arithmetic keys + - x / have the same effect.
- . (the decimal point) moves the highlight back one square, same as cursor left.
- When all the given digits have been typed in, press ENTER to begin solving.
If the keys are pressed too rapidly the screen display may lag behind, but it should catch up if you pause. Obviously care is needed to type all the digits in the correct places, otherwise the wrong solution (or even no solution) will be found.
The program has to perform some processing of the grid before it can begin solving, and the screen shown as figure 5 will appear for about a minute.
Figure 5 - Preparation screen.
A small black square is gradually drawn on the left side of the screen to show progress.
Next the message Solving... appears on the screen. The messages Singles:, Rows:, Columns: and 3x3s: will appear in turn. These refer to which groups of squares the solving algorithm is currently looking at and are just displayed to show that something is happening. A small 9x9 square is gradually drawn alongside the words to indicate which part of the main grid is being considered, and new digits are printed in the grid as they are deduced. See figure 6.
Figure 6 - Screen display while solving.
Generally more than one 'pass' through the grid will be needed to solve the puzzle and after each pass the word Finished? will briefly appear to the left of the grid while the program checks whether there are still any blank squares, then solving continues.
For most puzzles, after a few minutes all the squares will have been filled in and a screen like figure 7 will be displayed, showing the full grid and the time in minutes taken to solve it. The display is 'frozen' at this point - pressing any key will return to the calculator's PROGRAM catalog.
Figure 7 - Final screen when the puzzle has been solved.
The solution can be read from the screen and it is also stored in matrix M9, with the rows and columns as on the screen.
For some puzzles rated as 'fiendish' the solving process reaches a stage where it is impossible to deduce a unique value for any square, just a choice of two or three possible values. The program's action in this situation is to find the blank square with the fewest 'possible' values, pick one at random, then continue solving using this value. A screen like figure 8 will appear while it is choosing a random digit.
Figure 8 - Having to guess at a digit.
If the guessed digit was wrong then the grid will at some later stage reach a state where there are no allowed digits for one or more blank squares because all the digits from 1 to 9 have already been used in the same row, column and 3x3 block. Hence after the program has resorted to guesswork it performs an extra check for this situation at the end of each 'pass', where it makes sure the grid is still in a Solvable? state. See figure 9.
Figure 9 - Making sure the grid is not obviously unsolvable.
If the grid does become impossible to solve this means the guessed digit was wrong and so the program reverts to the state the grid was in immediately before it guessed, and makes a new guess. Reverting to the stored grid takes a little time, during which the screen of figure 10 is shown.
Figure 10 - Reverting to a saved grid after a wrong guess.
If the puzzle is particularly difficult then guesses may need to be made more than once, and since they are unlikely to all be correct the first time the program may have to revert to its saved grid several times before the puzzle is solved. This is why 'fiendish' puzzles can take a while to solve.
Hardware Requirements
SuDoku runs on a Hewlett-Packard 39g+ calculator. It should also work on the 39g and 40g but will take about three times as long to solve puzzles, due to the slower processor. It is written in HP-BASIC and may work on the 48g and 49g but has not been tried.
The program takes up 5.2 kilobytes of RAM when first loaded, which expands to 17 kilobytes when run. It also uses 7.2 kilobytes to store matrices as part of the solving process, though most is recovered when the program exits. This means the calculator must have about 25 kilobytes of free RAM to run SuDoku. This, plus use of the DISPXY command, rules it out for the 38g model.
Speed
Despite having a very fast (for a calculator) processor in the ARM 9, the BASIC on the hp 39g+ is disappointingly slow, even allowing for having to emulate the previous Saturn processor. As a result solving of Su Doku puzzles takes a little time. Exactly how long clearly depends on the difficulty of the puzzle but some typical times are:
- Puzzles rated as 'easy' - 4 to 5 minutes
- Puzzles rated as 'difficult' - 10 to 12 minutes
- Puzzles rated as 'fiendish' - 15 to 40 minutes
Variables Used
SuDoku uses the following HOME variables, and will therefore overwrite any existing information stored in them:
- The plotting limit variables Xmin, Xmax, Ymin, Ymax
- Real variables C, D, F, G, J, K, N, O, Q, R, S, T, W, Z
- Matrices M6, M7, M8, M9. When the program exits M9 holds the solved grid. The others have been deleted.
Known Bugs
SuDoku has no way to check that the initial set of digits, before it begins solving, actually has a solution. If there is a mistake in the printed puzzle or in the digits you enter then SuDoku may loop forever trying to solve it.
If insufficient starting digits are given then the puzzle may have more than one solution, and SuDoku will just find one of them.