Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Bit Based Sudoku Solver (BB_Sudoku) V0.5
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Wed Nov 26, 2008 6:27 pm    Post subject: Reply with quote

briturner wrote:
Greetings all,

Thanks for all the comments. v05 is now available http://tttarabians.com/sudoku/BB_Sudoku_v05.zip

brit



Hi Brit

Could you implement in your next version an option to save the output in a disk file? Very usefull for people searching for valid grids in a big batch of sudokus.

Thank you very much


Last edited by ChPicard on Thu Nov 27, 2008 11:44 am; edited 1 time in total
Back to top
View user's profile Send private message
zerothbase

Joined: 02 Nov 2008
Posts: 17
:

Items
PostPosted: Thu Nov 27, 2008 3:25 am    Post subject: Reply with quote

Quote:
Would it be possible for you to post a collection of internal trial puzzles from a removing clues style solver?


Sure!

Though fundamentally, a removing clues style generator always contains a valid puzzle - and tries to remove clues one-by-one. Thus you could take any collection of fully-reduced valid puzzles and simply remove a single random clue from each to get the invalid, internal state of a removing generator.

Here is a collection of ~600,000 random reduced puzzles I generated last night (all with unique solutions): puzzles.zip
And here is the same collection with a single random clue removed from each puzzle (guaranteeing multiple solutions): multiPuzz.zip

I haven't done any analysis on the valid puzzles other than reducing them as much as I could and making sure they couldn't be solved by hidden/naked singles alone. I used lrand48() for all my random numbers so I expect they are fairly random.

--Zerothbase
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Sat Nov 29, 2008 3:03 pm    Post subject: Reply with quote

JasonLion wrote:
Would it be possible for you to post a collection of internal trial puzzles from a removing clues style solver?

the -gg option of my solver produces a pseudo-random stream of solution grids for use by remove-a-clue generators
the -gg option of my solver produces a pseudo-random stream of puzzles using the add-a-clue method that starts with a solution grid and adds clues consistent with the solution grid
Back to top
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Sun Nov 30, 2008 5:33 am    Post subject: Reply with quote

gsf wrote:
JasonLion wrote:
Would it be possible for you to post a collection of internal trial puzzles from a removing clues style solver?

the -gg option of my solver produces a pseudo-random stream of solution grids for use by remove-a-clue generators
(edit fixed option typo in next sentence)
the -gp option of my solver produces a pseudo-random stream of puzzles using the add-a-clue method that starts with a solution grid and adds clues consistent with the solution grid
Back to top
View user's profile Send private message Visit poster's website
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Sun Nov 30, 2008 11:23 pm    Post subject: Reply with quote

Greetings,

A couple minor changes have been made, but no real changes made to the solver methodologies. It is at http://tttarabians.com/sudoku/BB_Sudoku_v05b.zip.

There is now options to enable or disable methodologies. Even backtracking can be disabled, though many puzzles would not be solved since many advanced methods are not implemented. For example, with subsets and locked candidates, but no backtracking, only 40534 of 47793 puzzles in the Sudoku 17 can be solved.

Another option is to display the puzzle rather than the solution, which helps with batch processing. For example, using -s2 -t2 -p the output will have the puzzle and if it has a unique solution, and the time needed for each puzzle.

All IO is through the standard IO, but using pipes can use files for both input and output.

These changes have added a slight bit of extra overhead, so timings are just a tad worse, but only by a percent or 2.

I do have a generator working based on this code, but it is still a work in progress, and not included in this build.

brit
Back to top
View user's profile Send private message
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Wed Dec 03, 2008 10:03 am    Post subject: Reply with quote

I have written a new kernel,every time put 3 grids.and guess while no single.
Back to top
View user's profile Send private message Send e-mail
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Mon Dec 08, 2008 4:17 am    Post subject: Reply with quote

give only one answer:
top50000 spends 10seconds
sodoku17 spends 20seconds
Back to top
View user's profile Send private message Send e-mail
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Mon Dec 15, 2008 4:37 pm    Post subject: Reply with quote

Code:

