Bit Based Sudoku Solver (BB_Sudoku) V0.5

briturner · Posted: Wed Dec 31, 2008 9:25 pm Post subject:

sorry, posted twice when I got a script error when posting

briturner · Posted: Wed Dec 31, 2008 9:45 pm Post subject:

Greetings again,

I have been away for awhile, but I have been reading the forum and making a few small changes to my solver.

I implemented 2 new solving methodologies, the first being a generic fishy searcher. X-Wing, Swordfish, and Jellyfish methods are all really just a variation of searching for subsets, and as such can be done with a similar generic routine.

After implementing that, it still only solved 75 of the top 50000 without guessing. I looked at a number of other solving techniques, but they mostly fell within 2 generic methods:
- If we assume X = a, and this leads to X cannot = a, then X != a
- If we assume each possibility of X, and all the possibilities lead to Y cannot = a, then Y != a

XY-Wing, XYZ-Wing, Connected pairs, Finned fish and others all fit in this category. So, I implemented a methodology that tries 1 step for each possibility, and searches for common eliminations. In my code, I called this "1-Step Commonality". This is different than guessing and backtracking in that we are only testing the changes in a single cell, and only 1 level. This was much easier than making specific routines each method.

With these 2 methods added, all the top 50000 can be solved without guessing, as can the top 1465. I am currently down to 551 puzzles that require guessing out of some 100,000+ puzzles.

Here are a couple puzzles that I still need to use guessing and backtracking:
3.......1.2...6.9...5...8...7.2.4......867........9.4...8...5...6.9...2.1.......3
.....1.8..3.5..2......4...62..3..5.......8.1.....6...4.5....7..3..97.....62......
.6.9....35....4.2.....8.4..8......5...3...7...9......1..1.5.....7.3....99....2.4.
.....1.2.3...4.5.....6....7..1.....6.4..8..9.5.....3..8....2....5..9.4....67.....
4.......3.1...2.7...8...5...6.2.9......1........68..9...5...8...2.7...1.3.......4

For those really interested, here are the code snippets for the 2 solving routines (only for those really really interested, since it is not commented):

Code:

inline void FindFishies (void)
{ int b, i, g, p, m, t[10], v[10], grid[10], x, y;

for (b = 1; b <= 9; b++)
{ if (Changed) break;
for (g = 0; g < 9; g++) grid[g] = 0;
for (g = 0; g < 9; g ++)
for (i = 0; i < 9; i++)
   if (G[PIdx].Grid[(g*9)+i] & V2B[b]) grid[g] |= V2B[i+1];

for (g = m = 0; g < 9; g++)
if (grid[g]) m++;
if (m <2> 0)
{ t[p]++;
if (t[p] == 9) { p--; continue; }
if (p == 1)
{ v[1] = grid[t[p]];
if ((!v[1]) || (NSet[v[1]] > m)) continue;
p++; t[2] = t[1]; continue;
}
if (!grid[t[p]]) continue;
v[p] = v[p-1] | grid[t[p]];
if (NSet[v[p]] > m) continue;
if (NSet[v[p]] == p)
{ for (i = 0; i < 9; i++)
      if (grid[i] & ~v[p])
      { x = grid[i] & v[p];
      while (x)
      { y = (i*9) + B2V[x & -x] - 1;
if (G[PIdx].Grid[y] & V2B[b])
         { G[PIdx].Grid[y] ^= V2B[b];
if (B2V[G[PIdx].Grid[y]])
PushSingle(y, G[PIdx].Grid[y]);
MarkChanged(y);
}
         x ^= (x & -x);
      }
}
p = 1;
continue;
}
if (p < m) { p++; t[p] = t[p-1]; }
}
}
}

