All advanced techniques boil down to this?

abangser

My non-expert analysis of advanced techniques I have found on the web is that they seem to boil down to only two rules: 1) evaluate the candidates in a given cell and eliminate any that lead (via basic techniques) to a "dead-end". (A dead-end is reached when any other cell is left with no remaining candidates, or a row, column or box is left without any candidates for a particular number), and 2) determine whether all candidates in a cell lead to the unanimous conclusion (again following basic techniques) that some candidate in another cell is not in the solution - and so turn that one off.

These two rules are all I need to solve every puzzle I have found on the web with unique solutions (so far) with my Excel VBA solver. It's seems clear that these rules incorporate techniques such as forcing chains and X-Wings. But can anyone point out an advanced technique that these rules do not address? I'm new to the group, so if this is an old question, just point me in the right direction. Thanks.

abangser · Posted: Sun Dec 03, 2006 11:45 pm Post subject:

Since posting this message, I have tested many of the hardest puzzles, up to a rating of 99995, and solved them all using only a) basic strategies of naked and hidden singles, doubles, and triples, and candidates common to intersecting rows, columns and boxes, and b) the two advanced strategies explained below. If anyone wants to try this Excel VBA solver, it's found at my bangser website.

I have no idea whether this proves that all advanced strategies can be "found" by programming these two rules, but it's worked so far. Please provide feedback if I have missing something and/or if there is an Advanced Technique that adds new information not found in these rules. Again, they are:

1. Try each candidate in a cell and eliminate the candidates that lead (using basic strategies) to a conflict. (To avoid guessing the solution, I ingore any 81-cell solutions found in this process.)

2. Examine where the candidates that do not lead to a conflict get stuck to see if theyunanimously agree that any candidate remaining anywhere on the board can be eliminated.

Ruud · Site Admin

Hi,

your method is also known as Trial & Error, Ariadne's Thread, Tabling and Forcing Nets. It will solve all but a few Sudokus.

Here is a puzzle that will escape your methods (#77/top1465):

abangser · Posted: Mon Dec 04, 2006 12:35 pm Post subject:

Hi,

My program easily solves the posted puzzle (#77/top1465). And every other puzzle I have tested.

I do not think there is a mathematical difference between my two processes and the many advanced strategies found on the board. I guess Advanced Strategies exist so that humans are more likely to find some of the simpler patterns. If you think about it, to find an X-Wing is to discover that both candidates in a cell lead to the same conclusion that one of the numbers can not be found in other cells of the same column or row. That's the same as my second process. OTOH forcing chains and coloring (and others) are found with my first process.

Thank you for your reply. If you think there are any other puzzles that I should use to test or improve my program, please forward. Thanks again.

Ruud · Site Admin

Hi,

if your solver easily solves #77, then you must have some hidden power in your solver that goes beyond simple implication networks.

Can you tell me which step your solver uses at this point?

abangser · Posted: Tue Dec 05, 2006 5:17 am Post subject:

Ruud -

My solver never hits exactly the position in your post. I'll write some code tomorrow to import your exact position to see what it finds next. If you want to run the program in the meantime, download it from www bangser com slash sudoku dot htm.

Andy

abangser · Posted: Tue Dec 05, 2006 1:02 pm Post subject:

Ruud - starting from your position and assuming (1,2) refers to the cell in row 1, col 2, then the first things my solver finds are:

1. Testing candidate 5 in (1,2) leads to conflict in (9,5) - so eliminate that candidate
2. Testing 5 in (1,3) leads to conflict in (6,5) - ditto
3. Testing 1 in (1,4) leads to conflict in (5,3) - ditto
4. Testing 5 in (1,5) leads to conflict in (9,2) - ditto
5. Testing 2 in (1,6) leads to conflict in (8,3) - ditto
6. Testing 6 in (1,6) leads to conflict in (6,8) - ditto
7. All 3 remaining candidates in (1,6) (they are 3, 5 and 9) agree that candidate 4 in (4,6) should be eliminated. That leaves only one candidate in (4,6).

"Testing " means to use basic strategies only to solve forward until either a conflict occurs or else you stop making progress.

"Conflict" means a cell has no remaining candidates or a test area has no candidates of a particular number.

I had my solver set to "Level 1" for this test. When I set it to "Level 3" it applies these tests recursively whenever it stops making progress during a test. The result is a much faster solution, but more difficult to express.

I'm new to this and appreciate your feedback. Regards.

Ruud · Site Admin

This clarifies a lot. Your solving method boils down to "trial & error", where you plug in a number and use your basic suite of solving techniques to detect a conflict.

In simple implication networks, as implemented in tabling and Bowman bingo, only direct implications (naked and hidden singles) are taken into consideration. To prove a conflict for candidate 5 in r1c2, you need at least locked candidates to reach a conflict.

I'm convinced that your method will lead to the solution, but what will it teach the human player using the program? Have you tried to write the full implication network that leads to the conflict in r9c5?

Many advanced solving techniques are designed to avoid T&E, by looking at means to advance the puzzle using repeatable methods that can be taught to the player.

abangser · Posted: Wed Dec 06, 2006 5:45 am Post subject:

Very interesting, actually. Based on your comments, I discovered that I do only need naked and hidden singles and locked candidates to solve #77, and it runs alot faster as a result. I reach a solution even if this process is not applied recursively. I'll see if I can use the solver to write out the implication network that leads to the conflict in r9c5, but I infer that better minds than mine have already proven this to be difficult.

BTW, why do you suggest that locked candidates makes this process "T&E"? Seems a simple step that humans can find/follow as easily as singles. Where is the line between T&E and testing candidates until an implication network is found? For example, the posts I read about Bowman Bingo seem to require similar testing.

Thanks again.