Hidato

For fans of Killer Sudoku, Samurai Sudoku and other variants

Postby evert » Wed Jan 28, 2009 4:39 pm

djape wrote: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.:D
evert
 
Posts: 186
Joined: 26 August 2005

Postby djape » Thu Jan 29, 2009 4:18 am

Evert, the reason why I didn't cover situations like the ones you indicated is because one of the rules of Hidato-Hidoku puzzles is that the numbers 1 and whatever the largest number is are always filled in.

This is clearly stated as rule number 3 on my Daily Hidato page.
djape
 
Posts: 34
Joined: 27 September 2005

Postby udosuk » Thu Jan 29, 2009 9:43 am

djape wrote:Evert, the reason why I didn't cover situations like the ones you indicated is because one of the rules of Hidato-Hidoku puzzles is that the numbers 1 and whatever the largest number is are always filled in.

This is clearly stated as rule number 3 on my Daily Hidato page.

However, from a solver's perspective, the puzzles can be more challenging/enjoyable without this constraint.

I've always been using evert's "advanced cornering" trick ever since I started solving these puzzles. Note they're much easier to see manually if you draw a line linking every consecutive numbers. In that case every cell (except the end numbers) must be linked to 2 of its orthogonal/diagonal neighbours without any branching.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby vidarino » Sun Feb 01, 2009 6:50 am

I agree that the constraint might seem superfluous, but in some cases the highest number isn't obvious, e.g. when the grid contains blacked out cells, or the grid isn't square or rectangular.

Examples:
http://images.amuniversal.com/ups/features/hidato/samples/Hidato_ENG_BW_d_sample.jpg

It's easy enough to find the highest possible number by counting, of course, but, well, it doesn't strike me as fun. ;-)
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby evert » Mon Feb 02, 2009 8:54 am

I thought about another technique - which is probably obvious when solving with pencil and paper
but it wasn't yet in my solver:

Fuzzy obstacle type I
=====================
Code: Select all
....|....|....|....|....|....|....|....|...9
....|....|....|....|....|....|....|....|....
....|....|....|....|..48|..47|..46|..45|44/43
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....

If the possibilities for R3C9 are limited to 44/43, then in R5C9 4 can be excluded

I found two puzzles requiring this technique, but only if fuzzy distance is not used:
Code: Select all
10|..|..|..|..|..|79|02|..
..|08|..|..|..|..|..|..|01
..|..|..|13|..|..|..|..|..
..|..|17|..|33|..|..|37|..
22|..|..|15|31|..|..|..|..
..|21|..|..|70|..|..|40|..
..|..|67|54|..|48|..|41|..
..|..|59|56|..|..|..|44|43
..|60|..|..|..|52|..|..|..

..|24|..|..|56|..|..|61|..
26|..|32|..|..|..|..|..|..
..|..|28|..|36|..|54|..|..
..|..|..|..|67|68|..|52|..
..|75|..|..|..|..|..|41|..
78|..|74|..|..|..|45|..|..
..|01|18|..|..|..|..|..|48
..|80|..|05|..|08|09|12|..
..|..|..|06|..|..|..|..|..

(fuzzy distance solves both of these without fuzzy obstacle)

Fuzzy obstacle type II
======================
Code: Select all
....|....|....|....|....|....|....|....|....
..70|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|..66|..23|....|....|....|....|....|....
....|..68|..24|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....

The fuzzy obstacle is 67, going in R45C1.
In R7C1 75 can be excluded.

I found - even with fuzzy distance involved - the following puzzles:
Code: Select all
45|..|41|..|..|..|14|..|..
44|..|..|35|36|37|12|..|..
..|..|..|69|..|..|..|..|..
..|67|..|..|..|..|..|..|18
..|..|..|..|..|32|..|..|77
..|50|..|..|..|..|..|..|76
..|51|60|..|..|..|..|..|21
53|..|..|02|..|..|25|28|..
55|56|..|03|04|..|..|..|..

