FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Optimizing the Search for Subsets Goto page Previous  1, 2          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Wed Nov 02, 2005 5:27 pm    Post subject: My oh my, I thought this topic had died ages ago! xyzzy wrote: It certainly is for singles! In my solver, I check each Cell.Candidates bitmap and each House.Value.Vacancies bitmap right after they are updated, to see if they reached 1 or 0 bits set. When 1 is reached, a naked/hidden single is reported and the corresponding bitmaps are checked and updated if required. When 0 is reached, the sudoku has no solution and the solvers reports the inconsistency and stops. I also keep 9x9 bitmaps for each digit, with the bits set for each unbound cell that has that digit amongst its candidates. Each time a candidate is eliminated, the bitmap for that digit is updated, and a change flag is set. This change flag is reset when coloring is tested for that digit. I could optimize this even further by keeping track of x-wing, swordfish, etc. tests, which also involve a single digit. There is also a central 9x9 bitmap for all unbound cells. The bits are set off when a clue is placed, or when the solver has bound a digit to a cell. I have a very efficient foreach implementation for these 9x9 bitmaps. In the static data, I have 9x9 bitmaps as a property of each cell, that have the bits set for each peer (20 bits set for each cell). These 9x9 bitmaps turned out to be the real timesaver for me, not only in solving time, but also in programming. Example: found an XY-wing, so I can eliminate the Z value at the intersection of cells XZ and YZ: VictimBitmap = CellXZ.PeerBitmap AND CellYZ.PeerBitmap AND Digit(Z).UnboundBitmap; foreach (int index in VictimBitmap) Cells[index].Values[Z].Eliminate(); 2 lines of code needed to handle this, and it can also be used in coloring. Each row, column and box also contain a changed flag, that is set when its candidates have changed. This flag is reset when it has been tested for subsets. The change you suggest would make it even more efficient. There are lots of ways to optimize the code, I think we haven't even scratched the surface yet. Ruud. Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Thu Nov 03, 2005 5:05 am    Post subject: Yes, isn't this marvelous? As I have mentioned on some other thread, all of the following are "the same": naked tuples hidden tuples x-wings & swordfish all they are are the same idea from different perspectives. That is why the simple routine as follows finds ALL of them: Code: function analyzeX(z,type,iscanfirstindex,List,ipt,jlist,ilist,nx,ny,msg){    var maxdim=List.length/2    if(ipt>=List.length||nx>maxdim||ny>maxdim)return 0    var maxlen=List.length/2+1    analyzeX(z,type,iscanfirstindex,List,ipt+1,jlist,ilist,nx,ny,msg)    if(iseliminated)return 1    var i=List[ipt]  //another row/col    ilist+=Pwr2[i]    if(iscanfirstindex){       jlist=jlist | Possible["X"+type][i][z]    }else{       jlist=jlist | Possible["X"+type][z][i]    }    nx=xNum(jlist)    ny++    if(nx>maxlen)return 0    if(ny==nx && analyzeFoundX(z,type,iscanfirstindex,jlist,ilist,nx,msg))return 1    return analyzeX(z,type,iscanfirstindex,List,ipt+1,jlist,ilist,nx,ny,msg) } (Note the doubly recursive code here -- this takes care of all possibilities of all dimensions in one go.) This is from http://www.stolaf.edu/people/hansonr/sudoku/subsets.js I'm sorry about the code, but the point is simly that passing through this routine 8 times does it all. Depending upon the parameters, we are searching for: naked sets in row i hidden sets in row i naked sets in column j hidden sets in column j X-Wings, Swordfish, etc. Row-based X-Wings, Swordfish, etc. Column-based these six amount to scanning the 6 sides of a cube in succession. Then we add a scan of the cells in a block and get: naked sets in block p hidden sets in block p I know, I could just look for naked and not hidden, but I didn't like getting the result that there was a 6-value naked set. So I let it go all ways, just half way each, as mentioned by others. _________________ Bob Hanson Professor of Chemistry St. Olaf College Northfield, MN http://www.stolaf.edu/people/hansonr Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Thu Nov 03, 2005 5:39 am    Post subject: Quote: So I let it go all ways, just half way each, as mentioned by others Actually, it is not quite half way each. When N is the number of unbound cells-digits in the set you're scanning, you can scan upto size N/2 in one direction, and (N-1)/2 in the other direction, so when searching subsets (tuples), you scan for naked subsets of size 2-3, and hidden subsets only of size 2, because a size 3 would have a complementary naked subset of size 3. I'm not sure whether you could also apply this limit to searching X-wing, swordfish, etc. in rows and columns. Ruud. Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Thu Nov 03, 2005 7:27 am    Post subject: right. With X-wings and Swordfish and the like it's the same. Say that we have a 6x6 grid of numbers. If there is a 2x6 set there that defines an x-wing (with attendant nodes that can be eliminated) then there is also a 6x4 in the other direction, rotated 90 degrees. (like hidden and naked). To see this, see http://www.stolaf.edu/people/hansonr/sudoku?,-9,-8,6,-1,-2,,-4,5,-5,-6,-2,-3ttt,5,-9ttt,-6,,-1,,-3,-6t,-5,-9,,-1,,-7,9,6tt,,-2ttt,,-6,-4,-5,-3,,-4,,-5,-7,,-8,-2 click the "4" in the number block to the right of the puzzle. You should see a 6x6 grid there of 4s. Jumping out at us is a 2x6 x-wing (taller than it is wide), but also there is, on its side, a 6x4 noname thing. So we need not search for the 4x4, just the 2x2. The presence of one actually guarrantees the presense of the other. It doesn't matter which we search for, the same intersecting blocks will be eliminated. _________________ Bob Hanson Professor of Chemistry St. Olaf College Northfield, MN http://www.stolaf.edu/people/hansonr Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Solving sudoku All times are GMT Goto page Previous  1, 2 Page 2 of 2   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