/* Author:zhouyundong*/
///////the 7th kernel///////////
///////every time put 3 numbers,guess while no single////////
///////the idea of guess is learned from briturner//////////
void getAnswer()
{
   int i, j, k;
   int temp, temp2;
   int least;
   int multLeast;
   int leastArea[IndexEnd];
   if(initArea() == false)
   {
      return;
   }
   G[0].SCnt = 0;
   G[0].cntGuessed = 0;
next:
   for(i=G[PIdx].SCnt; i<SCnt; i++)
   {
      if(!update(posStack[i]))
      {
again:      if(--PIdx == -1)
         {
            return;
         }
         least = leastArea[PIdx];
         if(G[PIdx].left[least] == 0)
         {
            goto again;
         }
         SCnt = G[PIdx+1].SCnt;
         multLeast = mult162[least];
         G[PIdx].area[multLeast] = G[PIdx].area[multLeast+G[PIdx].cntGuessed++];
         posStack[SCnt] = least;
         valueStack[SCnt++] = G[PIdx].area[multLeast];
         for(j=0; j<27; j++)
         {
            temp = G[PIdx].left[j];
            G[PIdx+1].left[j] = temp;
            temp2 = mult162[j];
            for(k=0; k<temp; k++)
            {
               G[PIdx+1].area[temp2+k] = G[PIdx].area[temp2+k];
            }
         }
         G[PIdx].left[least]--;
         PIdx++;
         G[PIdx].left[least] = 1;
         G[PIdx].cntGuessed = 0;
         G[PIdx].SCnt = SCnt-1;
         goto next;
      }
   }
   if(i == 27)
   {
      if(flagAnswer == 0)
      {
         flagAnswer = 1;
         if(underQuestion == 0)
         {
            stackToBoard(); // valueStack[0,1,2] to board[posStack[0,1,2]]
            moveBoard('b', 'a'); // board to answerBoard
         }
         goto again;
      }
      else
      {
         flagAnswer = 2;
         return;
      }
   }
   least = 163;
   for(i=0; i<27; i++)
   {
      if(G[PIdx].left[i] < least && G[PIdx].left[i] != 1)
      {
         least = G[PIdx].left[i];
         leastArea[PIdx] = i;
         if(least == 2)
         {
            break;
         }
      }
   }
   least = leastArea[PIdx];
   multLeast = mult162[least];
   G[PIdx].area[multLeast] = G[PIdx].area[multLeast+G[PIdx].cntGuessed++];
   posStack[SCnt] = least;
   valueStack[SCnt++] = G[PIdx].area[multLeast];
   for(j=0; j<27; j++)
   {
      temp = G[PIdx].left[j];
      G[PIdx+1].left[j] = temp;
      temp2 = mult162[j];
      for(k=0; k<temp; k++)
      {
         G[PIdx+1].area[temp2+k] = G[PIdx].area[temp2+k];
      }
   }
   G[PIdx].left[least]--;
   PIdx++;
   G[PIdx].left[least] = 1;
   G[PIdx].cntGuessed = 0;
   G[PIdx].SCnt = SCnt-1;
   goto next;
}
[/code]
Back to top
View user's profile Send private message Send e-mail
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Mon Dec 15, 2008 4:41 pm    Post subject: Reply with quote

Code:

