|
| View previous topic :: View next topic |
| Author |
Message |
| Nick70
| | Joined: 08 Jun 2005 | | Posts: 160 | | : | |
Items |
|
 Posted: Sat Jul 09, 2005 8:45 pm Post subject: Double implication chains |
 |
|
I don't think this is a "new" technique, but I haven't found a precise description of it the way I'm doing it, which seems to be more general than the common implementations.
The basic idea is to find two mutually excluding possibilities (only two possible numbers in a cell, or only two possible cells for a number in a row/column/box) which cause another cell to contain the same number no matter which of the two possibilities is chosen.
Now, I've usually seen this technique applied on chains of cells containing only two possibilities each. But it doesn't have to be like that! Let's see why with a very simple example.
| Code: | 3 4 9 | 6 5 8 | 7 2 1
7 8 5 | 9 2 1 | 6 3 4
16 2 16 | 3 7 4 | 8 9 5
-------------------+--------------------+-------------------
28 36 346 | 7 368 5 | 234 1 9
5 9 346 | 2 1 36 | 34 7 8
28 1 7 | 4 38 9 | 23 5 6
-------------------+--------------------+-------------------
4 7 8 | 5 9 2 | 1 6 3
9 36 2 | 1 4 36 | 5 8 7
16 5 136 | 8 36 7 | 9 4 2 |
In column 2, number 6 can only be in two cells.
If (8,2)=6, then (8,6)=3, and then (5,6)=6. Nothing new for now.
If (4,2)=6, then we don't know what (4,5) is; but we know it isn't 6. Therefore (5,6)=6.
The consistent notation I use for these chains is this:
(8,2)=6 => (8,6)<>6 => (5,6)=6
(4,2)=6 => (5,3)<>6 => (5,6)=6
Let's see how this can be turned into an algorithm, with a slightly more complicated example.
| Code: | 3 1 25 | 6 4578 89 | 2789 24 789
6 25 4 | 79 3578 389 | 23789 1 3789
8 9 7 | 1 2 34 | 5 6 34
----------------------+-----------------------+----------------------
129 2348 12369 | 79 13678 5 | 23678 24 13678
1245 7 12356 | 238 1368 12368 | 2368 9 13468
129 238 12369 | 4 13678 123689 | 23678 5 13678
----------------------+-----------------------+----------------------
24 6 8 | 23 9 234 | 1 7 5
7 235 12359 | 25 16 126 | 4 8 69
159 45 159 | 58 1468 7 | 69 3 2 |
We want to prove that (1,3)=5. We will do that by building an implication tree, and exploring it breadth first.
1/ Write a '1' under (1,3)=5, meaning that it's the first node in the tree.
2/ Look for all possibilities conjugated with (1,3)=5; that is, all possibilities that when false imply (1,3)=5. They are (1,3)=2, (2,2)=5 and (1,5)=5. Write a '2' under them, meaning that they are at level 2 in the tree.
3/ Look for all possibilities that exclude the possibilities we have just marked with '2'. Note that at this point we don't need them to be conjugates. We don't care what number actually gets placed in those placed, we just want the '2's to be false - because that will mean '1' is true.
Of course all three possibilities are excluded by (1,3)=5; but we have already written '1' under it so we won't consider it again.
(1,3)=2 is excluded by (1,7)=2, (1,8)=2, (2,2)=2, (4,3)=2, (5,3)=2, (6,3)=2, (8,3)=2.
(2,2)=5 is excluded by (2,2)=2, (2,5)=5, (8,2)=5, (9,2)=5.
(1,5)=5 is excluded by (2,5)=5, (1,5)=478
Write '3' under all those possibilities, meaning that they are at level 3 in the tree.
4/ go back to step 2/, writing '4' under all yet unmarked possibilities that are conjugates of possibilities you just marked as '3'.
The general rule is that when you go from an odd level to an even level in the tree, you look for conjugates; when you go from an even level to an odd level, you look for all excluding possibilities.
After placing the '4's the grid will look like this:
| Code: | 3 1 25 | 6 4578 89 | 2789 24 789
21 3233 3 34
6 25 4 | 79 3578 389 | 23789 1 3789
32 3 4
8 9 7 | 1 2 34 | 5 6 34
4
----------------------+-----------------------+----------------------
129 2348 12369 | 79 13678 5 | 23678 24 13678
3 4
1245 7 12356 | 238 1368 12368 | 2368 9 13468
3
129 238 12369 | 4 13678 123689 | 23678 5 13678
3
----------------------+-----------------------+----------------------
24 6 8 | 23 9 234 | 1 7 5
7 235 12359 | 25 16 126 | 4 8 69
3 3
159 45 159 | 58 1468 7 | 69 3 2
43 4 |
Now when going to fill in the '5's, you will notice that (9,2)=4 and (9,5)=4 are conjugates, and they are both at level 4 in the tree. This means that they both start an implication chain that forces (1,3)=5. So we have proven what we wanted.
From the grid above you can also reconstruct the chains back to the root. You start e.g from (9,2)=4, which is marked '4', and look for a '3' that can be reached from there. The rules are the opposite of the previous ones:
- when going from an odd level to an even level in the tree, look for any possibility;
- when going from an even level to an odd level, look only for conjugates.
Nodes at an odd level in the tree are TRUE; nodes at an even level are FALSE.
The end result is:
(9,2)<>4 => (9,2)=5 => (2,2)<>5 => (1,3)=5
(9,5)<>4 => (1,5)=4 => (1,5)<>2 => (1,3)=5
If starting with an exclusion disturbs you, you can view it like this:
(9,5)=4 => (9,2)<>4 => (9,2)=5 => (2,2)<>5 => (1,3)=5
(9,2)=4 => (9,5)<>4 => (1,5)=4 => (1,5)<>2 => (1,3)=5
Note that because of the way the algorithm works, the two chains will always have the same length and you'll always find the ones with minimal length.
I have mixed feelings about this technique.
On one hand, the chains are beautiful proofs, and give a pleasant sense of cleanliness.
On the other hand, like nishio, before finding a chain that works you have to go all around the grid testing a lot of possibilities. And every time you want to test a possibility, you have to start again.
The coloring algorithm is much better on this regard, because you color the grid only once, and then draw conclusions. But it doesn't give the same sense of "rightness" when you place a big number.
I have tested the double chains technique on my library of problems. It solved ALL problems that could be solved with coloring, and many more. So it is very powerful.
Very interestingly, I found also some problems that could not be solved eithe by coloring alone, not by double chains alone, but that could be solved by applying both techinques. I will have to double check if this is actually the case or just caused by some bug in the program. |
|
| Back to top |
|
 |
