The New Sudoku Players' Forum

[zhouyundong_2012]

I come back to setbb.

I have written a solver 2 years ago, it can solve every "17 sodoku" in 200 us average.(2.8G CPU)

But Now, I inprove my solver, It only use 12us to solve every "17 sodoku" average.(2.8G CPU)

Are you still here? My friend,Briturner.


I think my solver is very fast.

[zhouyundong_2012]

Maybe one day I will diliver my source code here, but not now.Now I must keep it secret, because I will improve my GT/LT Solver.


I Promiss what I said is truth.


I have tested 30000 questions:
Read File To Stack AllBoard[30000][81]. Filename: 17 sodoku
Set Process Priority(Toppest)
Set Thread Priority(Toppest)

Get Frequency
Get Start Counter

Test();



Get End Counter


GetTime

[zhouyundong_2012]

Total Case: 30000
Spend Time: 360154 us
Average: 12.005us
Answer Attribute: All Uniq Answer


It also give the result "The total 30000 questions are Uniq Answer".



I also Test case such like:
000000000000000100000000000000000000000000000000000000300000000000020000000000000 : More Answer
110000000000000000000000000000000000000000000000000000300000000000020000000000000 : No Answer 8us
It seems to the question( more answer or no answer), it is very fast too.

[ronk]

I come back to setbb.
...
Are you still here? My friend,Briturner.

This is not the setbb forum and AFAIK Brian Turner does not frequent this forum.

[zhouyundong_2012]

Thanks,
I haven't come here for 2 years.
I don't know the fastest solver.
I want to know the fastest solver.
zhouyundong

[JasonLion]

Which solver is fastest depends somewhat on what you are testing for. Do you want to verify uniqueness or just find a solution? Do you want to be fast at identifying puzzles with no solutions, or can that be a little slower as long as puzzles with solutions solve quickly. And so on.

The three fastest solvers known are BBSolve, fsss, and JSolve. Each is fastest by some measures and not by others. The best discussion of high speed solving is in this topic over at the Programmers Forum, though it does get quite technical.

I don't know which CPU you have. CPU speed doesn't really go by MHz any more, so you can't make comparisons knowing only the MHz. In any case, if I understand your timings correctly, your times are very respectable, certainly close to the three solvers I mentioned above. You might want to try out your solver on some of the other sets of puzzles mentioned in the topic I pointed to.

[zhouyundong_2012]

Thanks,
"The best discussion of high speed solving is in this topic over at the Programmers Forum, though it does get quite technical."
I went to http://www.programmingforums.org/search ... rocess,but I couldn't find "this topic".
I went to http://www.setbb.com/phpbb/?mforum=sudoku, Can't open the page.

[zhouyundong_2012]

In my program,I have tried to use Cross Method, but it is slower,So I get rid of Cross Method.
The methods what I use are only
SingleGrid In One Palace, SingleRow In One Palace, Single Column In One Palace, Double Column In One Palace, UniqRow In One Line

Method: SingleGrid, SingleRow, SingleColumn, DoubleColumn, UniqRow, Guess and Rollback.


2 years age, I insisted my program algrithim, but I could only reach 200us.

Because there were One Difficult Problem in Guess.

One Month age, I tried to solve this problem, but I failed.

I open the directory"The Saved 3grid Soul", I told myself, it's the last time to research it.

When I prepared to Give up, I raised my head. I Found something shining in my eyes! I got it!

When I rased my head when I thought of it, I got a NEW way to solve this problem.

In two weeks,
I improved my solver From 24us->23.5us->23us->22.5us->22us->21.5us->21us->20.5us->20us->19us->18.5us->18us......->11.8us
(2.8G general CPU(Intel),Single Core) testcase: 17sudoku , Get Answer And At the Same time Get Uniqueness. such as 0: NoAnswer, 1:UniqAnswer, 2:MoreAnswer



The code is very "Simple" and very easy to comprehense.

[zhouyundong_2012]

This morning I thought something about GT/LT. I Got a method to improve the method written 2 years age by me.

Code: Select all

A>B>C
  V V
  D>E

if A,B,C,D,E are all in the same Palace,
I called E's LGrade is 0, D' LGrade is 1, C's LGrade is 1, B's LGrade is 3, A's LGrade is 4

First, E can't be 6,7,8,9
So I will write: Suggest they are in the top(27) of Board(81)
F[(6-1)*3+0] And= TblBoard_Vertial[Vertical[i]];
F[(7-1)*3+0] And= TblBoard_Vertial[Vertical[i]];
F[(8-1)*3+0] And= TblBoard_Vertial[Vertical[i]];
F[(9-1)*3+0] And= TblBoard_Vertial[Vertical[i]];

[tarek]

Hi zhouyundong_2012,

I remeber some of the exchanges between you & b_turner 2 years ago, very annoying!!!

Here is the the link that you need to copy & paste into your browser.

http://www.setbb.com/phpbb/viewtopic.php?mforum=sudoku&p=11913

if A,B,C,D,E are all in the same Palace

Another fantastic term!!!

[zhouyundong_2012]

hi,tarek,
Why annoying?
What does Exchanges mean?

Thanks,
After I use proxy, I can browse setbb.

[zhouyundong_2012]

I tried to solve some of top50000.
top30000, use 782ms ,each 26us 2.2G (Double Core)

[zhouyundong_2012]

I compile my program with c++, I think if I use C ,it will faster a little. maybe 11.4us for 17sudoku. now 11.8us

[zhouyundong_2012]

Code: Select all

[code][/code]

mine is:

Code: Select all

//获取频率
   LARGE_INTEGER Frequency;
   ::QueryPerformanceFrequency(&Frequency);

   //开始时间
   LARGE_INTEGER start;
   ::QueryPerformanceCounter(&start);

   byte Answer = 0;
   //计算过程
   for (int i = 0; i < TestCaseNumber; i++)
   {
      memcpy(Board, AllBoard[i], 81);
      InitSodoku();
      if ((Answer = Calculate()) != UniqAnswer)
         break;
   }

   //结束时间
   LARGE_INTEGER stop;
   ::QueryPerformanceCounter(&stop);

   double spend = (double)(stop.QuadPart - start.QuadPart) / (double)Frequency.QuadPart - TimeBackground;

[zhouyundong_2012]

My source code is very readable, short , very easy to comprehense.

If I post my source code here, all improvement belongs to me , ok?

some of it:
SingleColumn DoubleColumn

Code: Select all

   for (int B = 0; B < 27; B += 3)
   {
      int C0 = FULL_TO_COLUMN(F[B]);
      int C1 = FULL_TO_COLUMN(F[B + 1]);
      int C2 = FULL_TO_COLUMN(F[B + 2]);
      F[B]     &= TblMaskSingle[C1] & TblMaskSingle[C2] & TblMaskDouble[C1 | C2];
      F[B + 1] &= TblMaskSingle[C0] & TblMaskSingle[C2] & TblMaskDouble[C0 | C2];
      F[B + 2] &= TblMaskSingle[C0] & TblMaskSingle[C1] & TblMaskDouble[C0 | C1];
   }

SingleRow

Code: Select all

   int Mask;
   for (int B = 0; B < 27; B++)
   {
      if (G[Index - 1].F[B] == F[B])
         continue;
      int FullMask = F[B];
      if ((Mask = HIGH_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblPalace_Row[Mask] + 2];
      if ((Mask = MID_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblPalace_Row[Mask] + 1];
      if ((Mask = LOW_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblPalace_Row[Mask]];
   }