inline bool initArea()
{
   int i, j;
   int value;
   int squareNo;
   int list[81];
   int temp, temp2;
   int pList0, pList1, pList2;
   int listStack0[9], listStack1[9], listStack2[9];
   int p0, p1, p2;
   PIdx = SCnt = flagAnswer = 0;
   for(i=0; i<81; i+=3)
   {
      list[i] = list[i+1] = list[i+2] = 511;
   }
   // board to list[81]
   for(i=0; i<81; i++)
   {
      if((value=board[i]-1) == -1) // board[i] is '0'
      {
         continue;
      }
      squareNo = squareNoTbl[i];
      temp = mult9[value] + squareNo;
      temp2 = ~areaTrans[i];
      for(j=squareNo; j<81; j+=9)
      {
         list[j] = list[j] & temp2;
      }
      list[temp] = areaTrans[i];
      if(mod3[squareNo] == 0)
      {
         list[temp+1] &= areaRow[i];
         list[temp+2] &= areaRow[i];
      }
      else if(mod3[squareNo] == 1)
      {
         list[temp-1] &= areaRow[i];
         list[temp+1] &= areaRow[i];
      }
      else
      {
         list[temp-2] &= areaRow[i];
         list[temp-1] &= areaRow[i];
      }
      if(squareNo < 3)
      {
         list[temp+3] &= areaColumn[i];
         list[temp+6] &= areaColumn[i];
      }
      else if(squareNo < 6)
      {
         list[temp-3] &= areaColumn[i];
         list[temp+3] &= areaColumn[i];
      }
      else
      {
         list[temp-6] &= areaColumn[i];
         list[temp-3] &= areaColumn[i];
      }
   }
   // legal check
   for(i=0; i<81; i++)
   {
      if((value=board[i]-1) != -1 && list[mult9[value]+squareNoTbl[i]] != areaTrans[i])
      {
         return false;
      }
   }
   for(i=0; i<81; i+=3)
   {
      // compress list[81] to pList0, pList1, pList2
      pList0 = pList1 = pList2 = 0;
      while((temp=lastOneTbl[list[i]]) != 9)
      {
         listStack0[pList0++] = temp;
         list[i] = list[i] & ~(1<<temp);
      }
      while((temp=lastOneTbl[list[i+1]]) != 9)
      {
         listStack1[pList1++] = temp;
         list[i+1] = list[i+1] & ~(1<<temp);
      }
      while((temp=lastOneTbl[list[i+2]]) != 9)
      {
         listStack2[pList2++] = temp;
         list[i+2] = list[i+2] & ~(1<<temp);
      }
      // set G[0].area and G[0].left
      G[0].left[divide3[i]] = 0;
      for(p0=0; p0<pList0; p0++)
      {
         for(p1=0; p1<pList1; p1++)
         {
            temp2 = mult81[listStack0[p0]]+mult9[listStack1[p1]];
            for(p2=0; p2<pList2; p2++)
            {
               if((temp=create[temp2+listStack2[p2]]) != 162)
               {
                  G[0].area[mult162[divide3[i]]+G[0].left[divide3[i]]++] = temp;
               }
            }
         }
      }
   }
   for(i=0; i<27; i++)
   {
      if((temp=G[0].left[i]) == 0)
      {
         return false;
      }
      else if(temp == 1)
      {
         PUSHSINGLE(i);
      }
   }
   return true;
}
Back to top
View user's profile Send private message Send e-mail
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Mon Dec 15, 2008 4:43 pm    Post subject: Reply with quote

Code:

inline bool update(int i)
{
   int m, n;
   int thisArea, thatIndex;
   int temp;
   // self check
   thisArea = mult162[G[PIdx].area[mult162[i]]];
   for(m=trim3[i]-3; m<trim3[i]; m++)
   {
      if(m == i)
      {
         continue;
      }
      temp = G[PIdx].left[m];
      for(n=0; n<temp; n++)
      {
         thatIndex = mult162[m] + n;
         if(self[thisArea+G[PIdx].area[thatIndex]])
         {
            G[PIdx].area[thatIndex] = G[PIdx].area[mult162[m]+--temp];
            if(temp == 0)
            {
               return false;
            }
            else if(temp == 1)
            {
               PUSHSINGLE(m);
            }
            n--;
         }
      }
      G[PIdx].left[m] = temp;
   }
   // other check
   for(m=mod3[i]; m<27; m+=3)
   {
      if(m == i)
      {
         continue;
      }
      temp = G[PIdx].left[m];
      for(n=0; n<temp; n++)
      {
         thatIndex = mult162[m] + n;
         if(other[thisArea+G[PIdx].area[thatIndex]])
         {
            G[PIdx].area[thatIndex] = G[PIdx].area[mult162[m]+--temp];
            if(temp == 0)
            {
               return false;
            }
            else if(temp == 1)
            {
               PUSHSINGLE(m);
            }
            n--;
         }
      }
      G[PIdx].left[m] = temp;
   }
   return true;
}

