3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Programs which generate, solve, and analyze Sudoku puzzles

3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Fri Feb 10, 2012 10:50 pm

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.
Last edited by zhouyundong_2012 on Sun Oct 28, 2012 4:16 am, edited 1 time in total.
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Fri Feb 10, 2012 11:00 pm

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
 
Posts: 138
Joined: 10 February 2012

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Fri Feb 10, 2012 11:13 pm

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.
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby ronk » Sat Feb 11, 2012 12:05 am

zhouyundong_2012 wrote: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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Sat Feb 11, 2012 7:56 am

Thanks,
I haven't come here for 2 years.
I don't know the fastest solver.
I want to know the fastest solver.
zhouyundong
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby JasonLion » Sat Feb 11, 2012 5:20 pm

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.
User avatar
JasonLion
2017 Supporter
 
Posts: 621
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Sun Feb 12, 2012 2:47 am

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
 
Posts: 138
Joined: 10 February 2012

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Sun Feb 12, 2012 4:23 am

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
 
Posts: 138
Joined: 10 February 2012

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Sun Feb 12, 2012 4:42 am

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]];
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby tarek » Sun Feb 12, 2012 9:21 am

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

zhouyundong_2012 wrote:if A,B,C,D,E are all in the same Palace
Another fantastic term!!!
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Sun Feb 12, 2012 1:57 pm

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

Thanks,
After I use proxy, I can browse setbb.
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Sun Feb 12, 2012 3:32 pm

I tried to solve some of top50000.
top30000, use 782ms ,each 26us 2.2G (Double Core)
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Sun Feb 12, 2012 3:36 pm

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
 
Posts: 138
Joined: 10 February 2012

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Sun Feb 12, 2012 3:42 pm

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
 
Posts: 138
Joined: 10 February 2012

Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Sun Feb 12, 2012 3:56 pm

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]];
   }
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

Next

Return to Software