The Duckology team are reasonably proud to present their first ever software project, a Sudoku solver for the Atari 400/800/XL/XE range of microcomputers (48K memory required). Released in 2015 only ~35 years after the original 400/800 microcomputers.
The program is distributed as a bootable (DOS 2.5) ATR and the latest version can be downloaded from the Resources menu. The ATR contains the program itself (SUDOKU.XEX) and some test cases (*.SUD).
The file AUTORUN.SYS on the ATR is a copy of SUDOKU.XEX, so booting the ATR in an emulator should bring up the main screen automatically.
Alternatively, the program can be loaded from DOS with the L (load) option, then enter SUDOKU.XEX and press RETURN.
The program is menu driven and the active menu items are indicated by their initial letters being shown in Inverse ATASCII. Menu items which are unavailable are shown without the inverse ATASCII initial letter.
The following menu items are available.
Edit mode is indicated by the appearance of a cursor in the first cell in the grid. Note that all but one of the menu items has been made inactive and Edit is now Exit. To exit edit mode, simply press E again. In edit mode, the number keys 1 - 9 will enter the value into the current cell then advance the cursor by one cell. The cursor will move on to the next row on entering a value in the last column and will wrap round to the top left cell when the bottom right cell is entered. Pressing SPACE will erase the current cell and advance the cursor, while pressing BACKSPACE will erase the current cell and move the cursor backwards. In addition the arrow keys move the cursor up, down, left and right as one might expect. However the arrow keys wrap within the same row or column rather than advancing. On real hardware, the CONTROL key will have to be used in conjunction with the arrow keys. Under emulation the arrow keys are usually mapped directly to the host computer's cursor keys.
Here is a completed input. This puzzle is saved in file TC1.SUD on the distribution ATR.
Now exit edit mode and run the solver (Press E , R).
And it's solved it in about 0.4 seconds according to the status panel. This is an extreme example. TC1.SUD, Test Case 1 is the simplest Sudoku we've seen.
When are more complex puzzle is being solved, you will see characters flashing on and off in inverse video as well as appearing and disappearing. The inverse video characters are those inserted in the current pass and the inverse video bit is cleared during the next pass. The characters which appear and disappear are guesses and the insertions which follow those guesses. When the puzzle is found to be inconsistent as a result of these guesses, the algorithm backtracks and the characters are removed. There is little practical benefit to this beyond some visual feedback.
As you can see from the status panel, this puzzle (TC5.SUD, Test Case 5) took substantially longer, used more memory and had to recurse 23 levels deep to come up with a solution. Note that this is just one solution, the program does not attempt to find all solutions, if multiple solutions exist.
What does the status panel tell us?
At the end of the run, Depth and Memory show the maximum values encountered and Stack shows the minimum value encountered.
To load a file, use Load and enter a valid file name. The program does expect you to enter something sensible here, only very basic error handling is provided. If no device (D:, D1:, D2: etc) is specified, D: is assumed.
To save a puzzle to disk, use Save and enter a valid file name.
In this example an unknown device name (X:) was entered.
Which resulted in an error message being shown.
How much of a start does the solver really need? What happens if we start from a completely blank grid? Well, it will come up with a solution, after about 20 seconds. During testing, this was used to get a feel for the maximum memory / minimum stack pointer to check we're not running out of resources and to stress test the algorithms.
According to the Daily Telegraph this is the world's hardest Sudoku.
Which this program can solve in ~69 seconds (or ~51 seconds in fast mode). Interestingly, while this takes longer than solving a blank grid, it uses less memory and a much lower recursion depth. Watching it solve the puzzle show that it gets very close to a solution before it hits an inconsistent state and has to backtrack. This seems to be what makes it so hard to solve.
Version 0.3 needed 457 passes and took nearly 2 minutes to arrive at the same solution. The additional algorithm added in version 0.4 helps here, but being quite resource intensive nearly doubles the time to solve a blank grid.
We suspect more work is required to make the program worthy of a version 1.0 release.
Retrospectively we refer to the original unreleased C (cc65) prototype as version 0.1. This was much slower (5m 36s vs 20s for the "Party Piece") and used a lot more memory, but had basically the same functionality. The speed difference is partly explained by the use of better algorithms in version 0.2.
We've assumed 48K, but you should get away with 32K, Less than 32K and you'll be struggling. The program loads at $2000 and is only about 8K, but deep recursion can use quite a lot more.
The program does not require BASIC (being written in 6502 assembler), but will operate with it enabled. However, please note that BASIC is unlikely to work properly afterwards as the program uses some of the same zero page addresses as BASIC.
Yes, it runs on a MiST.
To provide feedback, please reply to the AtariAge Forums - Sudoku Solver Thread.
.wordbecause it wrapped round when solving the world's hardest Sudoku (according to the Daily Telegraph). The program needed 457 passes and took nearly 2 minutes to run, but it managed it.
The program has not been tested on real hardware, only under emulation and on a MiST. Ideally we would prefer to have tested it on real hardware, but at time of writing we don't have any. However, as it does not depend on cycle accurate timing or make clever use of ANTIC, POKEY, CTIA/GTIA or Player/Missle graphics, we anticipate no major problems. Where we have made use of the OS, we have tried to do so in a standards compliant manner.