Sudoku Programmers :: View topic

FAQ

Memberlist

Usergroups

Profile

Ultracolouring
Goto page 1, 2, 3, 4 Next

Sudoku Programmers Forum Index -> Solving sudoku

View previous topic :: View next topic

Author

Message

AMcK

Joined: 07 Apr 2005

Posts: 89

Location: Cambridge

Items

Posted: Sat Aug 27, 2005 10:56 pm Post subject: Ultracolouring

[Note: I see after posting that Nick70 has already posted on this subject in the tabling thread]
Adding verities and veracities to supercolouring has enabled it to solve many more tough puzzles. The availability of the implies[u,v] matrix means that *all* of the common implications can be discovered by a short fragment of code in a fraction of a second.

The algorithm outline is now simply ...

Assign colours to every possible
Put possibles in each cell into exclusion matrix
Put possibles in each house into exclusion matrix
Put conjugate pairs in houses into conjugate matrix
Put conjugate pairs in 2-possible cells into conjugate matrix
Eliminate conjugate identities
Compute transitive closure of exclusion matrix
Create implication matrix from exclusion and conjugate matrices
Find contradictions in exclusion matrix
Find verities and veracities using implication matrix

Here's an example using Menneske 900610.

The original is

Code:

4 ¦ 8 ¦ 7
1 ¦ ¦ 4
9 8 ¦ 4 ¦ 2 5
---------+----------+----------
8 2 ¦ 6 ¦ 1 7
¦ 7 ¦
5 ¦ 2 ¦ 4
---------+----------+----------
2 9 ¦ 1 ¦ 4 7
5 ¦ ¦ 2
7 ¦ 3 ¦ 6

Simple reductions get us to

Code:

2 36 4 ¦ 1369 8 5 ¦ 7 139 1369
367 1 5 ¦ 3679 2 379 ¦ 389 4 3689
367 9 8 ¦ 1367 16 4 ¦ 2 5 136
------------------+-------------------+-------------------
8 34 2 ¦ 3459 459 6 ¦ 1 39 7
9 346 136 ¦ 1348 7 38 ¦ 5 68 2
5 7 136 ¦ 2 19 389 ¦ 39 68 4
------------------+-------------------+-------------------
36 2 9 ¦ 568 56 1 ¦ 4 7 358
14 5 36 ¦ 46789 469 789 ¦ 389 2 1389
14 8 7 ¦ 459 3 2 ¦ 6 19 159

The colour map is

Code:

2 3a6a 4 ¦ 1a3b6b9a 8 5 ¦ 7 1b3c9b 1c3d6c9c
3e6d7a 1 5 ¦ 3f6e7b9d 2 3g7c9e ¦ 3h8a9f 4 3i6f8b9g
3j6g7d 9 8 ¦ 1d3k6h7a 1e6i 4 ¦ 2 5 1f3l6j
---------------------+--------------------------+------------------------
8 3m4a 2 ¦ 3n4b5a9h 4c5b9i 6 ¦ 1 3o9j 7
9 3p4d6k 1g3q6l ¦ 1e3r4a8c 7 3s8d ¦ 5 6m8e 2
5 7 1e3t6m ¦ 2 1g9k 3u8e9l ¦ 3c9m 6o8g 4
---------------------+--------------------------+------------------------
3w6p 2 9 ¦ 5c6q8h 5a6r 1 ¦ 4 7 3x5e8i
1k4f 5 3x6s ¦ 4g6t7c8j9n 4h6u9o 7g8k9p ¦ 3z8b9q 2 1l3A8m9r
1l4i 8 7 ¦ 4f5e9s 3 2 ¦ 6 1n9t 1o5g9u

The full 106x106 matrices are rather too big to post but here's the first 29x29 corner combined

Code:

