The New Sudoku Players' Forum

[P.O.]

Code: Select all

. . 9   2 . .   . . .
. 3 .   . 8 .   . . .
8 . .   . . 7   . . .
2 . .   . . 4   5 . .
. 4 .   . 3 .   . 7 .
. . 5   8 . .   . . 3
. . 4   5 . .   . . 8
. 7 .   . 6 .   . 3 .
9 . .   . . 1   6 . .

..92......3..8....8....7...2....45...4..3..7...58....3..45....8.7..6..3.9....16..


[jco]

I found a solution in three (non-basic) moves. After basics,

Code: Select all

.---------------------------------------------------.
| 1456  15   9   | 2    145  3 |c1478  14568  14567 |
| 1456  3    7   | 146  8    9 | 124   12456  12456 |
| 8     125  126 | 146  145  7 | 3     14569  14569 |
|----------------+-------------+--------------------|
| 2     189  3   | 7    19   4 | 5     1689   169   |
|B16    4 aAu168 |g9-1  3    5 |b1289  7      129   |
| 7     19   5   | 8    2    6 | 149   149    3     |
|----------------+-------------+--------------------|
| 3     6    4   | 5   e79   2 |d179   19     8     |
| 15    7    12  |f49   6    8 | 249   3      2459  |
| 9     258  28  | 3    47   1 | 6     245    2457  |
'---------------------------------------------------'

1. Kraken Cell (168)r5c3 => - 1 r5c4 [8 placements]
(1)r5c3
(6)r5c3 - (6=1)r1c5
(8)r5c3 - r5c7 = (8-7)r1c7 = r7c7 - (7=9)r7c5 - r8c4 = (9)r5c4
---

Code: Select all

.-----------------------------------------------.
|d1456  15   9   | 2   45  3 | 148 d4568  7     |
| 1456  3    7   | 16  8   9 | 124  2456  12456 |
| 8     125  126 | 16  45  7 | 3    4569  14569 |
|----------------+-----------+------------------|
| 2    b89   3   | 7   1   4 | 5   c689   69    |
|e16    4    168 | 9   3   5 | 128  7     12    |
| 7     19   5   | 8   2   6 | 149  49    3     |
|----------------+-----------+------------------|
| 3     6    4   | 5   9   2 | 7    1     8     |
|a5-1   7    12  | 4   6   8 | 29   3     259   |
| 9    b258  28  | 3   7   1 | 6    245   245   |
'-----------------------------------------------'

2. (5)r8c1 = (58)r49c2 - (8)r4c8 = (86)r1c18 - (6=1)r5c1 => -1 r8c1 [6 placements, 1 LC elimination]
---

Code: Select all

.------------------------------------------------.
| 146  15    9  |  2    45  3 | 148  468    7    |
| 146  3     7  |  16   8   9 | 14   2      5    |
| 8    125 #(6)2|a(16)  45  7 | 3    49-6 b(1)9-6|
|---------------+-------------+------------------|
| 2    89    3  |  7    1   4 | 5    689    69   |
|(16)  4   #(6)8|  9    3   5 | 128  7    b(1)2  |
| 7    19    5  |  8    2   6 | 149  49     3    |
|---------------+-------------+------------------|
| 3    6     4  |  5    9   2 | 7    1      8    |
| 5    7     1  |  4    6   8 | 29   3      29   |
| 9    28    28 |  3    7   1 | 6    5      4    |
'------------------------------------------------'

3. W-wing with transport (16)r3c4, r5c1 connedted by (1)c9, extended by (6)c3 => -6 r3c89; ste

or, as a chain (6=1)r3c4 - r3c9 = r5c9 - (1=6)r5c1 - r5c3 = (6)r3c3 => -6 r3c89; ste

[Cenoman]

Two steps:

Code: Select all

 +---------------------+-------------------+-------------------------+
 |  1456   15    9     |  2     145   3    | c1478   14568   14567   |
 |  1456   3     7     |  146   8     9    |  124    12456   12456   |
 |  8      125   126   |  146   145   7    |  3      14569   14569   |
 +---------------------+-------------------+-------------------------+
 |  2      189   3     |  7     1-9   4    |  5      1689    169     |
 |  16     4     168   | e19    3     5    | d1289   7      d129     |
 |  7      19    5     |  8     2     6    |  149    149     3       |
 +---------------------+-------------------+-------------------------+
 |  3      6     4     |  5    a79    2    | b179    19      8       |
 |  15     7     12    |  4-9   6     8    |  249    3       2459    |
 |  9      258   28    |  3     47    1    |  6      245     2457    |
 +---------------------+-------------------+-------------------------+

