| View previous topic :: View next topic |
| Author |
Message |
| DarrylC
| | Joined: 22 Aug 2007 | | Posts: 11 | | : | | Location: Melbourne, Australia |
Items |
|
 Posted: Wed Oct 17, 2007 10:19 pm Post subject: |
 |
|
| gsf wrote: | does "cell/house singletons" mean "naked/hidden singles"?
I ask because, modulo bugs, easter monster requires { naked/hidden singles + locked-candidates } and 2 concurrent propositions to solve |
Rather than get the terminology wrong I mean:
| Code: |
1. Cell singleton=only candidate left for a cell
2. House singleton=only cell in house (row, column, box) with value |
Surprised me that this was all that was needed. I was stuck in the more is better approach, seems like I should have gone for the KISS approach.
When I first read your post I saw the singles+locked_candidates requirement for the easter monster and therefore assumed that this would be the "universal panacea", this was clearly my mistake. Rereading it, you had clearly alluded to the singles.
gsf, if you are interested, here is a way you can speed up your code.
| Code: |
Try what I am doing and start with the proposition of ~candidate and let it run/rip (applying sudoku solving rules)
1. Look for any cell with =candidate, any buddies of the two cells with candidate can be eliminated.
2. Look for any cell with another candidate (=candidate2) that is a buddie of the start cell. Cell1 <> candidate2, cell2 <> candidate1 |
|
|
| Back to top |
|
 |
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Thu Oct 18, 2007 2:33 am Post subject: |
|
|
| DarrylC wrote: |
Rather than get the terminology wrong I mean:
| Code: |
1. Cell singleton=only candidate left for a cell
2. House singleton=only cell in house (row, column, box) with value |
|
in this case the standard terminology will help us communicate
this is { (1) naked-singles (2) hidden-singles }
| Quote: |
| Code: |
1. Look for any cell with =candidate, any buddies of the two cells with candidate can be eliminated.
2. Look for any cell with another candidate (=candidate2) that is a buddie of the start cell. Cell1 <> candidate2, cell2 <> candidate1 |
|
please define buddy/buddies |
|
| Back to top |
|
|
| DarrylC
| | Joined: 22 Aug 2007 | | Posts: 11 | | : | | Location: Melbourne, Australia |
Items |
|
| Posted: Thu Oct 18, 2007 2:58 am Post subject: |
|
|
| gsf wrote: |
please define buddy/buddies |
Buddies, each cell has a set of 20 cells that it can see, I call these buddies. I originally saw this in Mad Overloards description of remote pairs section in his Sudoku Susser manual. The buddies are the 8 other cells in the box plus the 12 other cells of the row/column (6 in each) that are not in the same box but are in the same row/column as the original cell. Buddies do not include the original cell, ie a cell is not a buddie of itself.
buddies of both cells 1 & 2, any cells that can be seen by both cell 1 and cell 2.
I create a bitmap of the buddies for a cell, to get buddies of both I AND the two bitmaps together to get a bitmap with the common cells and then check these cells for the candidate. To check to see if a cell 1 is a buddy of cell 2 I merely check to see if the bit is set in the bitmap for the buddies of cell 2. |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Thu Oct 18, 2007 6:43 am Post subject: |
|
|
Darryl
After all this, I don't know what there remains in your chains/nets. You have no longer ALS, Hinges or any kind of subset in the chains?
Do you solve EM by merely combining "basic" AICs (~ nrc-chains) into nets? |
|
| Back to top |
|
|
| DarrylC
| | Joined: 22 Aug 2007 | | Posts: 11 | | : | | Location: Melbourne, Australia |
Items |
|
| Posted: Thu Oct 18, 2007 8:13 am Post subject: |
|
|
| berthier wrote: | Darryl
After all this, I don't know what there remains in your chains/nets. You have no longer ALS, Hinges or any kind of subset in the chains?
Do you solve EM by merely combining "basic" AICs (~ nrc-chains) into nets? |
The AIC extension is now very restricted as I only look for downstream implications that force cell/house singletons, however they are still recursive. I believe the basic net is extremely close to your xyt-chains (which I consider nets), however I incorporate bilocal cells as well so they may be more powerful.
If you run your program over the top1465 puzzles only using xyt-chains (any length) I would expect you to get a similar result (about 1100 puzzles solved) that I posted earlier.
The EM still needs two extra levels so you could think of it as xyt-chains with Almost Almost xyt-chains, still not easy to spot but an improvement. |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Thu Oct 18, 2007 9:12 am Post subject: |
|
|
| DarrylC wrote: | | The EM still needs two extra levels so you could think of it as xyt-chains with Almost Almost xyt-chains, still not easy to spot but an improvement. |
I think the proper reference here would be nrct chains, not xyt. If you consider them as nets, then I'm not sure we are speaking of the same thing.
xyt-chains with Almost Almost xyt-chains ????? Until I see such a thing, this remains very abstract for me. |
|
| Back to top |
|
|
| DarrylC
| | Joined: 22 Aug 2007 | | Posts: 11 | | : | | Location: Melbourne, Australia |
Items |
|
| Posted: Thu Oct 18, 2007 10:07 am Post subject: |
|
|
| berthier wrote: |
I think the proper reference here would be nrct chains, not xyt. If you consider them as nets, then I'm not sure we are speaking of the same thing. |
If nrct chains are the same as AIC/NL then I would agree and they are not nets. The extension I propose turns then into nets.
The reason for the xyt-chains reference is that with the updated algorithm then you can find xyt-chains by starting on a bivalued cell (AB) with ~A => B, then mark all cells that are affected by B with ~B, look for singletons and continue until you find a cell that ends up with a singleton A. Then any cells seen by the first and last with candidate A can have A removed.
| berthier wrote: |
xyt-chains with Almost Almost xyt-chains ????? Until I see such a thing, this remains very abstract for me. |
I am working on how to show the reductions although not as quickly as I would like. |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Fri Oct 19, 2007 3:33 am Post subject: |
|
|
| DarrylC wrote: | if you are interested, here is a way you can speed up your code.
| Code: |
Try what I am doing and start with the proposition of ~candidate and let it run/rip (applying sudoku solving rules)
1. Look for any cell with =candidate, any buddies of the two cells with candidate can be eliminated.
2. Look for any cell with another candidate (=candidate2) that is a buddie of the start cell. Cell1 <> candidate2, cell2 <> candidate1 |
|
thanks for the response(s) and buddy confirmation
I defined the P (proposition) method in my solver to exemine the results of each proposition independently
and not do link/chain-type analysis on those results (like 1. and 2. above)
that is left for the Y cycle method which handles 1. and 2. among other cases
this is because P is intendended for measuring and not solving
manily due to P being brute force / mechanical / too much work vs more traditional logic methods
but that's not to say the P method is devoid of anomalies (ratings that don't match percieved reality)
and cases like 1. and 2. above may help explain some of those, so that's something to keep in mind |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
