The New Sudoku Players' Forum

[PIsaacson]

Arghh!!! Found a bug in my "speed up" algorithm that was causing it to skip many possible DSSs and it's back to about 15 minutes for exhaustive scans for all DSSs size 2-9. However, I went back to investigate the RN/CN candidate elimination errors and they are all due to using BOX type processing within these spaces. I remember now that these transformations "violate" the normal RC sudoku restriction that a box must contain all 9 candidates. So, I guess the answer to one of my original questions, "what operations are valid in RN/CN (forget about BN) space are valid?" is answered. Any logic that depends on box constraints must be avoided in RC/CN space. This still leaves pinnings (except for box hiddens), subsets (except for boxes), coloring (except for box conjugates)... I'm modifying all of my algorithms to skip any box type logic if the grid type is RN/CN and I'll see just how far I can go. Currently I have pinnings, box/col/row restrictions (obviously cannot be used at all in RN/CN space??), DSS subsets, x-coloring, POM fishing, niceloops, ALS chains, nishio/forcing chains modified. I think it's probably sufficient to simply test RN space since CN space seems like a reflective transformation, but I'm out of my depth here.

Back to the basics - limiting DSS to sizes 2-5 is fast and finds all normal single-sector subsets as well as a maximum of 5-sector DSSs. Transposing to RN space finds additional DSSs (hidden???) and reductions that are valid, provided that I skip box restrictions. The question that I have yet to determine is whether or not this is "as good" as the RC exhaustive 15 minute search. It's definitely faster - only takes a few millisecs to find all RC/RN DSSs sized 2-5, but it's performing different reductions. I'm starting to test the top1465 using exhaustive DSS (that's 15 * 1465 = 21975 / 60 = 366 / 24 = 15 days!) worth of processing. I already have my RC/RN tests and they only took about 1 minute total. Checking against the known DSS exemplars, it looks like RC/RN DSS can accomplish similar, albeit different, reductions.

I'll post my test results in about 2-3 weeks.

[StrmCkr]

I've never quite figured out why this is so, but typically naked/hidden subsets are searched for sizes 2-4 only. That would seem to leave a "hole" in the 9 - size for the inverse, but I guess singletons and full decks (1 & 9) are respectively uninteresting.

alrighty ill answer this question. to do with the inversion

there is only 9 cells to check.

singles naked = 8 cells left.
singles hidden or obscured is one plane of nine holding 1 candiate.

pairs = 2 cells on 2 planes linked as one. they can be hidden or naked. which leaves 7 cells open,

triples = 3 cells leaving 6 .

quads = 4 cells leaving 5

why seach for the larger number?
when the inversion say a search for a smaller set is quicker.

like a search for 3. and leaves the opposite 6 exposed.

you could search for the 6 linked cells expressing the triple it is valid but requires alot more search time and algorithms to check.

The better news is that I've got a much faster algorithm for finding all naked DSS sized 2-9, so I'm giving up on the hidden searching. I could transpose the space and execute the searches, but the reductions in RN/CN/BN space didn't result in valid boards after re-translating back to RC space. I've been looking at the traces and I'm kinda baffled because I thought that symmetry of translation allowed for equivalent operations in any space: pinning, restrictions, subsets, coloring, als, niceloops... should work in any space, shouldn't they???

no..
there is more offset rules boxs superseed rows & columns. and work in conjunction with them.

a set in a row in a box = restricitons only on the row + box.
a set on a column in a box = restrictions in the box + column.

box = restrictios in box.

rows accross many boxes = limits to row only.
columns across many boxes = limit to column only.

box + box + box = restrictions in any box. that sees specific cells of these boxes.

[PIsaacson]

StrmCkr,

Thanks for the reply - we crossed postings, but your comments regarding transformation into RC/CN space are absolutely correct. It took me some time to realize that boxes are really the problem, but it still means that I can perform a lot of operations in RN/CN space provided I ignore box constraints/logic. My tests while incomplete, are starting to demonstrate that RN/CN transformed DSSs are not as effective as the fully sized ones in RC space. It's really critical to allow boxes to be one of the disjoint sectors in order to fully locate all DSSs. That's just not possible in RC/CN space, so it's back to the drawing board.

I'm going to retry your suggestion of dividing the work. I'm thinking that it might be better to try a sector limit as well as a size limit when searching. Since any sector involves a maximum of 9 cells, a 2 sector DSS search should be much faster than a 3 sector ... I'll model the search using 27 sectors x 9 cells and assume that at least 1 cell is assigned and compute the number of comparisons required by DSS size by sector size.

[StrmCkr]

I'm going to retry your suggestion of dividing the work. I'm thinking that it might be better to try a sector limit as well as a size limit when searching. Since any sector involves a maximum of 9 cells, a 2 sector DSS search should be much faster than a 3 sector ... I'll model the search using 27 sectors x 9 cells and assume that at least 1 cell is assigned and compute the number of comparisons required by DSS size by sector size.

i wouldnt limit the sector size as then you would be missing some of the possible possible.

start with a size limit - mutiplie identical/similar candidates cells with 2 choices. where only 1 of the candidates should be identical in most or all boxes. => restrictions in intersections.

like the 78-78-68-68-78 subset.
2 permutations- same restriction. i consider this code a issomorphic and palindronic. as its a vairable code with only 1 outcome order doesnt matter. the end does.

size limit 1: - 2 candidates cell clusters with 1 similar candidates.
size limit 2: a 3 candidates cell with a cluster of 2 chains:
size 3: mutiple 3+ candiates cells linked by 2 candidates cells.

secotor limit is number of sectors (boxes) its sprawled across not really relevent in my opinion.

i would start with the easiest first. as if there is any easier placemetns restrictions then it changes the subgrids making larger ones smaller and u can repeat the search again.

if there is not any smalller dss then go to the next level and search. break the work up by size.