1a 1b 1c 1d 1e 1f 1g 1k 1l 1n 1o 3a 3b 3c 3d 3e 3f 3g 3h 3i 3j 3k 3l 3m 3n 3o 3p 3q 3r 3s
1a . x x x x . i i x i x . x . . . . . . . . . . . x . . x . .
1b x i x . x x i i x xc x . . x . . . . . . . . . x x i . x x .
1c x x . . . x . i x i x . . . x . . . . . . . . . . . . . . .
1d x . . . x x i . . . x . . . . . . . . . x x . . x . . x . .
1e x x . x i x x i x i x x x i x . . x x x . . x i x x x x x i
1f . x x x x . i i x i x . . . . . . . . . . . x . x . . x . .
1g . . . . x . i . . . x . . . . . . . . . . . . . x . . x . .
1k . . . . . . . i xc . . . . . . . . . . . . . . . . . . . . .
1l x ix x . x x i ixcix ix x x x ix x . . . x x . . x ix x ix x x x .
1n . xc . . . . . i x i x . . . . . . . . . . . . . . . . . . .
1o x ix x x ix x ix i x ix x x x ix x x . x x x x . x ix x ix x x x i
3a . . . . x . i i x . x i x x x x . x . . x . . x x i x x x i
3b x . . . x . i i x . x x . x x . x x . . . x . x x i . x x .
3c . x . . . . . i x i x x x i x . . . x x . . x . . xc . . . .
3d . . x . x . i i x . x x x x . x . x x x x . x x x i x x x i
3e . . . . . . . . . . x x . . x . x x x x x . x . x . . x . .
3f . . . . . . . . . . . . x . . x . x x x . x . . x . . . x .
3g . . . . x . i . . . x x x . x x x . x x . x x . x . . x . x
3h . . . . x . i i x . x . . x x x x x . x . . x x x i . x x .
3i . . . . x . i i x . x . . x x x x x x . x . x x x i x x x i
3j . . . x . . . . . . x x . . x x . . . x . x x . x . . x . .
3k . . . x . . . . . . . . x . . . x x . . x . x . x . . . x .
3l . . . . x x i i x . x . . x x x . x x x x x . x x i x x x i
3m . x . . . . . i x i x x x i x . . . x x . . x i x x x x . .
3n x x . x ix x ix i x i x x x i x x x x x x x x x ix x x x x x ix
3o . . . . x . i i x . x . . xc . . . . . . . . . x x i . x x .
3p . . . . x . i i x . x x . . x . . . . x . . x x x . . x x x
3q x x . x ix x ix i x i x x x i x x . x x x x . x ix x x x x x ix
3r . x . . x . i i x i x x x i x . x . x x . x x i x x x x . x

Key: x=excludes, c=conjugates, i=implies

Ultracolouring makes the following deductions

Code:

Contradictions
Contradiction: 1l excludes itself
Reduction: 1l=false in {8,9} before=1389 after=389
Reduction: 1l=false in {9,1} before=14 after=4
Forcing: 1k=true {8,1} before=14 after=1
Reduction: 4f=false in {9,4} before=459 after=59
Contradiction: 1o excludes itself
Reduction: 1o=false in {9,9} before=159 after=59
Contradiction: 3n excludes itself
Reduction: 3n=false in {4,4} before=3459 after=459
Contradiction: 3q excludes itself
Reduction: 3q=false in {5,3} before=136 after=16
Contradiction: 6b excludes itself
Reduction: 6b=false in {1,4} before=1369 after=139
Contradiction: 6g excludes itself
Reduction: 6g=false in {3,1} before=367 after=37
Contradiction: 8c excludes itself
Reduction: 8c=false in {5,4} before=1348 after=134
Contradiction: 8k excludes itself
Reduction: 8k=false in {8,6} before=789 after=79
Contradiction: 9h excludes itself
Reduction: 9h=false in {4,4} before=459 after=45
Contradictions: 0 mS

Verities
Verity: {3,9}=1f3l6j all imply 6h=False
Reduction: 6h=false in {3,4} before=1367 after=137
Verity: {5,2}=3p4d6k all imply 3d=False
Reduction: 3d=false in {1,9} before=1369 after=169
Verity: {5,3}=1g3q6l all imply 4b=False
Reduction: 4b=false in {4,4} before=45 after=5
Forcing: 5a=true {7,5} before=56 after=5
Reduction: 5b=false in {4,5} before=459 after=49
Reduction: 5c=false in {7,4} before=568 after=68
Reduction: 5e=false in {7,9} before=358 after=38
Reduction: 5e=false in {9,4} before=59 after=9
Reduction: 1b=false in {1,8} before=139 after=39
Forcing: 1n=true {9,8} before=19 after=1
Forcing: 5g=true {9,9} before=59 after=5
Reduction: 9a=false in {1,4} before=139 after=13
Reduction: 9d=false in {2,4} before=3679 after=367
Reduction: 9n=false in {8,4} before=46789 after=4678
Reduction: 9o=false in {8,5} before=469 after=46
Reduction: 9p=false in {8,6} before=79 after=7
Reduction: 7c=false in {2,6} before=379 after=39
Reduction: 7c=false in {8,4} before=4678 after=468
Verity: {5,3}=1g3q6l all imply 5a=True
Verity: {5,3}=1g3q6l all imply 5b=False
Verity: {5,3}=1g3q6l all imply 5c=False
Verity: {5,3}=1g3q6l all imply 5e=False
Verity: {5,3}=1g3q6l all imply 5g=True
Verity: {5,3}=1g3q6l all imply 6r=False
Verity: {5,3}=1g3q6l all imply 9u=False
Verities: 141 mS

