Knight's tour: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: auto-vivification pretty reliable lately) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 25: | Line 25: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">V _kmoves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)] |
||
F chess2index(=chess, boardsize) |
F chess2index(=chess, boardsize) |
||
Line 81: | Line 81: | ||
V board = knights_tour(start, boardsize) |
V board = knights_tour(start, boardsize) |
||
print(boardstring(board, boardsize' boardsize)) |
print(boardstring(board, boardsize' boardsize)) |
||
print()</ |
print()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 124: | Line 124: | ||
=={{header|360 Assembly}}== |
=={{header|360 Assembly}}== |
||
{{trans|BBC PASIC}} |
{{trans|BBC PASIC}} |
||
< |
<syntaxhighlight lang="360asm">* Knight's tour 20/03/2017 |
||
KNIGHT CSECT |
KNIGHT CSECT |
||
USING KNIGHT,R13 base registers |
USING KNIGHT,R13 base registers |
||
Line 378: | Line 378: | ||
PG DC CL128' ' buffer |
PG DC CL128' ' buffer |
||
YREGS |
YREGS |
||
END KNIGHT</ |
END KNIGHT</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 396: | 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. |
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. |
||
< |
<syntaxhighlight lang="ada">generic |
||
Size: Integer; |
Size: Integer; |
||
package Knights_Tour is |
package Knights_Tour is |
||
Line 417: | Line 417: | ||
-- writes The_Tour to the output using Ada.Text_IO; |
-- writes The_Tour to the output using Ada.Text_IO; |
||
end Knights_Tour;</ |
end Knights_Tour;</syntaxhighlight> |
||
Here is the implementation: |
Here is the implementation: |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO, Ada.Integer_Text_IO; |
||
package body Knights_Tour is |
package body Knights_Tour is |
||
Line 505: | Line 505: | ||
end Tour_IO; |
end Tour_IO; |
||
end Knights_Tour;</ |
end Knights_Tour;</syntaxhighlight> |
||
Here is the main program: |
Here is the main program: |
||
< |
<syntaxhighlight lang="ada">with Knights_Tour, Ada.Command_Line; |
||
procedure Test_Knight is |
procedure Test_Knight is |
||
Line 519: | Line 519: | ||
begin |
begin |
||
KT.Tour_IO(KT.Get_Tour(1, 1)); |
KT.Tour_IO(KT.Get_Tour(1, 1)); |
||
end Test_Knight;</ |
end Test_Knight;</syntaxhighlight> |
||
For small sizes, this already works well (< 1 sec for size 8). Sample output: |
For small sizes, this already works well (< 1 sec for size 8). Sample output: |
||
Line 533: | 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. |
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"> |
|||
<lang Ada> |
|||
function Warnsdorff_Get_Tour(Start_X, Start_Y: Index; Scene: Tour := Empty) |
function Warnsdorff_Get_Tour(Start_X, Start_Y: Index; Scene: Tour := Empty) |
||
return Tour; |
return Tour; |
||
-- uses Warnsdorff heurisitic to find a tour faster |
-- uses Warnsdorff heurisitic to find a tour faster |
||
-- same interface as Get_Tour</ |
-- same interface as Get_Tour</syntaxhighlight> |
||
Its implementation is as follows. |
Its implementation is as follows. |
||
< |
<syntaxhighlight lang="ada"> function Warnsdorff_Get_Tour(Start_X, Start_Y: Index; Scene: Tour := Empty) |
||
return Tour is |
return Tour is |
||
Done: Boolean; |
Done: Boolean; |
||
Line 626: | Line 626: | ||
end if; |
end if; |
||
return Visited; |
return Visited; |
||
end Warnsdorff_Get_Tour;</ |
end Warnsdorff_Get_Tour;</syntaxhighlight> |
||
The modification for the main program is trivial: |
The modification for the main program is trivial: |
||
< |
<syntaxhighlight lang="ada">with Knights_Tour, Ada.Command_Line; |
||
procedure Test_Fast is |
procedure Test_Fast is |
||
Line 639: | Line 639: | ||
begin |
begin |
||
KT.Tour_IO(KT.Warnsdorff_Get_Tour(1, 1)); |
KT.Tour_IO(KT.Warnsdorff_Get_Tour(1, 1)); |
||
end Test_Fast;</ |
end Test_Fast;</syntaxhighlight> |
||
This works still well for somewhat larger sizes: |
This works still well for somewhat larger sizes: |
||
Line 670: | Line 670: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}} |
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}} |
||
< |
<syntaxhighlight lang="algol68"># Non-recursive Knight's Tour with Warnsdorff's algorithm # |
||
# If there are multiple choices, backtrack if the first choice doesn't # |
# If there are multiple choices, backtrack if the first choice doesn't # |
||
# find a solution # |
# find a solution # |
||
Line 957: | Line 957: | ||
FI |
FI |
||
)</ |
)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 979: | Line 979: | ||
ANSI BASIC doesn't allow function parameters to be passed by reference so X and Y were made global variables. |
ANSI BASIC doesn't allow function parameters to be passed by reference so X and Y were made global variables. |
||
< |
<syntaxhighlight lang="ansi standard basic">100 DECLARE EXTERNAL FUNCTION choosemove |
||
110 ! |
110 ! |
||
120 RANDOMIZE |
120 RANDOMIZE |
||
Line 1,053: | Line 1,053: | ||
820 IF X<0 OR X>7 OR Y<0 OR Y>7 THEN EXIT FUNCTION |
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 |
830 IF Board(X,Y)=FALSE THEN LET validmove = TRUE |
||
840 END FUNCTION</ |
840 END FUNCTION</syntaxhighlight> |
||
=={{header|ATS}}== |
=={{header|ATS}}== |
||
< |
<syntaxhighlight lang="ats">(* |
||
Find Knight’s Tours. |
Find Knight’s Tours. |
||
Line 1,782: | Line 1,782: | ||
val _ = make_and_fprint_tours (stdout_ref, 8, 8, i, j, max_tours, |
val _ = make_and_fprint_tours (stdout_ref, 8, 8, i, j, max_tours, |
||
closed_only) |
closed_only) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,845: | Line 1,845: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
{{libheader|GDIP}} |
{{libheader|GDIP}} |
||
< |
<syntaxhighlight lang="autohotkey">#SingleInstance, Force |
||
#NoEnv |
#NoEnv |
||
SetBatchLines, -1 |
SetBatchLines, -1 |
||
Line 1,940: | Line 1,940: | ||
If (A_Gui = 1) |
If (A_Gui = 1) |
||
PostMessage, 0xA1, 2 |
PostMessage, 0xA1, 2 |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
For start at b3 |
For start at b3 |
||
Line 1,947: | Line 1,947: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f KNIGHTS_TOUR.AWK [-v sr=x] [-v sc=x] |
# syntax: GAWK -f KNIGHTS_TOUR.AWK [-v sr=x] [-v sc=x] |
||
# |
# |
||
Line 2,016: | Line 2,016: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
<p>output:</p> |
<p>output:</p> |
||
<pre> |
<pre> |
||
Line 2,033: | Line 2,033: | ||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
[[Image:knights_tour_bbc.gif|right]] |
[[Image:knights_tour_bbc.gif|right]] |
||
< |
<syntaxhighlight lang="bbcbasic"> VDU 23,22,256;256;16,16,16,128 |
||
VDU 23,23,4;0;0;0; |
VDU 23,23,4;0;0;0; |
||
OFF |
OFF |
||
Line 2,092: | Line 2,092: | ||
DEF FNvalidmove(X%,Y%) |
DEF FNvalidmove(X%,Y%) |
||
IF X%<0 OR X%>7 OR Y%<0 OR Y%>7 THEN = FALSE |
IF X%<0 OR X%>7 OR Y%<0 OR Y%>7 THEN = FALSE |
||
= NOT(Board%(X%,Y%))</ |
= NOT(Board%(X%,Y%))</syntaxhighlight> |
||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
< |
<syntaxhighlight lang="bracmat"> ( knightsTour |
||
= validmoves WarnsdorffSort algebraicNotation init solve |
= validmoves WarnsdorffSort algebraicNotation init solve |
||
, x y fieldsToVisit |
, x y fieldsToVisit |
||
Line 2,199: | Line 2,199: | ||
$ (algebraicNotation$(solve$((!x.!y).!fieldsToVisit))) |
$ (algebraicNotation$(solve$((!x.!y).!fieldsToVisit))) |
||
) |
) |
||
& out$(knightsTour$a1);</ |
& out$(knightsTour$a1);</syntaxhighlight> |
||
<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> |
<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: | Line 2,207: | ||
The following draws on console the progress of the horsie. Specify board size on commandline, or use default 8. |
The following draws on console the progress of the horsie. Specify board size on commandline, or use default 8. |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <string.h> |
#include <string.h> |
||
Line 2,309: | Line 2,309: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C sharp}}== |
=={{header|C sharp}}== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 2,395: | Line 2,395: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
Line 2,402: | Line 2,402: | ||
Uses Warnsdorff's rule and (iterative) backtracking if that fails. |
Uses Warnsdorff's rule and (iterative) backtracking if that fails. |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <iomanip> |
#include <iomanip> |
||
#include <array> |
#include <array> |
||
Line 2,545: | Line 2,545: | ||
cout << b3 << endl; |
cout << b3 << endl; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
Line 2,605: | Line 2,605: | ||
For some reason, the interactive part does not work with sbcl, but it works fine wit clisp. |
For some reason, the interactive part does not work with sbcl, but it works fine wit clisp. |
||
< |
<syntaxhighlight lang="lisp">;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
||
;;; Solving the knight's tour. ;;; |
;;; Solving the knight's tour. ;;; |
||
;;; Warnsdorff's rule with random tie break. ;;; |
;;; Warnsdorff's rule with random tie break. ;;; |
||
Line 2,792: | Line 2,792: | ||
(prompt) |
(prompt) |
||
(main)</ |
(main)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Starting case (leave blank for random)? a8 |
<pre>Starting case (leave blank for random)? a8 |
||
Line 2,811: | Line 2,811: | ||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
Using warnsdorff's rule |
Using warnsdorff's rule |
||
<syntaxhighlight lang="clojure"> |
|||
<lang Clojure> |
|||
(defn isin? [x li] |
(defn isin? [x li] |
||
(not= [] (filter #(= x %) li))) |
(not= [] (filter #(= x %) li))) |
||
Line 2,837: | Line 2,837: | ||
(let [np (next-move mov pmoves n)] |
(let [np (next-move mov pmoves n)] |
||
(recur (conj mov np) (inc x))))))) |
(recur (conj mov np) (inc x))))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,854: | Line 2,854: | ||
=={{header|CoffeeScript}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="coffeescript"> |
||
graph_tours = (graph, max_num_solutions) -> |
graph_tours = (graph, max_num_solutions) -> |
||
# graph is an array of arrays |
# graph is an array of arrays |
||
Line 2,969: | Line 2,969: | ||
illustrate_knights_tour tours[0], BOARD_WIDTH |
illustrate_knights_tour tours[0], BOARD_WIDTH |
||
illustrate_knights_tour tours.pop(), BOARD_WIDTH |
illustrate_knights_tour tours.pop(), BOARD_WIDTH |
||
</syntaxhighlight> |
|||
</lang> |
|||
output |
output |
||
<lang> |
<syntaxhighlight lang="text"> |
||
> time coffee knight.coffee |
> time coffee knight.coffee |
||
100000 tours found (showing first and last) |
100000 tours found (showing first and last) |
||
Line 2,999: | Line 2,999: | ||
user 0m25.656s |
user 0m25.656s |
||
sys 0m0.253s |
sys 0m0.253s |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
===Fast Version=== |
===Fast Version=== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.random, std.range, |
||
std.conv, std.typecons, std.typetuple; |
std.conv, std.typecons, std.typetuple; |
||
Line 3,080: | Line 3,080: | ||
writeln(); |
writeln(); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>23 16 11 6 21 |
<pre>23 16 11 6 21 |
||
Line 3,131: | Line 3,131: | ||
===Shorter Version=== |
===Shorter Version=== |
||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.math, std.algorithm, std.range, std.typecons; |
||
alias Square = Tuple!(int,"x", int,"y"); |
alias Square = Tuple!(int,"x", int,"y"); |
||
Line 3,157: | Line 3,157: | ||
const board = iota(1, 9).cartesianProduct(iota(1, 9)).map!Square.array; |
const board = iota(1, 9).cartesianProduct(iota(1, 9)).map!Square.array; |
||
writefln("%(%-(%s -> %)\n%)", board.knightTour([sq]).map!toAlg.chunks(8)); |
writefln("%(%-(%s -> %)\n%)", board.knightTour([sq]).map!toAlg.chunks(8)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>e5 -> d7 -> b8 -> a6 -> b4 -> a2 -> c1 -> b3 |
<pre>e5 -> d7 -> b8 -> a6 -> b4 -> a2 -> c1 -> b3 |
||
Line 3,171: | Line 3,171: | ||
The algorithm uses iterative backtracking and Warnsdorff's heuristic. It can output closed or non-closed tours. |
The algorithm uses iterative backtracking and Warnsdorff's heuristic. It can output closed or non-closed tours. |
||
< |
<syntaxhighlight lang="lisp"> |
||
(require 'plot) |
(require 'plot) |
||
(define *knight-moves* |
(define *knight-moves* |
||
Line 3,240: | Line 3,240: | ||
(play starter 0 starter (dim n) wants-open) |
(play starter 0 starter (dim n) wants-open) |
||
(catch (hit mess) (show-steps n wants-open)))) |
(catch (hit mess) (show-steps n wants-open)))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="lisp"> |
||
(k-tour 8 0 #f) |
(k-tour 8 0 #f) |
||
♞-closed-tour: 66 tries. |
♞-closed-tour: 66 tries. |
||
Line 3,278: | Line 3,278: | ||
79 76 83 18 91 74 137 16 169 72 153 14 167 70 157 12 63 68 55 10 |
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 |
82 19 80 75 84 17 92 73 152 15 168 71 154 13 62 69 54 11 52 67 |
||
</syntaxhighlight> |
|||
</lang> |
|||
;Plotting: |
;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). |
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). |
||
< |
<syntaxhighlight lang="lisp"> |
||
(define (step-color x y n last-one) |
(define (step-color x y n last-one) |
||
(letrec ((sq (square (floor x) (floor y) n)) |
(letrec ((sq (square (floor x) (floor y) n)) |
||
Line 3,292: | Line 3,292: | ||
(define ( k-plot n) |
(define ( k-plot n) |
||
(plot-rgb (lambda (x y) (step-color x y n (dim n))) (- n epsilon) (- n epsilon))) |
(plot-rgb (lambda (x y) (step-color x y n (dim n))) (- n epsilon) (- n epsilon))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Line 3,301: | Line 3,301: | ||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="elixir">defmodule Board do |
||
import Integer, only: [is_odd: 1] |
import Integer, only: [is_odd: 1] |
||
Line 3,364: | Line 3,364: | ||
Board.knight_tour(4,9,1,1) |
Board.knight_tour(4,9,1,1) |
||
Board.knight_tour(5,5,1,2) |
Board.knight_tour(5,5,1,2) |
||
Board.knight_tour(12,12,2,2)</ |
Board.knight_tour(12,12,2,2)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,410: | Line 3,410: | ||
=={{header|Elm}}== |
=={{header|Elm}}== |
||
< |
<syntaxhighlight lang="elm">module Main exposing (main) |
||
import Browser exposing (element) |
import Browser exposing (element) |
||
Line 3,755: | Line 3,755: | ||
, subscriptions = subscriptions |
, subscriptions = subscriptions |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Link to live demo: https://dmcbane.github.io/knights-tour/ |
Link to live demo: https://dmcbane.github.io/knights-tour/ |
||
Line 3,761: | Line 3,761: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
Again I use backtracking. It seemed easier this time. |
Again I use backtracking. It seemed easier this time. |
||
<syntaxhighlight lang="erlang"> |
|||
<lang Erlang> |
|||
-module( knights_tour ). |
-module( knights_tour ). |
||
Line 3,840: | Line 3,840: | ||
next_moves_row( 8 ) -> [6, 7]; |
next_moves_row( 8 ) -> [6, 7]; |
||
next_moves_row( N ) -> [N - 2, N - 1, N + 1, N + 2]. |
next_moves_row( N ) -> [N - 2, N - 1, N + 1, N + 2]. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,866: | Line 3,866: | ||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
Taken from ERRE distribution disk. Comments are in Italian. |
Taken from ERRE distribution disk. Comments are in Italian. |
||
<syntaxhighlight lang="erre"> |
|||
<lang ERRE> |
|||
! ********************************************************************** |
! ********************************************************************** |
||
! * * |
! * * |
||
Line 4,076: | Line 4,076: | ||
UNTIL A$<>"" |
UNTIL A$<>"" |
||
END PROGRAM |
END PROGRAM |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> *** LA GALOPPATA DEL CAVALIERE *** |
<pre> *** LA GALOPPATA DEL CAVALIERE *** |
||
Line 4,097: | Line 4,097: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic"> |
||
Dim Shared As Integer tamano, xc, yc, nm |
Dim Shared As Integer tamano, xc, yc, nm |
||
Dim As Integer f, qm, nmov, n = 0 |
Dim As Integer f, qm, nmov, n = 0 |
||
Line 4,155: | Line 4,155: | ||
Sleep |
Sleep |
||
End |
End |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
[https://www.dropbox.com/s/s3bpwechpoueum4/Knights%20Tour%20FreeBasic.png?dl=0 Knights Tour FreeBasic image] |
[https://www.dropbox.com/s/s3bpwechpoueum4/Knights%20Tour%20FreeBasic.png?dl=0 Knights Tour FreeBasic image] |
||
Line 4,191: | Line 4,191: | ||
{{works with|gfortran|11.2.1}} |
{{works with|gfortran|11.2.1}} |
||
{{works with|f2c}} |
{{works with|f2c}} |
||
< |
<syntaxhighlight lang="fortran">C----------------------------------------------------------------------- |
||
C |
C |
||
C Find Knight’s Tours. |
C Find Knight’s Tours. |
||
Line 4,841: | Line 4,841: | ||
end |
end |
||
C-----------------------------------------------------------------------</ |
C-----------------------------------------------------------------------</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
$ echo "c5 2 T" | ./knights_tour |
$ echo "c5 2 T" | ./knights_tour |
||
Line 4,904: | Line 4,904: | ||
{{works with|gfortran|11.2.1}} |
{{works with|gfortran|11.2.1}} |
||
{{trans|ATS}} |
{{trans|ATS}} |
||
< |
<syntaxhighlight lang="fortran">!----------------------------------------------------------------------- |
||
! |
! |
||
! Find Knight’s Tours. |
! Find Knight’s Tours. |
||
Line 5,464: | Line 5,464: | ||
end program |
end program |
||
!-----------------------------------------------------------------------</ |
!-----------------------------------------------------------------------</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,528: | Line 5,528: | ||
{{works with|gfortran|11.2.1}} |
{{works with|gfortran|11.2.1}} |
||
(This one is ''not'' a translation of my ATS implementation. I wrote it earlier.) |
(This one is ''not'' a translation of my ATS implementation. I wrote it earlier.) |
||
< |
<syntaxhighlight lang="fortran">!!! |
||
!!! Find a Knight’s Tour. |
!!! Find a Knight’s Tour. |
||
!!! |
!!! |
||
Line 5,853: | Line 5,853: | ||
end if |
end if |
||
end do |
end do |
||
end program knights_tour_main</ |
end program knights_tour_main</syntaxhighlight> |
||
$ ./knights_tour a1 b2 c3 |
$ ./knights_tour a1 b2 c3 |
||
Line 5,885: | Line 5,885: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
===Warnsdorf's rule=== |
===Warnsdorf's rule=== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 5,992: | Line 5,992: | ||
} |
} |
||
return true |
return true |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 6,005: | Line 6,005: | ||
</pre> |
</pre> |
||
===Ant colony=== |
===Ant colony=== |
||
< |
<syntaxhighlight lang="go">/* Adapted from "Enumerating Knight's Tours using an Ant Colony Algorithm" |
||
by Philip Hingston and Graham Kendal, |
by Philip Hingston and Graham Kendal, |
||
PDF at http://www.cs.nott.ac.uk/~gxk/papers/cec05knights.pdf. */ |
PDF at http://www.cs.nott.ac.uk/~gxk/papers/cec05knights.pdf. */ |
||
Line 6,196: | Line 6,196: | ||
tourCh <- moves |
tourCh <- moves |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 6,212: | Line 6,212: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.Bifunctor (bimap) |
||
import Data.Char (chr, ord) |
import Data.Char (chr, ord) |
||
import Data.List (intercalate, minimumBy, sort, (\\)) |
import Data.List (intercalate, minimumBy, sort, (\\)) |
||
Line 6,273: | Line 6,273: | ||
printTour tour = do |
printTour tour = do |
||
putStrLn $ intercalate " -> " $ take 8 tour |
putStrLn $ intercalate " -> " $ take 8 tour |
||
printTour $ drop 8 tour</ |
printTour $ drop 8 tour</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>e5 -> f7 -> h8 -> g6 -> h4 -> g2 -> e1 -> f3 |
<pre>e5 -> f7 -> h8 -> g6 -> h4 -> g2 -> e1 -> f3 |
||
Line 6,291: | Line 6,291: | ||
The algorithm doesn't always generate a complete tour. |
The algorithm doesn't always generate a complete tour. |
||
< |
<syntaxhighlight lang="icon">link printf |
||
procedure main(A) |
procedure main(A) |
||
Line 6,391: | Line 6,391: | ||
} |
} |
||
every write(hdr2|hdr1|&null) |
every write(hdr2|hdr1|&null) |
||
end</ |
end</syntaxhighlight> |
||
The following can be used when debugging to validate the board structure and to image the available moves on the board. |
The following can be used when debugging to validate the board structure and to image the available moves on the board. |
||
< |
<syntaxhighlight lang="icon">procedure DumpBoard(B) #: Dump Board internals |
||
write("Board size=",B.N) |
write("Board size=",B.N) |
||
write("Available Moves at start of tour:", ImageMovesTo(B.movesto)) |
write("Available Moves at start of tour:", ImageMovesTo(B.movesto)) |
||
Line 6,404: | Line 6,404: | ||
every s ||:= " " || (!sort(movesto[k])|"\n") |
every s ||:= " " || (!sort(movesto[k])|"\n") |
||
return s |
return s |
||
end</ |
end</syntaxhighlight> |
||
Line 6,456: | Line 6,456: | ||
'''Solution:'''<br> |
'''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]]. |
[[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]]. |
||
< |
<syntaxhighlight lang="j">NB. knight moves for each square of a (y,y) board |
||
kmoves=: monad define |
kmoves=: monad define |
||
t=. (>,{;~i.y) +"1/ _2]\2 1 2 _1 1 2 1 _2 _1 2 _1 _2 _2 1 _2 _1 |
t=. (>,{;~i.y) +"1/ _2]\2 1 2 _1 1 2 1 _2 _1 2 _1 _2 _2 1 _2 _1 |
||
Line 6,472: | Line 6,472: | ||
assert. ~:p |
assert. ~:p |
||
(,~y)$/:p |
(,~y)$/:p |
||
)</ |
)</syntaxhighlight> |
||
'''Example Use:''' |
'''Example Use:''' |
||
< |
<syntaxhighlight lang="j"> ktourw 8 NB. solution for an 8 x 8 board |
||
0 25 14 23 28 49 12 31 |
0 25 14 23 28 49 12 31 |
||
15 22 27 50 13 30 63 48 |
15 22 27 50 13 30 63 48 |
||
Line 6,496: | Line 6,496: | ||
555 558 553 778 563 570 775 780 785 772 1000... |
555 558 553 778 563 570 775 780 785 772 1000... |
||
100 551 556 561 102 777 572 771 104 781 57... |
100 551 556 561 102 777 572 771 104 781 57... |
||
557 554 101 552 571 562 103 776 573 770 10...</ |
557 554 101 552 571 562 103 776 573 770 10...</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{Works with|Java|7}} |
{{Works with|Java|7}} |
||
< |
<syntaxhighlight lang="java">import java.util.*; |
||
public class KnightsTour { |
public class KnightsTour { |
||
Line 6,597: | Line 6,597: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>34 17 20 3 36 7 22 5 |
<pre>34 17 20 3 36 7 22 5 |
||
19 2 35 40 21 4 37 8 |
19 2 35 40 21 4 37 8 |
||
Line 6,608: | Line 6,608: | ||
===More efficient non-trackback solution=== |
===More efficient non-trackback solution=== |
||
{{Works with|Java|8}} |
{{Works with|Java|8}} |
||
<lang> |
<syntaxhighlight lang="text"> |
||
package com.knight.tour; |
package com.knight.tour; |
||
import java.util.ArrayList; |
import java.util.ArrayList; |
||
Line 6,767: | Line 6,767: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
Found a path for 8 X 8 chess board. |
Found a path for 8 X 8 chess board. |
||
Line 6,784: | Line 6,784: | ||
You can test it [http://paulo-jorente.de/webgames/repos/knightsTour/ here]. |
You can test it [http://paulo-jorente.de/webgames/repos/knightsTour/ here]. |
||
< |
<syntaxhighlight lang="javascript"> |
||
class KnightTour { |
class KnightTour { |
||
constructor() { |
constructor() { |
||
Line 7,000: | Line 7,000: | ||
} |
} |
||
new KnightTour(); |
new KnightTour(); |
||
</syntaxhighlight> |
|||
</lang> |
|||
To test it, you'll need an index.html |
To test it, you'll need an index.html |
||
<pre> |
<pre> |
||
Line 7,070: | Line 7,070: | ||
A composition of values, drawing on generic abstractions: |
A composition of values, drawing on generic abstractions: |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 7,363: | Line 7,363: | ||
// MAIN --- |
// MAIN --- |
||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>(Board size 8*8) |
<pre>(Board size 8*8) |
||
Line 7,392: | Line 7,392: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Uses the Hidato puzzle solver module, which has its source code listed [[Solve_a_Hidato_puzzle#Julia | here]] in the Hadato task. |
Uses the Hidato puzzle solver module, which has its source code listed [[Solve_a_Hidato_puzzle#Julia | here]] in the Hadato task. |
||
< |
<syntaxhighlight lang="julia">using .Hidato # Note that the . here means to look locally for the module rather than in the libraries |
||
const chessboard = """ |
const chessboard = """ |
||
Line 7,410: | Line 7,410: | ||
hidatosolve(board, maxmoves, knightmoves, fixed, starts[1][1], starts[1][2], 1) |
hidatosolve(board, maxmoves, knightmoves, fixed, starts[1][1], starts[1][2], 1) |
||
printboard(board) |
printboard(board) |
||
</ |
</syntaxhighlight>{{output}}<pre> |
||
0 0 0 0 0 0 0 0 |
0 0 0 0 0 0 0 0 |
||
0 0 0 0 0 0 0 0 |
0 0 0 0 0 0 0 0 |
||
Line 7,433: | Line 7,433: | ||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
< |
<syntaxhighlight lang="scala">data class Square(val x : Int, val y : Int) |
||
val board = Array(8 * 8, { Square(it / 8 + 1, it % 8 + 1) }) |
val board = Array(8 * 8, { Square(it / 8 + 1, it % 8 + 1) }) |
||
Line 7,461: | Line 7,461: | ||
col = (col + 1) % 8 |
col = (col + 1) % 8 |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 7,477: | Line 7,477: | ||
Influenced by the Python version, although computed tours are different. |
Influenced by the Python version, although computed tours are different. |
||
< |
<syntaxhighlight lang="locobasic">10 mode 1:defint a-z |
||
20 input "Board size: ",size |
20 input "Board size: ",size |
||
30 input "Start position: ",a$ |
30 input "Start position: ",a$ |
||
Line 7,523: | Line 7,523: | ||
450 ' skip this move |
450 ' skip this move |
||
460 next |
460 next |
||
470 return</ |
470 return</syntaxhighlight> |
||
[[File:Knights tour Locomotive Basic.png]] |
[[File:Knights tour Locomotive Basic.png]] |
||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">N = 8 |
||
moves = { {1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2} } |
moves = { {1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2} } |
||
Line 7,578: | Line 7,578: | ||
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] ) ) |
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] |
last = lst[i] |
||
end</ |
end</syntaxhighlight> |
||
=={{header|M2000 Interpreter}}== |
=={{header|M2000 Interpreter}}== |
||
<syntaxhighlight lang="m2000 interpreter"> |
|||
<lang M2000 Interpreter> |
|||
Function KnightTour$(StartW=1, StartH=1){ |
Function KnightTour$(StartW=1, StartH=1){ |
||
def boolean swapH, swapV=True |
def boolean swapH, swapV=True |
||
Line 7,683: | Line 7,683: | ||
Clipboard ex$ |
Clipboard ex$ |
||
Report ex$ |
Report ex$ |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 7,730: | Line 7,730: | ||
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.) |
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.) |
||
< |
<syntaxhighlight lang="m4">divert(-1) |
||
---------------------------------------------------------------------- |
---------------------------------------------------------------------- |
||
Line 7,908: | Line 7,908: | ||
find_tour(a1) |
find_tour(a1) |
||
find_tour(c5) |
find_tour(c5) |
||
find_tour(h8)</ |
find_tour(h8)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 7,920: | Line 7,920: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
'''Solution''' |
'''Solution''' |
||
< |
<syntaxhighlight lang="mathematica">knightsTourMoves[start_] := |
||
Module[{ |
Module[{ |
||
vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <> ToString[Mod[# - 1, 8] + 1]) & /@ Range[64], knightsGraph, |
vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <> ToString[Mod[# - 1, 8] + 1]) & /@ Range[64], knightsGraph, |
||
Line 7,927: | Line 7,927: | ||
hamiltonianCycle = ((FindHamiltonianCycle[knightsGraph] /. UndirectedEdge -> DirectedEdge) /. labels)[[1]]; |
hamiltonianCycle = ((FindHamiltonianCycle[knightsGraph] /. UndirectedEdge -> DirectedEdge) /. labels)[[1]]; |
||
end = Cases[hamiltonianCycle, (x_ \[DirectedEdge] start) :> x][[1]]; |
end = Cases[hamiltonianCycle, (x_ \[DirectedEdge] start) :> x][[1]]; |
||
FindShortestPath[g, start, end]]</ |
FindShortestPath[g, start, end]]</syntaxhighlight> |
||
'''Usage''' |
'''Usage''' |
||
< |
<syntaxhighlight lang="mathematica">knightsTourMoves["d8"] |
||
(* out *) |
(* out *) |
||
Line 7,936: | Line 7,936: | ||
"c7", "a8", "b6", "c8", "d6", "e4", "d2", "f1", "e3", "d1", "f2", "h1", "g3", "e2", "c1", "d3", "e1", "g2", "h4", "f5", "e7", "d5", \ |
"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"} |
"f4", "h5", "g7", "e8", "f6", "g8", "h6", "g4", "h2", "f3", "g1", "h3", "g5", "h7", "f8", "d7", "e5", "g6", "h8", "f7"} |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Analysis''' |
'''Analysis''' |
||
'''vertexLabels''' replaces the default vertex (i.e. square) names of the chessboard with the standard algebraic names "a1", "a2",...,"h8". |
'''vertexLabels''' replaces the default vertex (i.e. square) names of the chessboard with the standard algebraic names "a1", "a2",...,"h8". |
||
<syntaxhighlight lang="mathematica"> |
|||
<lang Mathematica> |
|||
vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <> ToString[Mod[# - 1, 8] + 1]) & /@ Range[64] |
vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <> ToString[Mod[# - 1, 8] + 1]) & /@ Range[64] |
||
Line 7,952: | Line 7,952: | ||
41 -> "f1", 42 -> "f2", 43 -> "f3", 44 -> "f4", 45 -> "f5", 46 -> "f6", 47 -> "f7", 48 -> "f8", |
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", |
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"}</ |
57 -> "h1", 58 -> "h2", 59 -> "h3", 60 -> "h4", 61 -> "h5", 62 -> "h6", 63 -> "h7", 64 -> "h8"}</syntaxhighlight> |
||
'''knightsGraph''' creates a graph of the solution space. |
'''knightsGraph''' creates a graph of the solution space. |
||
< |
<syntaxhighlight lang="mathematica">knightsGraph = KnightTourGraph[i, i, VertexLabels -> vertexLabels, ImagePadding -> 15];</syntaxhighlight> |
||
[[File:KnightsTour-3.png]] |
[[File:KnightsTour-3.png]] |
||
Find a Hamiltonian cycle (a path that visits each square exactly one time.) |
Find a Hamiltonian cycle (a path that visits each square exactly one time.) |
||
< |
<syntaxhighlight lang="mathematica">hamiltonianCycle = ((FindHamiltonianCycle[knightsGraph] /. UndirectedEdge -> DirectedEdge) /. labels)[[1]];</syntaxhighlight> |
||
Find the end square: |
Find the end square: |
||
< |
<syntaxhighlight lang="mathematica">end = Cases[hamiltonianCycle, (x_ \[DirectedEdge] start) :> x][[1]];</syntaxhighlight> |
||
Find shortest path from the start square to the end square. |
Find shortest path from the start square to the end square. |
||
<lang |
<syntaxhighlight lang="mathematica">FindShortestPath[g, start, end]]</syntaxhighlight> |
||
=={{header|Mathprog}}== |
=={{header|Mathprog}}== |
||
Line 7,977: | Line 7,977: | ||
2. It is possible to specify which square is used for any Knights Move. |
2. It is possible to specify which square is used for any Knights Move. |
||
<lang> |
<syntaxhighlight lang="text"> |
||
/*Knights.mathprog |
/*Knights.mathprog |
||
Line 8,039: | Line 8,039: | ||
end; |
end; |
||
</syntaxhighlight> |
|||
</lang> |
|||
Produces: |
Produces: |
||
<lang> |
<syntaxhighlight lang="text"> |
||
GLPSOL: GLPK LP/MIP Solver, v4.47 |
GLPSOL: GLPK LP/MIP Solver, v4.47 |
||
Parameter(s) specified in the command line: |
Parameter(s) specified in the command line: |
||
Line 8,089: | Line 8,089: | ||
23 10 21 16 25 |
23 10 21 16 25 |
||
Model has been successfully processed |
Model has been successfully processed |
||
</syntaxhighlight> |
|||
</lang> |
|||
and |
and |
||
<lang> |
<syntaxhighlight lang="text"> |
||
/*Knights.mathprog |
/*Knights.mathprog |
||
Line 8,158: | Line 8,158: | ||
end; |
end; |
||
</syntaxhighlight> |
|||
</lang> |
|||
Produces: |
Produces: |
||
<lang> |
<syntaxhighlight lang="text"> |
||
GLPSOL: GLPK LP/MIP Solver, v4.47 |
GLPSOL: GLPK LP/MIP Solver, v4.47 |
||
Parameter(s) specified in the command line: |
Parameter(s) specified in the command line: |
||
Line 8,227: | Line 8,227: | ||
10 55 20 57 12 37 40 1 |
10 55 20 57 12 37 40 1 |
||
Model has been successfully processed |
Model has been successfully processed |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
Line 8,235: | Line 8,235: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="nim">import algorithm, options, random, parseutils, strutils, strformat |
||
type |
type |
||
Line 8,336: | Line 8,336: | ||
#run[5]("c4") # No solution, so very slow compared to other cases. |
#run[5]("c4") # No solution, so very slow compared to other cases. |
||
run[8]("b5") |
run[8]("b5") |
||
run[31]("a1")</ |
run[31]("a1")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 8,394: | Line 8,394: | ||
=={{header|ObjectIcon}}== |
=={{header|ObjectIcon}}== |
||
{{trans|ATS}} |
{{trans|ATS}} |
||
< |
<syntaxhighlight lang="objecticon"># |
||
# Find Knight’s Tours. |
# Find Knight’s Tours. |
||
# |
# |
||
Line 8,756: | Line 8,756: | ||
return (((i_diff = 2 & j_diff = 1) | |
return (((i_diff = 2 & j_diff = 1) | |
||
(i_diff = 1 & j_diff = 2)) & &yes) | fail |
(i_diff = 1 & j_diff = 2)) & &yes) | fail |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 8,819: | Line 8,819: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Knight's tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]] |
Knight's tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]] |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
# Find a knight's tour |
# Find a knight's tour |
||
Line 8,905: | Line 8,905: | ||
return unless $square =~ /^([a-h])([1-8])$/; |
return unless $square =~ /^([a-h])([1-8])$/; |
||
return (8-$2, ord($1) - ord('a')); |
return (8-$2, ord($1) - ord('a')); |
||
}</ |
}</syntaxhighlight> |
||
Sample output (start square c3): |
Sample output (start square c3): |
||
Line 8,913: | Line 8,913: | ||
=={{header|Phix}}== |
=={{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 |
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 |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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> |
<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: | Line 8,998: | ||
<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: #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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 9,014: | Line 9,014: | ||
=={{header|Picat}}== |
=={{header|Picat}}== |
||
< |
<syntaxhighlight lang="picat">import cp. |
||
main => |
main => |
||
Line 9,049: | Line 9,049: | ||
fill_output_matrix(N,OutputM,V,V[I],Count+1) |
fill_output_matrix(N,OutputM,V,V[I],Count+1) |
||
end. |
end. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 9,064: | Line 9,064: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(load "@lib/simul.l") |
||
# Build board |
# Build board |
||
Line 9,093: | Line 9,093: | ||
(moves Tour) ) |
(moves Tour) ) |
||
(push 'Tour @) ) |
(push 'Tour @) ) |
||
(flip Tour) )</ |
(flip Tour) )</syntaxhighlight> |
||
Output: |
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 |
<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: | Line 9,101: | ||
=={{header|PostScript}}== |
=={{header|PostScript}}== |
||
You probably shouldn't send this to a printer. Solution using Warnsdorffs algorithm. |
You probably shouldn't send this to a printer. Solution using Warnsdorffs algorithm. |
||
< |
<syntaxhighlight lang="postscript">%!PS-Adobe-3.0 |
||
%%BoundingBox: 0 0 300 300 |
%%BoundingBox: 0 0 300 300 |
||
Line 9,210: | Line 9,210: | ||
3 1 100 { solve } for |
3 1 100 { solve } for |
||
%%EOF</ |
%%EOF</syntaxhighlight> |
||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
Line 9,216: | Line 9,216: | ||
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]] |
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]] |
||
< |
<syntaxhighlight lang="prolog">% N is the number of lines of the chessboard |
||
knight(N) :- |
knight(N) :- |
||
Max is N * N, |
Max is N * N, |
||
Line 9,296: | Line 9,296: | ||
M1 is M + 1, |
M1 is M + 1, |
||
display(N, M1, T). |
display(N, M1, T). |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output : |
Output : |
||
Line 9,335: | Line 9,335: | ||
===Alternative version=== |
===Alternative version=== |
||
{{Works with|GNU Prolog}} |
{{Works with|GNU Prolog}} |
||
< |
<syntaxhighlight lang="prolog">:- initialization(main). |
||
Line 9,391: | Line 9,391: | ||
main :- make_graph, hamiltonian(5*3,Pn), show_path(Pn), halt.</ |
main :- make_graph, hamiltonian(5*3,Pn), show_path(Pn), halt.</syntaxhighlight> |
||
{{Output}} |
{{Output}} |
||
<pre> 5 18 35 22 3 16 55 24 |
<pre> 5 18 35 22 3 16 55 24 |
||
Line 9,405: | Line 9,405: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]] |
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]] |
||
< |
<syntaxhighlight lang="python">import copy |
||
boardsize=6 |
boardsize=6 |
||
Line 9,469: | Line 9,469: | ||
start = input('Start position: ') |
start = input('Start position: ') |
||
board = knights_tour(start, boardsize) |
board = knights_tour(start, boardsize) |
||
print(boardstring(board, boardsize=boardsize))</ |
print(boardstring(board, boardsize=boardsize))</syntaxhighlight> |
||
;Sample runs |
;Sample runs |
||
Line 9,550: | Line 9,550: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="r">#!/usr/bin/Rscript |
||
# M x N Chess Board. |
# M x N Chess Board. |
||
Line 9,618: | Line 9,618: | ||
# Begin tour. |
# Begin tour. |
||
setboard(position, 1); knightTour(position, 2)</ |
setboard(position, 1); knightTour(position, 2)</syntaxhighlight> |
||
Output: |
Output: |
||
Line 9,636: | Line 9,636: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
(define N 8) |
(define N 8) |
||
Line 9,661: | Line 9,661: | ||
" ")))) |
" ")))) |
||
(draw (tour (random N) (random N))) |
(draw (tour (random N) (random N))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 9,677: | Line 9,677: | ||
(formerly Perl 6) |
(formerly Perl 6) |
||
{{trans|Perl}} |
{{trans|Perl}} |
||
<lang |
<syntaxhighlight lang="raku" line>my @board; |
||
my $I = 8; |
my $I = 8; |
||
Line 9,749: | Line 9,749: | ||
sub from_algebraic($square where /^ (<[a..z]>) (\d+) $/) { |
sub from_algebraic($square where /^ (<[a..z]>) (\d+) $/) { |
||
$I - $1, ord(~$0) - ord('a'); |
$I - $1, ord(~$0) - ord('a'); |
||
}</ |
}</syntaxhighlight> |
||
(Output identical to Perl's above.) |
(Output identical to Perl's above.) |
||
Line 9,755: | Line 9,755: | ||
{{trans|ATS}} |
{{trans|ATS}} |
||
For use with the public domain ratfor77 translator and a FORTRAN 77 compiler. |
For use with the public domain ratfor77 translator and a FORTRAN 77 compiler. |
||
< |
<syntaxhighlight lang="ratfor">#----------------------------------------------------------------------- |
||
# |
# |
||
# Find Knight’s Tours. |
# Find Knight’s Tours. |
||
Line 10,404: | Line 10,404: | ||
end |
end |
||
#-----------------------------------------------------------------------</ |
#-----------------------------------------------------------------------</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 10,474: | Line 10,474: | ||
This is an ''open tour'' solution. (See this task's ''discussion'' page for an explanation, the section is ''The 7x7 problem''.) |
This is an ''open tour'' solution. (See this task's ''discussion'' page for an explanation, the section is ''The 7x7 problem''.) |
||
< |
<syntaxhighlight lang="rexx">/*REXX program solves the knight's tour problem for a (general) NxN chessboard.*/ |
||
parse arg N sRank sFile . /*obtain optional arguments from the CL*/ |
parse arg N sRank sFile . /*obtain optional arguments from the CL*/ |
||
if N=='' | N=="," then N=8 /*No boardsize specified? Use default.*/ |
if N=='' | N=="," then N=8 /*No boardsize specified? Use default.*/ |
||
Line 10,511: | Line 10,511: | ||
end /*try different move. */ |
end /*try different move. */ |
||
end /*t*/ /* [↑] all moves tried.*/ |
end /*t*/ /* [↑] all moves tried.*/ |
||
return 0 /*tour is not possible. */</ |
return 0 /*tour is not possible. */</syntaxhighlight> |
||
'''output''' when using the default input: |
'''output''' when using the default input: |
||
<pre> |
<pre> |
||
Line 10,537: | Line 10,537: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_rule|Warnsdorffs rule]] |
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_rule|Warnsdorffs rule]] |
||
< |
<syntaxhighlight lang="ruby">class Board |
||
Cell = Struct.new(:value, :adj) do |
Cell = Struct.new(:value, :adj) do |
||
def self.end=(end_val) |
def self.end=(end_val) |
||
Line 10,608: | Line 10,608: | ||
knight_tour(5,5,0,1) |
knight_tour(5,5,0,1) |
||
knight_tour(12,12,1,1)</ |
knight_tour(12,12,1,1)</syntaxhighlight> |
||
Which produces: |
Which produces: |
||
<pre> |
<pre> |
||
Line 10,654: | Line 10,654: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">use std::fmt; |
||
const SIZE: usize = 8; |
const SIZE: usize = 8; |
||
Line 10,764: | Line 10,764: | ||
None => println!("Fail!"), |
None => println!("Fail!"), |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 10,780: | Line 10,780: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
<syntaxhighlight lang="scala"> |
|||
<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) |
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)} |
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") |
f(1,1,"a1") |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
a1b3a5b7c5a4b2c4a3b1c3a2b4a6b8c6a7b5c7a8b6c8d6e4d2f1e3c2d4e2c1d3e1g2f4d5e7g8h6f5h4g6h8f7d8e6f8d7e5g4h2f3g1h3g5h7f6e8g7h5g3h1f2d1 |
a1b3a5b7c5a4b2c4a3b1c3a2b4a6b8c6a7b5c7a8b6c8d6e4d2f1e3c2d4e2c1d3e1g2f4d5e7g8h6f5h4g6h8f7d8e6f8d7e5g4h2f3g1h3g5h7f6e8g7h5g3h1f2d1 |
||
Line 10,790: | Line 10,790: | ||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
;;/usr/bin/petite |
;;/usr/bin/petite |
||
;;encoding:utf-8 |
;;encoding:utf-8 |
||
Line 10,837: | Line 10,837: | ||
(display (map (lambda(x) (decode x)) result))) |
(display (map (lambda(x) (decode x)) result))) |
||
(go (renew position)))) |
(go (renew position)))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 10,846: | Line 10,846: | ||
=={{header|SequenceL}}== |
=={{header|SequenceL}}== |
||
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_rule|Warnsdorffs rule]] (No Backtracking) |
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_rule|Warnsdorffs rule]] (No Backtracking) |
||
<syntaxhighlight lang="sequencel"> |
|||
<lang sequenceL> |
|||
import <Utilities/Sequence.sl>; |
import <Utilities/Sequence.sl>; |
||
import <Utilities/Conversion.sl>; |
import <Utilities/Conversion.sl>; |
||
Line 10,897: | Line 10,897: | ||
value when x = i and y = j else |
value when x = i and y = j else |
||
board[i,j] foreach i within 1 ... size(board), j within 1 ... size(board[1]); |
board[i,j] foreach i within 1 ... size(board), j within 1 ... size(board[1]); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
8 X 8 board: |
8 X 8 board: |
||
Line 10,936: | Line 10,936: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="ruby">var board = [] |
||
var I = 8 |
var I = 8 |
||
var J = 8 |
var J = 8 |
||
Line 10,996: | Line 10,996: | ||
} |
} |
||
print "\n" |
print "\n" |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
Line 11,002: | Line 11,002: | ||
{{trans|Rust}} |
{{trans|Rust}} |
||
< |
<syntaxhighlight lang="swift">public struct CPoint { |
||
public var x: Int |
public var x: Int |
||
public var y: Int |
public var y: Int |
||
Line 11,131: | Line 11,131: | ||
} |
} |
||
b.printBoard()</ |
b.printBoard()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 11,146: | Line 11,146: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.6; # For object support, which makes coding simpler |
||
oo::class create KnightsTour { |
oo::class create KnightsTour { |
||
Line 11,252: | Line 11,252: | ||
expr {$a in [my ValidMoves $b]} |
expr {$a in [my ValidMoves $b]} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Demonstrating: |
Demonstrating: |
||
< |
<syntaxhighlight lang="tcl">set kt [KnightsTour new] |
||
$kt constructRandom |
$kt constructRandom |
||
$kt print |
$kt print |
||
Line 11,261: | Line 11,261: | ||
} else { |
} else { |
||
puts "This is an open tour" |
puts "This is an open tour" |
||
}</ |
}</syntaxhighlight> |
||
Sample output: |
Sample output: |
||
<pre> |
<pre> |
||
Line 11,273: | Line 11,273: | ||
</pre> |
</pre> |
||
The above code supports other sizes of boards and starting from nominated locations: |
The above code supports other sizes of boards and starting from nominated locations: |
||
< |
<syntaxhighlight lang="tcl">set kt [KnightsTour new 7 7] |
||
$kt constructFrom {0 0} |
$kt constructFrom {0 0} |
||
$kt print |
$kt print |
||
Line 11,280: | Line 11,280: | ||
} else { |
} else { |
||
puts "This is an open tour" |
puts "This is an open tour" |
||
}</ |
}</syntaxhighlight> |
||
Which could produce this output: |
Which could produce this output: |
||
<pre> |
<pre> |
||
Line 11,293: | Line 11,293: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="ecmascript">class Square { |
||
construct new(x, y) { |
construct new(x, y) { |
||
_x = x |
_x = x |
||
Line 11,350: | Line 11,350: | ||
System.write((col == 7) ? "\n" : " ") |
System.write((col == 7) ? "\n" : " ") |
||
col = (col + 1) % 8 |
col = (col + 1) % 8 |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 11,365: | Line 11,365: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">int Board(8+2+2, 8+2+2); \board array with borders |
||
int LegalX, LegalY; \arrays of legal moves |
int LegalX, LegalY; \arrays of legal moves |
||
def IntSize=4; \number of bytes in an integer (4 or 2) |
def IntSize=4; \number of bytes in an integer (4 or 2) |
||
Line 11,415: | Line 11,415: | ||
] |
] |
||
else Text(0, "No Solution.^M^J"); |
else Text(0, "No Solution.^M^J"); |
||
]</ |
]</syntaxhighlight> |
||
Example output: |
Example output: |
||
Line 11,434: | Line 11,434: | ||
First we build a generic package for solving any kind of tour over the chess board. Here it is… |
First we build a generic package for solving any kind of tour over the chess board. Here it is… |
||
<lang> |
<syntaxhighlight lang="text"> |
||
<xsl:package xsl:version="3.0" |
<xsl:package xsl:version="3.0" |
||
xmlns:xsl="http://www.w3.org/1999/XSL/Transform" |
xmlns:xsl="http://www.w3.org/1999/XSL/Transform" |
||
Line 11,491: | Line 11,491: | ||
</xsl:package> |
</xsl:package> |
||
</syntaxhighlight> |
|||
</lang> |
|||
And now for the style-sheet to solve the Knight’s tour… |
And now for the style-sheet to solve the Knight’s tour… |
||
<lang> |
<syntaxhighlight lang="text"> |
||
<xsl:stylesheet version="3.0" |
<xsl:stylesheet version="3.0" |
||
xmlns:xsl="http://www.w3.org/1999/XSL/Transform" |
xmlns:xsl="http://www.w3.org/1999/XSL/Transform" |
||
Line 11,534: | Line 11,534: | ||
</xsl:stylesheet> |
</xsl:stylesheet> |
||
</syntaxhighlight> |
|||
</lang> |
|||
So an input like this… |
So an input like this… |
||
<lang> |
<syntaxhighlight lang="text"> |
||
<tt> |
<tt> |
||
<knight> |
<knight> |
||
Line 11,544: | Line 11,544: | ||
</knight> |
</knight> |
||
</tt> |
</tt> |
||
</syntaxhighlight> |
|||
</lang> |
|||
…should be transformed in something like this… |
…should be transformed in something like this… |
||
<lang> |
<syntaxhighlight lang="text"> |
||
<tt> |
<tt> |
||
<knight> |
<knight> |
||
Line 11,557: | Line 11,557: | ||
</knight> |
</knight> |
||
</tt> |
</tt> |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl"> // Use Warnsdorff's rule to perform a knights tour of a 8x8 board in |
||
// linear time. |
// linear time. |
||
// See Pohl, Ira (July 1967), |
// See Pohl, Ira (July 1967), |
||
Line 11,607: | Line 11,607: | ||
fcn(ns){ vm.arglist.apply("%2s".fmt).concat(",")+"\n" }); |
fcn(ns){ vm.arglist.apply("%2s".fmt).concat(",")+"\n" }); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">b:=Board(); b.knightsTour(3,3); |
||
b.println();</ |
b.println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 11,623: | Line 11,623: | ||
</pre> |
</pre> |
||
Check that a solution for all squares is found: |
Check that a solution for all squares is found: |
||
< |
<syntaxhighlight lang="zkl">[[(x,y); [0..7]; [0..7]; |
||
{ b:=Board(); n:=b.knightsTour(x,y); if(n!=64) b.println(">>>",x,",",y) } ]];</ |
{ b:=Board(); n:=b.knightsTour(x,y); if(n!=64) b.println(">>>",x,",",y) } ]];</syntaxhighlight> |
||
{{out}}Nada |
{{out}}Nada |
||