inline void DoOneStep (int use_methods)
{ int i, j, x1, x2, x3, mt, testcell, tested[81], testpidx;

for (i = 0; i < 81; i++) tested[i] = 0;
testpidx = PIdx;

while (!Changed)
{ // Find next spot to check
testcell = mt = x3 = 99;
for (i = 0; i < 81; i++)
if ((NSet[G[PIdx].Grid[i]] <mt> 1) && !tested[i])
{ x1 = NSet[G[PIdx].Grp[C2Grp[i][0]]] + NSet[G[PIdx].Grp[C2Grp[i][1]]] + NSet[G[PIdx].Grp[C2Grp[i][2]]];
if ((NSet[G[PIdx].Grid[i]] < mt) ||
      ((NSet[G[PIdx].Grid[i]] == mt) && (x1 <= x2) && (OneStepP[i] <= x3)))
{ x2 = x1;
testcell = i;
mt = NSet[G[PIdx].Grid[i]];
      x3 = OneStepP[i];
}
}

if (testcell == 99) return;
tested[testcell] = 1;
OneStepI++; OneStepP[testcell] = OneStepI;

for (j = 0; j < NSet[G[PIdx].Grid[testcell]]; j++)
{
G[PIdx+1+j] = G[PIdx];
PushSingle(testcell, NSetX[G[PIdx].Grid[testcell]][j]);
   PIdx = testpidx + 1 + j;
   Solver(1, use_methods & ~(USE_GUESSES | USE_1_STEP), 0, PIdx, NULL);
PIdx = testpidx;
if (No_Sol)
for (i = 0; i < 81; i++) G[PIdx+1+j].Grid[i] = 0;
   else
for (i = 0; i < 81; i++)
   if (!G[PIdx+1+j].Grid[i]) G[PIdx+1+j].Grid[i] = SolGrid[i];
   No_Sol = 0; SingleCnt = 0;
}
for (j = 1; j < NSet[G[PIdx].Grid[testcell]]; j++)
for (i = 0; i < 81; i++) G[PIdx+1].Grid[i] |= G[PIdx+1+j].Grid[i];
for (i = 0; i < 27; i++) ChangedGroup[i] = 0; Changed = 0;
for (i = 0; i < 81; i++)
   if (G[PIdx].Grid[i] && (G[PIdx].Grid[i] != G[PIdx+1].Grid[i]))
   { G[PIdx].Grid[i] = G[PIdx+1].Grid[i];
   if (B2V[G[PIdx].Grid[i]]) PushSingle(i, G[PIdx].Grid[i]);
MarkChanged(i);
}
}
}

I will release the new code once I fix a problem in my generator that causes it to crash after a few hours (painful to find since it normally has no problems).

brit

JasonLion · Posted: Sun Jan 04, 2009 2:57 pm Post subject:

briturner, from your brief description, your new solving technique sounds like it might be the same as Bowman's Bingo, or at least very similar.

briturner · Posted: Sun Jan 04, 2009 5:50 pm Post subject:

Greetings.

My methods I used are all very generic, rather than specific solving methods. This makes programming much easier, but rating almost impossible. I only implemented 7 methods:

- Naked Singles
- Hidden Singles (these two are also used to determine if the puzzle is solved)
- Locked Candidates
- Disjoint Subsets (which include Naked/Hidden Pairs/Triples/Quads)
- Fishies (including X-Wing, Swordfish, and Jellyfish)
- 1-Step Commonality (includes many methods) and 2-Step Commonality
- Brute Force

Since the routines are all rather generic, a Naked Pair and Hidden Quad are calculated using the same routine, same with X-Wing and Jellyfish. Since my Fishy routine is based on the Subsets, it should theoretically detect Jellyfish with up to 7 legs (I do not know if that is possibly).

I looked up Bowman's Bingo, and from what I understand, it is looking for contradictions. My method will find both contradictions, and any common information that is true when all possibilities of a cell are tested. This is similar to XY-Wing, XYZ-Wing, and finned fish.

I was originally going to write a separate routine for the XY-Wing and XYZ-Wing, but it worked out to be easier to test everything.

4 notes on my 1-Step Commonality and 2-Step Commonality:
- It is a computer method, and not something that could be easily implemented by hand, similar to brute force
- I do not claim it is anything unique, but more of a generalization of other techniques. Like Subset Counting is more of a generalization of certain techniques.
- While I gave it a name, it was only because I did not know of any existing names that would cover what I implemented.
- Brute force is still the fastest method, I only implemented more methods so I could use them for rating in my generator and for my own personal curiosity.

My rater is really terrible, but I can categorize puzzles into 4 difficulty levels using these methods:

Easy : Solved using Naked/Hidden Singles and Locked Candidates Only
Medium : Adds Disjoint Subsets and Fishies
Hard : Requires using 1-Step Commonality
Insane : Requires using 2-Step Commonality

I have not found any puzzle that needs more than the 2-Step commonality to be solved.

I currently know of 549 puzzles that are insane. Using other raters they rank between 90375 and 97529 using gsf's rater, 256,179 and 3639,2371 using sueratt, and 9.9 and 11.9 suing SE (of the 30+ I rated so far, since some literally take hours to rate). I am working on generating more insane puzzles and am now on my 3rd generator method.

brit

garthd · Posted: Mon Jan 12, 2009 10:39 am Post subject: 1-Step Commonality

