The New Sudoku Players' Forum

[evert]

done...
Some puzzles with bottleneck:

Code: Select all

44;..;..;50;..;..;..;..;..
42;45;47;..;..;70;..;64;..
..;..;32;31;55;..;73;63;..
..;..;..;..;..;..;74;..;62
..;15;39;29;..;..;75;..;61
..;..;..;..;..;..;..;01;02
..;..;37;..;..;77;05;..;..
21;..;23;..;..;79;..;..;..
..;19;..;..;..;..;..;..;07

..;..;55;..;48;10;..;..;..
52;51;..;49;..;..;09;07;..
..;..;..;43;..;..;13;79;..
..;..;..;..;44;15;..;78;..
..;..;62;..;..;..;02;01;..
..;..;40;..;..;..;74;..;..
37;35;..;..;20;..;24;..;..
..;30;..;..;65;..;..;..;..
..;..;31;27;..;..;..;..;..

..;..;..;..;..;81;..;01;..
..;49;..;..;09;..;02;..;..
..;..;..;..;..;..;..;75;..
53;..;43;07;41;..;..;..;..
..;..;55;..;39;14;..;..;71
..;31;..;..;..;58;16;..;70
..;30;..;21;..;19;..;..;..
27;..;..;22;..;..;..;66;..
..;26;23;..;..;62;65;..;..

55;..;..;..;..;78;..;..;..
..;56;51;..;49;..;47;23;..
..;..;..;..;..;..;..;44;..
..;..;73;28;29;..;..;..;..
..;..;61;..;..;18;..;..;41
..;62;..;16;17;..;..;..;..
..;63;65;..;..;..;..;..;39
..;..;..;12;10;07;..;05;03
68;..;..;..;09;..;..;..;02

Some puzzles with pairs:

Code: Select all

..;44;..;50;..;..;53;59;..
..;46;45;..;51;52;..;..;..
..;39;..;..;..;..;..;63;..
..;..;..;..;02;..;..;..;..
..;..;36;04;..;01;..;65;..
..;81;19;..;23;..;..;..;28
09;..;18;..;..;..;..;68;..
..;11;..;..;..;..;25;69;..
..;..;..;78;..;76;..;..;..

76;..;..;..;..;..;05;..;..
..;..;78;..;..;04;..;..;..
..;49;51;16;..;..;..;..;01
..;..;52;44;..;19;..;..;10
..;..;..;42;..;..;..;12;24
54;..;67;..;..;..;..;..;..
..;..;57;..;36;..;38;27;..
..;..;..;..;..;35;..;29;..
..;..;..;59;60;..;..;..;..

This puzzle should require both:

Code: Select all

..;..;..;..;..;..;..;53;..
09;08;..;..;..;..;..;..;..
..;06;13;19;..;..;..;50;..
..;..;..;58;..;27;61;49;..
81;..;02;..;..;..;46;..;..
..;03;..;29;22;..;47;..;..
..;..;..;..;..;23;..;44;..
..;..;33;35;..;38;..;..;..
..;..;75;..;..;..;..;..;42

[udosuk]

Thanks for the puzzles, evert.

Have you (or your solver) tried djape's Jan 20 puzzle? Apparently it requires a new technique, which I call "path shaping". It's hard to describe the technique formally, so here is how I solved it, see if you can get the essence of that technique:



After "easy" moves:

Code: Select all

38 37 36 12 11 .. .. 64
39 40 35 43 13 .. .. 08
21 41 42 34 44 .. .. 07
20 22 33 .. .. .. 06 01
23 19 .. .. .. 05 .. ..
24 25 .. .. .. .. .. ..
27 26 30 .. .. .. 56 ..
28 29 .. .. .. 52 .. 55

Define the following paths:
_A: 14..18 (length 5)
_B: 57..63 (length 7)
_C: 45..51 (length 7)
_D: 31..32 (length 2)

Code: Select all

38 37 36 12 11 .. .. 64
39 40 35 43 13 .. .. 08
21 41 42 34 44 _* _* 07
20 22 33 _# _# _# 06 01
23 19 _@ _@ _@ 05 _@ ..
24 25 .. .. .. .. .. ..
27 26 30 .. .. .. 56 ..
28 29 .. .. .. 52 .. 55

