Challenge Puzzle #10

Everything about Sudoku that doesn't fit in one of the other sections

Challenge Puzzle #10

Postby Mike Barker » Sun Mar 09, 2008 6:12 am

A group of us have been posting challenge puzzles on the Eureka forum to provide an opportunity to compare different approaches to solving puzzles. I just posted Puzzle 10 which is also Andrew's Unsolvable #30. It has a Sudoku Explainer rating of 8.4 so is one of the "easier" next generation of unsolvables. Although the rating is a little high which may limit the number of solutions, I thought it might make a good challenge puzzle. The idea of challenge puzzles is that they are open to all types of solutions: pattern based, chain/net based, bifurcative/assumptive, and even such absurdities as looking up the answer in the back of the book. If you are using additional information or resources please make sure that is clear. As always high praise goes to solutions which:
    1) are human derivable (simple)
    2) innovative
    3) use understandable notation which completely describes the elimination
    4) result in simple subsequent steps
    5) are general (applicable to other puzzles)
    6) and most importantly, are enjoyable
Code: Select all
+-------------------+----------------------+-------------------+
| 1238     5  1378  |  13789  3789   1379  | 478     6  12479  |
|  168  1678     4  | 156789     2  15679  |   3   189   1789  |
|    9  2678  1378  |  13678     4   1367  |  78   128      5  |
+-------------------+----------------------+-------------------+
|  248     9     6  |   1237    37   1237  |   5   248   2478  |
|  123   127   137  |      4     5      8  |  67    29   2679  |
|  248  2478     5  |   2679    79   2679  |   1     3   2478  |
+-------------------+----------------------+-------------------+
|    7   148   189  |    589     6    459  |   2  1458      3  |
| 4568   468     2  |     37     1     37  |   9   458    468  |
|  456     3   189  |   2589    89   2459  | 468     7   1468  |
+-------------------+----------------------+-------------------+

In this case I thought I'd add a little spice to the challenge by making it a competition as well. Which forum will come up with the best solution, Eureka or the Players Forum? Judging will be purely subjective and individual, but who can resist kudus from their peers? Good luck!
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby StrmCkr » Sun Mar 09, 2008 9:58 am

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:33 am, edited 20 times in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby daj95376 » Sun Mar 09, 2008 10:49 am

Withdrawn: used below
Last edited by daj95376 on Mon Mar 10, 2008 8:02 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby tarek » Sun Mar 09, 2008 10:49 pm

