Knight's tour: Difference between revisions

=={{header|Nim}}==

{{trans|C++}}

This is a translation of the C++ and D versions with some changes, the most important being the addition of a check to detect that there is no solution. Without this check, the program crashes with an IndexError as Nim in debug and in release modes generates code to insure that indexes are valid.

We have added a case to test the absence of solution. Note that, in this case, there is a lot of backtracking which considerably slows down the execution.

<lang Nim>import algorithm, options, random, parseutils, strutils, strformat

type

Board[N: static Positive] = array[N, array[N, int]]

Move = tuple[x, y: int]

MoveList = array[8, Move]

MoveIndexes = array[8, int]

const Moves: MoveList = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]

proc `$`(board: Board): string =

## Display the board.

let size = len($(board.N * board.N)) + 1

for row in board:

for val in row:

stdout.write ($val).align(size)

echo ""

proc sortedMoves(board: Board; x, y: int): MoveIndexes =

## Return the list of moves sorted by count of possible moves.

var counts: array[8, tuple[value, index: int]]

for i, d1 in Moves:

var count = 0

for d2 in Moves:

let x2 = x + d1.x + d2.x

let y2 = y + d1.y + d2.y

if x2 in 0..<board.N and y2 in 0..<board.N and board[y2][x2] == 0:

inc count

counts[i] = (count, i)

counts.shuffle() # Shuffle to randomly break ties.

counts.sort() # Lexicographic sort.

for i, count in counts:

result[i] = count.index

proc knightTour[N: static Positive](start: string): Option[Board[N]] =

## Return the knight tour for a board of size N x N and the starting

## position "start.

## If no solution is found, return "node" else return "some".

# Initialize the board with the starting position.

var board: Board[N]

var startx, starty: int

startx = ord(start[0]) - ord('a')

if startx notin 0..<N:

raise newException(ValueError, "wrong column.")

if parseInt(start, starty, 1) != start.len - 1 or starty notin 1..N:

raise newException(ValueError, "wrong line.")

starty = N - starty

board[starty][startx] = 1

type OrderItem = tuple[x, y, idx: int; mi: MoveIndexes]

var order: array[N * N, OrderItem]

order[0] = (startx, starty, 0, board.sortedMoves(startx, starty))

# Search a tour.

var n = 0

while n < N * N - 1:

let x = order[n].x

let y = order[n].y

var ok = false

for i in order[n].idx..7:

let d = Moves[order[n].mi[i]]

if x + d.x notin 0..<N or y + d.y notin 0..<N: continue

if board[y + d.y][x + d.x] == 0:

order[n].idx = i + 1

inc n

board[y + d.y][x + d.x] = n + 1

order[n] = (x + d.x, y + d.y, 0, board.sortedMoves(x + d.x, y + d.y))

ok = true

break

if not ok:

# Failed: backtrack.

echo "backtrack"

board[y][x] = 0

dec n

if n < 0: return none(Board[N]) # No solution found.

result = some(board)

proc run[N: static Positive](start: string) =

## Run the algorithm and display the result.

let result = knightTour[N](start)

echo &"Board size: {N}x{N}, starting position: {start}."

if result.isSome(): echo result.get()

else: echo "No solution found.\n"

when isMainModule:

randomize()

run[5]("c3")

#run[5]("c4") # No solution, so very slow compared to other cases.

run[8]("b5")

run[31]("a1")</lang>

{{out}}

<pre>Board size: 5x5, starting position: c3.

23 16 11 6 21

10 5 22 17 12

15 24 1 20 7

4 9 18 13 2

25 14 3 8 19

Board size: 5x5, starting position: c4.

No solution found.

Board size: 8x8, starting position: b5.

63 20 3 24 59 36 5 26

2 23 64 37 4 25 58 35

19 62 21 50 55 60 27 6

22 1 54 61 38 45 34 57

53 18 49 44 51 56 7 28

12 15 52 39 46 31 42 33

17 48 13 10 43 40 29 8

14 11 16 47 30 9 32 41

Board size: 31x31, starting position: a1.

275 112 19 116 277 604 21 118 823 770 23 120 961 940 25 122 943 926 27 124 917 898 29 126 911 872 31 128 197 870 33

18 115 276 601 20 117 772 767 22 119 958 851 24 121 954 941 26 123 936 925 28 125 912 899 30 127 910 871 32 129 198

111 274 113 278 605 760 603 822 771 824 769 948 957 960 939 944 953 942 927 916 929 918 897 908 913 900 873 196 875 34 869