_*: r3c67={_A,_B} (can be considered as a "double gateway")
_#: r4c456={_A,_B,_C}
_@: r5c3457={_A,_B,_C,_D)
=> r5c8=02
Also r4c4 (_#) can't touch r3c67 (_*)
=> r4c4 can't be from _A or _B, must be from _C=45
=> _#: r4c56={_A,_B}

Code: Select all

38 37 36 12 11 .. .. 64
39 40 35 43 13 .. .. 08
21 41 42 34 44 _* _* 07
20 22 33 45 _# _# 06 01
23 19 _@ _@ _@ 05 _@ 02
24 25 .. .. .. .. .. ..
27 26 30 .. .. .. 56 ..
28 29 .. .. .. 52 .. 55

Now r5c7 (_@) must be from _A or _B
But it can't be from _A (too far away from 13 & 19)
=> r5c7 (_@) must be from _B
=> r4c6 (_#) must be from _B
=> r4c5 (_#) must be from _A
=> r3c6 (_*) must be from _A
=> r3c7 (_*) must be from _B
=> _@: r45c345={_A,_C,_D}

Code: Select all

38 37 36 12 11 .. .. 64
39 40 35 43 13 .. .. 08
21 41 42 34 44 _A _B 07
20 22 33 45 _A _B 06 01
23 19 _@ _@ _@ 05 _B 02
24 25 _$ _$ .. .. .. ..
27 26 30 .. .. .. 56 ..
28 29 .. .. .. 52 .. 55

Now one of r6c34 (_$) must be from _D=31
=> r6c34 (_$) can't be both from _A
=> one of r5c34 (_@) must be from _A
(otherwise the path for _A will have at least 6 cells, too long)
=> r5c4 (_@) must be from _A
=> r5c3 (_@) must be from _D=32
=> r5c5 (_@) must be from _C=46
=> r6c3 (_$) must be from _A=18
=> r6c4 (_$) must be from _D=31

Code: Select all

38 37 36 12 11 .. .. 64
39 40 35 43 13 .. .. 08
21 41 42 34 44 _A _B 07
20 22 33 45 _A _B 06 01
23 19 32 _A 46 05 _B 02
24 25 18 31 .. .. .. ..
27 26 30 .. .. .. 56 ..
28 29 .. .. .. 52 .. 55

Now r3c6+r4c5+r5c4 from _A must be [15..17]
=> r2c6=14
=> r2c7 must be from _B
=> r1c67=[10,09]
=> r23c7+r4c6+r5c7 from _B must be [63..60]

Code: Select all

38 37 36 12 11 10 09 64
39 40 35 43 13 14 63 08
21 41 42 34 44 15 62 07
20 22 33 45 16 61 06 01
23 19 32 17 46 05 60 02
24 25 18 31 .. .. .. ..
27 26 30 .. .. .. 56 ..
28 29 .. .. .. 52 .. 55

Now [04,03] must be @ either r6c67 or r6c78
Gateway: r6c7 is reserved for [04,03]
Also 54 must be @ either r7c8 or r8c7
=> [59..57] can't be @ r67c8+r8c7
=> 59 can't be @ r6c8, must be @ r6c6
=> [04,03] must be @ r6c78
=> 47 must be @ r6c5

Code: Select all

38 37 36 12 11 10 09 64
39 40 35 43 13 14 63 08
21 41 42 34 44 15 62 07
20 22 33 45 16 61 06 01
23 19 32 17 46 05 60 02
24 25 18 31 47 59 04 03
27 26 30 .. .. .. 56 ..
28 29 .. .. .. 52 .. 55

Gateway: r8c7 is reserved for [53,54]
=> 57 can't be @ r7c8 or r8c7, must be @ r7c6
=> 58 must be @ r7c5
=> [53,54] must be @ r8c7+r7c8
=> 48 must be @ r7c4
=> r8c345=[49,50,51]

Code: Select all

38 37 36 12 11 10 09 64
39 40 35 43 13 14 63 08
21 41 42 34 44 15 62 07
20 22 33 45 16 61 06 01
23 19 32 17 46 05 60 02
24 25 18 31 47 59 04 03
27 26 30 48 58 57 56 54
28 29 49 50 51 52 53 55

Hope your solver had a easier time than me.

[evert]

After "easy" moves:

Code: Select all

38 37 36 12 11 .. .. 64
39 40 35 43 13 .. .. 08
21 41 42 34 44 .. .. 07
20 22 33 .. .. .. 06 01
23 19 .. .. .. 05 .. ..
24 25 .. .. .. .. .. ..
27 26 30 .. .. .. 56 ..
28 29 .. .. .. 52 .. 55

Back to this point:
naked single in (8,3): 49.

[evert]

Apart from this I appreciate your ideas!

I'd like to call these paths (A/B/C/D) fragments.
Let's say:
Bottleneck means:
a given fragment needs a given empty cell as pass-through.
What you're pointing out is:
n given fragments need n given cells as pass-through.
So multiple-bottleneck, allowing to exclude not-involved numbers from the involved cells.

You mentioned one more thing:
If a cell is occupied by a fragment, than adjacent cells are occupied by the same fragment if they are necessary pass-throughs.

Hope your solver had a easier time than me.

It did; naked singles are quite dominant and not always very elegant in Hidato.

[udosuk]

Here is an alternative solving path to djape's Jan 20 puzzle, using naked singles predominantly:



After "easy" moves:

Code: Select all

38 37 36 12 11 .. .. 64
39 40 35 43 13 .. .. 08
21 41 42 34 44 .. .. 07
20 22 33 .. .. .. 06 01
23 19 .. .. .. 05 .. ..
24 25 .. .. .. .. .. ..
27 26 30 .. .. .. 56 ..
28 29 .. .. .. 52 .. 55

Naked Single: r8c3=49
=> r7c4=48 (r8c4 can't be 48, too far from 44)
=> r8c4=50
Naked Single: r8c5=51
Naked Single: r7c5=58
Naked Single: r7c8=54
=> r8c7=53
Naked Single: r7c6=57
Naked Single: r6c8=03
Naked Single: r5c8=02
Naked Single: r6c7=04
Naked Single: r5c8=60
=> r46c6=[61,59]
Naked Single: r6c5=47
Naked Single: r1c7=09
Naked Single: r1c6=10
=> r2c7=63
Naked Single: r3c7=62
Naked Single: r2c6=14
=> r3c6+r4c5=[15,16]
=> r4c4=45
Naked Single: r5c5=46
=> r5c4=17
=> r5c3=32
=> r6c34=[18,31]



(Hint: I found it easier applying this approach by listing all the unused numbers separately and then crossing out each of them as they're being inserted into the grid. Well things to do when you don't have a program to help. )

This puzzle should require both:

Code: Select all

..|..|..|..|..|..|..|53|..
09|08|..|..|..|..|..|..|..
..|06|13|19|..|..|..|50|..
..|..|..|58|..|27|61|49|..
81|..|02|..|..|..|46|..|..
..|03|..|29|22|..|47|..|..
..|..|..|..|..|23|..|44|..
..|..|33|35|..|38|..|..|..
..|..|75|..|..|..|..|..|42

Solution:

Code: Select all

10|11|15|16|17|55|54|53|52
09|08|12|14|18|56|63|64|51
07|06|13|19|57|60|62|50|65
05|01|20|58|59|27|61|49|66
81|04|02|21|28|26|46|48|67
80|03|30|29|22|25|47|45|68
79|31|34|36|24|23|39|44|69
78|32|33|35|37|38|40|70|43
77|76|75|74|73|72|71|41|42

Plenty of bottlenecks (gateways), but I didn't remember using any pair for cracking it. The corridor on c9 is nice though.

[evert]

I don't know how to UN-teach my solver naked singles. For it's often the final, trivial step in an elegant move.

After plainly commenting that part of the code, this puzzle was created:

Code: Select all

00;03;00;00;00;46;00;00;00
00;05;51;49;54;56;00;40;00
06;00;00;00;00;57;42;00;00
00;00;00;00;00;00;00;13;36
00;62;61;60;59;00;00;00;00
67;00;00;00;00;00;33;16;15
00;68;00;27;00;00;00;00;00
75;73;00;00;00;00;81;00;00
00;00;72;00;23;00;00;00;00

I think I like the others better ...

[udosuk]

04|03|50|48|47|46|45|44|39
02|05|51|49|54|56|43|40|38
06|01|52|53|55|57|42|41|37
63|07|08|09|10|58|12|13|36
64|62|61|60|59|11|34|35|14
67|65|69|26|28|29|33|16|15
66|68|70|27|25|80|30|32|17
75|73|77|71|79|24|81|31|18
74|76|72|78|23|22|21|20|19

Still, I don't think pairs are necessary for this one. However, djape's 2 latest daily puzzles (Thurs & Fri) I think needs them. (Probably unnecessary if one applies naked singles, but I didn't. )

I hope you will soon construct a puzzle which needs all the tricks mentioned: naked singles, pairs (subsets), gateway (bottleneck), path shaping (multiple bottleneck ) etc...

[evert]

Multiple bottleneck will not be easy.
In my first version what I did was:
Compute the shortest-path distance from each cell (i1,j1) to each other cell (i2,j2).

For bottleneck, what I’ve done is:
Compute the shortest-path distance from each cell (i1,j1) to each other cell (i2,j2) in the scenario that a third cell (i3,j3) is occupied - … for each (i3,j3)!!!

So the amount of work increased with factor 81 and so did the time needed to solve or create puzzles.

What will happen if I compute all these shortest-path distances for multiple bottleneck ((i3,j3), (i4,j4),…etc)?

Unless there is something smarter…

[evert]

I may know a new technique, which is quite obvious for a human player, but I didn’t program it yet. I’d like to call it fuzzy distance.

Do you agree with the logic?

Type I based on straight distance:

For any empty cell (i,j) and for any unplaced number n:
Define d as the smallest straight distance from (i,j) to any of the cells where n can be placed.
Then for any n2:
(n2 > n - d and n2 < n + d) -> then n2 can be excluded from (i,j)

Type I based on shortest-path-distance:

For any empty cell (i,j) and for any unplaced number n:
Define d as the smallest shortest-path-distance from (i,j) to any of the cells where n can be placed.
Then for any n2:
(n2 > n - d and n2 < n + d and n and n2 are in the same fragment) -> then n2 can be excluded from (i,j)

Type II based on straight distance:

For any pair of empte cells (i,j) and (i2,j2)
Define n_min and n_max as the lowest resp. the highest number that can be placed in (i,j).
Define d as the straight distance between (i,j) and (i2,j2)
Then for any n:
if n < n_min + d and n > n_max - d then n can be excluded from (i2,j2)

Type II based on shortest-path-distance:

For any pair of empte cells (i,j) and (i2,j2)
Define n_min and n_max as the lowest resp. the highest number that can be placed in (i,j).
Define d as the shortest-path-distance between (i,j) and (i2,j2)
If n_min and n_max are in the same fragment, then for any n in that same fragment:
if n < n_min + d and n > n_max - d then n can be excluded from (i2,j2)

[evert]

After programming type I & II Straight distance:

Code: Select all

..;..;13;..;..;..;..;..;01
15;..;..;08;81;..;78;03;..
20;..;48;..;..;..;04;..;75
..;21;..;..;..;45;44;73;74
23;..;..;..;46;..;..;..;..
..;..;..;..;68;..;39;37;..
..;..;..;..;..;30;..;..;..
..;53;58;27;..;..;31;33;..
..;..;..;..;..;62;..;..;..

[udosuk]

16|14|13|12|07|80|79|02|01
15|17|11|08|81|06|78|03|76
20|18|48|10|09|05|04|77|75
19|21|49|47|70|45|44|73|74
23|22|50|69|46|71|72|43|42
24|25|51|67|68|29|39|37|41
54|52|26|66|28|30|38|40|36
55|53|58|27|65|64|31|33|35
56|57|59|60|61|62|63|32|34

I had a great time solving this puzzle, thought about writing a walkthrough but not enough energy.

Could you give 2 examples how you applied each of the "types I & II straight distance" in this puzzle? I think some physical demonstration can be very helpful to explain your "fuzzy logic" instead of the cryptic formulas you wrote above.

[evert]

Could you give 2 examples how you applied each of the "types I & II straight distance" in this puzzle? I think some physical demonstration can be very helpful to explain your "fuzzy logic" instead of the cryptic formulas you wrote above.

An easy example of type I would be:
If number 5 can only go in R1C1, R1C2 or R1C3, then 6 could never go in R9C9.

I have a real-life example of type II:

Code: Select all

..;..;..;..;05;..;02;..;..;
09;08;07;..;..;74;73;69;..;
..;15;16;..;..;..;..;..;..;
..;13;..;..;..;..;..;66;64;
..;12;43;..;..;..;..;..;..;
..;..;27;40;..;..;61;62;..;
..;..;..;38;..;..;..;56;..;
33;..;..;..;23;..;..;52;..;
..;..;..;..;..;..;50;..;53;

After non-fuzzy moves:

Code: Select all

81;80;79;06;05;03;02;01;70
09;08;07;78;04;74;73;69;71
10;15;16;..;..;..;..;72;..
11;13;14;..;..;..;..;66;64
..;12;43;..;..;..;..;..;..
..;..;27;40;..;..;61;62;..
..;..;..;38;..;..;..;56;..
33;..;..;..;23;..;..;52;..
..;..;..;..;..;..;50;..;53

Now in R9C1 only 30, 31, 32, 34, 35 go.
In R5C1 only 29, 30 go.

Whether 29 or 30 is filled in R5C1, in both cases 30, 31 and 32
cannot go anymore in R9C1 since the distance to R5C1 is too large.

The formula says:

Code: Select all

d = 4
n_min = 29
n_max = 30
n < 29 + 4 and n > 30 - 4 --> n not allowed in R1C9

And only 34 and 35 remain as options for R9C1.

Same puzzle further:

Code: Select all

81;80;79;06;05;03;02;01;70
09;08;07;78;04;74;73;69;71
10;15;16;17;77;75;68;72;65
11;13;14;42;18;76;67;66;64
29;12;43;44;41;19;..;..;..
30;28;27;40;45;..;61;62;..
31;26;39;38;..;..;..;56;..
33;32;25;37;23;47;..;52;..
34;35;36;24;48;49;50;..;53

I know the program needs a combination of both types from here.

Due to lack of time I didn't reconstruct this in detail.

But I think I noticed with pencil and paper that 57 and 59 were excluded somewhere because the remaining options
for 58 were all too far away - which is type I.

I think these types of fuzzy distance are quite powerful.
Some earlier bottleneck-puzzles are also tackeled with this new technique instead.

[evert]

Still I did find one that requires BOTH fuzzy distance and bottleneck:

Code: Select all

00;00;59;00;00;46;00;00;00
00;00;00;00;00;00;53;00;00
00;00;41;40;00;44;00;52;00
00;00;00;33;00;00;11;14;00
30;00;00;00;08;10;00;13;00
00;00;28;00;01;00;00;00;00
00;00;00;00;05;00;00;00;00
00;71;00;00;00;00;19;20;00
00;69;74;00;00;25;00;00;21


[udosuk]

Thanks for the demonstration. Clear as crystal. Great work!

Code: Select all

81;80;79;06;05;03;02;01;70
09;08;07;78;04;74;73;69;71
10;15;16;..;..;..;..;72;..
11;13;14;..;..;..;..;66;64
..;12;43;..;..;..;..;..;..
..;..;27;40;..;..;61;62;..
..;..;..;38;..;..;..;56;..
33;..;..;..;23;..;..;52;..
..;..;..;..;..;..;50;..;53

Now in R9C1 only 30, 31, 32, 34, 35 go.
In R5C1 only 29, 30 go.

Whether 29 or 30 is filled in R5C1, in both cases 30, 31 and 32
cannot go anymore in R9C1 since the distance to R5C1 is too large.

The formula says:

Code: Select all

d = 4
n_min = 29
n_max = 30
n < 29 + 4 and n > 30 - 4 --> n not allowed in R1C9

And only 34 and 35 remain as options for R9C1.

I believe the last line of the formula should say R9C1. Also, if I were to explain this move, I'll say something like:

Code: Select all

r5c1 must be 29 or 30.
As a result, the numbers [27..32] are locked in cells within 3 cells away from r5c1 (27 being 30-3 and 32 being 29+3).
Hence r9c1, being 4 cells away from r5c1, can't have [27..32].

Will work at your latest puzzles later!

[evert]

Here is an explanation of a Hidato solving technique that some people might find obvious and they use it without even thinking of it as a special technique. But, for those who still struggle with the more difficult puzzles, here is a quick guide of the technique that I call “cornering“.
It can be used when a cell has only one “neighbor” that is an empty cell. In such a case, that cell (with only one empty neighbor), must contain a number that is consecutive to (at least) one of the already filled in neighbors.

Following situation:

Code: Select all

..;..;..;..;..;..;..;..;..
02;03;04;..;..;..;..;..;..
01;..;..;..;..;..;..;..;..
..;..;..;..;..;..;..;..;..
..;..;..;..;..;..;..;..;..
..;..;..;..;..;..;..;..;..
..;..;..;..;..;..;..;..;..
..;..;..;..;..;..;..;..;..
..;..;..;..;..;..;..;..;..

Only 81 goes into R1C1.

Following situation:

Code: Select all

..;..;..;..;..;..;..;..;..
..;..;..;..;..;..;..;..;..
..;..;..;..;..;..;..;..;..
..;..;01;80;07;..;..;..;..
..;..;02;..;06;..;..;..;..
..;..;03;04;05;..;..;..;..
..;..;..;..;..;..;..;..;..
..;..;..;..;..;..;..;..;..
..;..;..;..;..;..;..;..;..

Only 81 goes into R5C4.

Following situation:

Code: Select all

81;80;79;06;05;03;02;01;70
09;08;07;78;04;74;73;69;71
10;15;16;..;..;..;..;72;..
11;13;14;..;..;..;..;66;64
..;12;43;..;..;..;..;..;..
..;..;27;40;..;..;61;62;..
..;..;..;38;..;..;..;56;..
33;..;..;..;23;..;..;52;..
..;..;..;..;..;..;50;..;53

Only 65 goes into R3C9.

Although djape's explanation doesn't cover any of these situations, I'd also consider these as cornering.
About the last one: at first sight I thought it was a bug in my solver.