No elegant solution from me:(

A suggested startup move:
Code: Select all
*--------------------------------------------------------------------------*
|%1238    5      %1378   |%13789  %3789   %1379   | 478     6       12479  |
|*168     1678    4      | 156789  2       15679  | 3      ^189    ^1789   |
| 9       2678    1378   | 13678   4       1367   |^78      128     5      |
|------------------------+------------------------+------------------------|
|*248     9       6      | 1237    37      1237   | 5       248     2478   |
| 123     127     137    | 4       5       8      | 67      29      2679   |
|*248     2478    5      | 2679    79      2679   | 1       3       2478   |
|------------------------+------------------------+------------------------|
| 7       148     189    | 589     6       459    | 2       1458    3      |
|*4568    468     2      | 37      1       37     | 9       458     468    |
|*456     3       189    | 2589    89      2459   | 468     7       1468   |
*--------------------------------------------------------------------------*
ALS-XY  A=124568(*) [r24689c1] B=123789(%) [r1c13456] C=1789(^) [r2c89,r3c7]  x=2 y=1 z=789

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby daj95376 » Tue Mar 11, 2008 2:47 pm

Code: Select all
 +--------------------------------------------------------------------------------+
 |  1238    5       1378    |  13789   3789    1379    |  478     6       12479   |
 |  168     1678    4       |  156789  2       15679   |  3       189     1789    |
 |  9       2678    1378    |  13678   4       1367    |  78      128     5       |
 |--------------------------+--------------------------+--------------------------|
 |  248     9       6       |  1237    37      1237    |  5       248     2478    |
 |  123     127     137     |  4       5       8       |  67      29      2679    |
 |  248     2478    5       |  2679    79      2679    |  1       3       2478    |
 |--------------------------+--------------------------+--------------------------|
 |  7       148     189     |  589     6       459     |  2       1458    3       |
 |  4568    468     2       |  37      1       37      |  9       458     468     |
 |  456     3       189     |  2589    89      2459    |  468     7       1468    |
 +--------------------------------------------------------------------------------+

Kraken Swordfish c357\r139 => [r3c8]<>8,[r9c9]<>8
remote cell [r7c3]=8 => [r9c45]=8 => [r9c79]<>8 => [r13c7]=8 => [r3c8]<>8

[r5c8]=2 => [r3c8]=1 => { [r1c9]=2 => [r1c7 ]=4  => [r9c7]<>4 }
                        { [r9c9]=1 => [r9c35]=89 => [r9c7]<>8 } => [r9c7]=6 =>
[r5c7]=7 => [r5c123]=13 (invalid) => [r5c8]<>2   (contradiction net)

finned X-Wing r15\c19 => [r4c1]<>2,[r6c1]<>2

  c1b4  -  48    Locked Pair
  c1b7  -  56    Locked Pair

No points scored in Mike Barker's [1-6] because I knew that [r3c8]=2 is a backdoor single and forces [r5c8]<>2.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Steve R » Tue Mar 11, 2008 4:39 pm

Start:
Code: Select all
+-------------------+----------------------+-------------------+
| 1238     5  1378  |  13789  3789   1379  | 478     6  12479  |
|  168  1678     4  | 156789     2  15679  |   3   189   1789  |
|    9  2678  1378  |  13678     4   1367  |  78   128      5  |
+-------------------+----------------------+-------------------+
|  248     9     6  |   1237    37   1237  |   5   248   2478  |
|  123   127   137  |      4     5      8  |  67    29   2679  |
|  248  2478     5  |   2679    79   2679  |   1     3   2478  |
+-------------------+----------------------+-------------------+
|    7   148   189  |    589     6    459  |   2  1458      3  |
| 4568   468     2  |     37     1     37  |   9   458    468  |
|  456     3   189  |   2589    89   2459  | 468     7   1468  |
+-------------------+----------------------+-------------------+

Make the same move as tarek:
A = r24689c1; cand(A) = (124568)
B = {r2c8, r2c9, r3c7}; cand(B) = (1789)
C = r1c13456; cand(C) = (123789)
rcc(A, B) = 1
rcc(A, C) = 2

Eliminating 7, 8 and 9 from r1c79 and 9 from r2c46 leaves:

Code: Select all
+-------------------+----------------------+-------------------+
| 1238     5  1378  |  13789  3789   1379  |   4     6     12  |
|  168  1678     4  |  15678     2   1567  |   3   189   1789  |
|    9  2678  1378  |  13678     4   1367  |  78   128      5  |
+-------------------+----------------------+-------------------+
|  248     9     6  |   1237    37   1237  |   5   248   2478  |
|  123   127   137  |      4     5      8  |  67    29   2679  |
|  248  2478     5  |   2679    79   2679  |   1     3   2478  |
+-------------------+----------------------+-------------------+
|    7   148   189  |    589     6    459  |   2  1458      3  |
| 4568   468     2  |     37     1     37  |   9   458    468  |
|  456     3   189  |   2589    89   2459  | 468     7   1468  |
+-------------------+----------------------+-------------------+

Take:
D = r5c7; cand(D) = (67)
E = r14689c9; cand(E) = (124678)
rcc(D, E) = 7

Eliminating 6 from r5c9 and r9c7 leaves singles.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby Mike Barker » Thu Mar 13, 2008 3:07 am

Its funny that the reason I chose this puzzle was because I didn't like the large ALS that my solver used to find a solution and wanted to what alternatives existed. So what happens? Both tarek and Steve R find solutions with large ALS. I guess I need to rethink my ALS complexity factor. Any hints on how to find and use such big guys?

StrmCkr's forcing chain in his first step uses much of the same information, but breaks the ALS down by looking at r35c1 first and then r89c1. Kind of an interesting approach to dealing with a large ALS by looking at the almost hidden pairs and/or triples they contain.

As far as Danny's Kraken Swordfish, I'm biased, but I like anything Kraken.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby StrmCkr » Thu Mar 13, 2008 8:05 am

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:34 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby ronk » Thu Mar 13, 2008 11:48 am

Steve R and tarek, that's a very elegant solution IMO, so elegant that I've decided to not publish mine, even though it has a kraken house step (just for Mike).:)

