Sudominator is a program for automatic sudoku solving or assisting in manual solving. Sudoku is a popular, Japanese mathematic puzzle. Sudominator runs on MorphOS operating system, the AmigaOS successor. To solve a sudoku, Sudominator uses brute-force algorithm augmented with dynamic narrowing of the search tree. This technique ensures that every solvable sudoku will be solved, on the other hand it takes a fraction of second even on moderate speed computers. Sudominator is a free software, distributed with full source code on the Simplified BSD License. The current Sudominator version is 1.0.

AI Escargot? A piece of cake,
done in 0.4 second.

Live solve running.

Download

Sudominator 1.0 (67 kB) for MorphOS 2.x, on MorphOS Files. The source code is included inside the archive.

Features

The main feature of Sudominator is automatic sudoku solving. There are two modes of solving. In "Quick Solve" mode the computer takes steps at its maximum speed. Steps are not visualized, only the final result is displayed. Even the slowest MorphOS machine (which is Efika 5200B running at 400 MHz) is able to take about 20 000 steps per second. This number of steps should be enough to solve any sudoku. The second mode is "Live Solve". In this mode the program takes only 50 steps per second and updates sudoku after every step. A complete solution may take several minutes in this mode. On the other hand it takes very low amount of computing power, so it can run in the background.

Two other options are for users, who prefer to solve sudoku manually, but sometimes need some hint. Sudominator can show a single field of solution, either random, or selected one. To do this, the program solves the whole puzzle, but reveals only the single field. Sudominator also verifies sudoku correctness and displays wrongly filled fields. Saving and loading sudoku helps in manual solving too as backtrace points may be stored on disk. Additionally sudoku may be copied to the clipoard and pasted in another application as text.

The Algorithm

Sudominator uses the brute-force class algorithm, which replaces human intelect with computer ability to perform repeated simple computations very fast. The program just tries every possible number in every possible position as long as it conforms sudoku rules. The implementation is recursive – after entering a number in a field, the solver just calls itself, while storing the history of moves on the stack. If the solver encounters an unresolvable condition (no number can be entered in an empty field without breaking rules), it means some previous moves were wrong, so it steps back and tries another way.

A plain brute-force algorithm will just take the next or random free field when making a new step. But here is the place for optimization. Sudominator, instead of just getting nearest free field, searches for the most constrained one. For a given field, every other, already filled field in the same row, column or 3×3 square imposes a constraint on the field. In other words other fields can limit our choice of numbers to try. Sudominator always steps into a field where this choice is limited most, so the width of a search tree following current step is narrowed as much as possible. It resembles a bit typical strategy of a human player.

Of course I do not consider this optimization as my achievement. The idea is rather obvious and while I've got it myself, I guess many programmers invented it independently, so it is rather a common knowledge. Neverthless it speeds solving up significantly.