void stackToBoard()
{
   int i;
   int a, b, c;
   int area, value, temp;
   for(i=0; i<27; i++)
   {
      a = decompose0[valueStack[i]];
      b = decompose1[valueStack[i]];
      c = decompose2[valueStack[i]];
      area = mod3[posStack[i]];
      value = posStack[i] / 3 + 1;
      temp = area * 27;
      board[temp+a] = value;
      board[temp+b] = value;
      board[temp+c] = value;
   }
}
#define PUSHSINGLE(i) {posStack[SCnt] = i; valueStack[SCnt++] = G[PIdx].area[mult162[i]];}

#define IndexEnd 41

int posStack[27];
int valueStack[27];
int SCnt;
int PIdx;

struct GameBoard {
   int area[4374];
   int left[27];
   int SCnt;
   int cntGuessed;
} G[IndexEnd];

Back to top
View user's profile Send private message Send e-mail
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Mon Dec 15, 2008 4:55 pm    Post subject: Reply with quote

About Sodoku Sum, some people calls "Killer",I call it "sosum".
GT, I call it "sopare",means sodoku compare.
And one sodoku game with sopare, sosum, I call it somix,it is a mixture of sodoku,sosum,sopare,,,and future,I think diogird, and some other limit method will add to somix.
Here,I broadcast my program(spent 8 days).
its function is to draw dotted line(different colors).
As follows,welcome your advise.
Code:

