## Hidato

For fans of Killer Sudoku, Samurai Sudoku and other variants
udosuk wrote:Also, r4c7+r3c8 must be reserved for [082,083,084]

I missed this idea in my solver. Not anymore. Following puzzle should require a similar step:
Code: Select all
`03;..;..;..;..;..;..;27;....;02;..;..;..;..;..;..;26..;61;..;06;08;..;11;..;2260;..;..;..;..;14;13;..;81..;59;..;36;..;..;..;..;....;56;..;..;16;..;..;..;..66;..;55;..;..;18;..;45;....;..;53;50;49;..;47;..;....;..;..;..;..;73;..;..;..`
evert

Posts: 186
Joined: 26 August 2005

Thanks for a very nice puzzle!

You're right, that particular technique is very useful for this puzzle:

Highlight below to read what I wrote:03 04 __ __ __ __ __ 27 25
__ 02 05 __ __ __ __ 24 26
__ 61 __ 06 08 12 11 23 22
60 __ __ __ __ 14 13 21 81
__ 59 __ 36 __ __ __ __ __
__ 56 __ __ 16 17 19 __ __
66 __ 55 52 51 18 __ 45 __
67 54 53 50 49 48 47 __ __
68 69 70 71 72 73 74 __ __

r5c67 must be reserved for [37..44]
=> [15,20] must be @ r5c58

r2c4+r3c3 must be reserved for [28..35]
=> 7 must be @ r2c5

Afterwards, this same technique (I like to call it "bottleneck" ) can be applied a few more times near the end of the solution path.

This should be the unique solution:

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

udosuk

Posts: 2698
Joined: 17 July 2005

Evert, Matt

A couple of points:

These are succeptable to uniqueness, in short link choice and then in empty shape i.e. a four box open on one side is not possible. My temptation to shortcut significantly reduced the difficulty of DJ's 11*11.

I notice other places use odd shapes with stickyout bits - this simplyfies solution. We need to look at octagons for really difficult ones.
HATMAN

Posts: 219
Joined: 25 February 2006

HATMAN wrote:These are succeptable to uniqueness, in short link choice and then in empty shape i.e. a four box open on one side is not possible. My temptation to shortcut significantly reduced the difficulty of DJ's 11*11.

I do realise it, but always try my best to not use uniqueness. I suppose a puzzle can get very difficult that forces one to make use of this info (that the solution is unique).

Another interesting issue is the usage of 180 rotational symmetry (or perhaps diagonal reflection symmetry). It is possible, but the solution space must be very narrow.

HATMAN wrote:I notice other places use odd shapes with stickyout bits - this simplyfies solution. We need to look at octagons for really difficult ones.

Speaking of which, I'm still working on a Knight Link 2 puzzle from this blog:

Rule (not 100% sure though due to my deficient level of Japanese):

Draw a knight's circuit through all the blue dots. Draw another knight's circuit through all the intersections without blue dots. These 2 circuits must not cross each other.

(Edited: This is obviously wrong, because you can't draw any knight's circuit through the intersections without blue dots. But you can definitely draw one through the blue dots which does not cross itself and I think the answer is unique.)
udosuk

Posts: 2698
Joined: 17 July 2005

As of today, January 15, 2009, I'm posting Hidoku puzzles on my site on a daily basis.
djape

Posts: 34
Joined: 27 September 2005

I put my solver on Djapes 9x9 20090115.
Code: Select all
`58;00;00;00;00;00;09;11;00;00;57;56;55;00;00;00;00;12;00;00;00;00;00;51;00;00;00;45;00;47;00;01;04;17;00;00;63;00;38;00;00;35;00;00;20;00;64;00;40;00;00;00;32;00;00;00;00;76;74;00;31;00;00;00;66;00;00;00;72;00;00;00;81;00;78;00;00;00;26;00;28;`

For two moves it needed my manual help:
...
Code: Select all
`58;59;54;53;07;08;09;11;1360;57;56;55;52;06;10;14;1261;46;48;49;50;51;05;00;1545;62;47;02;01;04;17;00;0063;44;38;37;03;35;00;00;2043;64;39;40;36;00;00;32;0065;42;41;76;74;00;31;00;0000;66;00;00;00;72;00;00;0081;00;78;00;00;00;26;00;28`

Now in cell (8,1) only 80 and 67 are allowed due to cornering.
But the consequence of putting 67 there is that 68 will go into (9,2) which would isolate
81 from 79. Therefore 80 goes into (8,1).
...
Code: Select all
`58;59;54;53;07;08;09;11;1360;57;56;55;52;06;10;14;1261;46;48;49;50;51;05;00;1545;62;47;02;01;04;17;00;0063;44;38;37;03;35;00;00;2043;64;39;40;36;34;00;32;0065;42;41;76;74;73;31;00;0080;66;67;77;75;72;71;00;0081;79;78;68;69;70;26;00;28`

Now 27 can be placed in either (9,8) or (8,8).

But after placing 27 in (8,8), cornering in (9,8) would lead to
a contradiction. So 27 must go into (9,8).

I need some more work on it.
evert

Posts: 186
Joined: 26 August 2005

Here are some suggestions on concepts to "teach" your solver some new logic to crack these steps:

evert wrote:
Code: Select all
`58|59|54|53|07|08|09|11|1360|57|56|55|52|06|10|14|1261|46|48|49|50|51|05|..|1545|62|47|02|01|04|17|..|..63|44|38|37|03|35|..|..|2043|64|39|40|36|..|..|32|..65|42|41|76|74|..|31|..|....|66|..|..|..|72|..|..|..81|..|78|..|..|..|26|..|28`

