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.

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

New
Clears the existing puzzle and enters edit mode.
Edit
Enters edit mode, leaving the current puzzle intact.
Load
Load a previously saved puzzle from disk (or, in theory, cassette).
Save
Save the current puzzle to disk (or, in theory, cassette).
Run
Runs the solver.
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 user to easily correct the error and try again.
Analyse
Runs the solver, but does not display the solution, 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.
Trace
Runs the solver, but waits for a key press after inserting each number. This has been slightly useful during testing.
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.
Background
Toggles the background shading used to add a checkerboard pattern to the puzzle grid on and off. Note that while solving, the background is turned off as otherwise the DMA used to maintain the players slows down the solver.
Quit
Quits the program and returns to DOS.
Blank edit screen

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.

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 E , R).

Test case 1 - solved

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.

Test case 5 - working

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.

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 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?

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.
Inserted
Shows the number of cells inserted in the current pass.
Complete?
Shows whether the solution is complete or not (which we can also see from just looking at the grid).
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 has 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.
Depth
Shows the recursion depth of the algorithm. If this is shown as zero then the puzzle can be solved deterministically, without making guesses. Depth is a reasonable indicator of puzzle complexity.
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 and was originally to allow use to make sure we had sufficient memory available.
Stack
Shows the low point (approximately, because there will be a couple of extra JSR instructions which are not counted) of the 6502 stack pointer. This was added to check we were not in danger of the stack wrapping round (it's only 1 page, 256 bytes on a 6502) during deep recursion.
Time
Shows the approximate runtime in seconds, accurate to completed tenths of a second (so 0.4 could be nearly 0.5 and still show as 0.4). 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.

At the end of the run, Depth and Memory show the maximum values encountered and Stack shows the minimum value encountered.

Load & Save

Load

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.

Save

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

Save

In this example an unknown device name (X:) was entered.

Error

Which resulted in an error message being shown.

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

The World's Hardest Sudoku?

The World's Hardest Sudoku

According to the Daily Telegraph this is the world's hardest Sudoku.

The World's Hardest Sudoku - Solved

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.

FAQ

Why version 0.x?

We suspect more work is required to make the program worthy of a version 1.0 release.

What was version 0.1?

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.

Which development tools were used?

The WUDSN IDE for program development, the MADS assembler, Atari800MacX (Mac OS/X) and Altirra (Windows) emulators for testing and debugging.

Is 48K required?

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.

Is BASIC required?

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.

Will it run on a MiST?

Yes, it runs on a MiST.

Where can I provide feedback?

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

Version History

Version 0.6

Version 0.5

Version 0.4

Version 0.3

Version 0.2

Version 0.1

Warning

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.