(o, my , some // is written in Chinese.sorry
////////////////////////&#20197;&#19979;&#19982;&#30011;&#34394;&#32447;&#26694;&#26377;&#20851;////////////////////////
int getDegree(int x, int y, int &flag)
{
   // &#35774;&#32622;flag,&#27714;&#24230;&#25968;
   if(y >= 1 && edge[80+x+y*10])
   {
      flag |= 1;
   }
   if(x <= 8 && edge[x+y*9])
   {
      flag |= 2;
   }
   if(y <8>= 1 && edge[x+y*9-1])
   {
      flag |= 8;
   }
   // &#21482;&#26377;0&#24230;&#65292;1&#24230;&#65292;3&#24230;&#30340;&#24773;&#20917;&#65292;&#27809;&#26377;2&#24230;&#65292;4&#24230;
   if(flag == 7 || flag == 11 || flag == 13 || flag == 14) // 3&#24230;
   {
      flag = 15 - flag;
      if(flag == 1)
      {
         if(x >= 1 && y >= 1 && bodyIdx[x-1+mult9[y-1]])
         {
            flag = 8;
         }
         else
         {
            flag = 2;
         }
      }
      else if(flag == 2)
      {
         if(x <8>= 1 && bodyIdx[x+mult9[y-1]])
         {
            flag = 1;
         }
         else
         {
            flag = 4;
         }
      }
      else if(flag == 4)
      {         
         if(x <= 8 && y <8>= 1 && y <= 8 && bodyIdx[x-1+mult9[y]])
         {
            flag = 4;
         }
         else
         {
            flag = 1;
         }
      }
      return 3;
   }
   else if(flag == 0) // 0&#24230;
   {
      return 0;
   }
   else // 1&#24230;
   {
      return 1;
   }
}

void getEndPoint1(int i)
{
   int x, y;
   int flag = 2;
   int oldFlag = 4; // &#21521;&#19979;
   // set first point
   endPoint[0].x = mod9[i];
   endPoint[0].y = divide9[i];
   cntEndPoint = 1;
   while(edge[i])
   {
      edge[i] = false;
      // &#36793;&#27714;&#28857;
      if(oldFlag == flag)
      {
         cntEndPoint--;
      }
      if(flag == 1)
      {
         endPoint[cntEndPoint].x = (i-90)%10;
         endPoint[cntEndPoint].y = (i-90)/10;
      }
      else if(flag == 2)
      {
         endPoint[cntEndPoint].x = mod9[i] + 1;
         endPoint[cntEndPoint].y = divide9[i];
      }
      else if(flag == 4)
      {
         endPoint[cntEndPoint].x = (i-90)%10;
         endPoint[cntEndPoint].y = (i-90)/10+1;
      }
      else // must be 8
      {
         endPoint[cntEndPoint].x = mod9[i];
         endPoint[cntEndPoint].y = divide9[i];
      }
      cntEndPoint++;
      oldFlag = flag;
      // &#28857;&#27714;&#36793;
      x = endPoint[cntEndPoint-1].x;
      y = endPoint[cntEndPoint-1].y;
      flag = 0;
      if(getDegree(x, y, flag) == 0)
      {
         edge[i] = false;
      }
      else // 1&#24230;&#25110;&#32773;3&#24230;
      {
         if(flag == 1)
         {
            i = 80+x+y*10;
         }
         else if(flag == 2)
         {
            i = x+y*9;
         }
         else if(flag == 4)
         {
            i = 90+x+y*10;
         }
         else if(flag == 8)
         {
            i = x+y*9-1;
         }
      }
   }
}

void getEndPoint2()
{
   int i;
   int x, y;
   int flag; // &#24038;&#19978;&#20026;1&#65292;&#21491;&#19978;&#20026;2&#65292;&#21491;&#19979;&#20026;3&#65292;&#24038;&#19979;&#20026;4
   POINT oldPoint;
   for(i=0; i<cntEndPoint>= 1 && y >= 1 && bodyIdx[x-1+mult9[y-1]])
      {
         flag |= 1;
      }
      if(x <8>= 1 && bodyIdx[x+mult9[y-1]])
      {
         flag |= 2;
      }
      if(x <= 8 && y <8>= 1 && y <8> oldPoint.y)
               {
                  flag = 1;
               }
               else
               {
                  flag = 8;
               }
            }
            else
            {
               if(endPoint[i].y > oldPoint.y)
               {
                  flag = 2;
               }
               else
               {
                  flag = 4;
               }
            }
         }
         else
         {
            if(mult35[endPoint[i].y]-4 == endPoint[i-1].y)
            {
               if(endPoint[i].x > oldPoint.x)
               {
                  flag = 1;
               }
               else
               {
                  flag = 2;
               }
            }
            else
            {
               if(endPoint[i].x > oldPoint.x)
               {
                  flag = 8;
               }
               else
               {
                  flag = 4;
               }
            }
         }
      }
      else if(flag != 1 && flag != 2 && flag != 4 && flag != 8)
      {
         // 3&#20010;&#26684;&#23376;
         flag = 15 - flag;
         if(flag == 1 || flag == 2)
         {
            flag <<2>>= 2;
         }
      }
      oldPoint.x = endPoint[i].x;
      oldPoint.y = endPoint[i].y;
      if(flag == 1)
      {
         endPoint[i].x = mult35[x] - 4;
         endPoint[i].y = mult35[y] - 4;
      }
      else if(flag == 2)
      {
         endPoint[i].x = mult35[x] + 4;
         endPoint[i].y = mult35[y] - 4;
      }
      else if(flag == 4)
      {
         endPoint[i].x = mult35[x] + 4;
         endPoint[i].y = mult35[y] + 4;
      }
      else // must be 8
      {
         endPoint[i].x = mult35[x] - 4;
         endPoint[i].y = mult35[y] + 4;
      }
   }
}

void getEdge()
{
   int i;
   // set true when same idx
   for(i=0; i<81; i++)
   {
      if(bodyIdx[i])
      {
         edge[i] = true;
         edge[i+91+divide9[i]] = true;
         edge[i+9] = true;
         edge[i+90+divide9[i]] = true;
      }
   }
   // set false when nabour
   for(i=0; i<81>= 9 && bodyIdx[i-9])
         {
            edge[i] = false;
         }
         if(mod9[i] <= 7 && bodyIdx[i+1])
         {
            edge[i+91+divide9[i]] = false;
         }
         if(i <71>= 1 && bodyIdx[i-1])
         {
            edge[i+90+divide9[i]] = false;
         }
      }
   }
}

void getEndPoint3()
{
   for(int i=0; i<cntEndPoint; i++)
   {
      endPoints[pCircle][i].x = endPoint[i].x;
      endPoints[pCircle][i].y = endPoint[i].y;
   }
   pEndPoints[pCircle] = cntEndPoint;
   if((colorIdx&0x100) == 0x100) // &#31532;8&#20301;&#26159;1&#65292;&#40657;&#33394;
   {
      colorGroup[pCircle] = 0;
   }
   else if((colorIdx&0x200) == 0x200) // &#31532;9&#20301;&#26159;1&#65292;&#32418;&#33394;
   {
      colorGroup[pCircle] = MaxColorIdx - 1;
   }
   else
   {
      colorGroup[pCircle] = colorIdx;
   }
   pCircle++;
}

