The New Sudoku Players' Forum

[igustin]

I wrote a solver program for Sudoku in pure standard C on Linux, but it can be compiled on any Linux, Unix, BSD, DOS, Windows or Mac platform because it doesn't use any GUI or any other platform specific function. It is about 200 lines, including empty lines, comments and messages, and about 12Kb compiled on Linux.

Simple problems are solved under 1 second (about 300-600 steps), medium problems are solved for about 1 second (about 10.000 steps). The hardest problem I've found took about 5 second (about 230.000 steps). Test machine was Pentium III 600 MHz, so on P4 will be much faster.

Program can print out just a solution, or can display explanation message on every single atomic step it takes. So it is very good for learning how to solve Sudoku problems. For simple problems it prints out about few thousands lines, and for the hardest problem prints out over 1 milion lines of solving process.

Anybody interested?

[angusj]

for the hardest problem prints out over 1 milion lines of solving process. Anybody interested?

LOL

[simes]

...prints out over 1 milion lines of solving process

Crikey! You must go the long way around!:D

[igustin]

LOL

I know that is huge output (this is the worst case I ever generated for 230 thousands iterations on hardest problem found), but the quantity of output messages can easily be changed, and doesn't be such detailed.

Anyway, you don't need to read all output. You can scroll through output and analyze just some part of it. Anybody who saw that describing output was more satisfied in educational manner than watching GUI programs solving Sudoku by putting numbers in fields without explanation.

[igustin]

Crikey! You must go the long way around!

No, I am pretty sure that algorithm is very good and fast. Most problems are solved within a second (without printing out solving process).

The output can be long because program prints out explanation of every small step it done and why, so beginners can understand solving process.

[simes]

Could you post a small example of the output? I'm wondering how a million lines of anything can be helpful.

In all those lines, are there some that are more useful than others?

[igustin]

Could you post a small example of the output?

Of course. But give me some time to translate those messages to english, because it is on my native language now (Croatian). Those messages are something like this:

Field (0,0) is fixed, going to next field.
Field (0,1) is free, finding possible value for that field.
Trying to set value 1 to field (0,1).
Value 1 is not in row 0.
Value 1 is in column 0.
Trying to set value 2 to field (0,1).
Value 2 is not in row 0.
Value 2 is not in column 0.
Value 2 is not in smaller box.
Assigning value 2 to field (0,1), and going to next field.
...
There is no possible values left for field (0,2), so going back to previous field.

...


As you can see, those are very detailed atomic informations, and I found it more informative than just getting solved hints without explanation.

I'm wondering how a million lines of anything can be helpful.

Why it is so strange? Don't take word "million" as is. There is just about 20 possible messages depending of situation and phase of solving, and each iteration or step (in sense of how my program works) of solving prints just 5-10 messages. Huge output is just a result of many iterations which multiplies the same messages but for another cell, or because of returning to previous cells for changing to another value. For simple problems, there is just few hundreds lines. Hard problems has many possible values for more free cells, and that generates many iterations/steps, and so there is many output lines.

I am not saying that my algorithm is the best and the fastest. I am not using any advanced logic. It is just fast enough on old CPU and works fine for me. In my humble opinion and many years of programming experience - I think it works acceptable for situation. If I have more spare time, I'd try to optimize it.

In the contrast to your program I saw at your Web page which solves majority puzzles, my program doesn't stuck for any problem I tried. Every Sudoku puzzle problem I found at paper and on the Web and try to solve with my program was solved.

For example, for few last Sudoku problems published in The Times, I got following results (Pentium III 600):
Problem No. 173, June 17, fiendish: 0.584 seconds; 29,796 iterations; 149,094 lines of output
Problem No. 175, June 20, easy: 0.014 seconds; 568 iterations; 3,053 lines of output
Problem No. 180, June 22, fiendish: 0.371 seconds; 17,696 iterations; 91,932 lines of output
Problem No. 181, June 23, mild: 0.031 seconds; 1,536 iterations; 7,721 lines of output
Problem No. 182, June 23, fiendish: 14.855 seconds; 724,106 iterations; 3,696,289 lines of output (now I have new record!)
Problem No. 183, June 24, difficult: 1.013 seconds; 49,565 iterations; 249,301 lines of output
Problem No. 184, June 24, fiendish: 8.275 seconds; 399,384 iterations; 2,060,129 lines

In all those lines, are there some that are more useful than others?

Of course, there is some messages that are understandable without explicitly printing it out. I can make some sort of levels of messages, so there can be much fewer output lines. I didn't plan to make such huge output at the first place. I used those messages just for testing and debugging during development, but I liked it at the end and I left it and made more readable.

I can't see what is the problem with number of output lines - you can switch it off and you will see just the final solution. The point is that my program solves every Sudoku problem in short time, and works on every OS platform.

[simes]

...can display explanation message on every single atomic step it takes. So it is very good for learning how to solve Sudoku problems.

Well not really. Not at all in fact. Unless somebody wants to perform a brute force approach manually. People, being much slower than computers, tend to think about things, look for patterns, make logical deductions, rather than try every possible combination until they stumble across one that fits.

I can't see what is the problem with number of output lines

There's no problem with the number of lines at all... unless you claim it's a useful explanation that'll help people understand how to solve Sudoku.

The point is that my program solves every Sudoku problem in short time

Congratulations!

[simes]

For the sake of completeness, I thought I'd include similar stats:

Code: Select all

173: < 0.1 seconds, 57 lines of output
174: < 0.1 seconds, 57 lines
175: < 0.1 seconds, 47 lines
176: < 0.1 seconds, 58 lines
177: < 0.1 seconds, 55 lines
178: < 0.1 seconds, 55 lines
179: < 0.1 seconds, 53 lines
180: < 0.1 seconds, 60 lines
181: < 0.1 seconds, 55 lines
182: < 0.1 seconds, 57 lines
183: < 0.1 seconds, 53 lines
184: < 0.1 seconds, 61 lines

(On a 1.8GHz machine)

This is timing the solver only - it takes a little longer when the screen is updated to show the solving as it happens. Now, given a choice, I know which logs I'd rather examine.