Now in cell (8,1) only 80 and 67 are allowed due to cornering.
But the consequence of putting 67 there is that 68 will go into (9,2) which would isolate
81 from 79. Therefore 80 goes into (8,1).

For this, consider (9,2). It must be 79 or 80 (I called this move "bottleneck" above but on 2nd thought perhaps "gateway" is a better name. )

Now (8,1) can't be 67 since there is no path to get to the next highest number on the board, 72 (this might be a bit tricky to implement in your solver).

Therefore there is only 1 possible cell on the board for 67: (8,3).

And then similarly only 1 possible cell on the board for 79: (9,2).

evert wrote:
Code: Select all
`58|59|54|53|07|08|09|11|1360|57|56|55|52|06|10|14|1261|46|48|49|50|51|05|..|1545|62|47|02|01|04|17|..|..63|44|38|37|03|35|..|..|2043|64|39|40|36|34|..|32|..65|42|41|76|74|73|31|..|..80|66|67|77|75|72|71|..|..81|79|78|68|69|70|26|..|28`

Now 27 can be placed in either (9,8) or (8,8).

But after placing 27 in (8,8), cornering in (9,8) would lead to
a contradiction. So 27 must go into (9,8).

This is easier. There are only 2 possible cells on board for 25: (8,8) & (9,8). Also they are the only 2 possible cells on board for 27. As a result, (8,8) & (9,8) must be {25,27}. (This is analogical to a "hidden pair" in sudoku solving. )

As a result, there is only 1 possible cell on board for 29: (8,9).

And then there is only 1 possible cell on board for 30: (7,8).

Now "gateway" will force (7,9)+(8,8) to be {21..25}, leaving (9,8) as the only possible cell for 27.

udosuk

Posts: 2698
Joined: 17 July 2005

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;0368;..;..;..;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;..;..;..;2809;..;18;..;..;..;..;68;....;11;..;..;..;..;25;69;....;..;..;78;..;76;..;..;..76;..;..;..;..;..;05;..;....;..;78;..;..;04;..;..;....;49;51;16;..;..;..;..;01..;..;52;44;..;19;..;..;10..;..;..;42;..;..;..;12;2454;..;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`
evert

Posts: 186
Joined: 26 August 2005

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 .. .. 6439 40 35 43 13 .. .. 0821 41 42 34 44 .. .. 0720 22 33 .. .. .. 06 0123 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 .. .. 6439 40 35 43 13 .. .. 0821 41 42 34 44 _* _* 0720 22 33 _# _# _# 06 0123 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 .. .. 6439 40 35 43 13 .. .. 0821 41 42 34 44 _* _* 0720 22 33 45 _# _# 06 0123 19 _@ _@ _@ 05 _@ 0224 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 .. .. 6439 40 35 43 13 .. .. 0821 41 42 34 44 _A _B 0720 22 33 45 _A _B 06 0123 19 _@ _@ _@ 05 _B 0224 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 .. .. 6439 40 35 43 13 .. .. 0821 41 42 34 44 _A _B 0720 22 33 45 _A _B 06 0123 19 32 _A 46 05 _B 0224 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 6439 40 35 43 13 14 63 0821 41 42 34 44 15 62 0720 22 33 45 16 61 06 0123 19 32 17 46 05 60 0224 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 6439 40 35 43 13 14 63 0821 41 42 34 44 15 62 0720 22 33 45 16 61 06 0123 19 32 17 46 05 60 0224 25 18 31 47 59 04 0327 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 6439 40 35 43 13 14 63 0821 41 42 34 44 15 62 0720 22 33 45 16 61 06 0123 19 32 17 46 05 60 0224 25 18 31 47 59 04 0327 26 30 48 58 57 56 5428 29 49 50 51 52 53 55`

udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote:After "easy" moves:
Code: Select all
`38 37 36 12 11 .. .. 6439 40 35 43 13 .. .. 0821 41 42 34 44 .. .. 0720 22 33 .. .. .. 06 0123 19 .. .. .. 05 .. ..24 25 .. .. .. .. .. ..27 26 30 .. .. .. 56 ..28 29 .. .. .. 52 .. 55`

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

Posts: 186
Joined: 26 August 2005

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.
It did; naked singles are quite dominant and not always very elegant in Hidato.
evert

Posts: 186
Joined: 26 August 2005

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 .. .. 6439 40 35 43 13 .. .. 0821 41 42 34 44 .. .. 0720 22 33 .. .. .. 06 0123 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. )

evert wrote: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|5209|08|12|14|18|56|63|64|5107|06|13|19|57|60|62|50|6505|01|20|58|59|27|61|49|6681|04|02|21|28|26|46|48|6780|03|30|29|22|25|47|45|6879|31|34|36|24|23|39|44|6978|32|33|35|37|38|40|70|4377|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.
udosuk

Posts: 2698
Joined: 17 July 2005

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;0000;05;51;49;54;56;00;40;0006;00;00;00;00;57;42;00;0000;00;00;00;00;00;00;13;3600;62;61;60;59;00;00;00;0067;00;00;00;00;00;33;16;1500;68;00;27;00;00;00;00;0075;73;00;00;00;00;81;00;0000;00;72;00;23;00;00;00;00`
I think I like the others better ...
Last edited by evert on Fri Jan 23, 2009 3:55 am, edited 1 time in total.
evert

Posts: 186
Joined: 26 August 2005

Highlight below to see the solution of the puzzle above, I wrote: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...
udosuk

Posts: 2698
Joined: 17 July 2005

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

Posts: 186
Joined: 26 August 2005

Next