Mike Barker wrote:Its funny that the reason I chose this puzzle was because I didn't like the large ALS that my solver used to find a solution and wanted to what alternatives existed. So what happens? Both tarek and Steve R find solutions with large ALS. I guess I need to rethink my ALS complexity factor. Any hints on how to find and use such big guys?

Finding the smallest ALS is easy; just pick a bivalued cell. Finding the largest ALS (in a house) is also easy; first take all the cells (in the house) and then remove one cell. Finding the almost largest ALS is still pretty easy; first take all the cells and then remove the only two cells that contain one of the candidates, if any. This can, of course, be extended to three cells and two candidates, etc., but that soon becomes more difficult than starting a search with small ALSs and working up.

Except for set D, the bivalue, all of the ALSs in Steve R's solution -- to which tarek contributed -- are of this latter "all minus two" type: for set A, the 2 cells in c1 containing digit 3 are removed; for set B, digit 2 in b3; for set C, digit 4 in r1; and for set E, digit 9 in c9 (see Steve's second pencilmarks for this one).

Code: Select all
A1238   5      1378   | 13789  3789   1379   |C478    6    BC12479
 168    1678   4      | 156789 2      15679  | 3      189    1789
 9      2678   1378   | 13678  4      1367   | 78    B128    5
----------------------+----------------------+---------------------
 248    9      6      | 1237   37     1237   | 5      248    2478
A123    127    137    | 4      5      8      | 67    F29    F2679
 248    2478   5      | 2679   79     2679   | 1      3      2478
----------------------+----------------------+---------------------
 7      148    189    | 589    6      459    | 2      1458   3
 4568   468    2      | 37     1      37     | 9      458    468
 456    3      189    | 2589   89     2459   | 468    7      1468

Without looking too hard I see another in r5 by removing cells r5c89, the only cells containing digit 9 in r5. Thus, F = {r5c1237} = {12367} and voilà, we have the derived strong inference r5c7 =6|9= r5c8.

Finding an ALS that is useful is the difficult part, and it's more difficult to find a useful large ALS than a useful small ALS -- for two reasons. Firstly, an ALS larger than a bivalue frequently has fewer "directionality" options. One bivalue candidate sees twenty other cells, i.e., its "domain" includes a row, a column and a box. The domain of one large ALS candidate is often only one house.

Secondly, a useful ALS is also chainable even though we might think of them in sets. The larger the ALS, the more difficult it is to find a chain, simply because there are fewer cells (or cell sets) to which the large ALS may be chained.

But I preach to the choir, I'm sure.

[edit: The "all" above also applies to smaller naked n-tuples (subsets) within a house, e.g., the naked quintuple in b8.]
Last edited by ronk on Thu Mar 13, 2008 11:10 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Thu Mar 13, 2008 1:33 pm

