CLP(FD): Closed Knight's Tour

[Markus Triska-2]

Hi all,

a Closed Knight's Tour can be quite compactly expressed and readily
found with library(clpfd):

   http://www.logic.at/prolog/knight.pl

You need SWI >= 5.8.0 for the circuit/1 constraint that it uses.

The trick is to use a single finite domain variable per square, whose
domain elements represent the squares that are (still) reachable. (It is
tempting to use pairs of CLP(FD) variables for X/Y coordinates, which
can easily lead to worse pruning.)

Exercise: Describe and find tours that are not necessarily closed.

Please let me know if you have any comments or questions about this.

Thank you and all the best,
Markus
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Frederic Mesnard]

Hi Markus,

thank you for sharing!

Any animation as we had for:
http://stud4.tuwien.ac.at/~e0225855/sudoku/sudoku.html
http://stud4.tuwien.ac.at/~e0225855/queens/queens.html
?

Cheers,
Fred

> Hi all,
>
> a Closed Knight's Tour can be quite compactly expressed and readily
> found with library(clpfd):
>
>    http://www.logic.at/prolog/knight.pl
>
> You need SWI >= 5.8.0 for the circuit/1 constraint that it uses.
>
> The trick is to use a single finite domain variable per square, whose
> domain elements represent the squares that are (still) reachable. (It is
> tempting to use pairs of CLP(FD) variables for X/Y coordinates, which
> can easily lead to worse pruning.)
>
> Exercise: Describe and find tours that are not necessarily closed.
>
> Please let me know if you have any comments or questions about this.
>
> Thank you and all the best,
> Markus
> _______________________________________________
> SWI-Prolog mailing list
> SWI-Prolog@...
> https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
>
>

_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Markus Triska-2]

Hi Fred,

"Frederic Mesnard" <Frederic.Mesnard@...> writes:

> Any animation as we had for:
> http://stud4.tuwien.ac.at/~e0225855/sudoku/sudoku.html
> http://stud4.tuwien.ac.at/~e0225855/queens/queens.html
> ?

Of course! Please download the updated version and try:

   ?- n_tour(6, Ts), maplist(label, Ts), show(Ts).

   ?- n_tour(8, Ts), maplist(label, Ts), show(Ts).

You need the PostScript viewer "gs" installed. Samples:

   http://www.logic.at/prolog/knight6_1.pdf
   http://www.logic.at/prolog/knight6_2.pdf

   http://www.logic.at/prolog/knight8_2.pdf
   http://www.logic.at/prolog/knight8_1.pdf

They're also available in PNG format:

   http://www.logic.at/prolog/knight6_1.png
   http://www.logic.at/prolog/knight6_2.png

   http://www.logic.at/prolog/knight8_1.png
   http://www.logic.at/prolog/knight8_2.png

All the best,
Markus

_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Frederic Mesnard]

Hi Markus,

Nice! And it works great on my Mac, thanks again!

Cheers,
Fred




Le 4 nov. 09 à 01:58, Markus Triska a écrit :

> Hi Fred,
>
> "Frederic Mesnard" <Frederic.Mesnard@...> writes:
>
>> Any animation as we had for:
>> http://stud4.tuwien.ac.at/~e0225855/sudoku/sudoku.html
>> http://stud4.tuwien.ac.at/~e0225855/queens/queens.html
>> ?
>
> Of course! Please download the updated version and try:
>
>   ?- n_tour(6, Ts), maplist(label, Ts), show(Ts).
>
>   ?- n_tour(8, Ts), maplist(label, Ts), show(Ts).
>
> You need the PostScript viewer "gs" installed. Samples:
>
>   http://www.logic.at/prolog/knight6_1.pdf
>   http://www.logic.at/prolog/knight6_2.pdf
>
>   http://www.logic.at/prolog/knight8_2.pdf
>   http://www.logic.at/prolog/knight8_1.pdf
>
> They're also available in PNG format:
>
>   http://www.logic.at/prolog/knight6_1.png
>   http://www.logic.at/prolog/knight6_2.png
>
>   http://www.logic.at/prolog/knight8_1.png
>   http://www.logic.at/prolog/knight8_2.png
>
> All the best,
> Markus
>
>

