FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Find hidden singles with bits          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message arisser Joined: 11 Oct 2006 Posts: 7 : Items Posted: Mon Jul 16, 2007 1:06 pm    Post subject: Find hidden singles with bits Hi everyone, I am getting stuck finding hidden singles without a ton of looping and I wanted to see if some of you smart people out there could help me out. I am representing the possible candidates in a single cell as a binary string. So the candidates [2,3,9] would be 100000110. I am trying to find the hidden single 6 in the following row: Code:  [23], [23], [4], [12], [9], [8], [5], [36], [7] My question is, is there a bitwise operation I can do on the candidate cells 000000110 //23 000000110 //23 000000011 //12 000100100 //36 Where the end result is 000100000 //6 I can't figure it out, but it seems like it should be possible. Thanks for any insight you can provide! Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Mon Jul 16, 2007 3:09 pm    Post subject: This is how I store candidates in my current solver. My new solver -- still in progress -- uses a different way to store the bit patterns. One possibile solution to your query uses bitwise OR and bitwise NOT: temp = {23} OR {23} OR {12} = 000000111 hidden = {36} NOT temp = 000100000 Now, compare 'hidden' to each entry in array value[9] that contains a single bit for each value. If you get equality, then you know you have a hidden single for that value. Last edited by daj95376 on Mon Jul 16, 2007 3:16 pm; edited 1 time in total Back to top arisser Joined: 11 Oct 2006 Posts: 7 : Items Posted: Mon Jul 16, 2007 3:11 pm    Post subject: Here is the logic we used that seems to work 3 cells (a, b, and c): Code: a^(b|c)) & (b^(a|c) 4 cells: Code: a^(b|c|d)) & (b^(a|c|d)) & (c^(a|b|d)) Here is the code we used to figure it out. $bs contains the possible candidates for each cell we are checking. Code: # possible cell candidates $bs = array(262, 260, 132, 162); # all possible hidden singles $hs = 511;    #number of cells to check $count = count($bs);    for($x=0; $x<$count; $x++) {    $union = 0;    $currentCell = $bs[$x];    # union all other cell's candidates except current cell    for($y=0; $y<count> 0)         echo "hidden single is: " . $hs; Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Mon Jul 16, 2007 5:59 pm    Post subject: Quote: I am trying to find the hidden single 6 in the following row: Code: [23], [23], [4], [12], [9], [8], [5], [36], [7] I maintain bitvectors for: - Candidates in each cell - Unsolved cells in each house - Unsolved digits in each house - Candidates (by cell position) in each house + digit (unit constraint) These are used in various techniques, but the last will automatically reveal all hidden singles. Placements will update the "unsolved" bitvectors (and cause eliminations) Eliminations will update the "Candidates" bitvectors. Ruud _________________ Meet me at sudocue.net Back to top arisser Joined: 11 Oct 2006 Posts: 7 : Items Posted: Mon Jul 16, 2007 6:28 pm    Post subject: Ruud wrote: Quote: I am trying to find the hidden single 6 in the following row: Code: [23], [23], [4], [12], [9], [8], [5], [36], [7] I maintain bitvectors for: - Candidates in each cell - Unsolved cells in each house - Unsolved digits in each house - Candidates (by cell position) in each house + digit (unit constraint) These are used in various techniques, but the last will automatically reveal all hidden singles. Placements will update the "unsolved" bitvectors (and cause eliminations) Eliminations will update the "Candidates" bitvectors. Ruud Thanks for the reply, Ruud. I keep a bitvector of potential candidates for each house. I've been getting the candidates for a single cell by doing a union of the 3 houses a cell lives in. In the end, is it slower to do it this way compared to keeping track of it in a variable and updating it as you solve for cells? Also, could you elaborate a little by what you mean candidates in each house plus digit? I'm not sure you mean by unit constraint. Thanks again! Back to top arisser Joined: 11 Oct 2006 Posts: 7 : Items Posted: Mon Jul 16, 2007 6:48 pm    Post subject: daj95376 wrote: This is how I store candidates in my current solver. My new solver -- still in progress -- uses a different way to store the bit patterns. One possibile solution to your query uses bitwise OR and bitwise NOT: temp = {23} OR {23} OR {12} = 000000111 hidden = {36} NOT temp = 000100000 Now, compare 'hidden' to each entry in array value[9] that contains a single bit for each value. If you get equality, then you know you have a hidden single for that value. It looks like in your logic that you assume I know that {36} contains the hidden single, which I do not. Is this correct? Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Mon Jul 16, 2007 8:17 pm    Post subject: Quote: I keep a bitvector of potential candidates for each house. I've been getting the candidates for a single cell by doing a union of the 3 houses a cell lives in. In the end, is it slower to do it this way compared to keeping track of it in a variable and updating it as you solve for cells? It is slower by the time you implement more solving techniques, which will all need this data at some point. Quote: Also, could you elaborate a little by what you mean candidates in each house plus digit? I'm not sure you mean by unit constraint. A sudoku has cell constraints and unit constraints. A cell constraint specifies that each cell must contain a single digit. For obvious reasons, there are 81 cell constraints in a standard sudoku. A unit constraint specifies that a particular house must contain one instance of a particular digit. There are (9 * 3 * 9) = 243 unit constraints. A bitvector for a unit constraint has a bit for each cell position, which is set if the cell at that position still has a valid candidate for this digit. Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Mon Jul 16, 2007 8:24 pm    Post subject: arisser wrote: It looks like in your logic that you assume I know that {36} contains the hidden single, which I do not. Is this correct? No. Your initial post was very basic on content. You asked Code: ... is there a bitwise operation I can do on the candidate cells ... I can't figure it out, ... It appeared that you were having problems with bitmap set operations. I kept my reply simple and directed at the example you presented. There were N candidate cells. By ORing (N-1) of them and then performing a NOT with the N-th candidate cell, a hidden single could be detected in the N-th candidate cell if it exists. I left it up to you to realize that, in general, each candidate cell would need to be tested as the N-th candidate cell. Back to top Jean-Christophe Joined: 19 Mar 2006 Posts: 126 : Location: Belgium Items Posted: Tue Jul 17, 2007 3:13 am    Post subject: Hi, Here is the code I use. It iterates over the unsolved cells of a "house" (or sum cage for killer) and keep tracks of possibilities/candidates which may go in one cell or several cells. Code: /** * Searches all hidden singles in a "house" (or sum cage for killer) * @return bitset with all hidden singles possibilities/candidates. O if none found. * @param inCells array with unsolved cells in the house. * @param inMustHave bitset with (unsolved) mandatory inclusions of sum cage for killer. * For regular sudoku, inMustHave should contain all unsolved possibilities: * inMustHave = (1<<9)-1 * @param outValueToCell on exit, contains cells with hidden singles, indexed by value * Note: outValueToCell may contain references to cells which are not hidden singles, * should iterate over the returned bitset to get the hidden single values */ public static int findHiddenSingles(Cell[] inCells, int inMustHave, Cell[] outValueToCell) {    // iterate over the unsolved cells & count each unsolved possibility    // at each step in the cell iteration    // "one" holds hidden singles seen so far    // "several" holds possibilities which may go in several cells so far    int one=0, several=0, p, s, val;    for(int cellIdx=0; cellIdx<inCells.length; cellIdx++) {       // only consider mandatory inclusions of "unit"       p = inCells[cellIdx].getPossibilities() & inMustHave;       // intersect possibilities with hidden singles seen so far       s = p & one;       if(s != 0) {          // found several cells for some possibility(ies)          one &= ~s;      // not single any more          several |= s;   // but multiple          // if all possibilities may go in several cells          // no need to further search          if(several == inMustHave) {             return 0;          }       }       // remove possibilities which may go in several cells       s = p & ~several;       if(s != 0) {          // first cell for some possibility(ies)          // mark cell as possible hidden single          one |= s;          // store cell reference for all possibilities          do {             val = lowestBit(s);   // uses a lookup table             outValueToCell[val] = inCells[cellIdx];             s &= ~(1<<val);          } while(s != 0);       }    }    return one; } _________________ Jean-Christophe "When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes. Back to top dmhayden Joined: 01 Aug 2007 Posts: 16 : Location: Central New Jersey Items Posted: Fri Aug 17, 2007 5:17 pm    Post subject: Re: Find hidden singles with bits arisser wrote: Hi everyone, I am trying to find the hidden single 6 in the following row: Code:  [23], [23], [4], [12], [9], [8], [5], [36], [7] My question is, is there a bitwise operation I can do on the candidate cells 000000110 //23 000000110 //23 000000011 //12 000100100 //36 Where the end result is 000100000 //6 You can find all hidden singles in a row with a single pass through the cells. The trick here is to recognize that you're looking for a value that appears exactly once in the row. In the pseudo-C++ code below: BitMap is a bitmap. For simple sudoku, you can use an unsigned int. cell.knownValue is zero when the value of a cell is unknown and contains the value when it is known. cell.possibilities is a BitMap of the possible values that can go in that cell. Code:  1  BitMap atLeastOnce;    // Bit set when value appears in at least 1 cell  2  BitMap atLeastTwice;   // Bit set when value appears in at least 2 cells  3  BitMap exactlyOnce;    // Bit set when value appears in exactly 1 cell  4  5  // The above BitMaps are initially empty.  6  for each cell in the row {  7      if (!cell.knownValue) {  8           atLeastTwice |= atLeastOnce & cell.possibilities;  9           atLeastOnce |= cell.possibilities; 10      } 11  } 12  13  exactlyOnce = atLeastOnce & ~atLeastTwice; Lines 1-3 define bitmaps. Line 6 iterates over the cells in the row (or column, or box) Line 7 ensures that we only consider the cells that don't have known values yet. Line 8 updates the "atLeastTwice" bitmap. A value has been seen at least twice if you saw it already and you see it in the current cell's possibilities. Note that "&" is the bit-wise AND operator. Line 9 updates the "atLeastOnce" bitmap. You've seen it at least once if it occurs in this cell or if you've already seen it. Finally at line 13 we create our answer. A value appears in exactly one cell if it appears in AT LEAST one cell, but not in MORE THAN ONE cell. Here "&" is the bit-wise AND operator and "~" is the bit-wise NOT operator. At this point "exactlyOnce" is a bitmap of ALL the hidden singles in the row.[/code] Back to top bhavina Joined: 23 Feb 2008 Posts: 6 : Items Posted: Tue Feb 26, 2008 2:28 pm    Post subject: bit? why use bits? please explain Back to top dmhayden Joined: 01 Aug 2007 Posts: 16 : Location: Central New Jersey Items Posted: Tue Feb 26, 2008 2:57 pm    Post subject: Re: bit? bhavina wrote: why use bits? please explain Using the bitmap is typically a LOT faster than strings. You can "OR" together two bitmaps (i.e. a |= operation) in a single machine instruction. A bitmap also takes up substantially less space, although that doesn't really matter when solving sudoku puzzles. Back to top dmhayden Joined: 01 Aug 2007 Posts: 16 : Location: Central New Jersey Items Posted: Sat Jul 19, 2008 10:09 pm    Post subject: Re: bit? bhavina wrote: why use bits? please explain It occured to me just recently that I misunderstood bhavina's question. I thought he meant "why use bitmaps instead of arrays" when he probably really meant "why use a Bitmap class instead of just using integers and the bit-wise operators available in C++?" I used a Bitmap class so it would be clear when a variable was intended that way instead of being a number. It also let me add methods like count() to count the bits in the bitmap. Most of the simple methods are inline so the performance should be the same as with an int, at least as long as optimization is turned on. Finally, using a class means that I could extend the program to use a much larger board if I wanted to do that. The goal of my solver is clear code, with speed and elegance being a close second. Dave Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Programming sudoku All times are GMT Page 1 of 1   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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