47|..|..|58|..|..|74|73|..
49|..|..|..|56|..|..|..|..
..|..|..|..|..|68|..|..|..
44|..|51|..|63|66|..|06|..
43|..|..|53|..|65|..|..|..
..|40|24|..|..|..|..|03|81
39|..|..|22|..|11|13|02|..
..|34|..|28|..|..|..|..|16
..|..|32|..|..|19|..|..|..


There should be several ways to combine fuzzy obstacle with fuzzy distance, but I'm afraid
the solver code is turning into spaghetti here.

vidarino wrote:I agree that the constraint might seem superfluous, but in some cases the highest number isn't obvious, e.g. when the grid contains blacked out cells, or the grid isn't square or rectangular.
Then it's nice to have a feature for displaying all yet unfilled numbers, for example:
Code: Select all
00;24;00;00;56;00;00;61;00
26;00;32;00;00;00;00;00;00
00;00;28;00;36;00;54;00;00
00;00;00;00;67;68;00;52;00
00;75;00;00;00;00;00;41;00
78;00;74;00;00;00;45;00;00
00;01;18;00;00;00;00;00;48
00;80;00;05;00;08;09;12;00
00;00;00;06;00;00;00;00;00

. 2 3 4 . . 7 . . 10 11 . 13 14 15 16 17 . 19 20 21 22 23 . 25 . 27 . 29 30 31 . 33 34 35 . 37 38 39 40 . 42 43 44 . 46 47 . 49 50 51 . 53 . 55 . 57 58 59 60 . 62 63 64 65 66 . . 69 70 71 72 73 . . 76 77 . 79 . 81
Last edited by evert on Mon Feb 02, 2009 11:34 am, edited 2 times in total.
evert
 
Posts: 186
Joined: 26 August 2005

Postby udosuk » Mon Feb 02, 2009 11:22 am

evert wrote:I thought about another technique - which is probably obvious when solving with pencil and paper
but it wasn't yet in my solver:

Fuzzy obstacle type I
=====================
Code: Select all
....|....|....|....|....|....|....|....|...9
....|....|....|....|....|....|....|....|....
....|....|....|....|..48|..47|..46|..45|46/47
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....
....|....|....|....|....|....|....|....|....

If the possibilities for R3C9 are limited to 46/47, then in R5C9 4 can be excluded

It doesn't make sense?:?:

How could R3C9 be 46/47 when you have [47,46] @ R3C67?:?:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby evert » Mon Feb 02, 2009 3:33 pm

That was a mistake, I corrected it.
evert
 
Posts: 186
Joined: 26 August 2005

Postby udosuk » Wed Feb 04, 2009 3:25 am

evert wrote:Still I did find one that requires BOTH fuzzy distance and bottleneck:
Code: Select all
..|..|59|..|..|46|..|..|..
..|..|..|..|..|..|53|..|..
..|..|41|40|..|44|..|52|..
..|..|..|33|..|..|11|14|..
30|..|..|..|08|10|..|13|..
..|..|28|..|01|..|..|..|..
..|..|..|..|05|..|..|..|..
..|71|..|..|..|..|19|20|..
..|69|74|..|..|25|..|..|21