The final grid is

Code:

2 36 4 ¦ 13 8 5 ¦ 7 39 169
367 1 5 ¦ 367 2 39 ¦ 389 4 3689
37 9 8 ¦ 137 16 4 ¦ 2 5 136
------------+-------------+-------------
8 34 2 ¦ 5 49 6 ¦ 1 39 7
9 346 16 ¦ 134 7 38 ¦ 5 68 2
5 7 136 ¦ 2 19 389 ¦ 39 68 4
------------+-------------+-------------
36 2 9 ¦ 68 5 1 ¦ 4 7 38
1 5 36 ¦ 468 46 7 ¦ 389 2 389
4 8 7 ¦ 9 3 2 ¦ 6 1 5

A second pass of ultracolouring is required to discover the remaining contradictions needed to complete the solution.

Surpisingly, it's no longer necessary to run standard rules before and after ultracolouring although they do run a bit quicker.

There are still some tough puzzles that the technique can't solve completely but tabling can - I'm still looking at Mad Overlord and Trebor's results to see how they do it.

Regards
Andrew

MadOverlord

Joined: 01 Jun 2005

Posts: 80

Location: Wilmington, NC, USA

Items

Posted: Mon Sep 05, 2005 12:16 pm Post subject:

Quote:

There are still some tough puzzles that the technique can't solve completely but tabling can - I'm still looking at Mad Overlord and Trebor's results to see how they do it.

One and the same; my full nickname is "Trebor the Mad Overlord", from a character in a game I co-wrote about 25 years ago, "Wizardry". The other author is known on the net as "Werdna the Evil Wizard" for similar reasons.

Looking forward to see if you can find the "secret sauce" in Tabling that you are missing -- AFAICT I've completely documented it though.

The real payoff from these techniques is going to be using them to find new solving subheuristics that humans can learn to "just see."

AMcK

Joined: 07 Apr 2005

Posts: 89

Location: Cambridge

Items

Posted: Mon Sep 05, 2005 9:32 pm Post subject:

AMcK wrote:

There are still some tough puzzles that the technique can't solve completely but tabling can

MadOverlord wrote:

Looking forward to see if you can find the "secret sauce" in Tabling that you are missing -- AFAICT I've completely documented it though.

The secret sauce seems to lie in Susser's verity maneouvres like

Code:

R6C3=5 (All other possibilities excluded via pin)
R6C2=1 (All other possibilities excluded via pin)
R6C2=9 (All other possibilities excluded via force)
R9C3=1 (All other possibilities excluded via pin)
R3C3=9 (All other possibilities excluded via pin)
R2C3=4 (All other possibilities excluded via pin)
R2C3=8 (All other possibilities excluded via force)
R3C7=8 (All other possibilities excluded via pin)

I can't explain them from the Trebor's Tables transcript nor justify them from the state of the grid. Is there a description of this part of the algorithm somewhere or some additional tracing I can enable. Without a hint I still can't solve ultimate puzzles like "toughest".

MadOverlord wrote:

The real payoff from these techniques is going to be using them to find new solving subheuristics that humans can learn to "just see."

The simplest (and most frequent) proofs seem to be based on "unverities" where the assumption that two possibles in a cell are false leads to a common implication somewhere else on the grid. Once you know which cell and which possibles then the chains are not hard to write down. But which cells and which possibles - it's hard to imagine an heuristic that would do that. It's quite likely that there would have to be conjugates involved so perhaps looking for multiple coloured chains that link two cells might work.
Regards
Andrew

MadOverlord

Joined: 01 Jun 2005

Posts: 80

Location: Wilmington, NC, USA

Items

Posted: Tue Sep 06, 2005 2:06 am Post subject:

AMcK wrote:

The secret sauce seems to lie in Susser's verity maneouvres like

Code:

