|
| View previous topic :: View next topic |
| Author |
Message |
| nukefusion
| | Joined: 27 Jun 2009 | | Posts: 22 | | : | |
Items |
|
 Posted: Mon Jun 29, 2009 7:01 pm Post subject: Transposing Naked Subsets to find Hidden Subsets |
 |
|
Hi all,
I'm having trouble getting my head around finding hidden subsets. I can find naked subsets and I understand that you can transpose the data in a matrix somehow to get the hidden subset for the opposing cells within the given region or house. I've read the thread @ /phpbb/viewtopic.php?mforum=sudoku&t=296&postdays=0&postorder=asc&start=0&mforum=sudoku (sorry, can't use URL tag or post link properly as first post) but I still can't get my head around it. The order of the candidate list for the naked subset obviously affects the output after the transpose, so what order do the input values have to be in?
Can anybody provide me a little guidance please?
Thanks. |
|
| Back to top |
|
 |
| PIsaacson
| | Joined: 17 Jan 2006 | | Posts: 47 | | : | | Location: Campbell, CA |
Items |
|
| Posted: Tue Jun 30, 2009 5:10 pm Post subject: |
|
|
NukeFusion,
Usually, computer solvers maintain 4 different spaces or views of the sudoku grid. These are the RC, RN, CN and BN spaces and they all represent the 729 (9x9x9) candidates using (usually) a two dimensional array with the 3rd coordinate value being a set of bits within a word. For example, the RC space is usually defined in C/C++ as int RC[9][9] with the 1st dimension the row coordinate, the second dimension the col coordinate and the candidates represented as the bits 0..8 using (1 << Digit) to set or test a particular candidate. The RN space uses the row for the 1st dimension, the candidate digit for the second, and the cols as the bit offsets. The CN space uses the col for the 1st dimension, the candidate digit for the second and the rows for the bit offsets. The BN space uses the box coordinate for the 1st dimension, the candidate digit for the second and the offset within the box (0 to 8 left to right and top to bottom within the box) for the bit offsets. These 4 spaces should be maintained in sync so that eliminating a candidate in the RC space produces the correct updates in the respective RN/CN/BN spaces as well.
With that in mind, the normal subset algorithm uses the RC space and loads a vector containing the 9 RC cells from one of the 27 possible sectors (houses). I use a simple recursive function to OR the bit values until I have gathered the desired number of entries (N cells) and bits (N candidates). By specifying the limits for the cells and candidates, you can use this same function to find ALSs (N cells and N+1 candidates), AHSs (N+1 cells, N candidates) etc. If you use the correct parameters (start, level, current set), you can re-enter and continue searching for additional subsets within the current sector and find all possible locked sets.
For hidden sets, you load the search vector with the RN cells for all the digits of a given row, or the CN cells for all the digits of a given col, or the BN cells for all the digits of a given box. The same recursive routine you used to find naked sets will now find hidden sets.
By loading the search vector with all the RN cells for all the rows of a given digit, or the CN cells for all the cols of a given digit, you can search for simple fish (X-wing, swordfish, jellyfish etc) again using the same recursive function.
By expanding the search vector to include all the RC cells, you can search for disjoint locked sets, but it becomes slightly more complex since you'll need to validate that the candidates are peers.
If you want sample code, I can post what I'm using in pascal.
Cheers,
Paul |
|
| Back to top |
|
|
| nukefusion
| | Joined: 27 Jun 2009 | | Posts: 22 | | : | |
Items |
|
| Posted: Wed Jul 01, 2009 3:01 pm Post subject: |
|
|
| Thanks Paul for such a detailed explanation. I understand the declaration and structure of the arrays but having trouble wrapping my head around the actual usage. Some sample code would certainly be appreciated. |
|
| Back to top |
|
|
| PIsaacson
| | Joined: 17 Jan 2006 | | Posts: 47 | | : | | Location: Campbell, CA |
Items |
|
| Posted: Wed Jul 01, 2009 7:46 pm Post subject: |
|
|
Here 'tis. The comments are lame, but the pascal code should be fairly easy to follow since the 4 main searches, naked, hidden, simple row fish, and simple column fish are symmetrical. The recursive search function is really small, so it shouldn't be hard to follow how it locates a locked set.
I didn't include the globals which would contain the various supporting structures, so let me know if you want those as well. If you want everything, send me a PM and I'll e-mail you a zipped file with the source and instructions on lazarus and free-pascal in order to rebuild it.
| Code: | function grid_t.subsets_update (mask, sector, flag : integer) : integer;
var
n, r, c, d, rcbt, index, update, change : integer;
bc, cc : char;
begin
update := 0;
index := 0;
for n := 0 to ss_cells-1 do
index := index or (1 shl ss_start[n]);
case flag of
type_naked:
begin
for n := 0 to 8 do
begin
if ((index and (1 shl n)) <> 0) then
continue;
r := ss_stack[n].index div 9;
c := ss_stack[n].index mod 9;
for d := 0 to 8 do
begin
if ((mask and (1 shl d)) = 0) then
continue;
change := update_mbit (d, r, c);
update += change;
if (sw_verbose <> 0) and (change <> 0) then
begin
write (inc_stepno (): 3, ') r', r+1, 'c', c+1, ' <> ', d+1, ' naked subset[', ss_cells, '] ');
writeln (sector2str (sector, index), '.{', mask2str (mask), '}');
end;
end;
end;
end;
type_hidden:
begin
for n := 0 to 8 do
begin
if ((mask and (1 shl n)) = 0) then
continue;
r := ss_stack[n].index div 9;
c := ss_stack[n].index mod 9;
for d := 0 to 8 do
begin
if ((index and (1 shl d)) <> 0) then
continue;
change := update_mbit (d, r, c);
update += change;
if (sw_verbose <> 0) and (change <> 0) then
begin
write (inc_stepno (): 3, ') r', r+1, 'c', c+1, ' <> ', d+1, ' hidden subset[', ss_cells, '] ');
writeln (sector2str (sector, mask), '.{', mask2str (index), '}');
end;
end;
end;
end;
type_fishy:
begin
d := mask;
rcbt := sector div 9;
case rcbt of
type_row:
begin
bc := 'c';
cc := 'r';
end;
type_col:
begin
bc := 'r';
cc := 'c';
end;
end;
for n := 0 to 8 do
begin
if ((index and (1 shl n)) <> 0) then
continue;
r := sectors[sector, n] div 9;
c := sectors[sector, n] mod 9;
change := update_mbit (d, r, c);
update += change;
if (sw_verbose <> 0) and (change <> 0) then
begin
write (inc_stepno (): 3, ') r', r+1, 'c', c+1, ' <> ', d+1, ' fish[', ss_cells, '] ');
writeln (bc, mask2str (index), '\', cc, mask2str (ss_cover));
end;
end;
end;
end;
exit (update);
end;
function sets_search (level, start, mask : integer) : integer;
var
bits, nbits : integer;
begin
// Recursive and reentrant function to locate a set matching ss_cands and ss_cells limits
for start := start to ss_limit do
begin
ss_start[level] := start;
bits := ss_stack[start].cands;
if (bits = 0) then
continue;
bits := bits or mask;
nbits := cands2n[bits];
if (nbits > ss_cands) then
continue;
if (nbits = ss_cands) and (level = ss_cells-1) then
exit (bits);
bits := sets_search (level+1, start+1, bits);
if (bits <> 0) then
exit (bits);
end;
exit (0);
end;
function grid_t.subsets () : integer;
var
r, c, d, n, s, rcbt, rcbn, index, level, start, mask, count, update : integer;
begin
update := 0;
ss_limit := 8; // set stack limit to 9 cells for sets_search for standard locked sets searching
for s := 0 to 26 do // search each sector for naked locked sets
begin
for ss_cands := 2 to 4 do // find size 2 though 4 candidates
begin
ss_cells := ss_cands; // locked sets have ss_cells = ss_cands (N cells N candidates)
count := 0; // track how many cells are available for this sector/pass
for n := 0 to 8 do // look at all 9 cells within each sector using the sectors
begin
index := sectors[s, n]; // array sectors contains the 9 indexes for each sector
r := index div 9; // compute the row
c := index mod 9; // compute the column
mask := rc_cands[r, c]; // Use the RC space candidate bits cell r,c
ss_stack[n].cands := mask; // save the bits and the correct cell index
ss_stack[n].index := index; // in the search stack
if (cands2n[mask] < 2) then // if the number of bits is less than 2 (naked single or assigned)
ss_stack[n].cands := 0 // zap the candidates for this stack entry - it will be skipped
else
inc (count); // otherwise increment the counter of valid cells
end;
if (count < ss_cells) then // skip this sector if there are not enough cells to even try looking for a locked set N size
break;
level := 0; // initialize the 3 search parameters to start from the beginning of this sector
start := 0;
mask := 0;
while (level >= 0) do // level will go negative when we are completely done searching
begin
mask := sets_search (level, start, mask); // start the locked set search
while (mask <> 0) do // if the return value is not zero, then we found something
begin
update += subsets_update (mask, s, type_naked); // call the updating function with the mask sector and type
level := ss_cells - 1; // set the level to the top of the search stack (N - 1)
start := ss_start[level] + 1; // increment the start to skip the last entry found
mask := 0; // build a new mask to reflect everything prior to the top of the stack
for n := 0 to level-1 do
mask := mask or ss_stack[ss_start[n]].cands;
mask := sets_search (level, start, mask); // reenter the search for another locked set
end;
dec (level); // exhausted this scan - see if we can pick up elsewhere if the level is > 0
if level >= 0 then start := ss_start[level] + 1 else start := 0; // still possible to search
mask := 0; // rebuild the search mask and try again
for n := 0 to level-1 do
mask := mask or ss_stack[ss_start[n]].cands;
end;
end;
end;
for s := 0 to 26 do // search each sector for hidden locked sets
begin
rcbt := s div 9; // compute the type (row/col/box)
rcbn := s mod 9; // compute the correct row/col/box
for ss_cands := 2 to 4 do // find size 2 through 4 candidates
begin
ss_cells := ss_cands; // locked sets have ss_cells = ss_cands (N cells N candidates)
count := 0; // track how many cells are available for this sector/pass
for n := 0 to 8 do // look at all 9 cells within each sector using the sectors
begin
index := sectors[s, n]; // array sectors contains the 9 indexes for each sector
case rcbt of // use the correct RN/CN/BN space candidates depending on rcbt
type_row: // sectors 0..8 are rows
mask := rn_cands[rcbn, n];
type_col: // sectors 9..17 are cols
mask := cn_cands[rcbn, n];
type_box: // sectors 18..26 are boxes
mask := bn_cands[rcbn, n];
end;
ss_stack[n].cands := mask; // save the bits and the correct cell index
ss_stack[n].index := index; // in the search stack
if (cands2n[mask] < 2) then // if the number of bits is less than 2 (naked single or assigned)
ss_stack[n].cands := 0 // zap the candidates for this stack entry - it will be skipped
else
inc (count); // otherwise increment the counter of valid cells
end;
if (count < ss_cells) then
break;
level := 0;
start := 0;
mask := 0;
while (level >= 0) do
begin
mask := sets_search (level, start, mask);
while (mask <> 0) do
begin
update += subsets_update (mask, s, type_hidden);
level := ss_cells - 1;
start := ss_start[level] + 1;
mask := 0;
for n := 0 to level-1 do
mask := mask or ss_stack[ss_start[n]].cands;
mask := sets_search (level, start, mask);
end;
dec (level);
if level >= 0 then start := ss_start[level] + 1 else start := 0;
mask := 0;
for n := 0 to level-1 do
mask := mask or ss_stack[ss_start[n]].cands;
end;
end;
end;
for d := 0 to 8 do // search for simple fish in rows
begin
for ss_cands := 2 to fish_max do
begin
ss_cells := ss_cands;
count := 0;
for n := 0 to 8 do
begin
mask := rn_cands[n, d];
ss_stack[n].cands := mask;
ss_stack[n].index := 0;
if (cands2n[mask] < 2) then
ss_stack[n].cands := 0
else
inc (count);
end;
if (count < ss_cells) then
break;
level := 0;
start := 0;
mask := 0;
while (level >= 0) do
begin
mask := sets_search (level, start, mask);
while (mask <> 0) do
begin
ss_cover := mask;
for c := 0 to 8 do
begin
if ((mask and (1 shl c)) <> 0) then
update += subsets_update (d, c+9, type_fishy);
end;
level := ss_cells - 1;
start := ss_start[level] + 1;
mask := 0;
for n := 0 to level-1 do
mask := mask or ss_stack[ss_start[n]].cands;
mask := sets_search (level, start, mask);
end;
dec (level);
if level >= 0 then start := ss_start[level] + 1 else start := 0;
mask := 0;
for n := 0 to level-1 do
mask := mask or ss_stack[ss_start[n]].cands;
end;
end;
end;
for d := 0 to 8 do // search for simple fish in columns
begin
for ss_cands := 2 to fish_max do
begin
ss_cells := ss_cands;
count := 0;
for n := 0 to 8 do
begin
mask := cn_cands[n, d];
ss_stack[n].cands := mask;
ss_stack[n].index := 0;
if (cands2n[mask] < 2) then
ss_stack[n].cands := 0
else
inc (count);
end;
if (count < ss_cells) then
break;
level := 0;
start := 0;
mask := 0;
while (level >= 0) do
begin
mask := sets_search (level, start, mask);
while (mask <> 0) do
begin
ss_cover := mask;
for r := 0 to 8 do
begin
if ((mask and (1 shl r)) <> 0) then
update += subsets_update (d, r, type_fishy);
end;
level := ss_cells - 1;
start := ss_start[level] + 1;
mask := 0;
for n := 0 to level-1 do
mask := mask or ss_stack[ss_start[n]].cands;
mask := sets_search (level, start, mask);
end;
dec (level);
if level >= 0 then start := ss_start[level] + 1 else start := 0;
mask := 0;
for n := 0 to level-1 do
mask := mask or ss_stack[ss_start[n]].cands;
end;
end;
end;
exit (update);
end; |
|
|
| Back to top |
|
|
| nukefusion
| | Joined: 27 Jun 2009 | | Posts: 22 | | : | |
Items |
|
| Posted: Thu Jul 02, 2009 8:40 am Post subject: |
|
|
Fantastic, thanks again Paul. Your explanation has finally allowed me to understand this method, one that I thought completely out of my grasp. I've rewritten my algorithms and I've now got a shared search algorithm that can search for a subset in any of the 4 grid "views", whereas before there were different, messy algorithms for each of the different search types. It's massively reduced the amount of code and the readability has improved 10 fold. 
If there's one thing I've certainly learnt, it's that implementing a Sudoku solver, let alone one coded elegantly and not just a messy bunch of IF statements, is NOT the trivial task I foolishly assumed it would be.  |
|
| Back to top |
|
|
| strmckr
 | | Joined: 24 Apr 2009 | | Posts: 52 | | : | |
Items |
|
| Posted: Fri Jul 03, 2009 1:42 am Post subject: |
|
|
there is a few ways to search for a hidden subset,
i issolated mine into diffrent types over a generic call function.
to go from pairs to triples the sets are incresed by one candidate N.
and wrote a program for each.
i use a 3d arrays: x,y,(1-9) as a representation of the the pm state.
where 1-9 represent the active digits.
I have precalculatsion called R(ow) and C(ol) and Box.
i have issolated and sumed the # of each candidates per repestive area stored as:
x,(N total) for R & C
box,(n total) for boxes.
my functions calls the sum total per area and verifies it meets the requirment per level pairs <3, triples <4, quads <5
all it does is see that the row meets n candidtes requirment then validates the cells containing the spefic set of n candidtes total only 2 or 3 or 4 cells active per given type (pairs,triples,quads}.
if it identifies correctly i store the eliminations in its own respective array as: x,y,N where n is on or off.
notes:
i also use a box call function over a converting table function. to reperesnt bn space.
the box call function is pretty simplistic...
but more complex functions can get messy with out one.
there is a way to use this easy function to create the bn space.
so that all 4 areas are mainted easier.
ive written in pascal this test program so you can ser how it operates..
| Code: | program boxtest;
uses crt;
var
xb,yb, A,box,b:integer;
xn,yn:integer;
i,it:integer;
temp:integer;
begin
clrscr;
for yb:= 0 to 2 do
for xb:= 0 to 2 do
begin
Box:=(yb+(xb*3));
for it:=0 to 2 do { calls sub box y's}
for i:=(yb*3) to 2+(yb*3) do { calls sub box x's}
begin
Yn:= (it)+(xb*3); {calculates real y's given sub box x}
writeln(box,' ( ',I, ',',yn,' )'); {prints box:(x,y) coridnals on screen }
end;
end;
readln;
end |
on to the function.
| Code: |
procedure Hp;
var
xn,yn,yn2,n,n2,n3,temp,temp2,temp3,i,it:integer;
begin
for xn:= 0 to 2 do
for yn2:= 0 to 2 do
for n:= 1 to 8 do
for n2:= (n+1) to 9 do
begin
temp:=0;
temp2:=0;
temp3:=0;
if (R[(xn+(yn2*3)),n]>0) and (R[(xn+(yn2*3)),n]<3) and (R[(xn+(yn2*3)),n2]>0) and (R[(xn+(yn2*3)),n2]<3)
then
begin
for yn:= 0 to 8 do
if (pm[yn,(xn+(yn2*3)),n]=n) or (pm[yn,(xn+(yn2*3)),n2]=n2)
then temp:= temp+1;
end;
if (C[(xn+(yn2*3)),n]>0) and (C[(xn+(yn2*3)),n]<3) and (C[(xn+(yn2*3)),n2]>0) and (C[(xn+(yn2*3)),n2]<3)
then
begin
for yn:= 0 to 8 do
if (pm[(xn+(yn2*3)),yn,n]=n) or (pm[(xn+(yn2*3)),yn,n2]=n2)
then temp2:= temp2+1;
end;
if (Box[(xn+(yn2*3)),n]>0) and (Box[(xn+(yn2*3)),n]<3)
and (Box[(xn+(yn2*3)),n2]>0) and (Box[(xn+(yn2*3)),n2]<3)
then
for i:= 0 to 2 do
for it:= (xn*3) to 2+(xn*3) do
begin
yn:=(i)+(yn2*3);
if (pm[it,yn,n]=N) or (pm[it,yn,n2]=n2)
then
temp3:=1+temp3;
end;
{eliminations}
if temp=2
then
for yn:= 0 to 8 do
if (pm[yn,(xn+(yn2*3)),n]=n) or (pm[yn,(xn+(yn2*3)),n2]=n2)
then
for n3:=1 to 9 do
if ( n3 <> n) and ( n3 <> n2)
then
hpair[yn,(xn+(yn2*3)),N3]:=1;
if temp2=2
then
for yn:= 0 to 8 do
if (pm[(xn+(yn2*3)),yn,n]=n) or (pm[(xn+(yn2*3)),yn,n2]=n2)
then
for n3:=1 to 9 do
if ( n3 <> n) and ( n3 <> n2)
then
hpair[(xn+(yn2*3)),yn,N3]:=1;
if temp3=2
then
for i:= 0 to 2 do
for it:= (xn*3) to 2+(xn*3) do
begin
yn:=(i)+(yn2*3);
if (pm[it,yn,n]=n) or (pm[it,yn,n2]=n2)
then
for n3:= 1 to 9 do
if ( n3 <> n) and ( n3 <> n2)
then
Hpair[it,yn,n3]:=1;
end;
end;
end;
|
|
|
| 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