The technique of 1-Step Commonality sounds interesting...do you have a puzzle (say from top1465) where you can post the puzzle right before the 1-Step Commonality is applied and detail how the method moves forward. Am I right in saying that for a cell with candidate 1,3 and 7 remaining, you try placing each possible candidate as the solution for the cell, and then search for any common eliminations?

garthd · Posted: Mon Jan 12, 2009 10:40 am Post subject: 1-Step Commonality

The technique of 1-Step Commonality sounds interesting...do you have a puzzle (say from top1465) where you can post the puzzle right before the 1-Step Commonality is applied and detail how the method moves forward. Am I right in saying that for a cell with candidate 1,3 and 7 remaining, you try placing each possible candidate as the solution for the cell, and then search for any common eliminations?

garthd · Posted: Mon Jan 12, 2009 10:41 am Post subject: 1-Step Commonality

The technique of 1-Step Commonality sounds interesting...do you have a puzzle (say from top1465) where you can post the puzzle right before the 1-Step Commonality is applied and detail how the method moves forward. Am I right in saying that for a cell with candidate 1,3 and 7 remaining, you try placing each possible candidate as the solution for the cell, and then search for any common eliminations?

garthd · Posted: Mon Jan 12, 2009 10:42 am Post subject: 1-step commonality

The technique of 1-Step Commonality sounds interesting...do you have a puzzle (say from top1465) where you can post the puzzle right before the 1-Step Commonality is applied and detail how the method moves forward. Am I right in saying that for a cell with candidate 1,3 and 7 remaining, you try placing each possible candidate as the solution for the cell, and then search for any common eliminations?

briturner · Posted: Tue Jan 13, 2009 5:16 am Post subject:

Greetings,

here is an example from the first puzzle of the Top_1465:
4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........

After applying simpler techniques (hidden/naked singles, locked candidates, disjoint subsets, fishies), I ended up with this:

zhouyundong · Posted: Sun Jan 18, 2009 1:06 pm Post subject:

http://www.killersudokuonline.com/play.html?puzzle=GW471uzq1010
GT142,My solver can solute GT(Great Than,What I called Sopare, sodoku compare), and my solver tells There are 13 ">,<s>'s, the answer is still only one.
I think what i did is good work.Can somebody translate my poor english to standard English,and publish here,thanks.

briturner · Posted: Mon Jan 19, 2009 3:11 am Post subject:

Greetings, and congratulations zhouyundong. I went ahead and the GT, LT feature into my solver today.

Not quite perfect. It misses one logical elimination. if we have X > Y < Z, it eliminates 1 from X and Z, and eliminates 9 from Y. Y actually can not be a 9 or an 8 since there are 2 number greater than Y, but my routine does not catch that yet. It still solves the puzzle correctly, because that will be caught later on, but it could cause an extra guess.

Since it is part of my main solver, it can solve puzzles with combinations of givens (normal Sudoku) and "<" ">".

my problem is that I hardcoded a single puzzle into my solver to test. Is there a site with a collection of these that can be used for testing? Assuming there is, what is the format?

thanks,
brit

zhouyundong · Posted: Mon Jan 19, 2009 3:13 pm Post subject:

I did some work to the format,here is my string:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110010001000201200011000100000010101201100000002100020011000000101000000000020120210000020000000000012000000000000210000000000000001010012000201
The first 81 numbers mean that known numbers.
Then the 81*2 numbers mean that Killer's sum.
Then the 81*2 numbers mean that Killer's head index.
Then the 72*2 numbers mean that GT.(0:nothing,1:>,2:<)

zhouyundong · Posted: Mon Jan 19, 2009 3:31 pm Post subject:

Greetings All, congratulations Briturner.
I am happy to know that you are GT writer.
My solver can solve the most diffucult GT within 3 seconds,general question can be solved within 100 miliseconds.But some easy question,it can NOT solve........It can generate GT ,tonight I will generate some questions.
Do you have a good way to Connent with each other, what about ICQ?
I will send you my test cases which produced by my solver,every kind of GT cases, no answer, 1 answer 2 answers; ><5><11numbers><&2numbers...every kind.
I will send you my solver, and I am very glad to test speed with your sover,we use very different kernels. Very Happy

What I do next is to solve Killer.

zhouyundong · Posted: Tue Jan 20, 2009 2:53 pm Post subject:

I got The First GT questions abstract automatically produced by computer within 5 minutes.
Jan. 20 2009 22:50
It is a mile stone in the GT area,I think.
000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010200200011000200001000211200001200120010000200200001001222000012001011100202200010000000000000011000000120002120002012000102010000010000002002