The New Sudoku Players' Forum

[Morgoth]

I tried to solve this.

Code: Select all

***|5*3|6*1
***|*4*|***
*8*|*1*|**9
-----------
**9|23*|7**
8**|***|**6
**2|*61|5**
-----------
5**|*2*|*3*
***|*5*|***
1*4|7*6|***


After several naked pears, hidden pears and x-wings it was still incomplete and there was nothing to do with the standard methods. So I found new X structure. It has 2 crossing lines with only two possibilities for one number and one of them is in the crossroad (the X-Wing have two parallel lines). If you try to make a square the new lines is crossing in one box, and if the only possibilities for the searching number in this box lies on one of the lines, so the first cross is known.

I realize that this explanation is not very clear, so hare is an example (the same from the upper sudoku).

Code: Select all

{  }, {}, {}, {   }, {248 }, {}
{89}, {}, {}, {238}, {2578}, {}
{  }, {}, {}, {   }, {    }, {}
{  }, {}, {}, {   }, {    }, {}
{  }, {}, {}, {   }, {    }, {}
{89}, {}, {}, {   }, {89  }, {}


The first crossway is between the first left column and the lowest row. There are no other possible places for the number 8 in these lines.
The second crossway is in the up right box where the number 8 is not present. For this box only possible places for the number 8 lies on the second crossway and one of them must be 8. Nevertheless where is the exact place of the number 8 in the box, the low left corner must be 8 too (regarding the same logic like the X-Wing), otherwise the top left and the low right will be 8, so there is no place for 8 in the up right box.


My question here is – have I invent something or I have found the hot water?
And what do you think about methods that are so complex (this can be combine with Swordfish too – it interacts with a box in the same way like the X-Wing) – is it proper to invent more and more methods which are approaching the brood force?

[rubylips]

Morgoth,

As far as I'm aware, your pattern doesn't have a name. However, it is possible to find the pattern through colouring, which is described on the Sad Man Software site, or by chains, as described here.

The candidate grid at the point the pattern is found is as follows:

Code: Select all

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


The critical chain is:

Code: Select all

Consider the chain r1c8-8-r1c5-8-r2c4-8-r6c4-8-r6c8.
When the cell r1c8 contains the value 8, so does the cell r6c8 - a contradiction.
Therefore, the cell r1c8 cannot contain the value 8.
When the cell r6c8 contains the value 8, so does the cell r1c8 - a contradiction.
Therefore, the cell r6c8 cannot contain the value 8.
- The moves r1c8:=8 and r6c8:=8 have been eliminated.
The value 9 is the only candidate for the cell r6c8.


So your pattern might be new but the techniques necessary to find the pattern have already been discovered.

[Jeff]

Hi Morgoth, Welcome to the forum.

Sounds like a good idea. Could you code the entire candidate grid for clarity.

[Morgoth]

Hi Morgoth, Welcome to the forum.

Sounds like a good idea. Could you code the entire candidate grid for clarity.

Here it is:

Code: Select all

249  249  7    | 5    89   3    | 6    248  1
239  6    1    | 89   4    27   | 238  2578 25
234  8    5    | 6    1    27   | 234  247  9
---------------+----------------+--------------
6    15   9    | 2    3    58   | 7    14   48
8    15   3    | 4    7    59   | 29   129  6
47   47   2    | 89   6    1    | 5    89   3
---------------+----------------+--------------
5    79   6    | 1    2    489  | 49   3    478
279  279  8    | 3    5    49   | 1    6    47
1    3    4    | 7    89   6    | 289  2589 25


Enjoy

[Ruud]

Can you tell me how you got from here:

Code: Select all

.---------------.---------------.---------------.
| 249  249  7   | 5    89   3   | 6    248  1   |
| 2369 156  135 | 89   4    27  | 238  2578 2358|
| 234  8    35  | 6    1    27  | 234  2457 9   |
:---------------+---------------+---------------:
| 46   156  9   | 2    3    58  | 7    148  48  |
| 8    15   135 | 49   7    59  | 2349 1249 6   |
| 347  47   2   | 489  6    1   | 5    489  348 |
:---------------+---------------+---------------:
| 5    79   6   | 1    2    489 | 489  3    478 |
| 279  279  8   | 3    5    49  | 1    6    47  |
| 1    3    4   | 7    89   6   | 289  2589 258 |
'---------------'---------------'---------------'

to here:

Code: Select all

249  249  7    | 5    89   3    | 6    248  1
239  6    1    | 89   4    27   | 238  2578 25
234  8    5    | 6    1    27   | 234  247  9
---------------+----------------+--------------
6    15   9    | 2    3    58   | 7    14   48
8    15   3    | 4    7    59   | 29   129  6
47   47   2    | 89   6    1    | 5    89   3
---------------+----------------+--------------
5    79   6    | 1    2    489  | 49   3    478
279  279  8    | 3    5    49   | 1    6    47
1    3    4    | 7    89   6    | 289  2589 25