114 17 600 273 602 775 766 773 768 949 850 959 852 947 952 955 932 937 930 935 924 915 920 905 894 909 882 901 868 199 130

271 110 279 606 759 610 761 776 821 764 825 816 951 956 853 938 945 934 923 928 919 896 893 914 907 904 867 874 195 876 35

16 581 272 599 280 607 774 765 762 779 950 849 826 815 946 933 854 931 844 857 890 921 906 895 886 883 902 881 200 131 194

109 270 281 580 609 758 611 744 777 820 763 780 817 848 827 808 811 846 855 922 843 858 889 892 903 866 885 192 877 36 201

282 15 582 269 598 579 608 757 688 745 778 819 754 783 814 847 828 807 810 845 856 891 842 859 884 887 880 863 202 193 132

267 108 283 578 583 612 689 614 743 756 691 746 781 818 753 784 809 812 829 806 801 840 835 888 865 862 203 878 191 530 37

14 569 268 585 284 597 576 619 690 687 742 755 692 747 782 813 752 785 802 793 830 805 860 841 836 879 864 529 204 133 190

107 266 285 570 577 584 613 686 615 620 695 684 741 732 711 748 739 794 751 786 803 800 839 834 861 528 837 188 531 38 205

286 13 568 265 586 575 596 591 618 685 616 655 696 693 740 733 712 749 738 795 792 831 804 799 838 833 722 527 206 189 134

263 106 287 508 571 590 587 574 621 592 639 694 683 656 731 710 715 734 787 750 737 796 791 832 721 798 207 532 187 474 39

12 417 264 567 288 509 572 595 588 617 654 657 640 697 680 713 730 709 716 735 788 727 720 797 790 723 526 473 208 135 186

105 262 289 416 507 566 589 512 573 622 593 638 653 682 659 698 679 714 729 708 717 736 789 726 719 472 533 184 475 40 209

290 11 418 261 502 415 510 565 594 513 562 641 658 637 652 681 660 699 678 669 728 707 718 675 724 525 704 471 210 185 136

259 104 291 414 419 506 503 514 511 564 623 548 561 642 551 636 651 670 661 700 677 674 725 706 703 534 211 476 183 396 41

10 331 260 493 292 501 420 495 504 515 498 563 624 549 560 643 662 635 650 671 668 701 676 673 524 705 470 395 212 137 182

103 258 293 330 413 494 505 500 455 496 547 516 485 552 625 550 559 644 663 634 649 672 667 702 535 394 477 180 397 42 213

294 9 332 257 492 329 456 421 490 499 458 497 546 517 484 553 626 543 558 645 664 633 648 523 666 469 536 393 220 181 138

255 102 295 328 333 412 491 438 457 454 489 440 459 486 545 518 483 554 627 542 557 646 665 632 537 478 221 398 179 214 43

8 319 256 335 296 345 326 409 422 439 436 453 488 441 460 451 544 519 482 555 628 541 522 647 468 631 392 219 222 139 178

101 254 297 320 327 334 411 346 437 408 423 368 435 452 487 442 461 450 445 520 481 556 629 538 479 466 399 176 215 44 165

298 7 318 253 336 325 344 349 410 347 360 407 424 383 434 427 446 443 462 449 540 521 480 467 630 391 218 223 164 177 140

251 100 303 300 321 316 337 324 343 350 369 382 367 406 425 384 433 428 447 444 463 430 539 390 465 400 175 216 169 166 45

6 299 252 317 304 301 322 315 348 361 342 359 370 381 366 405 426 385 432 429 448 389 464 401 174 217 224 163 150 141 168

99 250 241 302 235 248 307 338 323 314 351 362 341 358 371 380 365 404 377 386 431 402 173 388 225 160 153 170 167 46 143

240 5 98 249 242 305 234 247 308 339 232 313 352 363 230 357 372 379 228 403 376 387 226 159 154 171 162 149 142 151 82

63 2 239 66 97 236 243 306 233 246 309 340 231 312 353 364 229 356 373 378 227 158 375 172 161 148 155 152 83 144 47

4 67 64 61 238 69 96 59 244 71 94 57 310 73 92 55 354 75 90 53 374 77 88 51 156 79 86 49 146 81 84

1 62 3 68 65 60 237 70 95 58 245 72 93 56 311 74 91 54 355 76 89 52 157 78 87 50 147 80 85 48 145</pre>