1. (9=7)r7c5 - r7c7 = (7-8)r1c7 = (8-29)r5c79 =(9)r5c4 => -9 r4c5, r8c4; 8 placements

Code: Select all

 +---------------------+-----------------+-----------------------+
 |  1456   15    9     |  2    45   3    |  148   4568   7       |
 |  1456   3     7     |  16   8    9    |  124   2456   12456   |
 |  8      125   126   |  16   45   7    |  3     4569   14569   |
 +---------------------+-----------------+-----------------------+
 |  2      89    3     |  7    1    4    |  5     689    69      |
 |  6-1    4     168   |  9    3    5    |  128   7     a12*     |
 |  7     e19    5     |  8    2    6    | d149   49     3       |
 +---------------------+-----------------+-----------------------+
 |  3      6     4     |  5    9    2    |  7     1      8       |
 | a15*    7     12    |  4    6    8    | c29    3    ba259*    |
 |  9      258   28    |  3    7    1    |  6     245    245     |
 +---------------------+-----------------+-----------------------+

2. Almost Y-Wing [(1=2)r5c9 - (2=*5)r8c9-(5=1)r8c1] = (9)r8c9 - r8c7 = (9-1)r6c7 = (1)r6c2 => -1 r5c1; ste

[eleven]

Code: Select all

 *-----------------------------------------------------------------*
 |  1456   15    9     |  2     145   3  | b1478   14568   14567   |
 |  1456   3     7     |  146   8     9  |  124    12456   12456   |
 |  8      125   126   |  146   145   7  |  3      14569   14569   |
 |---------------------+-----------------+-------------------------|
 |  2      189   3     |  7     19    4  |  5      1689    169     |
 | d16     4    d168   | d19    3     5  | c1289   7       129     |
 |  7      19    5     |  8     2     6  |  149    149     3       |
 |---------------------+-----------------+-------------------------|
 |  3      6     4     |  5     9-7   2  | a179    19      8       |
 |  15     7     12    | e49    6     8  |  249    3       2459    |
 |  9      258   28    |  3    e47    1  |  6      245     245-7   |
 *-----------------------------------------------------------------*

7r7c7 = (7-8)r1c7 = 8r5c7 - (8=169)r5c134 - (9=47)b8p48 => -7r9c9,r7c5

Code: Select all

 *-------------------------------------------------------------*
 |  1456   15    9     |  2    45   3  |  148   4568   7       |
 |  1456   3     7     |  16   8    9  |  124   2456   12456   |
 |  8      125   126   |  16   45   7  |  3     4569   14569   |
 |---------------------+---------------+-----------------------|
 |  2      89    3     |  7    1    4  |  5     689    69      |
 |  6-1    4     168   |  9    3    5  |  128   7     #12      |
 |  7     b19    5     |  8    2    6  | a149   49     3       |
 |---------------------+---------------+-----------------------|
 |  3      6     4     |  5    9    2  |  7     1      8       |
 | #15     7     12    |  4    6    8  | #29    3     #259     |
 |  9      258   28    |  3    7    1  |  6     245    245     |
 *-------------------------------------------------------------*

4 digits 1259 in 4 cells r5c9,r8c179:
- all in: 1r5c9 or 1 r8c1
- 2 twice: (2-9)r8c7 = r6c7 - (9=1)r6c2
=> -1r5c1, stte

[P.O.]

i post puzzles for which i have at least a two steps solution with the sort of chains i do, considering intersections as no-step, so not too difficult: they are easy enough to solve with a shortest-depth first strategy even if there may be lots of chains.
for this one i have three two steps solutions, whose second step is the same: the elimination of 1 from R5C1. the shortest-depth first path has 36 chains with depth <= 3.
when trying to find a shortest path solution to the puzzles proposed here i limit the search to two steps, maybe three sometimes, and at a 'reasonable' depth as at the moment i have only a android tablet with a lisp interpreter to explore the possibilities, a rather slow programming environment.
needless to say i am a poor manual solver.

