Knight's tour: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: auto-vivification pretty reliable lately) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (8 intermediate revisions by 5 users not shown) | |||
Line 25:
{{trans|Python}}
<
F chess2index(=chess, boardsize)
Line 81:
V board = knights_tour(start, boardsize)
print(boardstring(board, boardsize' boardsize))
print()</
{{out}}
Line 124:
=={{header|360 Assembly}}==
{{trans|BBC PASIC}}
<
KNIGHT CSECT
USING KNIGHT,R13 base registers
Line 378:
PG DC CL128' ' buffer
YREGS
END KNIGHT</
{{out}}
<pre>
Line 396:
First, we specify a naive implementation the package Knights_Tour with naive backtracking. It is a bit more general than required for this task, by providing a mechanism '''not''' to visit certain coordinates. This mechanism is actually useful for the task [[Solve a Holy Knight's tour#Ada]], which also uses the package Knights_Tour.
<
Size: Integer;
package Knights_Tour is
Line 417:
-- writes The_Tour to the output using Ada.Text_IO;
end Knights_Tour;</
Here is the implementation:
<
package body Knights_Tour is
Line 505:
end Tour_IO;
end Knights_Tour;</
Here is the main program:
<
procedure Test_Knight is
Line 519:
begin
KT.Tour_IO(KT.Get_Tour(1, 1));
end Test_Knight;</
For small sizes, this already works well (< 1 sec for size 8). Sample output:
Line 533:
For larger sizes we'll use Warnsdorff's heuristic (without any thoughtful tie breaking). We enhance the specification adding a function Warnsdorff_Get_Tour. This enhancement of the package Knights_Tour will also be used for the task [[Solve a Holy Knight's tour#Ada]]. The specification of Warnsdorff_Get_Tour is the following.
<syntaxhighlight lang="ada">
function Warnsdorff_Get_Tour(Start_X, Start_Y: Index; Scene: Tour := Empty)
return Tour;
-- uses Warnsdorff heurisitic to find a tour faster
-- same interface as Get_Tour</
Its implementation is as follows.
<
return Tour is
Done: Boolean;
Line 626:
end if;
return Visited;
end Warnsdorff_Get_Tour;</
The modification for the main program is trivial:
<
procedure Test_Fast is
Line 639:
begin
KT.Tour_IO(KT.Warnsdorff_Get_Tour(1, 1));
end Test_Fast;</
This works still well for somewhat larger sizes:
Line 670:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}
<
# If there are multiple choices, backtrack if the first choice doesn't #
# find a solution #
Line 957:
FI
)</
{{out}}
<pre>
Line 972:
1| 12 25 14 31 10 27 36 61
</pre>
=={{header|ATS}}==
<
Find Knight’s Tours.
Line 1,782 ⟶ 1,700:
val _ = make_and_fprint_tours (stdout_ref, 8, 8, i, j, max_tours,
closed_only)
}</
{{out}}
Line 1,845 ⟶ 1,763:
=={{header|AutoHotkey}}==
{{libheader|GDIP}}
<
#NoEnv
SetBatchLines, -1
Line 1,940 ⟶ 1,858:
If (A_Gui = 1)
PostMessage, 0xA1, 2
}</
{{out}}
For start at b3
Line 1,947 ⟶ 1,865:
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f KNIGHTS_TOUR.AWK [-v sr=x] [-v sc=x]
#
Line 2,016 ⟶ 1,934:
}
}
</syntaxhighlight>
<p>output:</p>
<pre>
Line 2,030 ⟶ 1,948:
</pre>
=={{header|
==={{header|ANSI BASIC}}===
{{trans|BBC BASIC}}
[[File:Knights_Tour.gif|right]]
{{works with|Decimal BASIC}}
ANSI BASIC does not allow function parameters to be passed by reference, so X and Y were made global variables.
<syntaxhighlight lang="basic">100 DECLARE EXTERNAL FUNCTION choosemove
110 !
120 RANDOMIZE
130 PUBLIC NUMERIC X, Y, TRUE, FALSE
140 LET TRUE = -1
150 LET FALSE = 0
160 !
170 SET WINDOW 1,512,1,512
180 SET AREA COLOR "black"
190 FOR x=0 TO 512-128 STEP 128
200 FOR y=0 TO 512-128 STEP 128
210 PLOT AREA:x+64,y;x+128,y;x+128,y+64;x+64,y+64
220 PLOT AREA:x,y+64;x+64,y+64;x+64,y+128;x,y+128
230 NEXT y
240 NEXT x
250 !
260 SET LINE COLOR "red"
270 SET LINE WIDTH 6
280 !
290 PUBLIC NUMERIC Board(0 TO 7,0 TO 7)
300 LET X = 0
310 LET Y = 0
320 LET Total = 0
330 DO
340 LET Board(X,Y) = TRUE
350 PLOT LINES: X*64+32,Y*64+32;
360 LET Total = Total + 1
370 LOOP UNTIL choosemove(X, Y) = FALSE
380 IF Total <> 64 THEN STOP
390 END
400 !
410 EXTERNAL FUNCTION choosemove(X1, Y1)
420 DECLARE EXTERNAL SUB trymove
430 LET M = 9
440 CALL trymove(X1+1, Y1+2, M, newx, newy)
450 CALL trymove(X1+1, Y1-2, M, newx, newy)
460 CALL trymove(X1-1, Y1+2, M, newx, newy)
470 CALL trymove(X1-1, Y1-2, M, newx, newy)
480 CALL trymove(X1+2, Y1+1, M, newx, newy)
490 CALL trymove(X1+2, Y1-1, M, newx, newy)
500 CALL trymove(X1-2, Y1+1, M, newx, newy)
510 CALL trymove(X1-2, Y1-1, M, newx, newy)
520 IF M=9 THEN
530 LET choosemove = FALSE
540 EXIT FUNCTION
550 END IF
560 LET X = newx
570 LET Y = newy
580 LET choosemove = TRUE
590 END FUNCTION
600 !
610 EXTERNAL SUB trymove(X, Y, M, newx, newy)
620 !
630 DECLARE EXTERNAL FUNCTION validmove
640 IF validmove(X,Y) = 0 THEN EXIT SUB
650 IF validmove(X+1,Y+2) <> 0 THEN LET N = N + 1
660 IF validmove(X+1,Y-2) <> 0 THEN LET N = N + 1
670 IF validmove(X-1,Y+2) <> 0 THEN LET N = N + 1
680 IF validmove(X-1,Y-2) <> 0 THEN LET N = N + 1
690 IF validmove(X+2,Y+1) <> 0 THEN LET N = N + 1
700 IF validmove(X+2,Y-1) <> 0 THEN LET N = N + 1
710 IF validmove(X-2,Y+1) <> 0 THEN LET N = N + 1
720 IF validmove(X-2,Y-1) <> 0 THEN LET N = N + 1
730 IF N>M THEN EXIT SUB
740 IF N=M AND RND<.5 THEN EXIT SUB
750 LET M = N
760 LET newx = X
770 LET newy = Y
780 END SUB
790 !
800 EXTERNAL FUNCTION validmove(X,Y)
810 LET validmove = FALSE
820 IF X<0 OR X>7 OR Y<0 OR Y>7 THEN EXIT FUNCTION
830 IF Board(X,Y)=FALSE THEN LET validmove = TRUE
840 END FUNCTION</syntaxhighlight>
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
[[Image:knights_tour_bbc.gif|right]]
<
VDU 23,23,4;0;0;0;
OFF
Line 2,092:
DEF FNvalidmove(X%,Y%)
IF X%<0 OR X%>7 OR Y%<0 OR Y%>7 THEN = FALSE
= NOT(Board%(X%,Y%))</
=={{header|Bracmat}}==
<
= validmoves WarnsdorffSort algebraicNotation init solve
, x y fieldsToVisit
Line 2,199:
$ (algebraicNotation$(solve$((!x.!y).!fieldsToVisit)))
)
& out$(knightsTour$a1);</
<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>
Line 2,207:
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>
Line 2,309:
return 0;
}</
=={{header|C sharp}}==
<
using System.Collections.Generic;
Line 2,395:
}
}
}</
=={{header|C++}}==
Line 2,402:
Uses Warnsdorff's rule and (iterative) backtracking if that fails.
<
#include <iomanip>
#include <array>
Line 2,545:
cout << b3 << endl;
return 0;
}</
Output:
Line 2,600:
This interactive program will ask for a starting case in algebraic notation and, also, whether a closed tour is desired. Each next move is selected according to Warnsdorff's rule; ties are broken at random.
The closed tour algorithm is quite crude: just find tours over and
This code is quite verbose: I tried to make it easy for myself and for
For some reason, the interactive part does not work with
<
;;; Solving the knight's tour. ;;;
;;; Warnsdorff's rule with random tie break. ;;;
Line 2,792:
(prompt)
(main)</
{{out}}
<pre>Starting case (leave blank for random)? a8
Line 2,811:
=={{header|Clojure}}==
Using warnsdorff's rule
<syntaxhighlight lang="clojure">
(defn isin? [x li]
(not= [] (filter #(= x %) li)))
Line 2,837:
(let [np (next-move mov pmoves n)]
(recur (conj mov np) (inc x)))))))
</syntaxhighlight>
{{out}}
<pre>
Line 2,854:
=={{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
Line 2,969:
illustrate_knights_tour tours[0], BOARD_WIDTH
illustrate_knights_tour tours.pop(), BOARD_WIDTH
</syntaxhighlight>
output
<syntaxhighlight lang="text">
> time coffee knight.coffee
100000 tours found (showing first and last)
Line 2,999:
user 0m25.656s
sys 0m0.253s
</syntaxhighlight>
=={{header|D}}==
===Fast Version===
{{trans|C++}}
<
std.conv, std.typecons, std.typetuple;
Line 3,080:
writeln();
}
}</
{{out}}
<pre>23 16 11 6 21
Line 3,131:
===Shorter Version===
{{trans|Haskell}}
<
alias Square = Tuple!(int,"x", int,"y");
Line 3,157:
const board = iota(1, 9).cartesianProduct(iota(1, 9)).map!Square.array;
writefln("%(%-(%s -> %)\n%)", board.knightTour([sq]).map!toAlg.chunks(8));
}</
{{out}}
<pre>e5 -> d7 -> b8 -> a6 -> b4 -> a2 -> c1 -> b3
Line 3,167:
d6 -> e4 -> c5 -> d3 -> e1 -> g2 -> h4 -> f5
d4 -> e2 -> f4 -> e6 -> g5 -> f3 -> g1 -> h3</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|Forms,Types,SysUtils,Graphics,ExtCtrls}}
[[File:DelphiKnightsTour.png|thumb|none]]
Brute force method. Takes a long time for most solutions, so some optimization should be used. However, it has nice graphics.
<syntaxhighlight lang="Delphi">
{ These routines would normally be in a library,
but are presented here for clarity }
function PointAdd(V1,V2: TPoint): TPoint;
{Add V1 and V2}
begin
Result.X:= V1.X+V2.X;
Result.Y:= V1.Y+V2.Y;
end;
const KnightMoves: array [0..7] of TPoint = (
(X: 2; Y:1),(X: 2; Y:-1),
(X:-2; Y:1),(X:-2; Y:-1),
(X:1; Y: 2),(X:-1; Y: 2),
(X:1; Y:-2),(X:-1; Y:-2));
var Board: array [0..7,0..7] of boolean;
var Path: array of TPoint;
var CellSize,BoardSize: integer;
var CurPos: TPoint;
var BestPath: integer;
{-------------------------------------------------------------}
procedure DrawBestPath(Image: TImage);
begin
Image.Canvas.TextOut(BoardSize+5,5, IntToStr(BestPath));
end;
procedure PushPath(P: TPoint);
begin
SetLength(Path,Length(Path)+1);
Path[High(Path)]:=P;
if Length(Path)>BestPath then BestPath:=Length(Path);
end;
function PopPath: TPoint;
begin
if Length(Path)<1 then exit;
Result:=Path[High(Path)];
SetLength(Path,Length(Path)-1);
end;
procedure ClearPath;
begin
SetLength(Path,0);
end;
{-------- Routines to draw chess board and path --------------}
function GetCellCenter(P: TPoint): TPoint;
{Get pixel position of the center of cell}
begin
Result.X:=CellSize div 2 + CellSize * P.X;
Result.Y:=CellSize div 2 + CellSize * P.Y;
end;
procedure DrawPoint(Canvas: TCanvas; P: TPoint);
{Draw a point on the board}
begin
Canvas.Pen.Color:=clYellow;
Canvas.MoveTo(P.X-1,P.Y-1);
Canvas.LineTo(P.X+1,P.Y+1);
Canvas.MoveTo(P.X+1,P.Y-1);
Canvas.LineTo(P.X-1,P.Y+1);
end;
procedure DrawPathLine(Canvas: TCanvas; P1,P2: TPoint);
{Draw the path line}
var PS1,PS2: TPoint;
begin
PS1:=GetCellCenter(P1);
PS2:=GetCellCenter(P2);
Canvas.Pen.Width:=5;
Canvas.Pen.Color:=clRed;
Canvas.MoveTo(PS1.X,PS1.Y);
Canvas.LineTo(PS2.X,PS2.Y);
DrawPoint(Canvas,PS1);
DrawPoint(Canvas,PS2);
end;
procedure DrawPath(Canvas: TCanvas);
{Draw all points on the path}
var I: integer;
begin
for I:=0 to High(Path)-1 do
begin
DrawPathLine(Canvas, Path[I],Path[I+1]);
end;
end;
procedure DrawBoard(Canvas: TCanvas);
{Draw the chess board}
var R,R2: TRect;
var X,Y: integer;
var Color: TColor;
begin
Canvas.Pen.Color:=clBlack;
R:=Rect(0,0,BoardSize,BoardSize);
Canvas.Rectangle(R);
R:=Rect(0,0,CellSize,CellSize);
for Y:=0 to High(Board[0]) do
for X:=0 to High(Board) do
begin
R2:=R;
if ((X+Y) mod 2)=0 then Color:=clWhite
else Color:=clBlack;
Canvas.Brush.Color:=Color;
OffsetRect(R2,X * CellSize, Y * CellSize);
Canvas.Rectangle(R2);
end;
DrawPath(Canvas);
end;
function AllVisited: boolean;
{Test if all squares have been visit by path}
var X,Y: integer;
begin
Result:=False;
for Y:=0 to High(Board[0]) do
for X:=0 to High(Board) do
if not Board[X,Y] then exit;
Result:=True;
end;
procedure ClearBoard;
{Clear all board positions}
var X,Y: integer;
begin
for Y:=0 to High(Board[0]) do
for X:=0 to High(Board) do
Board[X,Y]:=False;
end;
function IsValidMove(Pos,Move: TPoint): boolean;
{Test if potential move is valid}
var NP: TPoint;
begin
Result:=False;
NP:=PointAdd(Pos,Move);
if (NP.X<0) or (NP.X>High(Board)) or
(NP.Y<0) or (NP.Y>High(Board[0])) then exit;
if Board[NP.X,NP.Y] then exit;
Result:=True;
end;
procedure ConfigureScreen(Image: TImage);
{Configure screen size}
begin
if Image.Width<Image.Height then BoardSize:=Image.Width
else BoardSize:=Image.Height;
CellSize:=BoardSize div 8;
end;
procedure SetPosition(Image: TImage; P: TPoint; Value: boolean);
{Set a new position by adding it to path}
{Marking position as used and redrawing board}
begin
if Value then PushPath(P)
else P:=PopPath;
Board[P.X,P.Y]:=Value;
DrawBoard(Image.Canvas);
DrawBestPath(Image);
Image.Repaint;
end;
procedure TryAllMoves(Image: TImage; Pos: TPoint);
{Recursively try all moves}
var I: integer;
var NewPos: TPoint;
begin
SetPosition(Image,Pos,True);
if AllVisited then exit;
for I:=0 to High(KnightMoves) do
begin
if AbortFlag then Exit;
if IsValidMove(Pos,KnightMoves[I]) then
begin
NewPos:=PointAdd(Pos,KnightMoves[I]);
TryAllMoves(Image,NewPos);
end;
end;
SetPosition(Image,Pos,False);
Application.ProcessMessages;
end;
procedure DoKnightsTour(Image: TImage);
{Solve Knights tour by testing all paths}
begin
BestPath:=0;
ConfigureScreen(Image);
ClearPath;
ClearBoard;
DrawBoard(Image.Canvas);
TryAllMoves(Image, Point(0,0));
end;
</syntaxhighlight>
{{out}}
<pre>
</pre>
=={{header|EchoLisp}}==
The algorithm uses iterative backtracking and Warnsdorff's heuristic. It can output closed or non-closed tours.
<
(require 'plot)
(define *knight-moves*
Line 3,240 ⟶ 3,476:
(play starter 0 starter (dim n) wants-open)
(catch (hit mess) (show-steps n wants-open))))
</syntaxhighlight>
{{out}}
<
(k-tour 8 0 #f)
♞-closed-tour: 66 tries.
Line 3,278 ⟶ 3,514:
79 76 83 18 91 74 137 16 169 72 153 14 167 70 157 12 63 68 55 10
82 19 80 75 84 17 92 73 152 15 168 71 154 13 62 69 54 11 52 67
</syntaxhighlight>
;Plotting:
64 shades of gray. We plot the move sequence in shades of gray, from black to white. The starting square is red. The ending square is green. One can observe that the squares near the border are played first (dark squares).
<
(define (step-color x y n last-one)
(letrec ((sq (square (floor x) (floor y) n))
Line 3,292 ⟶ 3,528:
(define ( k-plot n)
(plot-rgb (lambda (x y) (step-color x y n (dim n))) (- n epsilon) (- n epsilon)))
</syntaxhighlight>
Line 3,301 ⟶ 3,537:
=={{header|Elixir}}==
{{trans|Ruby}}
<
import Integer, only: [is_odd: 1]
Line 3,364 ⟶ 3,600:
Board.knight_tour(4,9,1,1)
Board.knight_tour(5,5,1,2)
Board.knight_tour(12,12,2,2)</
{{out}}
Line 3,410 ⟶ 3,646:
=={{header|Elm}}==
<
import Browser exposing (element)
Line 3,755 ⟶ 3,991:
, subscriptions = subscriptions
}
</syntaxhighlight>
Link to live demo: https://dmcbane.github.io/knights-tour/
Line 3,761 ⟶ 3,997:
=={{header|Erlang}}==
Again I use backtracking. It seemed easier this time.
<syntaxhighlight lang="erlang">
-module( knights_tour ).
Line 3,840 ⟶ 4,076:
next_moves_row( 8 ) -> [6, 7];
next_moves_row( N ) -> [N - 2, N - 1, N + 1, N + 2].
</syntaxhighlight>
{{out}}
<pre>
Line 3,866 ⟶ 4,102:
=={{header|ERRE}}==
Taken from ERRE distribution disk. Comments are in Italian.
<syntaxhighlight lang="erre">
! **********************************************************************
! * *
Line 4,076 ⟶ 4,312:
UNTIL A$<>""
END PROGRAM
</syntaxhighlight>
{{out}}
<pre> *** LA GALOPPATA DEL CAVALIERE ***
Line 4,097 ⟶ 4,333:
=={{header|FreeBASIC}}==
<
Dim Shared As Integer tamano, xc, yc, nm
Dim As Integer f, qm, nmov, n = 0
Line 4,155 ⟶ 4,391:
Sleep
End
</syntaxhighlight>
{{out}}
[https://www.dropbox.com/s/s3bpwechpoueum4/Knights%20Tour%20FreeBasic.png?dl=0 Knights Tour FreeBasic image]
Line 4,180 ⟶ 4,416:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Knight%27s_tour}}
=={{header|Fortran}}==
Line 4,191 ⟶ 4,423:
{{works with|gfortran|11.2.1}}
{{works with|f2c}}
<
C
C Find Knight’s Tours.
Line 4,841 ⟶ 5,073:
end
C-----------------------------------------------------------------------</
{{out}}
$ echo "c5 2 T" | ./knights_tour
Line 4,904 ⟶ 5,136:
{{works with|gfortran|11.2.1}}
{{trans|ATS}}
<
!
! Find Knight’s Tours.
Line 5,464 ⟶ 5,696:
end program
!-----------------------------------------------------------------------</
{{out}}
Line 5,528 ⟶ 5,760:
{{works with|gfortran|11.2.1}}
(This one is ''not'' a translation of my ATS implementation. I wrote it earlier.)
<
!!! Find a Knight’s Tour.
!!!
Line 5,853 ⟶ 6,085:
end if
end do
end program knights_tour_main</
$ ./knights_tour a1 b2 c3
Line 5,885 ⟶ 6,117:
=={{header|Go}}==
===Warnsdorf's rule===
<
import (
Line 5,992 ⟶ 6,224:
}
return true
}</
{{out}}
<pre>
Line 6,005 ⟶ 6,237:
</pre>
===Ant colony===
<
by Philip Hingston and Graham Kendal,
PDF at http://www.cs.nott.ac.uk/~gxk/papers/cec05knights.pdf. */
Line 6,196 ⟶ 6,428:
tourCh <- moves
}
}</
Output:
<pre>
Line 6,212 ⟶ 6,444:
=={{header|Haskell}}==
<
import Data.Char (chr, ord)
import Data.List (intercalate, minimumBy, sort, (\\))
Line 6,273 ⟶ 6,505:
printTour tour = do
putStrLn $ intercalate " -> " $ take 8 tour
printTour $ drop 8 tour</
{{Out}}
<pre>e5 -> f7 -> h8 -> g6 -> h4 -> g2 -> e1 -> f3
Line 6,291 ⟶ 6,523:
The algorithm doesn't always generate a complete tour.
<
procedure main(A)
Line 6,391 ⟶ 6,623:
}
every write(hdr2|hdr1|&null)
end</
The following can be used when debugging to validate the board structure and to image the available moves on the board.
<
write("Board size=",B.N)
write("Available Moves at start of tour:", ImageMovesTo(B.movesto))
Line 6,404 ⟶ 6,636:
every s ||:= " " || (!sort(movesto[k])|"\n")
return s
end</
Line 6,456 ⟶ 6,688:
'''Solution:'''<br>
[[j:Essays/Knight's Tour|The Knight's tour essay on the Jwiki]] shows a couple of solutions including one using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]].
<
kmoves=: monad define
t=. (>,{;~i.y) +"1/ _2]\2 1 2 _1 1 2 1 _2 _1 2 _1 _2 _2 1 _2 _1
Line 6,472 ⟶ 6,704:
assert. ~:p
(,~y)$/:p
)</
'''Example Use:'''
<
0 25 14 23 28 49 12 31
15 22 27 50 13 30 63 48
Line 6,496 ⟶ 6,728:
555 558 553 778 563 570 775 780 785 772 1000...
100 551 556 561 102 777 572 771 104 781 57...
557 554 101 552 571 562 103 776 573 770 10...</
=={{header|Java}}==
{{Works with|Java|7}}
<
public class KnightsTour {
Line 6,597 ⟶ 6,829:
}
}
}</
<pre>34 17 20 3 36 7 22 5
19 2 35 40 21 4 37 8
Line 6,608 ⟶ 6,840:
===More efficient non-trackback solution===
{{Works with|Java|8}}
<syntaxhighlight lang="text">
package com.knight.tour;
import java.util.ArrayList;
Line 6,767 ⟶ 6,999:
}
}
</syntaxhighlight>
<pre>
Found a path for 8 X 8 chess board.
Line 6,784 ⟶ 7,016:
You can test it [http://paulo-jorente.de/webgames/repos/knightsTour/ here].
<
class KnightTour {
constructor() {
Line 7,000 ⟶ 7,232:
}
new KnightTour();
</syntaxhighlight>
To test it, you'll need an index.html
<pre>
Line 7,070 ⟶ 7,302:
A composition of values, drawing on generic abstractions:
{{Trans|Haskell}}
<
'use strict';
Line 7,363 ⟶ 7,595:
// MAIN ---
return main();
})();</
{{Out}}
<pre>(Board size 8*8)
Line 7,392 ⟶ 7,624:
=={{header|Julia}}==
Uses the Hidato puzzle solver module, which has its source code listed [[Solve_a_Hidato_puzzle#Julia | here]] in the Hadato task.
<
const chessboard = """
Line 7,410 ⟶ 7,642:
hidatosolve(board, maxmoves, knightmoves, fixed, starts[1][1], starts[1][2], 1)
printboard(board)
</
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Line 7,433 ⟶ 7,665:
{{trans|Haskell}}
<
val board = Array(8 * 8, { Square(it / 8 + 1, it % 8 + 1) })
Line 7,461 ⟶ 7,693:
col = (col + 1) % 8
}
}</
{{out}}
Line 7,477 ⟶ 7,709:
Influenced by the Python version, although computed tours are different.
<
20 input "Board size: ",size
30 input "Start position: ",a$
Line 7,523 ⟶ 7,755:
450 ' skip this move
460 next
470 return</
[[File:Knights tour Locomotive Basic.png]]
=={{header|Lua}}==
<
moves = { {1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2} }
Line 7,578 ⟶ 7,810:
print( string.format( "%s%d - %s%d", string.sub("ABCDEFGH",last[1],last[1]), last[2], string.sub("ABCDEFGH",lst[i][1],lst[i][1]), lst[i][2] ) )
last = lst[i]
end</
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Function KnightTour$(StartW=1, StartH=1){
def boolean swapH, swapV=True
Line 7,683 ⟶ 7,915:
Clipboard ex$
Report ex$
</syntaxhighlight>
{{out}}
<pre>
Line 7,730 ⟶ 7,962:
Beware the program writes to a file ‘__random_number__’ in the working directory. (This can be avoided in GNU m4 by using ‘esyscmd’ instead of ‘syscmd’. I do not know how to avoid it in general.)
<
----------------------------------------------------------------------
Line 7,908 ⟶ 8,140:
find_tour(a1)
find_tour(c5)
find_tour(h8)</
{{out}}
Line 7,920 ⟶ 8,152:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
'''Solution'''
<
Module[{
vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <> ToString[Mod[# - 1, 8] + 1]) & /@ Range[64], knightsGraph,
Line 7,927 ⟶ 8,159:
hamiltonianCycle = ((FindHamiltonianCycle[knightsGraph] /. UndirectedEdge -> DirectedEdge) /. labels)[[1]];
end = Cases[hamiltonianCycle, (x_ \[DirectedEdge] start) :> x][[1]];
FindShortestPath[g, start, end]]</
'''Usage'''
<
(* out *)
Line 7,936 ⟶ 8,168:
"c7", "a8", "b6", "c8", "d6", "e4", "d2", "f1", "e3", "d1", "f2", "h1", "g3", "e2", "c1", "d3", "e1", "g2", "h4", "f5", "e7", "d5", \
"f4", "h5", "g7", "e8", "f6", "g8", "h6", "g4", "h2", "f3", "g1", "h3", "g5", "h7", "f8", "d7", "e5", "g6", "h8", "f7"}
</syntaxhighlight>
'''Analysis'''
'''vertexLabels''' replaces the default vertex (i.e. square) names of the chessboard with the standard algebraic names "a1", "a2",...,"h8".
<syntaxhighlight lang="mathematica">
vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <> ToString[Mod[# - 1, 8] + 1]) & /@ Range[64]
Line 7,952 ⟶ 8,184:
41 -> "f1", 42 -> "f2", 43 -> "f3", 44 -> "f4", 45 -> "f5", 46 -> "f6", 47 -> "f7", 48 -> "f8",
49 -> "g1", 50 -> "g2", 51 -> "g3", 52 -> "g4", 53 -> "g5", 54 -> "g6",55 -> "g7", 56 -> "g8",
57 -> "h1", 58 -> "h2", 59 -> "h3", 60 -> "h4", 61 -> "h5", 62 -> "h6", 63 -> "h7", 64 -> "h8"}</
'''knightsGraph''' creates a graph of the solution space.
<
[[File:KnightsTour-3.png]]
Find a Hamiltonian cycle (a path that visits each square exactly one time.)
<
Find the end square:
<
Find shortest path from the start square to the end square.
<syntaxhighlight lang
=={{header|Mathprog}}==
Line 7,977 ⟶ 8,209:
2. It is possible to specify which square is used for any Knights Move.
<syntaxhighlight lang="text">
/*Knights.mathprog
Line 8,039 ⟶ 8,271:
end;
</syntaxhighlight>
Produces:
<syntaxhighlight lang="text">
GLPSOL: GLPK LP/MIP Solver, v4.47
Parameter(s) specified in the command line:
Line 8,089 ⟶ 8,321:
23 10 21 16 25
Model has been successfully processed
</syntaxhighlight>
and
<syntaxhighlight lang="text">
/*Knights.mathprog
Line 8,158 ⟶ 8,390:
end;
</syntaxhighlight>
Produces:
<syntaxhighlight lang="text">
GLPSOL: GLPK LP/MIP Solver, v4.47
Parameter(s) specified in the command line:
Line 8,227 ⟶ 8,459:
10 55 20 57 12 37 40 1
Model has been successfully processed
</syntaxhighlight>
=={{header|Nim}}==
Line 8,235 ⟶ 8,467:
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.
<
type
Line 8,336 ⟶ 8,568:
#run[5]("c4") # No solution, so very slow compared to other cases.
run[8]("b5")
run[31]("a1")</
{{out}}
Line 8,394 ⟶ 8,626:
=={{header|ObjectIcon}}==
{{trans|ATS}}
<
# Find Knight’s Tours.
#
Line 8,756 ⟶ 8,988:
return (((i_diff = 2 & j_diff = 1) |
(i_diff = 1 & j_diff = 2)) & &yes) | fail
end</
{{out}}
Line 8,819 ⟶ 9,051:
=={{header|Perl}}==
Knight's tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]]
<
use warnings;
# Find a knight's tour
Line 8,905 ⟶ 9,137:
return unless $square =~ /^([a-h])([1-8])$/;
return (8-$2, ord($1) - ord('a'));
}</
Sample output (start square c3):
Line 8,913 ⟶ 9,145:
=={{header|Phix}}==
This is pretty fast (<<1s) up to size 48, before some sizes start to take quite some time to complete. It will even solve a 200x200 in 0.67s
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">size</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span>
Line 8,998 ⟶ 9,230:
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"no solutions found\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</
{{out}}
<pre>
Line 9,014 ⟶ 9,246:
=={{header|Picat}}==
<
main =>
Line 9,049 ⟶ 9,281:
fill_output_matrix(N,OutputM,V,V[I],Count+1)
end.
</syntaxhighlight>
{{out}}
Line 9,064 ⟶ 9,296:
=={{header|PicoLisp}}==
<
# Build board
Line 9,093 ⟶ 9,325:
(moves Tour) )
(push 'Tour @) )
(flip Tour) )</
Output:
<pre>-> (b1 a3 b5 a7 c8 b6 a8 c7 a6 b8 d7 f8 h7 g5 h3 g1 e2 c1 a2 b4 c2 a1 b3 a5 b7
Line 9,101 ⟶ 9,333:
=={{header|PostScript}}==
You probably shouldn't send this to a printer. Solution using Warnsdorffs algorithm.
<
%%BoundingBox: 0 0 300 300
Line 9,210 ⟶ 9,442:
3 1 100 { solve } for
%%EOF</
=={{header|Prolog}}==
Line 9,216 ⟶ 9,448:
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]]
<
knight(N) :-
Max is N * N,
Line 9,296 ⟶ 9,528:
M1 is M + 1,
display(N, M1, T).
</syntaxhighlight>
Output :
Line 9,335 ⟶ 9,567:
===Alternative version===
{{Works with|GNU Prolog}}
<
Line 9,391 ⟶ 9,623:
main :- make_graph, hamiltonian(5*3,Pn), show_path(Pn), halt.</
{{Output}}
<pre> 5 18 35 22 3 16 55 24
Line 9,405 ⟶ 9,637:
=={{header|Python}}==
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]]
<
boardsize=6
Line 9,469 ⟶ 9,701:
start = input('Start position: ')
board = knights_tour(start, boardsize)
print(boardstring(board, boardsize=boardsize))</
;Sample runs
Line 9,550 ⟶ 9,782:
Based on a slight modification of [[wp:Knight%27s_tour#Warnsdorff.27s_rule|Warnsdorff's algorithm]], in that if a dead-end is reached, the program backtracks to the next best move.
<
# M x N Chess Board.
Line 9,618 ⟶ 9,850:
# Begin tour.
setboard(position, 1); knightTour(position, 2)</
Output:
Line 9,636 ⟶ 9,868:
=={{header|Racket}}==
<
#lang racket
(define N 8)
Line 9,661 ⟶ 9,893:
" "))))
(draw (tour (random N) (random N)))
</syntaxhighlight>
{{out}}
<pre>
Line 9,677 ⟶ 9,909:
(formerly Perl 6)
{{trans|Perl}}
<syntaxhighlight lang="raku"
my $I = 8;
Line 9,749 ⟶ 9,981:
sub from_algebraic($square where /^ (<[a..z]>) (\d+) $/) {
$I - $1, ord(~$0) - ord('a');
}</
(Output identical to Perl's above.)
Line 9,755 ⟶ 9,987:
{{trans|ATS}}
For use with the public domain ratfor77 translator and a FORTRAN 77 compiler.
<
#
# Find Knight’s Tours.
Line 10,404 ⟶ 10,636:
end
#-----------------------------------------------------------------------</
{{out}}
Line 10,474 ⟶ 10,706:
This is an ''open tour'' solution. (See this task's ''discussion'' page for an explanation, the section is ''The 7x7 problem''.)
<
parse arg N sRank sFile . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N=8 /*No boardsize specified? Use default.*/
Line 10,511 ⟶ 10,743:
end /*try different move. */
end /*t*/ /* [↑] all moves tried.*/
return 0 /*tour is not possible. */</
'''output''' when using the default input:
<pre>
Line 10,537 ⟶ 10,769:
=={{header|Ruby}}==
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_rule|Warnsdorffs rule]]
<
Cell = Struct.new(:value, :adj) do
def self.end=(end_val)
Line 10,608 ⟶ 10,840:
knight_tour(5,5,0,1)
knight_tour(12,12,1,1)</
Which produces:
<pre>
Line 10,654 ⟶ 10,886:
=={{header|Rust}}==
<
const SIZE: usize = 8;
Line 10,764 ⟶ 10,996:
None => println!("Fail!"),
}
}</
{{out}}
<pre>
Line 10,780 ⟶ 11,012:
=={{header|Scala}}==
<syntaxhighlight lang="scala">
val b=Seq.tabulate(8,8,8,8)((x,y,z,t)=>(1L<<(x*8+y),1L<<(z*8+t),f"${97+z}%c${49+t}%c",(x-z)*(x-z)+(y-t)*(y-t)==5)).flatten.flatten.flatten.filter(_._4).groupBy(_._1)
def f(p:Long,s:Long,v:Any){if(-1L!=s)b(p).foreach(x=>if((s&x._2)==0)f(x._2,s|x._2,v+x._3))else println(v)}
f(1,1,"a1")
</syntaxhighlight>
<pre>
a1b3a5b7c5a4b2c4a3b1c3a2b4a6b8c6a7b5c7a8b6c8d6e4d2f1e3c2d4e2c1d3e1g2f4d5e7g8h6f5h4g6h8f7d8e6f8d7e5g4h2f3g1h3g5h7f6e8g7h5g3h1f2d1
Line 10,790 ⟶ 11,022:
=={{header|Scheme}}==
<
;;/usr/bin/petite
;;encoding:utf-8
Line 10,837 ⟶ 11,069:
(display (map (lambda(x) (decode x)) result)))
(go (renew position))))
</syntaxhighlight>
{{out}}
<pre>
Line 10,846 ⟶ 11,078:
=={{header|SequenceL}}==
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_rule|Warnsdorffs rule]] (No Backtracking)
<syntaxhighlight lang="sequencel">
import <Utilities/Sequence.sl>;
import <Utilities/Conversion.sl>;
Line 10,897 ⟶ 11,129:
value when x = i and y = j else
board[i,j] foreach i within 1 ... size(board), j within 1 ... size(board[1]);
</syntaxhighlight>
{{out}}
8 X 8 board:
Line 10,936 ⟶ 11,168:
=={{header|Sidef}}==
{{trans|Raku}}
<
var I = 8
var J = 8
Line 10,996 ⟶ 11,228:
}
print "\n"
}</
=={{header|Swift}}==
Line 11,002 ⟶ 11,234:
{{trans|Rust}}
<
public var x: Int
public var y: Int
Line 11,131 ⟶ 11,363:
}
b.printBoard()</
{{out}}
Line 11,146 ⟶ 11,378:
=={{header|Tcl}}==
<
oo::class create KnightsTour {
Line 11,252 ⟶ 11,484:
expr {$a in [my ValidMoves $b]}
}
}</
Demonstrating:
<
$kt constructRandom
$kt print
Line 11,261 ⟶ 11,493:
} else {
puts "This is an open tour"
}</
Sample output:
<pre>
Line 11,273 ⟶ 11,505:
</pre>
The above code supports other sizes of boards and starting from nominated locations:
<
$kt constructFrom {0 0}
$kt print
Line 11,280 ⟶ 11,512:
} else {
puts "This is an open tour"
}</
Which could produce this output:
<pre>
Line 11,293 ⟶ 11,525:
=={{header|Wren}}==
{{trans|Kotlin}}
<
construct new(x, y) {
_x = x
Line 11,350 ⟶ 11,582:
System.write((col == 7) ? "\n" : " ")
col = (col + 1) % 8
}</
{{out}}
Line 11,365 ⟶ 11,597:
=={{header|XPL0}}==
<
int LegalX, LegalY; \arrays of legal moves
def IntSize=4; \number of bytes in an integer (4 or 2)
Line 11,415 ⟶ 11,647:
]
else Text(0, "No Solution.^M^J");
]</
Example output:
Line 11,434 ⟶ 11,666:
First we build a generic package for solving any kind of tour over the chess board. Here it is…
<syntaxhighlight lang="text">
<xsl:package xsl:version="3.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
Line 11,491 ⟶ 11,723:
</xsl:package>
</syntaxhighlight>
And now for the style-sheet to solve the Knight’s tour…
<syntaxhighlight lang="text">
<xsl:stylesheet version="3.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
Line 11,534 ⟶ 11,766:
</xsl:stylesheet>
</syntaxhighlight>
So an input like this…
<syntaxhighlight lang="text">
<tt>
<knight>
Line 11,544 ⟶ 11,776:
</knight>
</tt>
</syntaxhighlight>
…should be transformed in something like this…
<syntaxhighlight lang="text">
<tt>
<knight>
Line 11,557 ⟶ 11,789:
</knight>
</tt>
</syntaxhighlight>
=={{header|zkl}}==
<
// linear time.
// See Pohl, Ira (July 1967),
Line 11,607 ⟶ 11,839:
fcn(ns){ vm.arglist.apply("%2s".fmt).concat(",")+"\n" });
}
}</
<
b.println();</
{{out}}
<pre>
Line 11,623 ⟶ 11,855:
</pre>
Check that a solution for all squares is found:
<
{ b:=Board(); n:=b.knightsTour(x,y); if(n!=64) b.println(">>>",x,",",y) } ]];</
{{out}}Nada
| |||