The New Sudoku Players' Forum

[bobkart]

Okay Tom the QueryPerformance calls work fine with my C Compiler. On my 1.8GHz Pentium 4 Sony Viao, the frequency of the counter is 3.579545MHz, which seems to be a common number. On my 2.8GHz Pentium 4 2U Rackmount system, the frequency of the counter is 2.8GHz, same as the CPU. Just FYI.

Here are the performance numbers for the four tests I have, yours being the fourth one (on the 2.8GHz machine):

input1: 101 recursions, 0.117ms
input2: 7,390 recursions, 3.613ms
input3: 19,206 recursions, 8.988ms
input4: 2,484,424 recursions, 1190ms

So it looks like I have some work to do if I want to get close to your 36ms time!

[bobkart]

Alright guys, new results are in.

First I made some minor spot improvements to the efficiency:

input1: 0.055ms (101 recursions)
input2: 3.156ms (7,390 recursions)
input3: 7.992ms (19,206 recursions)
input4: 1030ms (2,482,424 recursions)

No change in the number of recursions from the original timings just above this post. So that's maybe a 15% improvement over the initial results.

Then I revised the algorithm, prefilling vacancies with only one possibility helped with the first three puzzles but not Tom's tough one (what I'm calling input4), so I abandonded that idea. What ended up working was clue 3# in Tom's earlier post, when you make a tentative move, make sure you have not made any remaining vacancies impossible to fill before you "recurse". I also realize now that this is what simes was trying to tell datprogrammer on the first page of this Topic:

input1: 0.150ms (63 recursions)
input2: 2.777ms (3056 recursions)
input3: 4.125ms (4139 recursions)
input4: 460ms (514,771 recursions)

So more than 50% improvement in runtime on the tough problem. And about 80% of the recursions were pruned in that situation too.

Then I realized I was doing an exhaustive search, finding all possible solutions, when you guys were probably stopping at the first solution. Rerunning the above set of tests without an exhaustive search yielded these even better results:

Original algorithm:
input1: 0.047ms (88 recursions)
input2: 0.860ms (1,974 recursions)
input3: 0.842ms (2,003 recursions)
input4: 394ms (939,409 recursions)

Revised algorithm:
input1: 0.140ms (59 recursions)
input2: 0.833ms (836 recursions)
input3: 0.714ms (599 recursions)
input4: 185ms (212,610 recursions)

That last number (185ms) doesn't look nearly as bad as 1190ms did in the initial timings. About a 6X improvement, just need another 5X to get near Tom's amazing 36ms.

[Eddard]

Hi there, I am new here but my father has been solving it for some time and he's been killing himself for some time so I made him a program:

I did it in c++ ofcourse using recursion and it works quite fast because i made good use of memory..
Although it is long, it is fast and certanly quicker than 10^8 which is one second...
It reads from a file and writes in it

These arrays tell if a number is already in a row, column, or a part square:
bool BeenRow[9][10];
bool BeenCol[9][10];
bool BeenCube[9][10];

and the recursion is a bit longer:


void Rek ( int Num ) {
int Row = Num / 9;
int Col = Num % 9;
int Cube = 3*(Num/27)+(Num%9)/3;

if ( Num == 81 ) {
fprintf(out, "Rjesenje je : \n");
for ( int i = 0 ; i < 9 ; i++, fprintf(out, "\n") )
for ( int j = 0 ; j < 9 ; j++ )
fprintf(out, "%d ", Table[i][j]);

exit(0);
}
else if (Table[Row][Col] != 0)
Rek(Num+1);
else {
for ( int i = 1 ; i < 10 ; i++ )
if (BeenRow[Row][i] == 0 && BeenCol[Col][i] == 0 && BeenCube[Cube][i] == 0 ){
BeenRow[Row][i] = 1;
BeenCol[Col][i] = 1;
BeenCube[Cube][i] = 1;
Table[Row][Col] = i;

Rek(Num+1);

BeenRow[Row][i] = 0;
BeenCol[Col][i] = 0;
BeenCube[Cube][i] = 0;
Table[Row][Col] = 0;
}
}
}

