Sudominator logo
Fast and versatile sudoku solver
Grzegorz Kraszewski

Su­dom­i­na­tor is a pro­gram for au­to­matic su­doku solv­ing or as­sist­ing in man­ual solv­ing. Su­doku is a pop­u­lar, Japan­ese math­e­matic puz­zle. Su­dom­i­na­tor runs on Mor­phOS op­er­at­ing sys­tem, the Ami­gaOS suc­ces­sor. To solve a su­doku, Su­dom­i­na­tor uses brute-force al­go­rithm aug­mented with dy­namic nar­row­ing of the search tree. This tech­nique en­sures that every solv­able su­doku will be solved, on the other hand it takes a frac­tion of sec­ond even on mod­er­ate speed com­put­ers. Su­dom­i­na­tor is a free soft­ware, dis­trib­uted with full source code on the Sim­pli­fied BSD Li­cense. The cur­rent Su­dom­i­na­tor ver­sion is 1.1.

Sudominator solved AI Escargot.
AI Escargot? A piece of cake,
done in 0.4 second.
Live solving running.
Live solve running.


Su­dom­i­na­tor 1.1 (67 kB) for Mor­phOS 2.x+, on Mor­phOS Files. The source code is in­cluded in­side the archive.


The main fea­ture of Su­dom­i­na­tor is au­to­matic su­doku solv­ing. There are two modes of solv­ing. In "Quick Solve" mode the com­puter takes steps at its max­i­mum speed. Steps are not vi­su­al­ized, only the final re­sult is dis­played. Even the slow­est Mor­phOS ma­chine (which is Efika 5200B run­ning at 400 MHz) is able to take about 20 000 steps per sec­ond. This num­ber of steps should be enough to solve any su­doku. The sec­ond mode is "Live Solve". In this mode the pro­gram takes only 50 steps per sec­ond and up­dates su­doku after every step. A com­plete so­lu­tion may take sev­eral min­utes in this mode. On the other hand it takes very low amount of com­put­ing power, so it can run in the back­ground.

Two other op­tions are for users, who pre­fer to solve su­doku man­u­ally, but some­times need some hint. Su­dom­i­na­tor can show a sin­gle field of so­lu­tion, ei­ther ran­dom, or se­lected one. To do this, the pro­gram solves the whole puz­zle, but re­veals only the sin­gle field. Su­dom­i­na­tor also ver­i­fies su­doku cor­rect­ness and dis­plays wrongly filled fields. Sav­ing and load­ing su­doku helps in man­ual solv­ing too as back­trace points may be stored on disk. Ad­di­tion­ally su­doku may be copied to the clipoard and pasted in an­other ap­pli­ca­tion as text.

The Algorithm

Su­dom­i­na­tor uses the brute-force class al­go­rithm, which re­places human in­t­elect with com­puter abil­ity to per­form re­peated sim­ple com­pu­ta­tions very fast. The pro­gram just tries every pos­si­ble num­ber in every pos­si­ble po­si­tion as long as it con­forms su­doku rules. The im­ple­men­ta­tion is re­cur­sive – after en­ter­ing a num­ber in a field, the solver just calls it­self, while stor­ing the his­tory of moves on the stack. If the solver en­coun­ters an un­re­solv­able con­di­tion (no num­ber can be en­tered in an empty field with­out break­ing rules), it means some pre­vi­ous moves were wrong, so it steps back and tries an­other way.

A plain brute-force al­go­rithm will just take the next or ran­dom free field when mak­ing a new step. But here is the place for op­ti­miza­tion. Su­dom­i­na­tor, in­stead of just get­ting the near­est free field, searches for the most con­strained one. For a given field, every other, al­ready filled field in the same row, col­umn or 3×3 square im­poses a con­straint on the field. In other words other fields can limit our choice of num­bers to try. Su­dom­i­na­tor al­ways steps into a field where this choice is lim­ited most, so the width of the search tree fol­low­ing cur­rent step is nar­rowed as much as pos­si­ble. It re­sem­bles a bit typ­i­cal strat­egy of a human player.

Of course I do not con­sider this op­ti­miza­tion as my achieve­ment. The idea is rather ob­vi­ous and while I've got it my­self, I guess many pro­gram­mers in­vented it in­de­pen­dently, so it is rather a com­mon knowl­edge. Nev­erth­less it speeds solv­ing up sig­nif­i­cantly.


Last updated: 30 Dec 2015.