_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Markus Triska-2]

Hi Fred,

Fred Mesnard <Frederic.Mesnard@...> writes:

> Nice! And it works great on my Mac, thanks again!

Meanwhile, I've tried it on a slower machine and found that re-opening
the Ghostscript window for each solution is a bit distracting; I have
therefore uploaded another revision with a different interface,
analogous to show/3 in the N-queens example. You can now use:

   ?- show(6, [ff], Ts).

   ?- show(8, [ff], Ts).

etc., where the arguments are the size of the board, a list of labeling
options, and a closed Knight's Tour that you can also print as text:

   ?- show(N, [ff], Ts), print_tour(Ts).
   %@   1  6 11 30 27  4
   %@  10 31  2  5 12 29
   %@   7 36  9 28  3 26
   %@  32 23 34 19 16 13
   %@  35  8 21 14 25 18
   %@  22 33 24 17 20 15
   %@ N = 6,
   %@ Ts = [[9, 13, 11, 8, 16, 10], ..., [20, 21, 29|...]] .

All the best,
Markus
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Markus Triska-2]

Hi Fred,

one additional point: it is much more efficient to post the circuit/1
constraint only after all in/2 constraints have been posted. The reason
is that each in/2 would otherwise re-trigger propagation of circuit/1,
whereas when posting circuit/1 afterwards it is only triggered then. The
latest uploaded version does that and yields for example:

   ?- time(show(8, [ff], Ts)), print_tour(Ts).
   %@ % 4,231,668 inferences, 0.800 CPU in 0.879 seconds (91% CPU, 5289585 Lips)
   %@   1  4 63 28 31 26 19 22
   %@  62 29  2  5 20 23 32 25
   %@   3 64 39 30 27 56 21 18
   %@  38 61  6 53 40 33 24 55
   %@   7 52 41 34 57 54 17 46
   %@  60 37  8 49 44 47 14 11
   %@  51 42 35 58  9 12 45 16
   %@  36 59 50 43 48 15 10 13

   ?- time(show(16, [ff], Ts)), print_tour(Ts, 4).
   %@ % 73,577,440 inferences, 14.810 CPU in 15.423 seconds (96% CPU, 4968092 Lips)
   %@    1   4 245 248 251   6 243 200 203 206 241 214 211 208 239 236
   %@  246 249   2   5 244 201 252   7 242 215 204 207 240 237 212 209
   %@    3 256 247 250 253   8 199 202 205  28 195 216 213 210 235 238
   %@  146 149 254   9 198 151  62  29 196 217  60  27 194 233  58  25
   %@  255  66 147 150  63  10 197 152  61  30 231 218  59  26 193 234
   %@  148 145  64  67 142 139  14  11 230 153  50  31 232 219  24  57
   %@   65  70 143 138  15  12 141 154  51  32 229 220  49  56 223 192
   %@  144 137  68  71 140 113  16  13 228 155  52  33 224 221  48  23
   %@   69  82 135 112  17  72 227 114  53  34 225 156  55  22 191 222
   %@  136 111  78  83 108 115  18  73 226 157  54  35  38 189 184  47
   %@   81 134 109 106  79  84 129 116  19  74  39 158  21  36 187 190
   %@  110 105  80  77 130 107  86  75 128 117  20  37 188 185  46 183
   %@  133  98 131 122  85  76 127 118  87  40 159  42 177 182 173 186
   %@  104 101  96 125  94 121  92 165  90 167 162 169 180 171 176  45
   %@   97 132  99 102 123 126 119  88 163 160  41 178  43 174 181 172
   %@  100 103 124  95 120  93 164  91 166  89 168 161 170 179  44 175

All the best,
Markus
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog