The New Sudoku Players' Forum

by **evert** » Tue Jan 27, 2009 9:16 am

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

by **udosuk** » Tue Jan 27, 2009 5:38 pm

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

evert wrote:
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!

by **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.

by **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.

by **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.

by **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. ;-)

by **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

by **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? :?:

by **evert** » Mon Feb 02, 2009 3:33 pm

That was a mistake, I corrected it.

by **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

by **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.

I like to take these puzzles in train, and very often there seems to be a shortcut in comparison to the solver-program.

by **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;..;..;..;..;..;..;..;..

by **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;..;..;..;..

by **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

by **dyitto** » Sat May 22, 2010 10:00 am

My hidato solver and generator is available for download here.
(Regards, evert)

The New Sudoku Players' Forum

Hidato

Re: Hidato