Kite Hunting

Advanced methods and approaches for solving Sudoku puzzles

Kite Hunting

Postby Yogi » Thu May 26, 2016 1:29 am

This is by way of a reply to Leren’s post about kites in Keith’s thread about Finding the Possibility of Single-Candidate Eliminations, but is now more specifically about Kites. Leren posted some examples of Kite Puzzles which I have worked through. Generally it went well but there were some difficulties which I will go into later, but this is what I have distilled.
When you combine Keith’s rule with Leren’s suggestions it shakes down to a simple 3-step process:

1) For each candidate you want to look at, identify the boxes that could be a kitebox (multiple sites for the candidate, but not all in the same row or column.)

2) Check each possible kitebox for a row AND column that has only one instance of the candidate outside the kitebox.
(But is Keith right that the string ENDS must also be in this c-type box? I’m not so sure about that.)

3) Check to see if there is an unsolved cell with your candidate which can see BOTH the outside end cells of the two strings. If so then this cell CANNOT be that candidate.

The revelation for me was the idea of starting with the right kind of box and then looking for the two strings. I used to do it the other way around and got no-where. Another thing that has become clear that I had not realised before is that although the two strings of the kite can have only two instances of your candidate, the kitebox may have more than two. However, it does not seem to work if the two cells you use in your kite are in the same row or column in the kitebox. Apparently they have to be distinct in row AND column for the logic to work. Something else to watch for is that often there will be two options for the two strings for a given candidate in the same box. This came up in Puzzle3 below.
There is a parallel to this in the skyscraper: the walls of the skyscraper (that’s Columns if it is upright or upside-down) must have only two instances of your candidate, but the base may have more than two. Sorry, but RCB’s Solver exports definitions with zeros

Puzzle1: With basics this came through to here: 056070900040620080280000000000080000730000618005000020000000000070500049000048701
This one worked like a dream. I found a 3Kite in Box2: r38c5 / r2c16, so r8c1=6 stte
My jottings looked like this: 1-4578 2-4578 3-12578. I stopped when I found a kite that solved the puzzle with candidate 3.

With basics, Puzzle2 came to here: 361700295842395671050261483108526034625000018034100526400610852580002167216857349
Solved after 9Kite found in Box4: r6c16 / r47c2, r7c6 = 3 Worksheet was 3-8, 7-4, 9-4578

Puzzle3 came through to here: 320547906006213050045698230500472000007901025002805700214359678673184592050726143
My worksheet shows that I wasted a lot of time on this one: 1-1346 4-6 8-1346 9-4. This was because I got side-tracked by noticing that Box1 had two separate working kites for candidate 1, resulting in two different eliminations: r1c38 / r36c1 shows r6c8 is NOT 1, and r14c3 / r3c19 removes 1 from r4c9. What I did not realise at the time was that this means r4c9=9 and the puzzle can now be solved in singles.

I got Puzzle4 through to here: 081020600042060089056800240693142758428357916175689324510036892230008460860200000
For the four candidates I looked at, my Kite worksheet looked like this 1-2389 5-2389 7-2389 9-28 but I could not find a working kite anywhere.
The puzzle was solved when r2c4=7 after r2c4 set to 5 chained through to r2c7=5, which is not possible.

After trying for a skyscraper, I applied this Kite Hunt to another puzzle I got from Hodoku: 590036000006009000000800962807620490600090000059010206704003609960000100000960004
Because there are a lot of unsolved cells in this one it takes a lot of wading through and the only systematic way I could think of was to look at the possibilities for each cell, one-by-one. For candidate 1, Box1 looks like a possible kitebox, but is it? Which cells in it could be ‘strung?’ Here we see that none of the unsolved cells in rows 1 and 2 of Box1 could be strung as ROWS, because they have too many instances of candidate 1 in Boxes 2 & 3. Does this now rule Box1 out as a possible kitebox for candidate 1? No, because r2c1 can still be strung as a Column. Now we find the 1Kite r29c1 / r3c26 eliminating 1 from r9c6, which makes r7c4=1 and this solves the puzzle.
I’m putting this up as a thesis. Does my proposed 3-step process work for you?
I would welcome your input.
Yogi
Yogi
2017 Supporter
 
Posts: 85
Joined: 05 December 2015
Location: New Zealand

Re: Kite Hunting

Postby Leren » Thu May 26, 2016 10:00 pm