Good one Steve R (I'm obviously biased:D )
ronk wrote:a useful ALS is also chainable even though we might think of them in sets.

Yes, in the case of ALS-XY you can break this big chain into 3 sets.

if the ALS is big & the grid candidate number is also big ... then it would be of extreme difficulty to find one that is useful without some T&E.

The reason is because you need to have a large group of cells to provide an inference that would match a corresponding inference stemming from another set of cells.

Difficult to isolate (like in bivalue/bilocation) or like in x-cycles. It also requires a multi-layered (Look ahead) strategy that is IMO complex.

Only when you have fewer cells & candidates, then, an ALS-XY (springs out). [There was a recent puzzle in the HELP section which I can't locate now:( ].

This remins (YET AGAIN) a subjective matter.

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby Steve R » Thu Mar 13, 2008 2:27 pm

Mike asked for hints in finding the big guys. It’s easy: get tarek to do the hard work!

More seriously, taking up Ron’s point, it is possible that “all minus two” ALSs are sufficiently productive to warrant inspection before the intermediate sizes. We know that conjugate cells are powerful and an “all minus two” is the complement of a pair of conjugate cells in a house.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby Mike Barker » Fri Mar 14, 2008 4:38 am

Strmckr, if I were to write your first elimination as a forcing chain, it might look something like:
Code: Select all
            +-2-r5c8-9------------------+         +-7-r5c7-6-
            |                           |         |
r6c2-7-r5c123-2-r46c1-48-r89c1-6-r2c1-1-r2c8-8-r3c7-7-r1c7-4-r9c7-6- -><- => r6c2<>7
   |                |            |         |          |      |
   |                +-8----------+         +-8--------+      |
   +-7-r6c5-9-r9c5-8-----------------------------------------+

Probably not something I'd try on my own, but it gets the job done.

Ron, Tarek, and Steve, thanks for the insights and for the elegant solution. Actually, I think the idea of an ALS with one digit existing in only one cell probably should get more publicity. It was something Sudtryo talked about before in a slightly different context. As it turns out the solution I came up with makes use of an ALS with a singlton. I was looking at 2-3 cell ALSs and noticed two in block 3 (r13c7=478 and r2c89|r3c7=1789). These can be combined into a four cell ALS with "4" only appearing in r1c7. This ALS can be used to create a multi-inference nice loop using the kraken column, r125c1=1 (the same as Ron's?) with the result that r1c9<>479. The same thing could have been done by treating r1c7 as an AALS, but combining the ALS seems a better approach and by combining them we get the immediate placement: r1c7=4.

Code: Select all
Kraken Column r125c1=1 => r1c9<>479
-4789-r13c7|r2c89-1-r2c1=1=r5c1=3=r1c1=2=r1c9
                      ||
                      ++=1=r1c1=2=r1c9
+--------------------+----------------------+-------------------+
| 1238cd    5  1378  |  13789  3789   1379  | 478a    6  12-479d|
|  168b  1678     4  | 156789     2  15679  |   3   189a  1789a |
|    9   2678  1378  |  13678     4   1367  |  78a  128      5  |
+--------------------+----------------------+-------------------+
|  248      9     6  |   1237    37   1237  |   5   248   2478  |
|  123bc  127   137  |      4     5      8  |  67    29   2679  |
|  248   2478     5  |   2679    79   2679  |   1     3   2478  |
+--------------------+----------------------+-------------------+
|    7    148   189  |    589     6    459  |   2  1458      3  |
| 4568    468     2  |     37     1     37  |   9   458    468  |
|  456      3   189  |   2589    89   2459  | 468     7   1468  |
+--------------------+----------------------+-------------------+


One question might be can we define a set of necessary and sufficient conditions which defines the minimum set of useful ALS?
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Fri Mar 14, 2008 11:19 am

Mike Barker wrote:This ALS can be used to create a multi-inference nice loop using the kraken column, r125c1=1 (the same as Ron's?) with the result that r1c9<>479.

Amazingly close! Mine used the same kraken column for r1c7<>78. Modifying your illustration just a bit ...
Code: Select all
Kraken Column r125c1=1 => r1c7<>78
r1c7-78-r3c7|r2c89-1-r2c1=1=r5c1=3=r1c1=2=r1c9=4=r1c7
                      ||
                      ++=1=r1c1=2=r1c9=4=r1c7
+--------------------+----------------------+-------------------+
| 1238cd    5  1378  |  13789  3789   1379  | 4-78e   6  12479de|
|  168b  1678     4  | 156789     2  15679  |   3   189a  1789a |
|    9   2678  1378  |  13678     4   1367  |  78a  128      5  |
+--------------------+----------------------+-------------------+
|  248      9     6  |   1237    37   1237  |   5   248   2478  |
|  123bc  127   137  |      4     5      8  |  67    29   2679  |
|  248   2478     5  |   2679    79   2679  |   1     3   2478  |
+--------------------+----------------------+-------------------+
|    7    148   189  |    589     6    459  |   2  1458      3  |
| 4568    468     2  |     37     1     37  |   9   458    468  |
|  456      3   189  |   2589    89   2459  | 468     7   1468  |
+--------------------+----------------------+-------------------+

The multi-inference expression could be "linearized" by treating r125c1 as an almost-hidden-pair, but that might be confusing rather than helpful.

One question might be can we define a set of necessary and sufficient conditions which defines the minimum set of useful ALS?

I probably don't understand the question, but wouldn't that be the ALS xz-rule?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Fri Mar 14, 2008 12:32 pm

I made a quick but late check of that puzzle.

It can be solved nearly without ALS thru ternary kraken blossoms.

It's a (relative) long way, but it works. It remains nearly out of the field covered by my group of hand solvers.

The way is shorter if I force use of ALS, but still far from very short solutions produced here. The solver produces about ten AICs most of them crossing ALS/AHS some of them likely of no interest.
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

Postby StrmCkr » Fri Mar 14, 2008 1:47 pm

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:34 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Next

Return to General