A Sudoku solver for the Atari 400/800/XL/XE range of microcomputers.
Version 1.0, updated 21st December 2019.
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. Commands are actioned and options changed by pressing their initial letters.
The following commands are available.
The following options are available.
Edit mode is indicated by the appearance of a cursor in the first cell in the grid. To exit edit mode, press Escape. 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 or . 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 Escape , R).
And it's solved it in about 0.16 seconds according to the status panel. This is a very simple example.
When are more complex puzzle is being solved, you will see numbers appearing and disappearing. The numbers 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 numbers 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 16 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?
To load a file, use Load and enter a valid file name, including the device name. For example, "D1:FILE.SUD" The program does expect you to enter something sensible here, only very basic error handling is provided. Device names take the form D:, D1:, D2: etc. Where available (such as under emulation), H: etc. may also be used.
To save a puzzle to disk, use Save and enter a valid file name, including the device name.
In this example a bad device name (X:) was entered and an error message was shown.
Successful file operations are confirmed.
The name of the current file is shown in the information panel. The rest of the information shown was to help with development and isn't really useful in everyday usage. If running on a computer with less than 48K of memory, the number of slots available for recursion may be fewer than shown and will limit the program's ability to solve very hard puzzles.
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 18 seconds. During development, this was used to determine the maximum memory and hardware stack usage 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. That assertion may or may not be true, but it is certainly a very hard puzzle to solve. It is available on the distrubution disk as "HARDEST.SUD".
Which this program can solve in ~8.2 seconds (or ~5.4 seconds in fast mode).
During development of the BBC micro version of the program it became clear that the original implementation was flawed and was unable to solve very hard puzzles. While it was able to solve the example above, this was good fortune rather than good programming. Therefore versions prior to v1.0 have been withdrawn.
48K is recommended. The program will adjust the maximum recursion depth if insufficient memory is available which may limit its ability to solve very hard puzzles.
The program does not require BASIC (being written in 6502 assembler), but will operate with it enabled.
To provide feedback, please reply to the AtariAge Forums - Sudoku Solver Thread.
The program has not been tested on real hardware, only under emulation.