Repeating the five Kite puzzles :

.56.7.9...4.62..8.28...........8....73....618..5....2...........7.5...49....487.1
.617....5842.95....5..6.4.........3..25........41...26..........8.....672.....349
32..479.6..6........5.9..3.....7.......9.1..5..28..7.........7.6.3..4....5..26143
.81.2............9..68...4...31..7....8.57916........45....6.9223...84...........
59..36.....6..9......8..9628.762.49.6...9.....59.1.2.67.4..36.996....1.....96...4

Puzzle 3

Code: Select all
*-----------------------------------------------------*
| 3    2   b18    | 5    4    7     | 9   a18   6     |
| 789  89   6     | 2    1    3     | 48   5    47    |
|c17   4    5     | 6    9    8     | 2    3    17    |
|-----------------+-----------------+-----------------|
| 5    3689 189   | 4    7    2     | 38   168  19    |
| 48   368  7     | 9    36   1     | 348  2    5     |
|d149  369  2     | 8    36   5     | 7    6-1  149   |
|-----------------+-----------------+-----------------|
| 2    1    4     | 3    5    9     | 6    7    8     |
| 6    7    3     | 1    8    4     | 5    9    2     |
| 89   5    89    | 7    2    6     | 1    4    3     |
*-----------------------------------------------------*

(1) r1c8 = r1c3 - r3c1 = (1) r6c1 => - 1 r6c8; stte

Puzzle 4

Code: Select all
*-----------------------------------------------------*
| 379  8    1     | 4579 2    345   | 6    37   357   |
| 37   4    2     | 7-5  6    135   |a15   8    9     |
| 379  5    6     | 8    179  13    | 2    4    137   |
|-----------------+-----------------+-----------------|
| 6    9    3     | 1    4    2     | 7    5    8     |
| 4    2    8     | 3    5    7     | 9    1    6     |
| 1    7    5     | 6    8    9     | 3    2    4     |
|-----------------+-----------------+-----------------|
| 5    1    47    | 47   3    6     | 8    9    2     |
| 2    3    79    |d579  179  8     | 4    6   c157   |
| 8    6    479   | 2    179  145   |b15   37   1357  |
*-----------------------------------------------------*

(5) r1c7 = r9c7 - r7c9 = (5) r7c4 = > - 5 r2c4; stte

Puzzle 5

Code: Select all
*-----------------------------------------------------------------------*
| 5      9      128     | 1247   3      6       | 78     1478   178     |
| 124    12478  6       | 1247   47     9       | 3578   134578 13578   |
| 134    347-1  13      | 8      5     a147     | 9      6      2       |
|-----------------------+-----------------------+-----------------------|
| 8      13     7       | 6      2      5       | 4      9      13      |
| 6      1234   123     | 347    9      478     | 3578   13578  13578   |
| 34     5      9       | 347    1      478     | 2      378    6       |
|-----------------------+-----------------------+-----------------------|
| 7     d12     4       |c15     8      3       | 6      25     9       |
| 9      6      2358    | 457    47     247     | 1      23578  3578    |
| 123    1238   12358   | 9      6     b127     | 3578   23578  4       |
*-----------------------------------------------------------------------*

(1) r3c6 = r9c6 - r7c4 = (1) r7c2 => - 1 r3c2

This Kite does not solve the puzzle - there is more work to do which I won't detail here.

Leren
Leren
 
Posts: 2754
Joined: 03 June 2012

Re: Kite Hunting

Postby Kozo Kataya » Fri May 27, 2016 1:35 am

With puzzle 5, adding to r3c2<>1, one more r3c3<>1 can be at this stage.
Because, as shown below: if r3c3=1, table A shifts to table B,
if r3c3=1 is true, r45c2=1 is true and r9c1=1 is true,
these cause both r3c6=1 and r9c6=1 are false.
Ths is a contradiction, so r3c3<>1.
How can i express the above, like this?
[ 1r3c3-1r9c1-(1)r39c6=>-1r3c3 ]

Although r3c23<>1 is not enough to solve this puzzle, as Leren said.
[ chain forcing r12c4<>1 ] leads to stte.