Other is #include, input, and output..
So what do you think?

[/list]

[Eddard]

and... FYI:
i didn't watch you're posts before or anyones so that you think I got this from you..
and i didn't need to improve it so.. in my opiniion it's good for a 15 year old programmer

[Tom Wirschell]

They recently put Sudoku puzzles in the dutch newspaper 'De Telegraaf' where it piqued my interest. Solved a couple by hand and figured this was just _begging_ for a computerised solver.
After having my dad claim it was impossible (heh), I had all the incentive to get to work.

The end result is here: http://www.wirschell.nl/sdk.c
It's a bit crude because it has the input puzzle hardcoded. I'll work on that a bit.

What seems to differentiate my solver from the ones discussed in this thread is that mine isn't recursive, and doesn't brute-force. Instead, it uses the puzzle's logic to solve the thing.

Oh, and like the other solvers discussed here, it's mindnumbingly fast. I made the program repeat the same puzzle 1000 times and used the UNIX 'time' program to see how fast it was. Result: real 0m0.294s
300ms for 1000 (!!) puzzles on an Athlon XP 2200+.
The solver needed 3 iterations to complete the puzzle, where one iteration means
- Fill in fields that can only have 1 value.
- Fill in row fields that can only have 1 value in the context of the row.
- Fill in column fields that can only have 1 value in the context of the column.
- Fill in block fields that can only have 1 value in the context of the block.
The puzzle used was the one on the screen shot here.

Since my solver doesn't guess, the difficult puzzle Tom posted which his program solved in 36 ms cannot be solved by my program. I don't blame it, though, because I can't see how any human could solve that one, and in fact I wonder if that puzzle really has only 1 solution (think you could test that for me?).

Kind regards,

Tom Wirschell

[Tom Wirschell]

Looks like I need to add a bit more (and more difficult) logic to the solver.

The puzzle posted in this thread can't be solved by my program in its current form. I'm having a hard time solving the puzzle manually, but the hint provided in that thread is the logic rule I need to figure out how to add.

Damn you, pappocom! ;)

Kind regards,

Tom Wirschell

[simes]

Both of these puzzles can be solved without trial and error. (If you don't believe this, download my solver, enter the puzzle, press the solve button, then view the log - it'll show you why each number was entered.)

The simpler techniques you describe will only solve the "easier" puzzles, but the harder ones require more advanced techniques.

You might like to take a look at theprogrammer's forum.

[bobkart]

Since my solver doesn't guess, the difficult puzzle Tom posted which his program solved in 36 ms cannot be solved by my program. I don't blame it, though, because I can't see how any human could solve that one, and in fact I wonder if that puzzle really has only 1 solution (think you could test that for me?).

