A Sudoku solver for the BBC Model B, Master 128 and Acorn Electron range of microcomputers.
Version 1.0, released 22nd December 2019.
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.
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.
Alternatively, the program can be loaded from a command prompt with the *LOADER command.
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 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.
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).
And it's solved it in about 0.23 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 (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?
To load a file, use Load and enter a valid file name, including disk and directory information as necessary. For example, "T:FILE".
To save a puzzle to disk, use Save and enter a valid file name, including disk and directory information as necessary.
In this example a file name which is too long for DFS 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. 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.
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.
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".
Which this program can solve in ~5 seconds.
To provide feedback, please reply to the Stardot Forums - Sudoku Solver Thread.