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   

Transposing Naked Subsets to find Hidden Subsets

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
nukefusion

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Mon Jun 29, 2009 7:01 pm    Post subject: Transposing Naked Subsets to find Hidden Subsets Reply with quote

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
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Tue Jun 30, 2009 5:10 pm    Post subject: Reply with quote

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
View user's profile Send private message
nukefusion

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Wed Jul 01, 2009 3:01 pm    Post subject: Reply with quote

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
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Wed Jul 01, 2009 7:46 pm    Post subject: Reply with quote

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
View user's profile Send private message
nukefusion

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Thu Jul 02, 2009 8:40 am    Post subject: Reply with quote

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. Very Happy

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. Embarassed
Back to top
View user's profile Send private message
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Fri Jul 03, 2009 1:42 am    Post subject: Reply with quote

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
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
Page 1 of 1

 
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