Sudominator 0.1 for MorphOS

[krashan]

Sudominator is a fast sudoku puzzle solver. It has a comfortable MUI based graphical interface. Thanks to optimized brute-force algorithm it solves any resolvable sudoku in a fraction of second, even on slow machines. The second, "live solve" mode allows for watching how the program solves the puzzle (every step is displayed at a rate of 50 steps per second). The program is distributed with the source code and can be downloaded from MorphOS Files.

[krashan]

This program has been written to show some person that solving sudoku manually is just waste of time. It also has been written just for the fun of programming of course :-). Once I've written the algorithm (running in shell) I've decided that wrapping it with some nice GUI may be fun. And it was indeed :-).

[krashan]

The sort of thing thats easier to work out with pen and paper than it would writing a tight algorithim to do it.

I've implemented the first version (shell based, sudoku initial state had to be entered in the code before compilation) in 30 minutes. I guess solving an usual sudoku with pencil and paper takes similar amount of time. But look, instead of solving one, I've solved all 6 670 903 752 021 072 936 960 possible in one go! ;-)

[krashan]

Do you have to do any research or did you just work it all out yourself.

I've designed the algorithm myself, since it is rather obvious. The algorithm is based on recursion and is a brute-force one. It means it checks all possibilities until it finds a solution. The thing starts from finding an empty field, which is most constrained by already entered numbers. Then the program tries to enter numbers from 1 to 9 into the field and checks if resulting partial solution is valid. If it is not, the algorithm steps back. If it is, the routine calls itself recursively, taking the next most constrained field.

The algorithm either finds that there are no more empty fields (which means the sudoku is solved), or steps back to its root call (which means the starting position is unresolvable).

I've found this algorithm to be very fast. Testing different sudoku, I've found that no more than 50 000 steps are needed usually. Even my poor Efika @ 400 MHz needs less than 100 miliseconds to do it.

[krashan]

Cool! The next step should be a solvable puzzle generator of varying difficulty

It requires some strict definition of sudoku difficulty first...

[krashan]

Wouldnt it relate to how many numbers are given to start?

It is related, but not linearly. Sudoku with very few numbers are easier, as they have very high number of solutions. Adding more numbers will make them harder. Minimal quantity of numbers giving an unique solution is estimated to be between 17 and 19, probably these are the hardest to solve. Adding more numbers will make them easier again.