| Nick70
| | Joined: 08 Jun 2005 | | Posts: 160 | | : | |
Items |
|
| Posted: Sat Jul 09, 2005 11:15 pm Post subject: |
|
|
This is probably one of the hardest problems that can be solved using double implication chains.
| Code: | ..9.7.6.4
.326.....
5........
.....5...
..6.1.7..
...4.....
........3
.....752.
8.7.6.1.. |
|
|
| Back to top |
|
|
| Insight
| | Joined: 08 Aug 2005 | | Posts: 3 | | : | |
Items |
|
| Posted: Mon Aug 08, 2005 11:05 am Post subject: |
|
|
Hi
Here is a simpler one for you to test, which was actually the puzzle published in the Daily Telegraph newspaper (UK) on 4 August:
| Code: | 4..|21.|.6.
...|.7.|.8.
.52|.6.|...
-----------
..1|6..|..4
67.|...|.95
3..|..7|8..
-----------
...|.4.|25.
.3.|.2.|...
.4.|.93|..1
|
Standard logic can advance it to this position:
| Code: | 4..|21.|.6.
...|.7.|.82
.52|.6.|...
-----------
5.1|6.9|7.4
67.|..2|.95
3..|.57|8.6
-----------
...|.4.|253
.3.|.2.|948
24.|.93|671
|
At this point (after cleaning up any naked pairs/naked triples) the Simple Sudoku program is stuck, and guesswork looks like the only option.
But if we focus on the top 3 rows only:
| Code: |
4 89 3789 | 2 1 58 | 53 6 79
| |
19 16 369 | 39 7 45 | 45 8 2
| |
789 5 2 | 39 6 48 | 134 13 79
| | |
(1,9) and (3,9) contain the pair {79}. Whichever way around those are, the value in (2,4) must be 9 (three moves one way, five the other way). Inserting that value makes the solution of the remainder of the puzzle trivial.
I don't know how an algorithm could tell you that the best pair (or one of the best pairs) to look here at is the pair in (1,9) and (3,9) - I mean there are plenty of other pairs you could choose which might or might not lead to a solution of the puzzle. For a human player, this approach is suggested by the "right angled" or "L shaped" configuration of the 3s and 9s in boxes (2,3) (2,4) and (3,4).
(Please forgive if this post is very newbish or off-topic) |
|
| Back to top |
|
|
| MadOverlord
| | Joined: 01 Jun 2005 | | Posts: 80 | | : | | Location: Wilmington, NC, USA |
Items |
|
| Posted: Tue Aug 09, 2005 11:55 am Post subject: |
|
|
It's a nasty puzzle, but it also falls to Bowman Bingo after a struggle. My hunch is DIC has elements of that algorithm and Tables.
What we seem to be finding is a toolkit of techniques of varying degrees of generality that solve particular problems. The art (and difficulty) is figuring out what techniques to try in order to most efficiently solve the problem.
It's one thing to say "the following short chain of inferences generates a contradiction". The real question is "how much work was it to find that chain?" The cost of checking several "simpler" techniques and having them fail might be more than the cost of trying a more laborious but general heuristic.
I was going to post the Susser trace of the solution to your puzzle, but it's too long for the forum! That's definitely a sign that it's a good one! |
|
| Back to top |
|
|
|
|
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 |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
