Knight's tour: Difference between revisions

{{task}}

[[wp:Knight%27s_tour|Problem]]: you have a standard 8x8 chessboard, empty but for a single knight on some square. Your task is to emit a series of legal knight moves that result in the knight visiting every square on the chessboard exactly once. Note that it is ''not'' a requirement that the tour be "closed"; that is, the knight need not end within a single move of its start position.

 

Output: move sequence

 

* [[N-queens problem]]

 

=={{header|Ada}}==

 

 

Size: Integer;

package Knights_Tour is

subtype Index is Integer range 1 .. Size;

type Tour is array (Index, Index) of Natural;

-- finds tour via backtracking

-- or the Result(X,Y)=K if and only if I,J is visited at the K-th move

-- writes The_Tour to the output using Ada.Text_IO;

 

Here is the implementation:

 

package body Knights_Tour is

type Pair is array(1..2) of Integer;

type Pair_Array is array (Positive range <>) of Pair;

Pairs: constant Pair_Array (1..8)

:= ((-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1));

 

procedure Visit(X, Y: Index; Move_Number: Positive; Found: out Boolean) is

XX, YY: Integer;

Found := False;

Visited(X, Y) := Move_Number;

Found := True;

else

end if;

end Visit;

begin

Visit(Start_X, Start_Y, 1, Done);

if not Done then

end if;

return Visited;

end Get_Tour;

begin

for I in Index loop

for J in Index loop

end loop;

Ada.Text_IO.New_Line;

end loop;

end Tour_IO;

 

Here is the main program:

 

 

procedure Test_Knight is

begin

KT.Tour_IO(KT.Get_Tour(1, 1));

 

For small sizes, this already works well (< 1 sec for size 8). Sample output:

50 43 30 61 14 63 28 7</pre>

 

-- uses Warnsdorff heurisitic to find a tour faster

 

function Neighbors(X, Y: Index) return Natural is

Result: Natural := 0;

return Result;

end Neighbors;

procedure Sort(Options: in out Pair_Array) is

N_Bors: array(Options'Range) of Natural;

end loop;

end Sort;

procedure Visit(X, Y: Index; Move: Positive; Found: out Boolean) is

Next_Count: Natural range 0 .. 8 := 0;

Found := False;

Visited(X, Y) := Move;

Found := True;

else

end if;

end loop;

Sort(Next_Steps(1 .. Next_Count));

for N in 1 .. Next_Count loop

Visit(Next_Steps(N)(1), Next_Steps(N)(2), Move+1, Found);

end if;

end loop;

-- if we didn't return above, we have to undo our move

Visited(X, Y) := 0;

end if;

end Visit;

begin

Visit(Start_X, Start_Y, 1, Done);

if not Done then

end if;

return Visited;

 

The modification for the main program is trivial:

 

procedure Test_Fast is

begin

KT.Tour_IO(KT.Warnsdorff_Get_Tour(1, 1));

 

This works still well for somewhat larger sizes:

383 34 97 92 391 32 405 90 393 30 547 88 471 28 505 86 469 26 465 84 369 24 429 82

96 381 384 33 386 91 392 31 406 89 472 29 506 87 470 27 504 85 468 25 430 83 368 23</pre>

 

=={{header|AutoHotkey}}==

{{libheader|GDIP}}

#NoEnv

SetBatchLines, -1

If (A_Gui = 1)

PostMessage, 0xA1, 2

{{out}}

For start at b3

... plus an animation.

 

{{works with|BBC BASIC for Windows}}

[[Image:knights_tour_bbc.gif|right]]

VDU 23,23,4;0;0;0;

OFF

DEF FNvalidmove(X%,Y%)

IF X%<0 OR X%>7 OR Y%<0 OR Y%>7 THEN = FALSE

 

=={{header|Bracmat}}==

= validmoves WarnsdorffSort algebraicNotation init solve

, x y fieldsToVisit

$ (algebraicNotation$(solve$((!x.!y).!fieldsToVisit)))

)

 

<pre>a1 b3 a5 b7 d8 f7 h8 g6 f8 h7 g5 h3 g1 e2 c1 a2 b4 a6 b8 c6 a7 c8 e7 g8 h6 g4 h2 f1 d2 b1 a3 c2 e1 f3 h4 g2 e3 d1 b2 a4 c3 b5 d4 f5 d6 c4 e5 d3 f2 h1 g3 e4 c5 d7 b6 a8 c7 d5 f4 e6 g7 e8 f6 h5</pre>

 

The following draws on console the progress of the horsie. Specify board size on commandline, or use default 8.

#include <stdlib.h>

#include <string.h>

 

return 0;

 

=={{header|C++}}==

Uses Warnsdorff's rule and (iterative) backtracking if that fails.

 

#include <iomanip>

#include <array>

continue;

 

get<2>(order[n]) = i + 1;

data[y+dy][x+dx] = n + 1;

order[n] = make_tuple(x+dx, y+dy, 0, sortMoves(x+dx, y+dy));

cout << b3 << endl;

return 0;

 

Output:

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>

 

 

 

=={{header|CoffeeScript}}==

This algorithm finds 100,000 distinct solutions to the 8x8 problem in about 30 seconds. It precomputes knight moves up front, so it turns into a pure graph traversal problem. The program uses iteration and backtracking to find solutions.

graph_tours = (graph, max_num_solutions) ->

# graph is an array of arrays

illustrate_knights_tour tours[0], BOARD_WIDTH

illustrate_knights_tour tours.pop(), BOARD_WIDTH

 

output

> time coffee knight.coffee

100000 tours found (showing first and last)

user 0m25.656s

sys 0m0.253s

 

=={{header|D}}==

{{trans|C++}}

std.conv, std.typecons, std.typetuple;

 

writeln();

}

{{out}}

<pre>23 16 11 6 21

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>

 

=={{header|Erlang}}==

Again I use backtracking. It seemed easier this time.

-module( knights_tour ).

 

next_moves_row( 8 ) -> [6, 7];

next_moves_row( N ) -> [N - 2, N - 1, N + 1, N + 2].

{{out}}

<pre>

1 10 31 64 33 26 53 62

</pre>