Code: Select all
  table A          table B
  |..1|1..|.11|    |...|1..|.11|
  |11.|1..|.11|    |...|1..|.11|
  |111|..1|...|    |..1|...|...|
  +---+---+---+    +---+---+---+
  |.1.|...|..1|    |.1.|...|..1|
  |.11|...|.11|    |.1.|...|.11|
  |...|.1.|...|    |...|.1.|...|
  +---+---+---+    +---+---+---+
  |.1.|1..|...|    |...|1..|...|
  |...|...|1..|    |...|...|1..|
  |111|..1|...|    |1..|...|...|


PS: How do you call this kind of table, [ single digit ] or else ?
Kozo Kataya
 
Posts: 24
Joined: 06 July 2012

Re: Kite Hunting

Postby Leren » Fri May 27, 2016 7:25 am

What the previous contributor was presumably referring to was a Grouped Skyscraper/Finned XWing:

Code: Select all
*-----------------------------------------------------------------------*
| 5      9      128     | 1247   3      6       | 78     1478   178     |
|d124f   12478  6       | 1247   47     9       | 3578   134578 13578   |
|d134*   347-1  3-1     | 8      5     a147*    | 9      6      2       |
|-----------------------+-----------------------+-----------------------|
| 8      13     7       | 6      2      5       | 4      9      13      |
| 6      1234   123     | 347    9      478     | 3578   13578  13578   |
| 34     5      9       | 347    1      478     | 2      378    6       |
|-----------------------+-----------------------+-----------------------|
| 7      12     4       | 15     8      3       | 6      25     9       |
| 9      6      2358    | 457    47     247     | 1      23578  3578    |
|c123*   1238   12358   | 9      6     b127*    | 3578   23578  4       |
*-----------------------------------------------------------------------*

(1) r3c6 = r9c6 - r9c1 = (1) r23c1 => - 1 r3c23 as a Grouped Skyscraper, or

Finned XWing c16 r49 fin Cell r2c1 => - 1 r3c23

Since you were looking for kites I ignored these moves.

Leren
Leren
 
Posts: 2754
Joined: 03 June 2012

Re: Kite Hunting

Postby Yogi » Sun May 29, 2016 12:32 am

It will take me some time to work through your comments about the puzzles I examined above, but do you have any feedback about the accuracy and usefulness of the Kite-hunting process I proposed? I have since come to the conclusion that there is a fourth rule which can simplify things and save time. So it now reads:

1) For each candidate you want to look at, first identify the boxes that could be a kitebox (multiple sites for the candidate, but not all in the same row or column.)

2) When the possible kiteboxes for a candidate are confined to one Band or Stack, there will be no kite for that candidate.

3) Check each possible kitebox for a row AND column that has only one instance of the candidate outside the kitebox.

4) Is there is an unsolved cell with your candidate which can see BOTH the outside end cells of the two strings? If so then this cell CANNOT be that candidate.
Yogi
2017 Supporter
 
Posts: 85
Joined: 05 December 2015
Location: New Zealand

Re: Kite Hunting

Postby Leren » Sun May 29, 2016 6:21 am

I'd say it something like this:

1. Look for 2 cells, one in a row R and one in a column C that have the only instance of a candidate k outside a box. If the box is at the intersection of Row R and column C then it's a possible Kite box.

2. Look for a possible elimination candidate k, which will be at the other intersection of the row and column k cells.

(ie if the Row R k cell is in column c and the Column C candidate is in Row r then the elimination cell will be rrcc.) The minimum number of k's in a Kite box is 2 and the maximum is 8.

3. The Kite box will be suitable if : 1. The row R k cell and the Column C k cell both see at least one k in the Kite box but not all of the k's in the Kite box, and 2. There must be no k in the Kite box in Row R and Column C.

Code: Select all
*-------*-------*-------*
| # k # |       |       |
| k / k | / / / | / K / |
| # k # |       |       |
*-------*-------*-------*
|   /   |       |       |
|   /   |       |       |
|   /   |       |       |
*-------*-------*-------*
|   /   |       |       |
|   K   |       |   K   |
|   /   |       |       |
*-------*-------*-------*

A picture is worth a thousand words, so I've drawn the above exemplar diagram that illustrates what I think I have just said !

The cells in the Kite box marked with a k may hold k but collectively must conform to Rule 2.

What this means (in terms of the exemplar diagram) is that at least one of r1c2 and r3c2 must hold k, and at least one of r2c1 and r2c3 must hold k. There must be no k at r2c2.

I've marked 4 cells in the Kite box with #. These cells may or may not hold k and have no influence on the move.

