Knight's tour: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 5,132: | Line 5,132: | ||
</pre> |
</pre> |
||
=={{header|SequenceL}}== |
|||
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_rule|Warnsdorffs rule]] (No Backtracking) |
|||
<lang sequenceL> |
|||
import <Utilities/Sequence.sl>; |
|||
import <Utilities/Conversion.sl>; |
|||
main(args(2)) := |
|||
let |
|||
N := stringToInt(args[1]) when size(args) > 0 else 8; |
|||
M := stringToInt(args[2]) when size(args) > 1 else N; |
|||
startX := stringToInt(args[3]) when size(args) > 2 else 1; |
|||
startY := stringToInt(args[4]) when size(args) > 3 else 1; |
|||
board[i,j] := 0 foreach i within 1 ... N, j within 1 ... M; |
|||
spacing := size(toString(N*M)) + 1; |
|||
in |
|||
join(printRow( |
|||
tour(setBoard(board, startX, startX, 1), [startX,startY], 2), |
|||
spacing)); |
|||
potentialMoves := [[2,1], [2,-1], [1,2], [1,-2], [-1,2], [-1,-2], [-2,1], [-2,-1]]; |
|||
printRow(row(1), spacing) := join(printSquare(row, spacing)) ++ "\n"; |
|||
printSquare(val, spacing) := |
|||
let |
|||
str := toString(val); |
|||
in |
|||
duplicate(' ', spacing - size(str)) ++ str; |
|||
tour(board(2), current(1), move) := |
|||
let |
|||
validMoves := validMove(board, current + potentialMoves); |
|||
numMoves[i] := size(validMove(board, validMoves[i] + potentialMoves)); |
|||
chosenMove := minPosition(numMoves); |
|||
in |
|||
board when move > size(board) * size(board[1]) else |
|||
[] when size(validMoves) = 0 else |
|||
[] when move < size(board) * size(board[1]) and numMoves[chosenMove] = 0 else |
|||
tour(setBoard(board, validMoves[chosenMove][1], validMoves[chosenMove][2], move), validMoves[chosenMove], move + 1); |
|||
validMove(board(2), position(1)) := |
|||
(position when board[position[1], position[2]] = 0) |
|||
when position[1] >= 1 and position[1] <= size(board) and position[2] >= 1 and position[2] <= size(board); |
|||
minPosition(x(1)) := minPositionHelper(x, 2, 1, x[1]); |
|||
minPositionHelper(x(1), i, minPos, minVal) := |
|||
minPos when i > size(x) else |
|||
minPositionHelper(x, i + 1, minPos, minVal) when x[i] > minVal else |
|||
minPositionHelper(x, i + 1, i, x[i]); |
|||
setBoard(board(2), x, y, value)[i,j] := |
|||
value when x = i and y = j else |
|||
board[i,j] foreach i within 1 ... size(board), j within 1 ... size(board[1]); |
|||
</lang> |
|||
{{out}} |
|||
8 X 8 board: |
|||
<pre> |
|||
1 16 31 40 3 18 21 56 |
|||
30 39 2 17 42 55 4 19 |
|||
15 32 41 46 53 20 57 22 |
|||
38 29 48 43 58 45 54 5 |
|||
33 14 37 52 47 60 23 62 |
|||
28 49 34 59 44 63 6 9 |
|||
13 36 51 26 11 8 61 24 |
|||
50 27 12 35 64 25 10 7 |
|||
</pre> |
|||
20 X 20 board: |
|||
<pre> |
|||
1 40 81 90 3 42 77 94 5 44 73 102 7 46 69 62 9 48 51 60 |
|||
82 89 2 41 92 95 4 43 76 101 6 45 72 103 8 47 68 61 10 49 |
|||
39 80 91 96 153 78 93 100 129 74 109 104 123 70 111 120 63 50 59 52 |
|||
88 83 154 79 98 159 152 75 108 105 128 71 110 121 124 67 112 119 64 11 |
|||
155 38 97 160 157 200 99 162 151 130 107 122 127 132 141 118 125 66 53 58 |
|||
84 87 156 199 176 161 158 201 106 163 150 131 142 145 126 133 140 113 12 65 |
|||
37 182 85 178 207 198 175 164 173 216 143 166 149 222 139 146 117 134 57 54 |
|||
86 179 206 197 204 177 208 217 202 165 172 221 144 167 148 223 138 55 114 13 |
|||
183 36 181 212 209 218 203 174 215 220 227 170 281 224 303 168 147 116 135 56 |
|||
180 211 196 205 230 213 238 219 228 171 280 225 302 169 282 343 304 137 14 115 |
|||
35 184 231 210 237 246 229 214 279 226 301 298 283 342 367 308 347 344 305 136 |
|||
232 195 236 245 234 239 278 247 300 297 284 359 366 309 348 345 368 307 350 15 |
|||
185 34 233 240 261 248 287 296 285 358 299 310 341 378 365 384 349 346 369 306 |
|||
194 241 250 235 244 277 260 313 294 311 360 373 364 383 354 379 370 385 16 351 |
|||
33 186 243 262 249 288 295 286 361 316 357 340 377 372 395 386 353 380 333 388 |
|||
242 193 254 251 276 259 314 293 312 321 374 363 398 355 382 371 394 387 352 17 |
|||
187 32 263 258 267 252 289 322 315 362 317 356 339 376 399 396 381 334 389 332 |
|||
192 255 190 253 264 275 268 271 292 323 320 375 326 397 338 335 390 393 18 21 |
|||
31 188 257 266 29 270 273 290 27 318 327 324 25 336 329 400 23 20 331 392 |
|||
256 191 30 189 274 265 28 269 272 291 26 319 328 325 24 337 330 391 22 19 |
|||
</pre> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Perl 6}} |
{{trans|Perl 6}} |