Code: Select all

after singles and intersections:

 1456   15     9       2      145    3     a14×7-8 b1456+8  14567           
 1456   3      7       146    8      9      124     12456   12456           
 8      125    126     146    145    7      3       14569   14569           
 2     d1+89   3       7     g+19    4      5      c16-89   169             
e(16)   4     e(16-8) f-19    3      5      1289    7       129             
 7      19     5       8      2      6      149     149     3               
 3      6      4       5     h7+9    2     i1+79    19      8               
 15     7      12      49     6      8      249     3       2459           
 9      258    28      3      47     1      6       245     2457           

depth: 5  candidate: 7  from start
 
((8 0) (1 7 3) (1 4 7 8))
((8 0) (1 8 3) (1 4 5 6 8))
((8 1 1) (4 2 4) (1 8 9))
((1 2 1 31) ((5 1 4) (1 6)) ((5 3 4) (1 6 8)))
((1 3 12) (4 5 5) (1 9))
((9 4 10) (7 5 8) (7 9))
((7 5 10) (7 7 9) (1 7 9))

singles:
( r5c4b5 n9   r4c5b5 n1   r9c5b8 n7   r8c4b8 n4   r7c8b9 n1
  r7c5b8 n9   r1c9b3 n7   r7c7b9 n7 )

 1456    15     9      2      45     3     148    4568   7               
 1456    3      7      16     8      9     124    2456   12456           
 8       125    126    16     45     7     3      4569   14569           
 2       89     3      7      1      4     5      689    69             
 ×16     4      168    9      3      5     128    7     d-1+2             
 7      a-19    5      8      2      6    b+149   49     3               
 3       6      4      5      9      2     7      1      8               
e+15     7      12     4      6      8    c2+9    3     d-2+5-9             
 9       258    28     3      7      1     6      245    245             

depth: 3  candidate: 1  from cell
(((5 1 4) (1 6)))

((1 0) (6 2 4) (1 9))
((1 0) (6 7 6) (1 4 9))
((9 1 10) (8 7 9) (2 9))
((5 2 102) (8 9 9) (2 5 9))
((1 3 9) (8 1 7) (1 5))

ste.


[denis_berthier]

.

Code: Select all

Resolution state after Singles and whips[1]:
   +-------------------+-------------------+-------------------+
   ! 1456  15    9     ! 2     145   3     ! 1478  14568 14567 !
   ! 1456  3     7     ! 146   8     9     ! 124   12456 12456 !
   ! 8     125   126   ! 146   145   7     ! 3     14569 14569 !
   +-------------------+-------------------+-------------------+
   ! 2     189   3     ! 7     19    4     ! 5     1689  169   !
   ! 16    4     168   ! 19    3     5     ! 1289  7     129   !
   ! 7     19    5     ! 8     2     6     ! 149   149   3     !
   +-------------------+-------------------+-------------------+
   ! 3     6     4     ! 5     79    2     ! 179   19    8     !
   ! 15    7     12    ! 49    6     8     ! 249   3     2459  !
   ! 9     258   28    ! 3     47    1     ! 6     245   2457  !
   +-------------------+-------------------+-------------------+
133 candidates

There's a simplest-first solution in S+Z4. The number of steps in S+Z4 can probably be decreased, but my main point here is to compute the rating.

Code: Select all