The row R cell, the Column C cell and the elimination cell are marked K and they must hold k.

Cells marked / must not hold k. Blank cells outside of the Kite box may or may not hold k and have no influence on the move.

I think I'll stop there.

Leren
Leren
 
Posts: 2754
Joined: 03 June 2012

Lost in Translation?

Postby keith » Sun May 29, 2016 7:58 am

Right now, my response is leaning to: That's what I said (or meant to say), or: Isn't that in Havard's classic post on Two Strong Links?

But, I am unsure of the terminology. What is a "Kitebox"? What is a "String". Here is Puzzle1 at the end of basics:

Code: Select all
+-------------------+-------------------+-------------------+
| 1     5     6     | 8     7     4     | 9     3     2     |
| 39    4     7     | 6     2     39    | 1     8     5     |
| 2     8     39    | 139   1359  1359  | 4     7     6     |
+-------------------+-------------------+-------------------+
| 46    126   124   | 12347 8     12367 | 5     9     47    |
| 7     3     249   | 249   59    259   | 6     1     8     |
| 8     169   5     | 1479  169   1679  | 3     2     47    |
+-------------------+-------------------+-------------------+
| 4569  1269  12489 | 1279  169   12679 | 28    56    3     |
| 36    7     1238  | 5     136   1236  | 28    4     9     |
| 3569  269   239   | 239   4     8     | 7     56    1     |
+-------------------+-------------------+-------------------+

Please use it as an example to explain the detail of the logic and terminology.

Thank you,

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Postby Pat » Sun May 29, 2016 9:05 am

User avatar
Pat
 
Posts: 3340
Joined: 18 July 2005

Re: Kite Hunting

Postby Leren » Sun May 29, 2016 9:37 am

Keith wrote : Please use it as an example to explain the detail of the logic and terminology.

This is how I would normally document the Kite solution to Puzzle 1.

Code: Select all
*--------------------------------------------------------------*
| 1     5     6      | 8     7     4      | 9     3     2      |
|a39    4     7      | 6     2    b39     | 1     8     5      |
| 2     8     39     | 139  c1359  1359   | 4     7     6      |
|--------------------+--------------------+--------------------|
| 46    126   124    | 12347 8     12367  | 5     9     47     |
| 7     3     249    | 249   59    259    | 6     1     8      |
| 8     169   5      | 1479  169   1679   | 3     2     47     |
|--------------------+--------------------+--------------------|
| 4569  1269  12489  | 1279  169   12679  | 28    56    3      |
| 6-3   7     1238   | 5    d136   1236   | 28    4     9      |
| 3569  269   239    | 239   4     8      | 7     56    1      |
*--------------------------------------------------------------*

Kite : (3) r2c1 = r2c6 - r3c5 = (3) r8c5 => - 3 r8c2; stte

In terms of the terminology I used for Yogi's benefit in my previous post the Kite digit k is 3 the Kite box is Box 2 and the two "strings" of the Kite are Row 2 and Column 5.

In terms of the exemplar diagram I used, it needs to be rotated clockwise by 90 deg and Stacks 2 and 3 swapped, to line up pretty well with the Kite pattern in this puzzle.

The logic should be self explanatory from the chain notation. At least one of r2c1 and r8c5 must be 3, so r8c1 <> 3, which solves the puzzle via follow-on singles (stte).

Leren
Leren
 
Posts: 2754
Joined: 03 June 2012

Re: Kite Hunting

Postby Yogi » Wed Jun 08, 2016 7:16 am

To clarify the points you have raised here and elsewhere I have re-written and expanded my proposed rules for kite hunting, and put in a little something for the P & P Brigade:

1) For each candidate you want to look at, first identify the boxes that could be a kitebox. (They will have multiple sites for the candidate, but NOT only in one row or column.)

2) When the possible kiteboxes for a candidate are confined to one Band or Stack, there will be no kite for that candidate in the puzzle.

3) Check each possible kitebox for a row AND column that has only One instance of the candidate outside the kitebox. While there may be up to two instances of the candidate in any one row or column within the possible kitebox, the Intersecting Cell between your strings must NOT have that candidate.

4) Is there is an unsolved cell with your candidate which can see BOTH the outside end cells of the two strings? If so then this cell CANNOT be that candidate.

5) For Pen & Paper solvers who do not write in pencilmark candidates, this method of kite hunting can be a lot of work for little reward if you do not yet have 40+ cells solved.