with singles, locked candidates and subsets only, because my solver requires at least coloring to go beyond the first stage.

Ruud.

[ronk]

Code: Select all

{  }, {}, {}, {   }, {248 }, {}
{89}, {}, {}, {238}, {2578}, {}
{  }, {}, {}, {   }, {    }, {}
{  }, {}, {}, {   }, {    }, {}
{  }, {}, {}, {   }, {    }, {}
{89}, {}, {}, {   }, {89  }, {}


[edit: This original statement .... I believe that 8s pattern has been named 'turbot fish'. When the turbot fish has two 'adjacent' strong links (in r6 and c4, in this case), the 8s at the ends of the chain of strong links (r4c2 and r6c8, in this case) may be eliminated ... is incorrect, even though the eliminations were correct.

I don't recall the 'baptizer' and I'm unable to find a good link right now. [edit: Nick70's writeup found later]

[Morgoth]

Morgoth,

As far as I'm aware, your pattern doesn't have a name. However, it is possible to find the pattern through colouring, which is described on the Sad Man Software site, or by chains, as described here.

Hi rubylips,

Technically everything can be solved with brood force. As I understand coloring and chains they both are kind of brood force.
My goal is not to solve one puzzle; I want to make a program which will be able to solve as more as possible puzzles (just for the sport), so I’m interested from all methods which are not using brood force. It will be too easy, too slow and too stupid to solve the complete puzzle with back-tracking (another kind of brood force) – there is no challenge here.
Additionally if I try to generate puzzles using the same algorithms (with back tracking), some of them will be too hard to be solved without computer.

[Jeff]

Thank you Morgoth, it's crystal clear now.

Congratulations, you have just spotted a 'lost digit contradiction'. It is the other side of an 'empty cell contradiction' where the assignment of a digit forces all candidates to vanish in a cell; whereas in this case, the assignment of the 8 in r6c4 forces a digit to vanish in box 3. I don't think it has anything to do with x-wing though. It goes like this:

r6c4=9 => r2c4=8 => r2r7<>8 and r2r8<>8
r6c4=9 => r6r8=8 => r1r8<>8 and r2r8<>8
No digit 8 in box 3 contradiction, therefore r6c4<>9 => r6c4=8

And for the chain enthusiasts, this deduction can be expressed as a triple implication chain with the bilocation triangle at r1c8, r2c7 and r2c8.

Chain notation:
[r6c4]=8=[r2c4]-8-[r2c7]=8=[r2c8]-8-[r6c8]=8=[r6c4]
[r6c4]=8=[r2c4]-8-[r2c7]=8=[r1c8]-8-[r6c8]=8=[r6c4]
[r6c4]=8=[r2c4]-8-[r2c8]=8=[r1c8]-8-[r6c8]=8=[r6c4]
All imply r6c4=8

[Jeff]

I believe that 8s pattern has been named 'turbot fish'. When the turbot fish has two 'adjacent' strong links (in r6 and c4, in this case), the 8s at the ends of the chain of strong links (r4c2 and r6c8, in this case) may be eliminated.

Ronk, although it might look like a turbot fish, but I think it is not because the 2 strong links are in the wrong positions.

[rubylips]

Technically everything can be solved with brood force. As I understand coloring and chains they both are kind of brood force.

Most people on the forum would disagree with this statement.

'Brute force' is a relative term. To establish that a given value is the only candidate for a given cell requires some 'brute force' - you have to check that the other possible candidates have been eliminated. To look for the your pattern within a puzzle would require more 'brute force' that this - but less 'brute force' than for backtracking. The trick is to find search algorithms that find these critical patterns efficiently. Most people agree that colouring and forced chains are efficient search algorithms. It would require too much effort to catalogue each possible pattern, such as yours, that these methods would uncover and, even if you did, as I said earlier, you'd still have to employ some 'brute force' to locate these patterns.

[Morgoth]

Can you tell me how you got from here:

Code: Select all

.---------------.---------------.---------------.
| 249  249  7   | 5    89   3   | 6    248  1   |
| 2369 156  135 | 89   4    27  | 238  2578 2358|
| 234  8    35  | 6    1    27  | 234  2457 9   |
:---------------+---------------+---------------:
| 46   156  9   | 2    3    58  | 7    148  48  |
| 8    15   135 | 49   7    59  | 2349 1249 6   |
| 347  47   2   | 489  6    1   | 5    489  348 |
:---------------+---------------+---------------:
| 5    79   6   | 1    2    489 | 489  3    478 |
| 279  279  8   | 3    5    49  | 1    6    47  |
| 1    3    4   | 7    89   6   | 289  2589 258 |
'---------------'---------------'---------------'

to here:

Code: Select all

249  249  7    | 5    89   3    | 6    248  1
239  6    1    | 89   4    27   | 238  2578 25
234  8    5    | 6    1    27   | 234  247  9
---------------+----------------+--------------
6    15   9    | 2    3    58   | 7    14   48
8    15   3    | 4    7    59   | 29   129  6
47   47   2    | 89   6    1    | 5    89   3
---------------+----------------+--------------
5    79   6    | 1    2    489  | 49   3    478
279  279  8    | 3    5    49   | 1    6    47
1    3    4    | 7    89   6    | 289  2589 25

with singles, locked candidates and subsets only, because my solver requires at least coloring to go beyond the first stage.

Ruud.

9:2 -3 Hidden Pair with 9:9
9:6 3 One in column
3:5 3 One in row
3:3 5 Only one
3:2 1 Only one
4:6 -4 Naked Pair 1:6; 2:6
4:5 4 One in column
8:6 -4 Naked Pair 1:6; 2:6
1:4 -4 Naked Pair 1:6; 2:6
1:4 6 Only one
2:2 6 One in column
2:4 -4 Naked Pair 1:6; 2:6
9:2 -8 Hidden Pair with 9:9
9:9 -8 Hidden Pair with 9:2
8:4 -8 X-Wing 6:4; 6:7; 9:4; 9:7
7:7 -8 X-Wing 6:4; 6:7; 9:4; 9:7

[Morgoth]

Technically everything can be solved with brood force. As I understand coloring and chains they both are kind of brood force.

Most people on the forum would disagree with this statement.

'Brute force' is a relative term. To establish that a given value is the only candidate for a given cell requires some 'brute force' - you have to check that the other possible candidates have been eliminated. To look for the your pattern within a puzzle would require more 'brute force' that this - but less 'brute force' than for backtracking. The trick is to find search algorithms that find these critical patterns efficiently. Most people agree that colouring and forced chains are efficient search algorithms. It would require too much effort to catalogue each possible pattern, such as yours, that these methods would uncover and, even if you did, as I said earlier, you'd still have to employ some 'brute force' to locate these patterns.

First, sorry for my stupid English , brood is not equals to brute of course.

You are right there should be a line between patterns and the search algorithm, because the patterns may go more and more complex and always there will be an example which will not be possible to solve with them.

I’ll see more about the chains to be able to put the line on the right place.

[Bob Hanson]

Getting from "here" to "there" is easier than that. No X-wings. Just simple subset elimination and locked candidates. From Sudoku Assistant http://www.stolaf.edu/people/hansonr/sudoku

Ruud, is it possible your solver isn't finding locked candidates properly. I find that hard to believe.

(in reverse chronological order):
Step 17 Strong Chains: 20
r6c8 ISN'T 4: candidate 4 is locked in another subset of row 6
r6c4 ISN'T 4: candidate 4 is locked in another subset of row 6
r2c6 ISN'T 8: 2-long naked set in 3x3 block 2 involving 8,9
r2c6 ISN'T 9: 2-long naked set in 3x3 block 2 involving 8,9
r2c2 ISN'T 2: 3-long hidden set in column 2 involving rows 2,4,5
r4c2 ISN'T 4: 3-long hidden set in column 2 involving rows 2,4,5
r5c2 ISN'T 4: 3-long hidden set in column 2 involving rows 2,4,5
r2c2 ISN'T 9: 3-long hidden set in column 2 involving rows 2,4,5
r2c9 ISN'T 3: 2-long hidden set in column 9 involving rows 2,9
r2c9 ISN'T 8: 2-long hidden set in column 9 involving rows 2,9
r9c9 ISN'T 8: 2-long hidden set in column 9 involving rows 2,9
r6c9 ISN'T 4: 3-long naked set in column 9 involving 4,7,8
r6c9 ISN'T 8: 3-long naked set in column 9 involving 4,7,8
r8c9 ISN'T 2: candidate 2 is locked in another subset of row 8
r5c6 ISN'T 4: candidate 4 is locked in another subset of column 6
r4c6 ISN'T 4: candidate 4 is locked in another subset of column 6
r2c9 ISN'T 7: candidate 7 is locked in another subset of column 9

Step 1
55 cells left to solve; 26 clues; 504 tidbits of information

[ronk]

I believe that 8s pattern has been named 'turbot fish'. When the turbot fish has two 'adjacent' strong links (in r6 and c4, in this case), the 8s at the ends of the chain of strong links (r4c2 and r6c8, in this case) may be eliminated.

Ronk, although it might look like a turbot fish, but I think it is not because the 2 strong links are in the wrong positions.

Correctomundo! When there are only two strong sides (links), the sides may not be adjacent ('consecutive' in terms of the original post by Nick70.

[stuartn]

Getting from "here" to "there" is easier than that. No X-wings

I suppose Bob, that it all depends what you want to do - in an earlier thread I ventured to (nearly) solve a grid using x-wings only. It just depends on your preference - if I want to search for hidden quads before looking for naked pairs it'll change the whole solving experience - and I may learn a few things along the way. You found a path from one grid to another because your solver looks at possibilities in a particular order... change the order and you may find an even 'easier' (whatever that may mean ) way through.

BTW - the worst my Excel solver could find was a hidden quad!)

stuartn