void getColorIdx()
{
   int count = 0;
   // &#26681;&#25454;headIdx&#21462;&#24471;&#39068;&#33394;&#20449;&#24687;
   if(selectIdx == nowIdx)
   {
      colorIdx &= 0x2FF; // &#31532;8&#20301;&#32622;0
      colorIdx |= 0x200; // &#31532;9&#20301;&#32622;1
      return;
   }
   for(int i=0; i<81>= 9 && leftIdx[grid-9] == nowIdx && bodyIdx[grid-9] == false)
   {
      getBodyIdx(grid-9);
   }
   if(mod9[grid] <= 7 && leftIdx[grid+1] == nowIdx && bodyIdx[grid+1] == false)
   {
      getBodyIdx(grid+1);
   }
   if(grid <71>= 1 && leftIdx[grid-1] == nowIdx && bodyIdx[grid-1] == false)
   {
      getBodyIdx(grid-1);
   }
}

void getEndPoint()
{
   int i, j, k;
   // &#22788;&#29702;&#27599;&#19968;&#20010;idx
   colorIdx = 0;
   pCircle = 0;
   // clear
   for(i=0; i<180; i++)
   {
      edge[i] = false;
   }
   for(i=1; i<=maxIdx; i++)
   {
      nowIdx = i;
      getColorIdx();
      // &#22788;&#29702;&#27599;&#19968;&#20010;&#31751;
      for(j=0; j<81; j++)
      {
         if(headIdx[j] == nowIdx)
         {
            // get bodyIdx based on leftIdx
            for(k=0; k<81; k++)
            {
               bodyIdx[k] = false;
            }
            getBodyIdx(j);
            // get edge based on bodyIdx
            getEdge();
            // &#22788;&#29702;&#27599;&#19968;&#20010;&#29615;
            for(k=0; k<90>= 9 && tempIdx[grid-9] == nowIdx)
   {
      clearNabour(grid-9);
   }
   if(mod9[grid] <= 7 && tempIdx[grid+1] == nowIdx)
   {
      clearNabour(grid+1);
   }
   if(grid <71>= 1 && tempIdx[grid-1] == nowIdx)
   {
      clearNabour(grid-1);
   }
}

void updateHeadUniq()
{
   int i, j;
   int bakSelectIdx;
   int temp2Idx[81];
   // get headIdx based on leftIdx
   for(i=0; i<81; i++)
   {
      tempIdx[i] = leftIdx[i];
      headIdx[i] = 0;
   }
   for(i=0; i<81; i++)
   {
      if(tempIdx[i] != 0)
      {
         nowIdx = tempIdx[i];
         headIdx[i] = nowIdx;
         clearNabour(i);
      }
   }
   // get uniqIdx based on headIdx
   for(i=0; i<81; i++)
   {
      tempIdx[i] = headIdx[i];
   }
   for(i=0; i<81; i++)
   {
      if(tempIdx[i] != 0)
      {
         nowIdx = tempIdx[i];
         for(j=i+1; j<81; j++)
         {
            if(tempIdx[j] == nowIdx)
            {
               tempIdx[j] = 0;
            }
         }
      }
   }
   for(i=0; i<81; i++)
   {
      uniqIdx[i] = tempIdx[i] != 0;
   }
   // get maxIdx and leastize idx
   maxIdx = 0;
   for(i=0; i<81; i++)
   {
      tempIdx[i] = 0;
      temp2Idx[i] = 0;
   }
   for(i=0; i<81; i++)
   {
      if(uniqIdx[i])
      {
         nowIdx = leftIdx[i];
         maxIdx++;
         for(j=i; j<81; j++)
         {
            if(leftIdx[j] == nowIdx)
            {
               tempIdx[j] = maxIdx;
            }
            if(headIdx[j] == nowIdx)
            {
               temp2Idx[j] = maxIdx;
            }
         }
         if(selectIdx == nowIdx)
         {
            bakSelectIdx = maxIdx;
         }
      }
   }
   for(i=0; i<81; i++)
   {
      leftIdx[i] = tempIdx[i];
      headIdx[i] = temp2Idx[i];
   }
   // update selectIdx
   selectIdx = bakSelectIdx;
   for(i=0; i<81; i++)
   {
      if(editingIdx[i])
      {
         editingHead = i;
         break;
      }
   }
   if(i == 81)
   {
      selectIdx = 0;
      underSumEditing = false;
   }
}

/*****************************************************
 * &#25353;&#20303;shift&#28857;&#36873;&#24050;&#32463;&#36873;&#20013;&#30340;&#26684;&#28857;&#26102;&#65292;&#21462;&#28040;&#27492;&#26684;&#28857;
 * &#28857;&#36873;&#27809;&#26377;idx&#30340;&#26684;&#28857;&#26102;&#65292;&#36873;&#20013;&#27492;&#26684;&#28857;(&#31532;&#19968;&#27425;&#36873;&#21644;&#38750;&#31532;&#19968;&#27425;&#36873;)
 * &#28857;&#36873;idx&#30340;&#26684;&#28857;&#26102;&#65292;&#36873;&#20013;&#25152;&#26377;idx&#30340;&#26684;&#28857;
 * &#31373;&#38376;&#65306;&#36319;&#30528;&#21035;&#20154;&#36305;
 *****************************************************/
void updateIdxShift(int grid)
{
   int i;
   // &#24050;&#30693;uniqIdx, headIdx, leftIdx, editingIdx
   if(editingIdx[grid])
   {
      editingIdx[grid] = false;
      leftIdx[grid] = 0;
   }
   else if(leftIdx[grid] == 0)
   {
      if(selectIdx == 0)
      {
         selectIdx = ++maxIdx;
         editingIdx[grid] = true;
         leftIdx[grid] = selectIdx;
      }
      else
      {
         editingIdx[grid] = true;
         leftIdx[grid] = selectIdx;
      }
   }
   else // leftIdx[grid] != 0
   {
      if(selectIdx == 0)
      {
         selectIdx = leftIdx[grid];
         nowIdx = selectIdx;
      }
      else
      {
         nowIdx = selectIdx;
         selectIdx = leftIdx[grid];
      }
      for(i=0; i<81; i++)
      {
         if(leftIdx[i] == selectIdx)
         {
            editingIdx[i] = true;
         }
         else if(leftIdx[i] == nowIdx) // &#30456;&#31561;&#30340;&#26102;&#20505;&#19979;&#38754;&#26080;&#24847;&#20041;
         {
            leftIdx[i] = selectIdx;
         }
      }
   }
   // &#26681;&#25454;leftIdx&#27714;headIdx&#65292;uniqIdx
   updateHeadUniq();
}

/*****************************************************
 * &#25353;&#20303;ctrl&#28857;&#36873;&#24050;&#32463;&#36873;&#20013;&#30340;&#26684;&#28857;&#26102;&#65292;&#21462;&#28040;&#27492;&#26684;&#28857;
 * &#28857;&#36873;&#27809;&#26377;idx&#30340;&#26684;&#28857;&#26102;&#65292;&#36873;&#20013;&#27492;&#26684;&#28857;(&#31532;&#19968;&#27425;&#36873;&#21644;&#38750;&#31532;&#19968;&#27425;&#36873;)
 * &#28857;&#36873;idx&#30340;&#26684;&#28857;&#26102;&#65292;&#36873;&#20013;idx&#30340;&#26684;&#28857;
 * &#31373;&#38376;&#65306;&#36319;&#30528;&#33258;&#24049;&#36305;
 *****************************************************/
void updateIdxCtrl(int grid)
{
   // &#24050;&#30693;uniqIdx, headIdx, leftIdx, editingIdx
   if(editingIdx[grid])
   {
      editingIdx[grid] = false;
      leftIdx[grid] = 0;
   }
   else
   {
      if(selectIdx == 0)
      {
         selectIdx = ++maxIdx;
      }
      editingIdx[grid] = true;
      leftIdx[grid] = selectIdx;
   }
   // &#26681;&#25454;leftIdx&#27714;headIdx&#65292;uniqIdx
   updateHeadUniq();
}

/*****************************************************
 * &#22788;&#20110;&#32534;&#36753;&#25968;&#21644;&#29366;&#24577;&#26102;&#65292;&#25353;&#19979;&#22238;&#36710;&#25110;&#32773;&#40736;&#26631;&#24038;&#38190;&#28857;&#19968;&#19979;&#31561;
 *****************************************************/
void terminateSumEdit()
{
   int i;
   selectIdx = 0;
   for(i=0; i<81; i++)
   {
      editingIdx[i] = false;
   }
   underSumEditing = false;
}
Back to top
View user's profile Send private message Send e-mail
serbo

Joined: 22 Dec 2008
Posts: 6
:

Items
PostPosted: Mon Dec 22, 2008 4:08 pm    Post subject: Reply with quote

JasonLion wrote:
I
One other thing to keep in mind: the puzzles that a puzzle generator needs checked in the process of creating a puzzle have very different properties than the collections you have reported testing against. One of my solvers is one quarter the speed of yours on top1465, but twice as fast at the partial puzzles my generator needs double checked during the generation process.


This is interesting observation! Could you explain it a bit?
What algorithm does your solver use so it is faster than backracking with only singles handling? Does it apply some more advanced logic methods or something else? If it uses method other than naked/hidden singles, which one does it use (locked candidates, naked/hidden subset, x-wing ...)?
Or it does not use advanced soloving but use special tuning? How?
Back to top
View user's profile Send private message
JasonLion

Joined: 16 Nov 2008
Posts: 62
:
Location: Silver Spring, MD

Items
PostPosted: Mon Dec 22, 2008 10:03 pm    Post subject: Reply with quote

I use the same basic approach briturner uses, naked and hidden singles and work on the cell with the fewest possibilities first, but I use a completely different data structure. Instead of keeping a list of the remaining possibilities for each cell, I keep a list of the remaining possibilities for each house. Also, I don't keep a copy of the entire state for each guess but instead go through the steps to undo the guess when needed (which is comparatively inexpensive with my data structure).

This approach changes the relative costs of the various kinds of steps, single detection is just slightly more expensive while guessing is noticeably cheaper. As it happens, guessing is much more common for boards that don't have enough clues yet, enough so that my approach is cheaper on the average for those puzzles. But the opposite is true for puzzles in the top1465 collection, which have more singles and less guessing.

I don't do Locked Candidates at all, but then they aren't really gaining briturner anything on the kinds of puzzles I am interested in. I also have a couple of other minor historical differences and a few small refinements that fine tune the speed for the situations I see most often, but they are minor in comparison.
Back to top
View user's profile Send private message
serbo

Joined: 22 Dec 2008
Posts: 6
:

Items
PostPosted: Thu Dec 25, 2008 1:08 am    Post subject: Reply with quote

[quote="zerothbase"]
Quote:
Alternatively you can start from a random solved board and always choose subsets. Usually you can find a random subset with a unique solution of 30ish values (on a 3x3) fairly quickly and then reduce down to a minimum by removing values and checking for 1 or 2+ solutions. This way, you will never hit an unsolvable board - only 1 or 2+ solutions. Additionally, try hill-climbing (add one or two and then remove others) to get out of local-minima.

--zerothbase


For this to work you need fast generator of solved grid. Than I do not really see the difference
between two aproaches unles you are feeding puzzle generator with solved grids.
Have you some recomendation how to optimize generator of solved grid?
Back to top
View user's profile Send private message
zerothbase

Joined: 02 Nov 2008
Posts: 17
:

Items
PostPosted: Thu Dec 25, 2008 6:34 am    Post subject: Reply with quote

Generating random solved grids is a very fast operation compared to the rest of the steps involved.

see 2nd post on this topic in the setting sudoku forum

You can simply iterate over the squares in order (1 to 81) and set a random value of the possible for each square. If you run into a square with no possibilities, backtrack.

This is very fast.

--Zerothbase
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next
Page 4 of 9

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron