A Sudoku solver for the Atari 400/800/XL/XE range of microcomputers.
Version 1.0, updated 21st December 2019.

Getting Started

Main screen

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.

Load program

Alternatively, the program can be loaded from DOS with the L (load) option, then enter SUDOKU.XEX and press RETURN.

Basic Operation

Main screen

The program is menu driven. Commands are actioned and options changed by pressing their initial letters.


The following commands are available.

New
Clears the existing puzzle and enters edit mode.
Edit
Enters edit mode, leaving the current puzzle intact.
Run
Runs the solver.
Load
Load a previously saved puzzle from disk.
Save
Save the current puzzle to disk.
Undo
Restores the grid to show the original inputs, after having run the solver. This can be useful if a mistake was made during puzzle entry, leading to no solution being found, as it allows the error to be corrected.
Info
Shows the name of the file loaded and some diagnostic information.
Quit
Quits the program. Pressing the Escape key also quits the program.

The following options are available.

Analyse
Toggles analysis mode on and off. When on, the puzzle solution is not displayed, only the status information. This can be used to check a puzzle can be solved without seeing the solution. Information in the status panel can be used to gauge how hard the puzzle might be to solve.
Fast
Toggles fast mode on and off. If fast mode is on, all screen DMA is disabled while the solver runs, improving performance by ~30%, at the expense of the screen going completely black for the duration.
Blank edit screen

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.

Test case 1

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).

Test case 1 - solved

And it's solved it in about 0.16 seconds according to the status panel. This is a very simple example.

Test case 5 - working

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.

Status Panel

Test case 5 - solved

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?

Pass
Shows how many passes the solver had to use to fill in all the cells. The solver can sometimes find values for a lot of cells in a single pass as it tries a number of strategies in a single pass.
Depth
Shows the current recursion depth of the algorithm.
Max Depth
Shows the maximum recursion depth used in solving the puzzle and is a reasonable indicator of puzzle complexity. If this is shown as zero then the puzzle was solved deterministically, without making guesses.
Consistent
Shows whether there is a solution or not. If during the solution process the puzzle is put into a state where one or more cells have no possible values, then the puzzle is inconsistent. For simple puzzles, the inconsistent state usually indicates that an value has been put in the wrong cell. For more complex puzzle where guesses must be made, you will briefly see the puzzle go into an inconsistent state before the algorithm backtracks and tries a different guess.
Solved
Shows whether the solution is complete or not (which we can also see from just looking at the grid).
Memory
Shows how much memory is being used by the program, as measured from the load address to the end of the recursion buffer. This will increase significantly with deeper recursion depths.
Time
Shows the approximate runtime in seconds to two decimal places. In calculating the time, allowance is made for PAL/NTSC timing differences, but not for hybrid machines. Under emulation, the time shown is the time that a machine running at normal speed would take.

Load & Save

Load

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.

Save

To save a puzzle to disk, use Save and enter a valid file name, including the device name.

Save

In this example a bad device name (X:) was entered and an error message was shown.

Confirm

Successful file operations are confirmed.

Information Panel

Information

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.

Party Piece

Party piece

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.

The World's Hardest Sudoku?

The World's Hardest Sudoku

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".

The World's Hardest Sudoku - Solved

Which this program can solve in ~8.2 seconds (or ~5.4 seconds in fast mode).

FAQ

What happened to the earlier versions?

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.

Which development tools were used?

How much memory is required?

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.

Is BASIC required?

The program does not require BASIC (being written in 6502 assembler), but will operate with it enabled.

Where can I provide feedback?

To provide feedback, please reply to the AtariAge Forums - Sudoku Solver Thread.

Disclaimer

The program has not been tested on real hardware, only under emulation.