I can confirm (to the extent that my solver doesn't have a bug) that Tom's "36ms" puzzle has but one solution. My solver was initially developed to find all solutions, and was later extended to have a flag that makes it stop after find the first (and typically only) solution.

To address your lack of recursion, indeed if you are not doing Trial and Error, recursion is not applicable, since there will be no need to backtrack. Backtracking can of course be achieved without resorting to recursion, it's just usually easier with recursion since you get the natural stacking behavior of the language's function call mechanism. But since in general, Trial and Error is called for, and certainly is for Tom's "36ms" puzzle (there are at least 3 possible values for each initial vacancy), any program that cannot handle backtracking will not be able to solve all problems.

EDIT: I see simes is saying that Trial and Error is not required to solve Tom's "36ms" puzzle, at least that's what I think he is saying. That could be true if you are able to further restrict the possible values in each vacancy beyond the obvious restriction that the value does not appear in the same row, column, and grid. As a newcomer to Sudoku, and Sudoku solvers, I am not familiar with such advanced (for me anyway) techniques. The one technique that simes suggested, which I did incorporate into my solver, is that of looking ahead to make sure a proposed value for a vacancy does not reduce the number of possibilities in any of the remaining vacancies to zero. Considerably fewer possibilities were tried as a result of that extension.

[simes]

Both of these puzzles can be solved without trial and error.

EDIT: I see simes is saying that Trial and Error is not required to solve Tom's "36ms" puzzle, at least that's what I think he is saying.

Eh? I though that was pretty clear and unambioguous!

[bobkart]

Wasn't sure which "these puzzles" you were referring to. Thanks for clearing it up!

Now if I could just get a clue as to how Tom's "36ms" puzzle can be solved without resorting to Trial and Error . . .

[simes]

Now if I could just get a clue as to how Tom's "36ms" puzzle can be solved without resorting to Trial and Error . . .

did you mean this one?

Code: Select all

+---+---+---+
|...|.1.|78.|
|5..|..9|...|
|...|...|.4.|
+---+---+---+
|.26|...|...|
|...|6..|..3|
|.74|.8.|...|
+---+---+---+
|...|..3|..2|
|.8.|.4.|.1.|
|6..|5..|...|
+---+---+---+


Code: Select all

Note: Cell coordinates are in (row,column) format with (1,1) at top-left and (9,9) at bottom-right.
block 4: column 1 must contain 3, removing 3 from candidates for cell(s) (1,1)(3,1)(8,1)
block 4: row 5 must contain 5, removing 5 from candidates for cell(s) (5,5)(5,6)(5,7)(5,8)
column 9: unique subset 48 in cells (4,9)(9,9) - removing other candidates for these cells
(8,9) = 7 : only cell in column 9 that can contain 7
row 8: disjoint subset 29 in cells (8,1)(8,4) - updating candidates for cell(s) (8,3)(8,6)(8,7)
(8,6) = 6 : only possible value for this cell
block 8: unique subset 18 in cells (7,4)(9,6) - removing other candidates for these cells
block 8: column 5 must contain 7, removing 7 from candidates for cell(s) (2,5)(3,5)(4,5)(5,5)
row 2: unique subset 78 in cells (2,3)(2,4) - removing other candidates for these cells
(2,2) = 4 : only cell in row 2 that can contain 4
(7,1) = 4 : only cell in column 1 that can contain 4
(3,1) = 7 : only cell in column 1 that can contain 7
(2,4) = 7 : only cell in block 2 that can contain 7
(2,3) = 8 : only possible value for this cell
block 1: row 3 must contain 1, removing 1 from candidates for cell(s) (3,7)(3,9)
blocks 1 and 7 must contain 1 in columns 2 and 3 - removing 1 from candidates for cell(s) (5,2)(5,3)
row 5: disjoint subset 59 in cells (5,2)(5,3) - updating candidates for cell(s) (5,1)(5,5)(5,7)(5,8)
(5,5) = 2 : only possible value for this cell
...etc...


[noeldillabough]

Here's a chunk of code, it solves any board ~instantly; I fed it a few thousand boards to test it and it averaged 35 boards per second, the more pieces on the board the faster it is:

The function GetGridStates returns a list of sorted empty spaces, PickPiece picks a legal move and then its a matter of adding it to a list that can be unrolled if the move ends up in failure. GetBestState returns a random placement from the best placements (ie if 10 places have 2 possibilities it will return one of them randomly)

while(GetGridStates(lstStates,GRID_ADD,TRUE)) {
pState=GetBestState(lstStates);
if(pState->m_nMoves) {
nPiece=PickPiece(pState->m_nPos);
lstMoves.AddTail(new CKFullMove(*this,nPiece,pState->m_nPos));
PlacePiece(nPiece,pState->m_nPos);
} else {
if(lstMoves.IsEmpty()) return FALSE;
pMove=(CKFullMove*)lstMoves.RemoveTail();
*this=pMove->m_board;
SetFlag(pMove->m_nPos,pMove->m_nPiece,FALSE);
delete pMove;
}
}

Sorry I don't know how to indent but you can paste it into a code window.

[Tom]

See my new thread in this forum...

Basically, my time of 36ms has been reduced to 7ms with a new logic rule (28 lines of code).

....1.78.5....9..........4..26.........6....3.74.8.........3..2.8..4..1.6..5.....

http://www.mottosearch.com/sudoku/

-Tom

[kat]

that website and programme are great