Definitely a very hard puzzle (especially when one doesn't have a program to help track of the candidates in each cell). I don't recall using fuzzy distance specifically, but might have used it unknowingly.

Here is one of the early critical moves in my path:

Code: Select all
..|..|59|..|..|46|..|..|..
..|..|..|..|..|..|53|..|..
..|..|41|40|..|44|..|52|..
..|..|..|33|..|..|11|14|..
30|..|..|..|08|10|..|13|..
..|..|28|..|01|..|..|..|..
..|..|..|27|05|..|..|..|..
..|71|..|..|26|..|19|20|..
..|69|74|..|..|25|..|..|21

[24..22] must be @ either r8c6+r9c78 or r9c78+r8c9
But if r8c6+r9c78=[24..22], then there is no value possible for r8c9
(in particular, [75..81] become out of reach - fuzzy obstacle?)
Therefore [24..22] must be @ r9c78+r8c9.

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

Postby evert » Wed Feb 04, 2009 8:27 am

I totally agree with your move!
It's not exactly the intended move, but it's nice though.:D

I like to take these puzzles in train, and very often there seems to be a shortcut in comparison to the solver-program.
evert
 
Posts: 186
Joined: 26 August 2005

Postby evert » Thu Feb 05, 2009 7:47 am

This one should be nice, since it requires many tricks:)
Code: Select all
..;..;..;..;09;..;..;..;..
..;..;45;..;..;14;80;..;..
..;..;..;11;12;..;..;..;76
04;02;..;..;..;60;..;18;..
..;03;..;..;..;..;..;..;..
..;..;..;..;..;..;..;20;..
52;..;..;35;27;..;25;72;..
..;..;..;..;..;..;..;23;..
55;..;..;..;..;..;..;..;..
evert
 
Posts: 186
Joined: 26 August 2005

Postby evert » Thu Feb 19, 2009 7:27 am

I think "fuzzy cornering" should be possible also.

A very theoretical workout would be:

Code: Select all
......;......;......;......;......;......;......;......;......
.41/42;.42/43;......;......;......;......;......;......;......
.40/41;......;......;......;......;......;......;......;......
.39/40;......;......;......;......;......;......;......;......
......;......;......;......;......;......;......;......;......
......;......;......;......;......;......;......;......;......
......;......;..01..;..81..;......;......;......;......;......
......;......;......;......;......;......;......;......;......
......;......;......;......;......;......;......;......;......

==> In R1C1 only 43 or 44 are allowed


The following puzzles are specifically only solved with this "fuzzy cornering":
Code: Select all
..;..;..;..;01;..;04;..;09
28;..;24;..;..;03;06;..;..
31;35;33;..;81;13;..;15;..
..;..;..;..;..;..;..;..;70
40;..;38;..;..;..;..;..;..
..;..;..;76;..;..;..;..;68
..;..;..;..;75;..;..;..;67
..;..;43;44;..;..;59;60;..
53;..;..;..;..;58;..;..;..

..;28;..;17;..;..;..;..;..
..;..;..;..;18;67;..;..;70
..;34;..;..;22;..;..;..;74
..;35;13;..;..;..;64;..;..
..;36;..;..;..;..;..;76;..
..;39;..;57;..;..;..;04;..
..;55;..;..;10;..;05;79;..
..;54;52;..;..;08;..;..;80
..;..;..;..;49;..;..;01;..

..;..;..;40;..;..;..;..;46
..;62;..;..;..;42;43;27;..
..;..;58;..;..;52;..;..;..
..;66;..;..;53;..;..;..;25
67;..;..;..;..;33;..;30;..
73;..;01;..;..;..;32;21;..
74;..;..;..;..;..;..;19;..
..;..;..;08;..;81;..;15;..
..;04;..;..;07;..;11;..;17

..;..;53;..;56;..;..;..;..
..;49;..;..;..;..;..;..;60
47;..;..;69;..;35;..;33;..
..;41;..;70;..;..;..;..;..
44;..;..;..;..;65;..;..;28
..;..;..;..;..;66;..;..;80
..;07;..;..;03;..;..;26;..
..;..;12;16;02;..;19;..;23
..;13;..;..;..;20;..;..;..

..;..;..;..;..;..;..;25;..
72;..;74;78;77;..;..;22;27
..;67;..;..;..;19;21;..;..
..;52;51;..;..;..;..;..;29
54;..;50;..;..;15;14;33;..
..;..;..;..;..;..;..;..;32
61;..;..;04;..;..;..;36;..
57;..;..;47;43;42;..;37;..
58;..;..;..;45;..;..;..;38