Okay, all I'm doing there is generating additional implications by exclusion.

All I do is, for each assertion, start with the original puzzle state and apply all the implications to it.

ie: if R1C1=1 has implication R1C2<>1, then I can remove the <1> possibility from R1C2 in my temp copy of the puzzle.

Then I look for forces and pins that appear but are not already implications of the original assertion, and add them as implications. Normally I just look for these forces/pins in the same R/C/B as the square of the original assertion, but if "aggressive forces and pins" is set, I look for them in all squares.

In the manual I refer to this as looking for "implied forces and pins"

Nick70

Joined: 08 Jun 2005

Posts: 160

Items

Posted: Tue Sep 06, 2005 8:58 am Post subject:

What I don't understand is what "force" and "pin" are. This is the first time I see those terms.

AMcK

Joined: 07 Apr 2005

Posts: 89

Location: Cambridge

Items

Posted: Tue Sep 06, 2005 9:49 am Post subject:

Nick70 wrote:

What I don't understand is what "force" and "pin" are. This is the first time I see those terms.

Hi Nick
Yes, they had me foxed for a while.
AFAIK a "pin" occurs when a possible is excluded by becoming certain in an overlapping house and a "force" occurs when a possible in a cell becomes unique in a house.
I'll look again for the "implied pin and force" in unver(ac)ities tonight.
I'd come to the same conclusion but thought I had them all covered.
Regards
Andrew

Nick70

Joined: 08 Jun 2005

Posts: 160

Items

Posted: Tue Sep 06, 2005 12:00 pm Post subject:

Perhaps I know what makes tabling more powerful than colouring. If a => b and a => c and (b and c) => d, then with tabling you can say (in some cases) that a => d. With colouring you can't.

MadOverlord

Joined: 01 Jun 2005

Posts: 80

Location: Wilmington, NC, USA

Items

Posted: Tue Sep 06, 2005 1:59 pm Post subject:

Nick70 wrote:

What I don't understand is what "force" and "pin" are. This is the first time I see those terms.

A force is when a square only has one possible remaining value.

A pin is when a square is the only square in a group (row/col/block) (aka "house") that has a particular possibility.

Removing a possibility from a square that has two possibilities left forces it to the other possibility.