I went hunting in one puzzle recently and I found kites which eliminated candidates in 4 cells, but none of those cells were completely solved. It was a lengthy exercise which in the end did not greatly contribute to solving the whole puzzle. There is a better chance of a kite solving a cell if you are further on with the puzzle.
Yogi
2017 Supporter
 
Posts: 85
Joined: 05 December 2015
Location: New Zealand

Re: Kite Hunting

Postby JasonLion » Wed Jun 08, 2016 3:01 pm

While you do seem to be zeroing in on a "correct" specification for Kites, your specification seems to me to miss the point. Kites are a subclass of Turbots, which are defined in terms of 5 links, two of which need to be strong links (typically conjugate pairs), and all 5 of which have a specific relationship.

Your specification lacks any explicit mention of the 5 links, and their required strong and weak pattern. Instead you choose to use a much more verbose definition that obscures the logical relationships. That doesn't make your specification incorrect, but it does greatly hamper understanding of how Kites are a subclass of Turbots and how strong and weak links are used more generally in other techniques.
User avatar
JasonLion
2017 Supporter
 
Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Kite Hunting

Postby Leren » Wed Jun 08, 2016 8:47 pm

Here are 4 puzzles that have Kites that solve a cell and the puzzle. They are the only move required to solve the puzzle, apart from obvious mark-offs and singles.

.56.7.9...4.62..8.28...........8....73....618..5....2...........7.5...49....487.1
.617....5842.95....5..6.4.........3..25........41...26..........8.....672.....349
32..479.6..6........5.9..3.....7.......9.1..5..28..7.........7.6.3..4....5..26143
.81.2............9..68...4...31..7....8.57916........45....6.9223...84...........

Leren
Leren
 
Posts: 2754
Joined: 03 June 2012

Kite Hunting

Postby Yogi » Sun Jun 12, 2016 8:36 pm

A good challenge, but not an entirely satisfactory result. I found a kite that solved the first three of these puzzles quite routinely, but not in the last, which I brought to here:
.81.2.6...42.6..89.568..24.69314275842835791617568932451..3689223...846.86.2.....
There are of course a number of potential kites in various candidates based in Boxes 2, 3, 8 & 9, but as far as I can see they are all ruled out for one reason or another.
Maybe I still haven't got this intersection limitation right yet. I'm taking the Intersecting Cell as being the cell that is in line with BOTH proposed strings.
The puzzle is solved with the X-Chain in candidate 5 proving r2c4=7

Yogi
Yogi
2017 Supporter
 
Posts: 85
Joined: 05 December 2015
Location: New Zealand

Re: Kite Hunting

Postby Leren » Mon Jun 13, 2016 1:50 am

Code: Select all
*--------------------------------------------------------------*
| 379   8     1      | 4579  2     345    | 6     37    357    |
| 37    4     2      | 7-5   6     135    |a15    8     9      |
| 379   5     6      | 8     179   13     | 2     4     137    |
|--------------------+--------------------+--------------------|
| 6     9     3      | 1     4     2      | 7     5     8      |
| 4     2     8      | 3     5     7      | 9     1     6      |
| 1     7     5      | 6     8     9      | 3     2     4      |
|--------------------+--------------------+--------------------|
| 5     1     47     | 47    3     6      | 8     9     2      |
| 2     3     79     |d579   179   8      | 4     6    c157    |
| 8     6     479    | 2     179   145    |b15    37    1357   |
*--------------------------------------------------------------*

For the 4th puzzle singles will bring you to here : Kite : (5) r2c7 = r9c7 - r8c9 = (5) r8c4 => - 5 r2c4; stte

Leren
Leren
 
Posts: 2754
Joined: 03 June 2012

Re: Kite Hunting

Postby Yogi » Mon Jun 13, 2016 8:26 am

Gotcha, Thanx. I was too quick off the mark in ruling out Box9 as a possible kitebox for candidate 5, believing that whichever way it was strung, r9c9 would be the Intersecting Cell and being candidate 5 it would invalidate any kite I might have assembled. I see now that in your kite the intersecting cell is r8c7 which is already solved at 4.
My notation is 5Kite in Box9 r29c7/r8c49 => -5r2c4.
Yogi
Yogi
2017 Supporter
 
Posts: 85
Joined: 05 December 2015
Location: New Zealand

Next

Return to Advanced solving techniques