Hidato

For fans of Killer Sudoku, Samurai Sudoku and other variants

Postby evert » Thu Dec 11, 2008 1:12 pm

I tried some programming on this.

The source code so far can be found here.

My solver could solve djape's 9x9 sample puzzle on his own site.

Here's another puzzle:
Code: Select all
00;22;20;00;00;00;00;80;00
00;00;00;00;00;00;73;00;00
00;00;00;69;00;00;00;00;77
35;00;66;00;64;05;00;00;00
00;00;27;00;00;00;00;00;00
00;39;00;03;00;00;00;00;58
00;40;00;02;30;00;00;00;12
00;43;00;00;00;00;00;00;00
00;00;00;00;47;00;10;00;52
Would anybody like to try if the puzzle is OK?
:)
evert
 
Posts: 187
Joined: 26 August 2005

Postby udosuk » Sat Dec 13, 2008 1:11 am

evert wrote:Here's another puzzle:
Code: Select all
.. 22 20 .. .. .. .. 80 ..
.. .. .. .. .. .. 73 .. ..
.. .. .. 69 .. .. .. .. 77
35 .. 66 .. 64 05 .. .. ..
.. .. 27 .. .. .. .. .. ..
.. 39 .. 03 .. .. .. .. 58
.. 40 .. 02 30 .. .. .. 12
.. 43 .. .. .. .. .. .. ..
.. .. .. .. 47 .. 10 .. 52
Would anybody like to try if the puzzle is OK?
:)

Yep, that's a very nice Hidato/Hidoku puzzle. I'm quite certain it has a unique solution as the following:

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

I thought the 11x11 puzzle from djape (here) was quite challenging, and yours doesn't fade at all in comparison, so congrats.:)

I wish I had the time to write a walkthrough for my logical steps, but unfortunately no. Good luck about your solver!

(PS: I remember a couple years back people have posted similar puzzles, but based on knights' move instead of kings'. Perhaps you would like to incorporate your solver for other chess pieces too.:) )
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby evert » Sat Dec 13, 2008 5:43 am

That's indeed the solution that my solver produces.
evert
 
Posts: 187
Joined: 26 August 2005

Postby evert » Sat Dec 13, 2008 6:27 am

Djape's 11x11:
Code: Select all
...   ...   ...   046   ...   ...   ...   ...   ...   ...   093
042   041   ...   048   052   ...   ...   ...   ...   095   ...
...   ...   039   ...   ...   056   088   ...   085   096   ...
...   ...   ...   ...   ...   ...   ...   078   077   ...   097
023   ...   ...   037   ...   ...   081   ...   ...   ...   ...
...   024   ...   ...   017   ...   059   060   ...   ...   101
021   ...   035   ...   ...   ...   ...   104   ...   102   ...
121   002   ...   ...   013   ...   ...   105   ...   065   ...
001   ...   ...   ...   ...   ...   ...   ...   ...   066   ...
005   ...   010   ...   ...   112   ...   ...   ...   ...   070
...   ...   ...   ...   ...   ...   114   ...   109   ...   068
I could solve it until here:
Code: Select all
043   044   ...   046   ...   ...   054   090   091   092   093
042   041   ...   048   052   ...   ...   ...   ...   095   094
027   040   039   ...   ...   056   088   ...   085   096   098
026   028   038   030   ...   ...   ...   078   077   099   097
023   025   029   037   031   058   081   080   079   076   100
022   024   019   036   017   032   059   060   075   074   101
021   020   035   018   033   016   061   104   103   102   073
121   002   119   034   013   015   062   105   064   065   072
001   120   003   118   012   014   111   063   106   066   071
005   004   010   011   117   112   113   110   107   067   070
006   007   008   009   116   115   114   108   109   069   068
What's the next logical step?
evert
 
Posts: 187
Joined: 26 August 2005

Postby udosuk » Sat Dec 13, 2008 2:50 pm