Now consider two squares in a group that are a conjugate pair in <1> (they are the only squares in the group that can contain a <1>. If one of them was <123> and you can remove the <1> from it (leaving <12>), then the other square is now "pinned" to <1> even if its remaining possibilities were <1456789>.

AMcK

Joined: 07 Apr 2005

Posts: 89

Location: Cambridge

Items

Posted: Tue Sep 06, 2005 9:38 pm Post subject:

MadOverlord wrote:

Now consider two squares in a group that are a conjugate pair in <1> (they are the only squares in the group that can contain a <1>. If one of them was <123> and you can remove the <1> from it (leaving <12>), then the other square is now "pinned" to <1> even if its remaining possibilities were <1456789>.

The colouring of your example would be
{1a2a3a} {1b4b5b6b7b8b9b}
If we assert ¬1a then the first cell reduces to {2a2b}
Because 1a and 1b are conjugates then ¬1a -> 1b and we can assert 1b
Because 1b4b5b6b7b8b9b are all mutually exclusive then 1b -> ¬4b, 1b -> ¬5b etc so we can assert ¬4b, ¬5b etc and the second cell reduces to {1b}
So there should be no need to fall back on "implicit pins and forces"
Still looking ...
Andrew

AMcK

Joined: 07 Apr 2005

Posts: 89

Location: Cambridge

Items

Posted: Tue Sep 06, 2005 9:45 pm Post subject:

Here's six new ultracolourable puzzles.

Ultra 1

Code:

..6¦ .3.¦ .5.
87.¦ 6.4¦ 93.
134¦ .8.¦ ...
---+----+----
52.¦ ...¦ .96
.6.¦ ...¦ .4.
74.¦ ...¦ .12
---+----+----
...¦ .1.¦ 475
.52¦ 3.7¦ .89
.1.¦ .5.¦ 2..

Ultra 2

Code:

7..¦ .6.¦ 3.8
18.¦ 32.¦ ..6
65.¦ 8..¦ .4.
---+----+----
...¦ .3.¦ .5.
...¦ 9.7¦ ...
.6.¦ .5.¦ ...
---+----+----
.2.¦ ..3¦ .85
3..¦ .96¦ .24
4.5¦ .1.¦ ..9

Ultra 3

Code:

...¦ 412¦ 795
92.¦ ..5¦ ...
4..¦ .9.¦ ...
---+----+----
3..¦ 1..¦ .4.
5..¦ 7.3¦ ..9
.8.¦ ..4¦ ..7
---+----+----
...¦ .3.¦ ..1
...¦ 6..¦ .84
856¦ 241¦ ...

Ultra 4

Code:

3.7¦ .82¦ 6.5
.2.¦ .7.¦ .8.
...¦ 3..¦ .1.
---+----+----
...¦ ..4¦ ..1
28.¦ .1.¦ .36
1..¦ 9..¦ ...
---+----+----
.5.¦ ..8¦ ...
.7.¦ .4.¦ .5.
8.4¦ 25.¦ 7.9

Ultra 5

Code:

.68¦ 9.7¦ 3.5
7.4¦ 5.1¦ 8.6
3.1¦ .2.¦ ...
---+----+----
...¦ ...¦ 25.
...¦ 8.2¦ ...
.23¦ ...¦ ...
---+----+----
...¦ .1.¦ 6.2
8.7¦ 2.9¦ 5.1
6.2¦ 4.5¦ 73.

Ultra 6

Code:

..1¦ 6..¦ ..3
..9¦ .8.¦ 21.
57.¦ .13¦ 9..
---+----+----
...¦ ..6¦ 72.
...¦ .4.¦ ...
.97¦ 8..¦ ...
---+----+----
..2¦ 47.¦ .86
.48¦ .6.¦ 1..
6..¦ ..8¦ 5..

I'd be interested to hear of any easier solution methods.
Regards
Andrew

angusj
Site Admin

Joined: 18 Jun 2005

Posts: 406

Items

Posted: Tue Sep 06, 2005 10:27 pm Post subject:

AMcK wrote:

I'd be interested to hear of any easier solution methods.

The only puzzle which stumps my Simple Sudoku program is the second.
Puzzles 1 & 3 require XY-wing.
Puzzles 4,5 & 6 require simple colors only.

AMcK

Joined: 07 Apr 2005

Posts: 89

Location: Cambridge

Items

Posted: Wed Sep 07, 2005 9:17 pm Post subject:

angusj wrote:

Puzzles 4,5 & 6 require simple colors only.

Hi Angus
I don't see the simple colouring opportunity, but it may depend on how far you stretch the definition of "simple colors". My watershed is when you start to analyse all the possible together.

The 6 "Ultra" puzzles are deliberately simple examples of supercolouring, in the hope that it will no longer be dismissed as unsuitable for manual use. Many of you already know what I show below.

Look at Ultra 6

Code:

. . 6 ¦ . 3 . ¦ . 5 .
8 7 . ¦ 6 . 4 ¦ 9 3 .
1 3 4 ¦ . 8 . ¦ . . .
------+-------+-------
5 2 . ¦ . . . ¦ . 9 6
. 6 . ¦ . . . ¦ . 4 .
7 4 . ¦ . . . ¦ . 1 2
------+-------+-------
. . . ¦ . 1 . ¦ 4 7 5
. 5 2 ¦ 3 . 7 ¦ . 8 9
. 1 . ¦ . 5 . ¦ 2 . .

It easily reduces to

Code:

28 28 1 ¦ 6 59 79 ¦ 4 57 3
3 6 9 ¦ 57 8 4 ¦ 2 1 57
5 7 4 ¦ 2 1 3 ¦ 9 6 8
------------+-------------+-------------
48 38 5 ¦ 1 39 6 ¦ 7 2 49
12 23 6 ¦ 57 4 79 ¦ 8 35 159
14 9 7 ¦ 8 35 2 ¦ 6 345 145
------------+-------------+-------------
9 5 2 ¦ 4 7 1 ¦ 3 8 6
7 4 8 ¦ 3 6 5 ¦ 1 9 2
6 1 3 ¦ 9 2 8 ¦ 5 47 47

We see linked sequences of conjugates of two types: pairs of of different possibles in cells like the 2,8 in {1,1}; and pairs of the same possible in houses like the 2's in {1,1} and {1,2}.

Let's colour them in with two pens. Let colour X denote the proposition that {1,1}=2 and Y denote the conjugate proposition that {1,1}=8. One of X or Y must be true - we just don't know which yet. If {1,1}=2 then {1,2}<>2 so {1,1}=8. Conversely if {1,1}=8 then {1,2}<>8 and {1,2}=2. So the proposition {1,2}=8 must also have colour X and {1,2}=2 must have colour Y.

If we ripple this process through the grid we get

Code:

2X8Y 2Y8X 1 ¦ 6 5X9Y 7Y9X ¦ 4 5Y7X 3
3 6 9 ¦ 5Y7X 8 4 ¦ 2 1 5X7Y
5 7 4 ¦ 2 1 3 ¦ 9 6 8
------------+----------------+-----------------
4Y8X 3X8Y 5 ¦ 1 3Y9X 6 ¦ 7 2 4X9Y
1X2Y 2X3Y 6 ¦ 5X7Y 4 7X9Y ¦ 8 3X5f 1Y5Y9X
1Y4X 9 7 ¦ 8 3X5Y 2 ¦ 6 3Y4Y5i 1X4e5j
------------+----------------+-----------------
9 5 2 ¦ 4 7 1 ¦ 3 8 6
7 4 8 ¦ 3 6 5 ¦ 1 9 2
6 1 3 ¦ 9 2 8 ¦ 5 4X7Y 4Y7X

Note the stray 5's and 4 in box 6 that aren't conjugates with anything and can't be coloured to join either of the competing X or Y chains. There's 3 5's in columns 8 and 9, rows 5 and 6 and box 6 and there's 3 4's in column 9, row 6 and box 6.

However, the presence in row 6 of conjugates 4X in {6,1} and 4Y in {6,8} implies that one or the other must be true and so the stray 4e can be eliminated.

Note: I don't think you can do this with simple colouring of possible 4 because you get

Code:

- - - ¦ - - - ¦ 4 - -
- - - ¦ - - 4 ¦ - - -
- - 4 ¦ - - - ¦ - - -
-------+-------+---------
4a - - ¦ - - - ¦ - - 4b
- - - ¦ - 4 - ¦ - - -
4b - - ¦ - - - ¦ - 4d 4
-------+-------+---------
- - - ¦ 4 - - ¦ - - -
- 4 - ¦ - - - ¦ - - -
- - - ¦ - - - ¦ - 4c 4d

and I don't think it's valid in general to assert that 4b conjugates 4d (in this case they turn out to be exclusive - but they might not be and it could be the spare 4 that excludes them both).

Let's ignore this and look at the 2 Y's in {6,8}. We know that all the Y colours are all linked so if one is true they must all be true and if one is false they must all be false. There is an "immediate contradiction" because {6,8} can't be both 3 and 4 so Y must be False in {6,8} and everywhere else on the grid - and X must be True. The Y's in {5,9}support the same story.

By forcing all the Y's to be true and removing all the X's we get the characteristic supercolouring collapse of the entire grid in just one move.

Certainly, you could probably find some complex pattern that allowed you to make a little progress - but why bother, when you can have fun colouring in most of the grid and finding all possible moves.

Computer proofs using supercoloring tend to be rather mechanical and verbose, unlike the one presented here, using "colour identities". Like tabling, ultracolouring can take the analysis even further when confronted by a more intractable problem, using additional techniques such as verities and veracities which would need a lot of paper. These are the types of example that are typically published and I believe that the impression they give that supercolouring is not crayon-friendly is exaggerated.

Regards
Andrew

angusj
Site Admin

Joined: 18 Jun 2005

Posts: 406

Items

Posted: Wed Sep 07, 2005 11:48 pm Post subject:

AMcK wrote:

Hi Angus
I don't see the simple colouring opportunity, but it may depend on how far you stretch the definition of "simple colors".

Hi again Andrew.

Puzzle 4 (filtering on 1s):

Code:

*-----------*
|.B.|G..|...|
|..G|..x|...|
|...|...|...|
|---+---+---|
|...|...|...|
|...|...|...|
|...|...|...|
|---+---+---|
|...|...|...|
|...|...|...|
|.G.|..B|...|
*-----------*

Puzzle 5: sorry, I made a mistake - it did require 2 xy-wings in Simple Sudoku.

Puzzle 6 (filtering on 5s):

Code:

*-----------*
|...|.B.|.G.|
|...|G..|...|
|...|...|...|
|---+---+---|
|...|...|...|
|...|B..|.x.|
|...|...|...|
|---+---+---|
|...|...|...|
|...|...|...|
|...|...|...|
*-----------*

Both puzzles 4 & 6 required only one use of simple colors as illustrated above and otherwise solve with simpler techniques.

AMcK

Joined: 07 Apr 2005

Posts: 89

Location: Cambridge

Items

Posted: Thu Sep 08, 2005 9:34 am Post subject:

angusj wrote:

Puzzle 4 (filtering on 1s):

Code:

*-----------*
|.B.|G..|...|
|..G|..x|...|
|...|...|...|
|---+---+---|
|...|...|...|
|...|...|...|
|...|...|...|
|---+---+---|
|...|...|...|
|...|...|...|
|.G.|..B|...|
*-----------*

Puzzle 6 (filtering on 5s):

Code:

*-----------*
|...|.B.|.G.|
|...|G..|...|
|...|...|...|
|---+---+---|
|...|...|...|
|...|B..|.x.|
|...|...|...|
|---+---+---|
|...|...|...|
|...|...|...|
|...|...|...|
*-----------*

Thanks Angus,
That's a neat use of simple colouring that I haven't used before. It's a neat either/or proof. If blue=true than the 5 in r5c8 is excluded in row 5 or if green=true then it's excluded in column 8.
Regards Andrew

AMcK

Joined: 07 Apr 2005

Posts: 89

Location: Cambridge

Items

Posted: Thu Sep 08, 2005 10:31 am Post subject:

angusj wrote:

The only puzzle which stumps my Simple Sudoku program is the second.

Ultra 2

Code:

7..¦ .6.¦ 3.8
18.¦ 32.¦ ..6
65.¦ 8..¦ .4.
---+----+----
...¦ .3.¦ .5.
...¦ 9.7¦ ...
.6.¦ .5.¦ ...
---+----+----
.2.¦ ..3¦ .85
3..¦ .96¦ .24
4.5¦ .1.¦ ..9

Simple reductions to ...

Code:

7 49 2 ¦ 14 6 5 ¦ 3 19 8
1 8 49 ¦ 3 2 49 ¦ 5 7 6
6 5 3 ¦ 8 7 19 ¦ 29 4 12
------------+-------------+-------------
28 49 149 ¦ 6 3 124 ¦ 48 5 7
5 3 14 ¦ 9 8 7 ¦ 24 6 12
28 6 7 ¦ 14 5 124 ¦ 489 19 3
------------+-------------+-------------
9 2 6 ¦ 7 4 3 ¦ 1 8 5
3 1 8 ¦ 5 9 6 ¦ 7 2 4
4 7 5 ¦ 2 1 8 ¦ 6 3 9

supercolor map

Code:

7 4A9B 2 ¦ 1A4B 6 5 ¦ 3 1B9A 8
1 8 4B9A ¦ 3 2 4A9B ¦ 5 7 6
6 5 3 ¦ 8 7 1B9A ¦ 2A9B 4 1A2B
-----------------+---------------+------------------
2D8E 4B9A 1B4f9B ¦ 6 3 1A2E4g ¦ 4E8D 5 7
5 3 1A4B ¦ 9 8 7 ¦ 2B4A 6 1B2A
2E8D 6 7 ¦ 1B4A 5 1c2D4h ¦ 4i8E9A 1A9B 3
-----------------+---------------+------------------
9 2 6 ¦ 7 4 3 ¦ 1 8 5
3 1 8 ¦ 5 9 6 ¦ 7 2 4
4 7 5 ¦ 2 1 8 ¦ 6 3 9

Immediate contradiction in r4c3 B=False, A=True

Code:

7 4 2 ¦ 1 6 5 ¦ 3 9 8
1 8 9 ¦ 3 2 4 ¦ 5 7 6
6 5 3 ¦ 8 7 9 ¦ 1 4 1
---------+------------+----------
2D8E 9 4 ¦ 6 3 1 ¦ 4E8D 5 7
5 3 1 ¦ 9 8 7 ¦ 4 6 2
2E8D 6 7 ¦ 4 5 1c2D4h ¦ 9 1 3
---------+------------+----------
9 2 6 ¦ 7 4 3 ¦ 1 8 5
3 1 8 ¦ 5 9 6 ¦ 7 2 4
4 7 5 ¦ 2 1 8 ¦ 6 3 9

E=False, D=True solves
Regards
Andrew

Display posts from previous:

	Sudoku Programmers Forum Index -> Solving sudoku	All times are GMT Goto page 1, 2, 3, 4 Next
Page 1 of 4

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