|
View previous topic :: View next topic |
Author |
Message |
| ChPicard
| Joined: 12 Mar 2008 | Posts: 82 | : | Location: Montreal, Canada | Items |
|
Posted: Wed Nov 26, 2008 6:27 pm Post subject: |
|
|
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 |
|
|
| zerothbase
| Joined: 02 Nov 2008 | Posts: 17 | : | | Items |
|
Posted: Thu Nov 27, 2008 3:25 am Post subject: |
|
|
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 |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Sat Nov 29, 2008 3:03 pm Post subject: |
|
|
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 |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Sun Nov 30, 2008 5:33 am Post subject: |
|
|
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 |
|
|
| briturner
| Joined: 14 Oct 2008 | Posts: 75 | : | | Items |
|
Posted: Sun Nov 30, 2008 11:23 pm Post subject: |
|
|
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 |
|
|
| zhouyundong
| Joined: 22 Nov 2008 | Posts: 43 | : | | Items |
|
Posted: Wed Dec 03, 2008 10:03 am Post subject: |
|
|
I have written a new kernel,every time put 3 grids.and guess while no single. |
|
Back to top |
|
|
| zhouyundong
| Joined: 22 Nov 2008 | Posts: 43 | : | | Items |
|
Posted: Mon Dec 08, 2008 4:17 am Post subject: |
|
|
give only one answer:
top50000 spends 10seconds
sodoku17 spends 20seconds |
|
Back to top |
|
|
| zhouyundong
| Joined: 22 Nov 2008 | Posts: 43 | : | | Items |
|
Posted: Mon Dec 15, 2008 4:37 pm Post subject: |
|
|
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 |
|
|
| zhouyundong
| Joined: 22 Nov 2008 | Posts: 43 | : | | Items |
|
Posted: Mon Dec 15, 2008 4:41 pm Post subject: |
|
|
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 |
|
|
| zhouyundong
| Joined: 22 Nov 2008 | Posts: 43 | : | | Items |
|
Posted: Mon Dec 15, 2008 4:43 pm Post subject: |
|
|
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 |
|
|
| zhouyundong
| Joined: 22 Nov 2008 | Posts: 43 | : | | Items |
|
Posted: Mon Dec 15, 2008 4:55 pm Post subject: |
|
|
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
////////////////////////以下与画虚线框有关////////////////////////
int getDegree(int x, int y, int &flag)
{
// 设置flag,求度数
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;
}
// 只有0度,1度,3度的情况,没有2度,4度
if(flag == 7 || flag == 11 || flag == 13 || flag == 14) // 3度
{
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度
{
return 0;
}
else // 1度
{
return 1;
}
}
void getEndPoint1(int i)
{
int x, y;
int flag = 2;
int oldFlag = 4; // 向下
// set first point
endPoint[0].x = mod9[i];
endPoint[0].y = divide9[i];
cntEndPoint = 1;
while(edge[i])
{
edge[i] = false;
// 边求点
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;
// 点求边
x = endPoint[cntEndPoint-1].x;
y = endPoint[cntEndPoint-1].y;
flag = 0;
if(getDegree(x, y, flag) == 0)
{
edge[i] = false;
}
else // 1度或者3度
{
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; // 左上为1,右上为2,右下为3,左下为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个格子
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) // 第8位是1,黑色
{
colorGroup[pCircle] = 0;
}
else if((colorIdx&0x200) == 0x200) // 第9位是1,红色
{
colorGroup[pCircle] = MaxColorIdx - 1;
}
else
{
colorGroup[pCircle] = colorIdx;
}
pCircle++;
}
void getColorIdx()
{
int count = 0;
// 根据headIdx取得颜色信息
if(selectIdx == nowIdx)
{
colorIdx &= 0x2FF; // 第8位置0
colorIdx |= 0x200; // 第9位置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;
// 处理每一个idx
colorIdx = 0;
pCircle = 0;
// clear
for(i=0; i<180; i++)
{
edge[i] = false;
}
for(i=1; i<=maxIdx; i++)
{
nowIdx = i;
getColorIdx();
// 处理每一个簇
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();
// 处理每一个环
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;
}
}
/*****************************************************
* 按住shift点选已经选中的格点时,取消此格点
* 点选没有idx的格点时,选中此格点(第一次选和非第一次选)
* 点选idx的格点时,选中所有idx的格点
* 窍门:跟着别人跑
*****************************************************/
void updateIdxShift(int grid)
{
int i;
// 已知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) // 相等的时候下面无意义
{
leftIdx[i] = selectIdx;
}
}
}
// 根据leftIdx求headIdx,uniqIdx
updateHeadUniq();
}
/*****************************************************
* 按住ctrl点选已经选中的格点时,取消此格点
* 点选没有idx的格点时,选中此格点(第一次选和非第一次选)
* 点选idx的格点时,选中idx的格点
* 窍门:跟着自己跑
*****************************************************/
void updateIdxCtrl(int grid)
{
// 已知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;
}
// 根据leftIdx求headIdx,uniqIdx
updateHeadUniq();
}
/*****************************************************
* 处于编辑数和状态时,按下回车或者鼠标左键点一下等
*****************************************************/
void terminateSumEdit()
{
int i;
selectIdx = 0;
for(i=0; i<81; i++)
{
editingIdx[i] = false;
}
underSumEditing = false;
} |
|
|
Back to top |
|
|
| serbo
| Joined: 22 Dec 2008 | Posts: 6 | : | | Items |
|
Posted: Mon Dec 22, 2008 4:08 pm Post subject: |
|
|
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 |
|
|
| JasonLion
| Joined: 16 Nov 2008 | Posts: 62 | : | Location: Silver Spring, MD | Items |
|
Posted: Mon Dec 22, 2008 10:03 pm Post subject: |
|
|
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 |
|
|
| serbo
| Joined: 22 Dec 2008 | Posts: 6 | : | | Items |
|
Posted: Thu Dec 25, 2008 1:08 am Post subject: |
|
|
[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 |
|
|
| zerothbase
| Joined: 02 Nov 2008 | Posts: 17 | : | | Items |
|
Posted: Thu Dec 25, 2008 6:34 am Post subject: |
|
|
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 |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|