evert wrote:I could solve it until here:
Code: Select all
043  044  ...  046  ...  ...  054  090  091  092  093
042  041  ...  048  052  ...  ...  ...  ...  095  094
027  040  039  ...  ...  056  088  ...  085  096  098
026  028  038  030  ...  ...  ...  078  077  099  097
023  025  029  037  031  058  081  080  079  076  100
022  024  019  036  017  032  059  060  075  074  101
021  020  035  018  033  016  061  104  103  102  073
121  002  119  034  013  015  062  105  064  065  072
001  120  003  118  012  014  111  063  106  066  071
005  004  010  011  117  112  113  110  107  067  070
006  007  008  009  116  115  114  108  109  069  068
What's the next logical step?

Highlight below to read what I wrote:089 is locked @ r2c78
Also, r4c7+r3c8 must be reserved for [082,083,084]
=> [086,087] must be @ r2c98

:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby evert » Sun Dec 14, 2008 11:08 am

BTW
Random creation of a complete grid:
This was a major problem in my program.
How it worked was: choose a random empty cell and fill it with a random number that can be placed in that cell then go on to the next random empty cell. (works fine with sudoku)
How it works now:
It tries to place the numbers in ascending order, first 1 then 2 etc, and just chooses random the cells wher to place them.
Before this it took literally hours to create a random grid.
Now it's a matter of few seconds.
I don't understand why, I'm just happy it improved.
evert
 
Posts: 187
Joined: 26 August 2005

Postby evert » Mon Dec 15, 2008 12:51 pm

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;..;22
60;..;..;..;..;14;13;..;81
..;59;..;36;..;..;..;..;..
..;56;..;..;16;..;..;..;..
66;..;55;..;..;18;..;45;..
..;..;53;50;49;..;47;..;..
..;..;..;..;..;73;..;..;..
evert
 
Posts: 187
Joined: 26 August 2005

Postby udosuk » Mon Dec 15, 2008 4:55 pm

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

:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby HATMAN » Tue Dec 16, 2008 8:10 am

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: 311
Joined: 25 February 2006
Location: Saudi Arabia

Postby udosuk » Tue Dec 16, 2008 3:12 pm

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.:idea:

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:
h-syouyuyaki.blog.drecom.jp/archive/256 { broken link }
blog.drecom.jp/h-syouyuyaki/img/256/keima.gif { broken link }

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

Postby djape » Wed Jan 14, 2009 8:44 pm

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

Postby evert » Sat Jan 17, 2009 12:47 am

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;13
60;57;56;55;52;06;10;14;12
61;46;48;49;50;51;05;00;15
45;62;47;02;01;04;17;00;00
63;44;38;37;03;35;00;00;20
43;64;39;40;36;00;00;32;00
65;42;41;76;74;00;31;00;00
00;66;00;00;00;72;00;00;00
81;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;13
60;57;56;55;52;06;10;14;12
61;46;48;49;50;51;05;00;15
45;62;47;02;01;04;17;00;00
63;44;38;37;03;35;00;00;20
43;64;39;40;36;34;00;32;00
65;42;41;76;74;73;31;00;00
80;66;67;77;75;72;71;00;00
81;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: 187
Joined: 26 August 2005

Postby udosuk » Sun Jan 18, 2009 3:42 am

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|13
60|57|56|55|52|06|10|14|12
61|46|48|49|50|51|05|..|15
45|62|47|02|01|04|17|..|..
63|44|38|37|03|35|..|..|20
43|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.:idea: )

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|13
60|57|56|55|52|06|10|14|12
61|46|48|49|50|51|05|..|15
45|62|47|02|01|04|17|..|..
63|44|38|37|03|35|..|..|20
43|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.:idea: )

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.

:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby evert » Tue Jan 20, 2009 11:05 am

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
evert
 
Posts: 187
Joined: 26 August 2005

Postby udosuk » Tue Jan 20, 2009 11:25 pm

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.:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Next

Return to Sudoku variants