81;03;02;47;..;..;..;..;40
..;05;..;..;..;44;42;37;..
..;79;..;49;52;..;..;..;..
..;77;08;..;..;51;..;32;..
76;..;..;..;15;..;..;31;..
..;73;..;..;13;..;..;..;..
72;..;..;..;17;19;..;..;28
..;65;..;..;..;20;..;23;..
..;67;64;63;62;..;..;..;..
evert
 
Posts: 186
Joined: 26 August 2005

Postby evert » Fri Feb 27, 2009 6:25 pm

Here's an even more challenging puzzle.

Code: Select all
..|..|..|..|77|..|28|..|..
..|13|..|..|..|..|..|21|..
..|..|..|15|16|..|31|..|..
..|06|..|..|73|..|19|..|..
..|58|..|..|..|..|36|..|33
60|..|62|..|71|..|..|..|..
..|..|..|..|64|..|..|..|43
..|54|..|..|..|68|..|..|..
..|..|..|..|..|..|..|..|..


My solver can't solve this one directly and needs manual help at several points. But a with a separate algorithm I verified that
it has one unique solution.

Solving it by hand was great fun.

I've written a walk-through, concentrating on the points where my solver is stuck.

(For this I had no total computer help so I hope I didn't make any mistake.)

/
/
/
/
/
/
/
/
/
/
/
/

Code: Select all
After some regular moves:

..|81|80|79|77|27|28|25|24
..|13|14|76|78|29|26|21|23
..|..|75|15|16|30|31|20|22
..|06|..|74|73|17|19|32|34
..|58|..|..|..|18|36|35|33
60|..|62|..|71|..|..|..|..
..|..|..|..|64|..|..|..|43
..|54|..|..|..|68|..|..|..
..|..|..|..|..|..|..|..|..

Due to cornering, R1C1 contains 1 or 12. Let's assume 1 here.
Then segment 7-12 won't fit over R345C1 so 2-5 will have to go over R345C1.
Then 7-12 must use R5C3-R6C4
Then 59 must go into R6C2 and this would leave 58 isolated from 54.

Therefore 1 cannot go into R1C1

12|81|80|79|77|27|28|25|24
11|13|14|76|78|29|26|21|23
..|..|75|15|16|30|31|20|22
..|06|..|74|73|17|19|32|34
..|58|..|..|..|18|36|35|33
60|..|62|..|71|..|..|..|..
..|..|..|..|64|..|..|..|43
..|54|..|..|..|68|..|..|..
..|..|..|..|..|..|..|..|..

Mind that segment 1-5 cannot go through R6C2R5C1.
So with 5 in C1 or C2, 7..12 wouldn't fit anywhere.
With 5 in R4C3 7..11 might fit starting from R5C1, but this will lead to a uniqueness pattern (9 or 10 in R3C12)

So 5 goes into R5C3

12|81|80|79|77|27|28|25|24
11|13|14|76|78|29|26|21|23
..|..|75|15|16|30|31|20|22
..|06|..|74|73|17|19|32|34
59|58|05|..|..|18|36|35|33
60|57|62|..|71|..|..|..|..
..|61|..|..|64|..|..|..|43
..|54|..|..|..|68|..|..|..
..|..|..|..|..|..|..|..|..

With 10 in R3C2 7..9 wouldn't fit
so 10 goes into R3C1

12|81|80|79|77|27|28|25|24
11|13|14|76|78|29|26|21|23
10|08|75|15|16|30|31|20|22
09|06|07|74|73|17|19|32|34
59|58|05|..|..|18|36|35|33
60|57|62|..|71|..|..|..|..
..|61|..|..|64|..|..|..|43
..|54|..|..|..|68|..|..|..
..|..|..|..|..|..|..|..|..

4 and 72 are locked in R56C4 and R5C45
3 could go in one of these cells or in R7C3
but after 3 in R7C3, 4 -> R6C4
-> 72 in R5C4 (cornering)
-> none in r5C5 (cornering)

So 3 cannot go in R7C3
So 3/4/72 occupy R5C4/R5C5/R6C4 (triple **)
(and 63 -> R7C4)

12|81|80|79|77|27|28|25|24
11|13|14|76|78|29|26|21|23
10|08|75|15|16|30|31|20|22
09|06|07|74|73|17|19|32|34
59|58|05|**|**|18|36|35|33
60|57|62|**|71|..|..|..|..
..|61|..|63|64|..|..|..|43
..|54|..|..|..|68|..|..|..
..|..|..|..|..|..|..|..|..

Let's assume 70 in R7C6
-> 44..53 needs R9C6 as pass-through
and 65..67 can't fit anywhere without isolating 43 from 54

So 70 goes into R6C6 -> 2 goes into R7C3
For the same reason 69 cannot go into R7C6 -> 69 goes into R7C7

12|81|80|79|77|27|28|25|24
11|13|14|76|78|29|26|21|23
10|08|75|15|16|30|31|20|22
09|06|07|74|73|17|19|32|34
59|58|05|04|72|18|36|35|33
60|57|62|03|71|70|..|..|..
56|61|02|63|64|..|69|..|43
55|54|..|..|..|68|..|..|..
53|52|..|..|..|..|..|..|..

Assuming 1 in R8C4, 50 and 51 will form a uniqueness pattern
in R89C3
So 1 goes into R8C3

12|81|80|79|77|27|28|25|24
11|13|14|76|78|29|26|21|23
10|08|75|15|16|30|31|20|22
09|06|07|74|73|17|19|32|34
59|58|05|04|72|18|36|35|33
60|57|62|03|71|70|..|..|..
56|61|02|63|64|..|69|..|43
55|54|01|..|..|68|..|..|..
53|52|51|..|..|..|..|..|..

37..42 cannot use R7C6 since then 65..67 would isolate 43 from 51

-> 44..47 cannot occupy R7C8 otherwise 37..42 would be locked in too few cells
So 37..42 must first occupy all cells R6C789 and then R7C8

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

The remaining moves are easy:

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

Re: Hidato

Postby dyitto » Sat May 22, 2010 10:00 am

My hidato solver and generator is available for download here.
(Regards, evert)
Last edited by dyitto on Sat Aug 11, 2012 11:20 pm, edited 1 time in total.
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Hidato

Postby Para » Thu Jun 24, 2010 5:11 pm

Here are my handmade hidato puzzles again.

The first one is a really hard one I made. It's harder than any computermade hidato I have come across so far. Tough nut to crack, but you can still logically get through it. If you really want one that is even harder, you can remove the 64 as it is not needed for uniqueness.

Image

The second one was an attempt to make a minimal hidato for a 9 by 9 grid. I managed to make one with only 10 clues. I have no way to verify this is minimal, but I have never seen one that comes even close to this amount.

Image

Enjoy

Bram
Para
 
Posts: 46
Joined: 20 February 2007

Re: Hidato

Postby TANARENEALEBER » Sat Jul 30, 2011 8:33 am

Para wrote:Here are my handmade hidato puzzles again.

The first one is a really hard one I made. It's harder than any computermade hidato I have come across so far. Tough nut to crack, but you can still logically get through it. If you really want one that is even harder, you can remove the 64 as it is not needed for uniqueness.

Image

The second one was an attempt to make a minimal hidato for a 9 by 9 grid. I managed to make one with only 10 clues. I have no way to verify this is minimal, but I have never seen one that comes even close to this amount.

Image

Enjoy

Bram




I NEED HELP I HAVE BEEN TRYING TO FIND GET THE PUZZLE DONE FOR ABOUT TWO YEARS OFF AN ON PLEASE HELP ME IM ON FACKBOOK AT TANA LEBER HOPE U CAN HELP ME CAUSE IM GOING CRAZY I CAN GET ALL OTHERS BUT THIS ONE SO PLEASE HELP ME AN THANKS :]
TANARENEALEBER
 
Posts: 1
Joined: 30 July 2011

PreviousNext

Return to Sudoku variants