A Sudoku solver for the BBC Model B, Master 128 and Acorn Electron range of microcomputers.
Version 1.0, released 22nd December 2019.

A note for Electron users

In order to have sufficient memory to solve harder puzzles, the program runs in MODE 7 (Teletext) on the BBC Model B and Master 128. As the Electron lacks MODE 7, it runs in MODE 6 which means there is less memory available to solve harder puzzles. The screen shots here are in MODE 7, the program will be in monochrome on the Electron.

Getting Started

Main screen

The program is distributed as a bootable DFS format SSD and the latest version can be downloaded from the Resources menu. The SSD contains three versions of the program (B.SUDOKU, M.SUDOKU & E.SUDOKU) and some test cases in the "T" directory (T.*).

The LOADER program runs when the disk is booted and detects whether the computer is a Model B, Master or Electron and loads the correct version of the program.

Load program

Alternatively, the program can be loaded from a command prompt with the *LOADER command.

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 output is disabled while the solver runs, improving performance slightly.
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 DELETE 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.

Test case 1

Here is a completed input. This puzzle is saved in file T.TC1 on the distribution SSD.

Now exit edit mode and run the solver (Press Escape , R).

Test case 1 - solved

And it's solved it in about 0.23 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 (T.TC5, 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.

Load & Save

Load

To load a file, use Load and enter a valid file name, including disk and directory information as necessary. For example, "T:FILE".

Save

To save a puzzle to disk, use Save and enter a valid file name, including disk and directory information as necessary.

Save

In this example a file name which is too long for DFS 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. On an Electron, the number of slots available for recursion is 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 11 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 "T.HARDEST".

The World's Hardest Sudoku - Solved

Which this program can solve in ~5 seconds.

FAQ

Which development tools were used?

Where can I provide feedback?

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