First of all, thank you all for the replies.
Since I'm a noob here, my posts have to be approved before they appear on the forum. So, there's going to be a bit of time lag between your comments and my responses. My second post was sent before my first post had received any replies, after realizing I'd used a poor example. I was trying to anticipate some of the comments.
To keep things in chronological order, I'm now posting after SpAce's second comment. (My second post hasn't appeared yet.)
I think my second post addresses SpAce's first comments.
Regarding eleven's comment, this is a technique that I used very early on when I first started doing Sudokus, and wasn't very familiar with the standard solving methods. I was self taught up to that point. I was applying techniques like naked pairs/triples and pointing pairs/triples techniques erratically, without exactly knowing that there was a systematic way to look for them. So, at that time, the idea of looking at the possible arrangements of unused digits, was the only systematic way that I could think of, even though it is indeed cumbersome.
I had suspected that it was redundant and could be removed from my solver program, except for the previously mentioned fact that it would occasionally solve a cell even when applied immediately after a search for naked subsets. I now understand why that was happening. (Best way to answer my own question is to post it on a forum, and then right after I click the "Post" button, the answer comes to me, and I slap my forehead.)
My conclusion is that the "musical chairs" technique will solve all cells in a row, column or box that could have been solved by any other non-intersection technique or combination thereof, and does it in one application. However, it's unlikely that this technique would be any more efficient than that combination of techniques.
In looking for examples of why this technique solved cells when the other methods didn't catch the pattern, I found that it was simply due to the solve order. In one case there would have been a naked triple, but one of the participating cells was also a hidden single, which obscured the triple.
My solver program is definitely a work in progress, and no doubt the solve order is not optimal.
In its current form, it detects:
- Naked singles
- Hidden singles
- Naked subsets (pairs, triples, all the way up to naked septuples)
- Box/Line intersections (pointing pairs/triples etc.)
- X-wing
- XY-wing
I didn't include hidden pairs/triples/quads because the complementary naked subsets are detected, and my naked subset routine seemed to be far more efficient than I could make a hidden subset routine. At some point I'll have another look at that. My immediate priority is to add swordfish and some colouring techniques.
As for the solve order, this is how it goes:
- Code: Select all
1. Do an initial scan to set the cell candidates and solve any naked singles;
Loop:
2. Scan the grid repeatedly for hidden singles until no more can be found;
3. Scan the grid repeatedly for naked subsets until no more can be found;
4. Scan the grid repeatedly for box/line intersections until no more can be found;
5. Scan the grid once for "musical chairs;"
6. Scan the grid once for XY-wings;
7. Scan the grid once for X-wings;
8. If puzzle is not completely solved then:
Did the previous steps result in at least one candidate elimination?
- If yes, then go back and repeat starting at step 2.
- If no, then find the empty cell with the fewest candidates and call this main routine recursively, trying each of the cell's candidates until the correct one is found and the puzzle is solved.
Whenever any of the above techniques results in a naked single, that cell is solved, and a "RemoveCandidates" subroutine is called to remove that cell's value from the candidates of cells in the intersecting row/column/box. If that results in one or more naked singles then those cells are immediately solved and RemoveCandidates is called recursively. So, there is no need for a separate step in the main loop to solve naked singles.
So, with the above solve order and the RemoveCandidates routine, naked singles are immediately solved, but hidden singles won't be solved until the loop repeats.
FYI, I haven't looked at any existing solver source code to see how others have done it. I wanted to do this on my own, at least until I get to the point where I can't figure out how to proceed.
(Many do but that doesn't make them right.)
Besides, there are such good solvers around already that it's hard to see why I should write my own, except as a possibly fun exercise. However, I'm pretty sure that it would actually make me a better manual solver too, because coding requires one to think things through in a very detailed way, as you've probably noticed.