|
| View previous topic :: View next topic |
| Author |
Message |
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
 Posted: Tue Sep 20, 2005 5:52 am Post subject: Coloring in C |
 |
|
I just got my simple coloring algorithm working, and I thought I'd share it for everyone who might be interested in implementing something similar.
A bit of introduction here: My solver is based on DLX, and uses the arrays Uc and Ur to mark which cols/rows of the exact cover matrix are used. To eliminate a possibility I simply mark the row in Ur. The col array is laid out so that every 4 consecutive values are the columns corresponding to a row, and row is laid out similarly with 9 values per column; both are size3*4 in length, where size=9, size2=81, size3=729 (for flexibility; I also defined width=3, used by some algorithms).
| Code: | int puzzle::Coloring()
{
int i,j,k,h,m,r,c1,c2,c,nc,N,L,sp=0,rep,ret=0;
int *C=new int[size2];
for(N=0;N<size;++N) {
memset(C,0,sizeof(int)*size2);
nc=2;
do {
rep=0;
// look for conjugates--by row, then by col, then by box
for(c=N+size2*4-size;c>=size2;c-=size) {
m=0;
for(j=0,k=c*size;j<size;++j,++k) {
if(Ur[row[k]]) continue;
if(m++) c2=row[k]/size;
else c1=row[k]/size;
}
if(m==2) {
if(!C[c1]) {
if(!C[c2]) {C[c1]=nc++; C[c2]=nc++;}
else C[c1]=C[c2]^1;
}
else if(!C[c2]) C[c2]=C[c1]^1;
else {
// replace one "color" conjugate set with an existing one
k=(C[c2]>C[c1]?C[c2]:C[c1])|1;
m=C[c1]^C[c2]^1;
for(j=0;j<size2;++j) if(C[j] && (C[j]|1)==k) C[j]^=m;
}
}
}
// now look for weak links and follow their implications
// it may be possible to combine 2 colors or eliminate one
// L bits: 1: a->b; 2: A->B; 4: a->B; 8: A->b
for(c1=nc-1;c1>4;c1-=2) {
for(c2=c1-2;c2>2;c2-=2) {
for(i=L=0;i<size2;++i) {
if(!C[i] || (C[i]|1)!=c1) continue;
k=(i*size+N)*4;
for(m=0;m<3;++m) {
c=col[++k]*size;
for(j=0;j<size;++j) {
if(Ur[r=row[c++]]) continue;
h=r/size;
if(C[h] && (C[h]|1)==c2) {
L|=1 << ((((C[i]^C[h])&1)<<1) | (C[i]&1));
if(L&(L-1)) goto Lfound;
}
}
}
}
Lfound:
// find if colors are linked; e.g. if a=b,A=B or a=B,A=b
if(L==3 || L==12) {
m=c1^c2^(L==12?0:1);
for(i=0;i<size2;++i) if(C[i] && (C[i]|1)==c1) C[i]^=m;
break;
}
// find if one half color was eliminated; e.g. if one contradicts another
// this should never happen if standard elimination techniques already ran
else if(L&(L-1)) {
c=(L&(L>>2))?(L>8?c1:(c1^1)):(L<8?c2:(c2^1));
for(i=0;i<size2;++i) if(C[i]==c) {
C[i]=0;
++Ur[i*size+N];
++ret;
++rep;
if(hints) printf("Coloring reveals %d,%d may not be %d\n",i%size+1,i/size+1,N+1);
}
}
}
}
// look for uncolored candidate cells which share houses with each half of a conjugate
// cell must be in same house as c1T, and same house as c1F
for(r=N;r<size3;r+=size) {
if(Ur[r] || C[i=r/size]) continue;
k=r*4+1;
// search per color
for(c1=3;c1<nc;c1+=2) {
L=0;
for(j=0;j<size2;++j) {
if(!C[j] || (C[j]|1)!=c1) continue;
c=(j*size+N)*4;
if(col[k]==col[++c] || col[k+1]==col[++c] || col[k+2]==col[++c]) L|=1<<(C[j]&1);
if(L==3) break;
}
if(L==3) {
++Ur[r];
++ret;
++rep;
if(hints) printf("Coloring reveals %d,%d may not be %d\n",i%size+1,i/size+1,N+1);
break;
}
}
}
} while(rep); // end of do-while
}
delete C;
return ret;
} |
The part I'm most proud of is that this can check double weak links between colors to combine them. It does this by use of bit flags checking the implications a->B, A->b, a->b, and A->B. As soon as two different implications are found, we've learned that either one of these letters cannot appear at all, or that two pairs of them are equivalent. L&(L-1), a widget I like to use a lot, tells if L has more than one bit set.
As an example of combining colors, here's the grid it was tested with, for the digit 7:
| Code: | Original (7): First pass: a->B,A->b => aA=Bb
* . .|. * .|. . . b . .|. B .|. . . A . .|. a .|. . .
. . .|. . .|. . . . . .|. . .|. . . . . .|. . .|. . .
. . *|* . *|. . . . . B|* . *|. . . . . a|* . *|. . .
----------------- ----------------- -----------------
* . *|* . .|. . . * . b|a . .|. . . * . A|a . .|. . .
. . .|. . .|. . . . . .|. . .|. . . . . .|. . .|. . .
. * .|. * .|. . . . a .|. A .|. . . . a .|. A .|. . .
----------------- ----------------- -----------------
. . .|. . .|. . . . . .|. . .|. . . . . .|. . .|. . .
* . .|. * *|. . . a . .|. * *|. . . a . .|. * *|. . .
. * .|* . *|. . . . A .|* . *|. . . . A .|* . *|. . .
Elimination: Second pass: Elimination:
A . .|. a .|. . . A . .|. a .|. . . A . .|. a .|. . .
. . .|. . .|. . . . . .|. . .|. . . . . .|. . .|. . .
. . a|* . *|. . . . . a|A . *|. . . . . a|A . -|. . .
----------------- ----------------- -----------------
- . A|a . .|. . . - . A|a . .|. . . - . A|a . .|. . .
. . .|. . .|. . . . . .|. . .|. . . . . .|. . .|. . .
. a .|. A .|. . . . a .|. A .|. . . . a .|. A .|. . .
----------------- ----------------- -----------------
. . .|. . .|. . . . . .|. . .|. . . . . .|. . .|. . .
a . .|. - *|. . . a . .|. - A|. . . a . .|. - A|. . .
. A .|- . *|. . . . A .|- . a|. . . . A .|- . a|. . . |
The result is that 7 cannot appear at (1,4), (4,9), (5,8), or (6,3). If I test with fishy cycles I can only manage to eliminate (1,4) and (5,8). This is a good sign to me because it means I actually grasp what I'm doing here, and finally know coloring well enough to have made it an algorithm.
Most of my tests bail out if a clue is found, but fishy cycles and coloring are exceptions. When going to all the trouble to build a fishy cycle, of course, you want to use all the eliminations it gives you. And coloring, likewise, can yield multiple eliminations, especially if you run it through multiple iterations as I did here. Each elimination potentially creates new conjugates which in turn can reveal a lot about the puzzle.
Last edited by Lummox JR on Thu Sep 22, 2005 4:01 am; edited 1 time in total |
|
| Back to top |
|
 |
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
| Posted: Tue Sep 20, 2005 2:35 pm Post subject: |
|
|
>Most of my tests bail out if a clue is found, but fishy cycles
>and coloring are exceptions. When going to all the trouble to
>build a fishy cycle, of course, you want to use all the
>eliminations it gives you. And coloring, likewise, can
>yield multiple eliminations, especially if you run it
>through multiple iterations as I did here. Each elimination
>potentially creates new conjugates which in turn can reveal
>a lot about the puzzle.
the question is however, whether it's worth the effort.
Has anyone succeeded to make his/her solver faster by
including these advanced methods ? Or is it only for humans
who don't like backtracking ?
Would we expect speed-increase for larger sudokus, 16*16,25*25 ? |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Tue Sep 20, 2005 9:30 pm Post subject: |
|
|
| Oh this is for a human-style solver, absolutely. I'm using it to assess difficulty, but it could also be used to provide hints. Solving sudoku with DLX is no challenge at all. |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Thu Sep 22, 2005 5:16 am Post subject: |
|
|
Minor correction. In the section in which one half-color is removed by contradiction, my figuring was wrong. I've edited the post to replace this line:
| Code: | | c=(L&(L>>1))?(L<8?c2:(c2^1)):(L>8?c1:(c1^1)); |
...with this:
| Code: | | c=(L&(L>>2))?(L>8?c1:(c1^1)):(L<8?c2:(c2^1)); |
It should be fine now.
The puzzle where I expereinced the problem, and have since determined to work properly, is here:
| Code: | . . .|3 7 .|6 . 4
. 9 .|. . .|. . 8
. 1 3|. . .|. . .
-----------------
. 2 .|. 9 .|. . .
. . 7|. . .|. . 2
. . .|. 5 4|9 . .
-----------------
2 . .|9 . .|. . 1
8 . .|. 2 7|. . 6
. . .|4 . 1|. 8 . |
At a critical point you can do coloring on the digit 5, which in my solver algorithm works out like this:
| Code: | . . .|. . .|. . .
. . .|. . c|* * .
. . .|. . C|* * .
-----------------
. . B|. . .|. * a
. b .|. . .|. B .
. . .|. . .|. . .
-----------------
. * b|. . .|* * .
. . .|. . .|. . .
. a .|. . .|. . A |
Since the value a is present alongside both b and B, a must be false and A must be true. My algorithm doesn't bother to mark the A's true; it just lets single solving do that. However this will eliminate 5 at (2,9), (9,4), and also where b and B intersect at (8,7). The algorithm will continue on from this point and try to recolor the result, which will end up determining correctly that (7,7), (8,2), and (8,3) are not 5 either. This helps to illustrate that a surprising number of simple techniques can also be done with coloring. |
|
| 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 |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