finned-x-wing-in-rows: n5{r8 r2}{c1 c9} ==> r3c9≠5, r1c9≠5
biv-chain[3]: r1c2{n1 n5} - b7n5{r9c2 r8c1} - b7n1{r8c1 r8c3} ==> r3c3≠1
biv-chain[3]: r9c3{n2 n8} - r5n8{c3 c7} - b6n2{r5c7 r5c9} ==> r9c9≠2
biv-chain[3]: r1n8{c8 c7} - c7n7{r1 r7} - b9n1{r7c7 r7c8} ==> r1c8≠1
z-chain[3]: r4n8{c8 c2} - c2n9{r4 r6} - r6n1{c2 .} ==> r4c8≠1
z-chain[3]: r4c5{n1 n9} - c2n9{r4 r6} - r6n1{c2 .} ==> r4c9≠1
biv-chain[3]: r4n1{c5 c2} - r1c2{n1 n5} - b2n5{r1c5 r3c5} ==> r3c5≠1
z-chain[3]: c9n1{r3 r5} - r5n2{c9 c7} - c7n8{r5 .} ==> r1c7≠1
biv-chain[4]: c4n6{r2 r3} - r3c3{n6 n2} - c2n2{r3 r9} - c8n2{r9 r2} ==> r2c8≠6
biv-chain[4]: r1n7{c9 c7} - r7n7{c7 c5} - c5n9{r7 r4} - c5n1{r4 r1} ==> r1c9≠1
finned-x-wing-in-rows: n1{r4 r1}{c5 c2} ==> r3c2≠1
biv-chain[4]: c4n6{r2 r3} - r3c3{n6 n2} - r3c2{n2 n5} - r3c5{n5 n4} ==> r2c4≠4
biv-chain[4]: r1n7{c9 c7} - r7n7{c7 c5} - c5n9{r7 r4} - r4c9{n9 n6} ==> r1c9≠6
biv-chain[3]: r1c9{n4 n7} - r9n7{c9 c5} - b8n4{r9c5 r8c4} ==> r8c9≠4
z-chain[3]: r1n6{c8 c1} - c1n4{r1 r2} - r2n5{c1 .} ==> r1c8≠5
biv-chain[4]: r5n8{c3 c7} - b3n8{r1c7 r1c8} - r1n6{c8 c1} - b4n6{r5c1 r5c3} ==> r5c3≠1
hidden-single-in-a-column ==> r8c3=1
naked-single ==> r8c1=5
whip[1]: r2n5{c9 .} ==> r3c8≠5
whip[1]: r8n2{c9 .} ==> r9c8≠2
singles ==> r2c8=2, r2c9=5, r9c8=5
naked-pairs-in-a-column: c9{r1 r9}{n4 n7} ==> r3c9≠4
biv-chain[3]: b9n7{r7c7 r9c9} - b9n4{r9c9 r8c7} - r2c7{n4 n1} ==> r7c7≠1
hidden-single-in-a-block ==> r7c8=1
biv-chain[2]: r7n9{c7 c5} - b5n9{r4c5 r5c4} ==> r5c7≠9
biv-chain[3]: c4n4{r8 r3} - r3n1{c4 c9} - r2c7{n1 n4} ==> r8c7≠4
stte

And there are lots of 2-step solutions in W6 (a relatively acceptable increase of complexity for each step in order to reduce the number of steps):

Code: Select all

whip[5]: c7n8{r1 r5} - r5n2{c7 c9} - r5n9{c9 c4} - c5n9{r4 r7} - r7n7{c5 .} ==> r1c7≠7
singles ==> r1c9=7, r7c7=7, r7c5=9, r4c5=1, r5c4=9, r7c8=1, r8c4=4, r9c5=7
whip[6]: r5c9{n1 n2} - r5c7{n2 n8} - b6n1{r5c7 r6c7} - c7n9{r6 r8} - r8c9{n9 n5} - r8c1{n5 .} ==> r5c1≠1
stte

Code: Select all

whip[5]: r7c5{n9 n7} - c7n7{r7 r1} - c7n8{r1 r5} - r5n9{c7 c9} - r5n2{c9 .} ==> r4c5≠9
singles ==> r4c5=1, r5c4=9, r8c4=4, r9c5=7, r7c5=9, r7c8=1, r7c7=7, r1c9=7
whip[6]: r5c9{n1 n2} - r5c7{n2 n8} - b6n1{r5c7 r6c7} - c7n9{r6 r8} - r8c9{n9 n5} - r8c1{n5 .} ==> r5c1≠1
stte

Code: Select all

whip[5]: c7n7{r7 r1} - c7n8{r1 r5} - r5n2{c7 c9} - r5n9{c9 c4} - b8n9{r8c4 .} ==> r7c5≠7
singles ==> r7c5=9, r4c5=1, r5c4=9, r7c8=1, r7c7=7, r8c4=4, r9c5=7, r1c9=7
whip[6]: r5c9{n1 n2} - r5c7{n2 n8} - b6n1{r5c7 r6c7} - c7n9{r6 r8} - r8c9{n9 n5} - r8c1{n5 .} ==> r5c1≠1
stte

Code: Select all

whip[5]: r7c5{n9 n7} - c7n7{r7 r1} - c7n8{r1 r5} - r5n9{c7 c9} - r5n2{c9 .} ==> r8c4≠9
singles ==> r8c4=4, r9c5=7, r7c5=9, r4c5=1, r5c4=9, r7c8=1, r7c7=7, r1c9=7
whip[6]: r5c9{n1 n2} - r5c7{n2 n8} - b6n1{r5c7 r6c7} - c7n9{r6 r8} - r8c9{n9 n5} - r8c1{n5 .} ==> r5c1≠1
stte

Code: Select all

z-chain[6]: c4n9{r5 r8} - r7c5{n9 n7} - c7n7{r7 r1} - c7n8{r1 r5} - r5c3{n8 n6} - r5c1{n6 .} ==> r5c4≠1
singles ==> r5c4=9, r4c5=1, r8c4=4, r9c5=7, r7c5=9, r7c8=1, r7c7=7, r1c9=7
whip[6]: r5c9{n1 n2} - r5c7{n2 n8} - b6n1{r5c7 r6c7} - c7n9{r6 r8} - r8c9{n9 n5} - r8c1{n5 .} ==> r5c1≠1
stte

[denis_berthier]

Hi P.O.

i post puzzles ... easy enough to solve with a shortest-depth first strategy even if there may be lots of chains.

I guess this is closely related to looking for braids of minimum length (but it depends on the details of your algorithm).

at the moment i have only a android tablet with a lisp interpreter to explore the possibilities, a rather slow programming environment.

Happy to meet a fellow Lispian. We're an endangered species. What version of Lisp do you have on Android?

Lisp makes it very easy to handle lists and strings. So why don't you write a better output function? I have no idea of what each line is supposed to mean.

[P.O.]

hi Denis,

it is true than lisp is not one of the favorite languages nowadays; i use CL REPL found on the play store, an open source project: https://gitlab.com/eql/EQL5-Android
i agree that the output of the solver is unusual compared to the notation i see on the forum, some of which are still obscure to me; each line is for a link in the chain, only the first list of digits is complicated, the other ones represent the cell(s): coordinates then content; for the first one: three digits if the link is a single cell, four if it is a group of cells; the first digit is the candidate set in the cell, the second the depth in the BFS algorithm, if the link is a group of cells the third denotes its unit 1 row 2 col 3 box, the last digit is a code that helps to understand the logic for adding the link to the chain.
but i dont expect that people should bother with that notation; i would readily comply to a agreed upon notation if there was one but there does not seem to be a consensus in that matter: which one should i use; i could use the eureka notation for the simplest chains but for the complicated ones, those that incorporate subsets or links that result from the eliminations done by previous ones. but i will think about it.
braids hum... i am aware of your work, i have read some of your books, but i am still lost in your formalism; my approach is purely empirical, i dont theorize in the least but i use what i understand here and there to ameliorate the solving capacity of the algorithm.

[denis_berthier]

it is true than lisp is not one of the favorite languages nowadays; i use CL REPL found on the play store, an open source project: https://gitlab.com/eql/EQL5-Android

Don't you have memory overflow problems on a tablet?

i would readily comply to a agreed upon notation if there was one but there does not seem to be a consensus in that matter: which one should i use; i could use the eureka notation for the simplest chains but for the complicated ones, those that incorporate subsets or links that result from the eliminations done by previous ones. but i will think about it.

Of course, I'd recommend my nrc-notation, but if you prefer the AIC, even that would be better than yours. Eureka seems to have fallen into oblivion.

braids hum... i am aware of your work, i have read some of your books, but i am still lost in your formalism; my approach is purely empirical, i dont theorize in the least but i use what i understand here and there to ameliorate the solving capacity of the algorithm.

The books were written for academic publication, not for Sudoku players; but the content remains very elementary. Most of the time, the formalism can be skipped and most of my readers have no problem with it. For an informal presentation of the main patterns, maybe the CSP-Rules User Manual is easier to read.

[P.O.]

i have the samsung galaxy tab s6, its ram is 8 go, i haven't had any memory problems so far; the main drawback with android is the lack of a good programming environment: editor, debugger, compliler.