Knight's tour: Difference between revisions

{{trans|Python}}

F chess2index(=chess, boardsize)

V board = knights_tour(start, boardsize)

print(boardstring(board, boardsize' boardsize))

{{out}}

=={{header|360 Assembly}}==

{{trans|BBC PASIC}}

KNIGHT CSECT

USING KNIGHT,R13 base registers

PG DC CL128' ' buffer

YREGS

{{out}}

<pre>

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

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

Here is the implementation:

package body Knights_Tour is

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:

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.

function Warnsdorff_Get_Tour(Start_X, Start_Y: Index; Scene: Tour := Empty)

return Tour;

-- uses Warnsdorff heurisitic to find a tour faster

Its implementation is as follows.

return Tour is

Done: Boolean;

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:

=={{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 #

FI

{{out}}

<pre>

ANSI BASIC doesn't allow function parameters to be passed by reference so X and Y were made global variables.

110 !

120 RANDOMIZE

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

=={{header|ATS}}==

Find Knight’s Tours.

val _ = make_and_fprint_tours (stdout_ref, 8, 8, i, j, max_tours,

closed_only)

{{out}}

=={{header|AutoHotkey}}==

{{libheader|GDIP}}

#NoEnv

SetBatchLines, -1

If (A_Gui = 1)

PostMessage, 0xA1, 2

{{out}}

For start at b3

=={{header|AWK}}==

# syntax: GAWK -f KNIGHTS_TOUR.AWK [-v sr=x] [-v sc=x]

#

}

}

<p>output:</p>

<pre>

{{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 sharp}}==

using System.Collections.Generic;

}

}

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

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

#include <iomanip>

#include <array>

cout << b3 << endl;

return 0;

Output:

For some reason, the interactive part does not work with sbcl, but it works fine wit clisp.

;;; Solving the knight's tour. ;;;

;;; Warnsdorff's rule with random tie break. ;;;

(prompt)

{{out}}

<pre>Starting case (leave blank for random)? a8

=={{header|Clojure}}==

Using warnsdorff's rule

(defn isin? [x li]

(not= [] (filter #(= x %) li)))

(let [np (next-move mov pmoves n)]

(recur (conj mov np) (inc x)))))))

{{out}}

<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}}==

===Fast Version===

{{trans|C++}}

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

writeln();

}

{{out}}

<pre>23 16 11 6 21

===Shorter Version===

{{trans|Haskell}}

alias Square = Tuple!(int,"x", int,"y");

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

The algorithm uses iterative backtracking and Warnsdorff's heuristic. It can output closed or non-closed tours.

(require 'plot)

(define *knight-moves*

(play starter 0 starter (dim n) wants-open)

(catch (hit mess) (show-steps n wants-open))))

{{out}}

(k-tour 8 0 #f)

♞-closed-tour: 66 tries.

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

;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))

(define ( k-plot n)

(plot-rgb (lambda (x y) (step-color x y n (dim n))) (- n epsilon) (- n epsilon)))

=={{header|Elixir}}==

{{trans|Ruby}}

import Integer, only: [is_odd: 1]

Board.knight_tour(4,9,1,1)

Board.knight_tour(5,5,1,2)

{{out}}

=={{header|Elm}}==

import Browser exposing (element)

, subscriptions = subscriptions

}

Link to live demo: https://dmcbane.github.io/knights-tour/

=={{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>

=={{header|ERRE}}==

Taken from ERRE distribution disk. Comments are in Italian.

! **********************************************************************

! * *

UNTIL A$<>""

END PROGRAM

{{out}}

<pre> *** LA GALOPPATA DEL CAVALIERE ***

=={{header|FreeBASIC}}==

Dim Shared As Integer tamano, xc, yc, nm

Dim As Integer f, qm, nmov, n = 0

Sleep

End

{{out}}

[https://www.dropbox.com/s/s3bpwechpoueum4/Knights%20Tour%20FreeBasic.png?dl=0 Knights Tour FreeBasic image]

{{works with|gfortran|11.2.1}}

{{works with|f2c}}

C

C Find Knight’s Tours.

end

{{out}}

$ echo "c5 2 T" | ./knights_tour

{{works with|gfortran|11.2.1}}

{{trans|ATS}}

!

! Find Knight’s Tours.

end program

{{out}}

{{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.

!!!

end if

end do

$ ./knights_tour a1 b2 c3

=={{header|Go}}==

===Warnsdorf's rule===

import (

}

return true

{{out}}

<pre>

</pre>

===Ant colony===

by Philip Hingston and Graham Kendal,

PDF at http://www.cs.nott.ac.uk/~gxk/papers/cec05knights.pdf. */

tourCh <- moves

}

Output:

<pre>

=={{header|Haskell}}==

import Data.Char (chr, ord)

import Data.List (intercalate, minimumBy, sort, (\\))

printTour tour = do

putStrLn $ intercalate " -> " $ take 8 tour

{{Out}}

<pre>e5 -> f7 -> h8 -> g6 -> h4 -> g2 -> e1 -> f3

The algorithm doesn't always generate a complete tour.

procedure main(A)

}

every write(hdr2|hdr1|&null)

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))

every s ||:= " " || (!sort(movesto[k])|"\n")

return s

'''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

assert. ~:p

(,~y)$/:p

'''Example Use:'''

0 25 14 23 28 49 12 31

15 22 27 50 13 30 63 48

555 558 553 778 563 570 775 780 785 772 1000...

100 551 556 561 102 777 572 771 104 781 57...

=={{header|Java}}==

{{Works with|Java|7}}

public class KnightsTour {

}

}

<pre>34 17 20 3 36 7 22 5

19 2 35 40 21 4 37 8

===More efficient non-trackback solution===

{{Works with|Java|8}}

package com.knight.tour;

import java.util.ArrayList;

}

}

<pre>

Found a path for 8 X 8 chess board.

You can test it [http://paulo-jorente.de/webgames/repos/knightsTour/ here].

class KnightTour {

constructor() {

}

new KnightTour();

To test it, you'll need an index.html

<pre>

A composition of values, drawing on generic abstractions:

{{Trans|Haskell}}

'use strict';

// MAIN ---

return main();

{{Out}}

<pre>(Board size 8*8)

=={{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 = """

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

{{trans|Haskell}}

val board = Array(8 * 8, { Square(it / 8 + 1, it % 8 + 1) })

col = (col + 1) % 8

}

{{out}}

Influenced by the Python version, although computed tours are different.

20 input "Board size: ",size

30 input "Start position: ",a$

450 ' skip this move

460 next

[[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} }

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]

=={{header|M2000 Interpreter}}==

Function KnightTour$(StartW=1, StartH=1){

def boolean swapH, swapV=True

Clipboard ex$

Report ex$

{{out}}

<pre>

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.)

----------------------------------------------------------------------

find_tour(a1)

find_tour(c5)

{{out}}

=={{header|Mathematica}}/{{header|Wolfram Language}}==

'''Solution'''

Module[{

vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <> ToString[Mod[# - 1, 8] + 1]) & /@ Range[64], knightsGraph,

hamiltonianCycle = ((FindHamiltonianCycle[knightsGraph] /. UndirectedEdge -> DirectedEdge) /. labels)[[1]];

end = Cases[hamiltonianCycle, (x_ \[DirectedEdge] start) :> x][[1]];

'''Usage'''

(* out *)

"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"}

'''Analysis'''

'''vertexLabels''' replaces the default vertex (i.e. square) names of the chessboard with the standard algebraic names "a1", "a2",...,"h8".

vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <> ToString[Mod[# - 1, 8] + 1]) & /@ Range[64]

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",

'''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.

=={{header|Mathprog}}==

2. It is possible to specify which square is used for any Knights Move.

/*Knights.mathprog

end;

Produces:

GLPSOL: GLPK LP/MIP Solver, v4.47

Parameter(s) specified in the command line:

23 10 21 16 25

Model has been successfully processed

and

/*Knights.mathprog

end;

Produces:

GLPSOL: GLPK LP/MIP Solver, v4.47

Parameter(s) specified in the command line:

10 55 20 57 12 37 40 1

Model has been successfully processed

=={{header|Nim}}==

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

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

run[8]("b5")

{{out}}

=={{header|ObjectIcon}}==

{{trans|ATS}}

# Find Knight’s Tours.

#

return (((i_diff = 2 & j_diff = 1) |

(i_diff = 1 & j_diff = 2)) & &yes) | fail

{{out}}

=={{header|Perl}}==

Knight's tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]]

use warnings;

# Find a knight's tour

return unless $square =~ /^([a-h])([1-8])$/;

return (8-$2, ord($1) - ord('a'));

Sample output (start square c3):

=={{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>

<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>

=={{header|Picat}}==

main =>

fill_output_matrix(N,OutputM,V,V[I],Count+1)

end.

{{out}}

=={{header|PicoLisp}}==

# Build board

(moves Tour) )

(push '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

=={{header|PostScript}}==

You probably shouldn't send this to a printer. Solution using Warnsdorffs algorithm.

%%BoundingBox: 0 0 300 300

3 1 100 { solve } for

=={{header|Prolog}}==

Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]]

knight(N) :-

Max is N * N,

M1 is M + 1,

display(N, M1, T).

Output :

===Alternative version===

{{Works with|GNU Prolog}}

{{Output}}

<pre> 5 18 35 22 3 16 55 24

=={{header|Python}}==

Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]]

boardsize=6

start = input('Start position: ')

board = knights_tour(start, boardsize)

;Sample runs

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.

# Begin tour.

Output:

=={{header|Racket}}==

#lang racket

(define N 8)

" "))))

(draw (tour (random N) (random N)))

{{out}}

<pre>

(formerly Perl 6)

{{trans|Perl}}

my $I = 8;

sub from_algebraic($square where /^ (<[a..z]>) (\d+) $/) {

$I - $1, ord(~$0) - ord('a');

(Output identical to Perl's above.)

{{trans|ATS}}

For use with the public domain ratfor77 translator and a FORTRAN 77 compiler.

#

# Find Knight’s Tours.

end

{{out}}

This is an &nbsp; ''open tour'' &nbsp; solution. &nbsp; (See this task's &nbsp; ''discussion'' &nbsp; page for an explanation, the section is &nbsp; ''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.*/

end /*try different move. */

end /*t*/ /* [↑] all moves tried.*/

'''output''' &nbsp; when using the default input:

<pre>

=={{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)

knight_tour(5,5,0,1)

Which produces:

<pre>

=={{header|Rust}}==

const SIZE: usize = 8;

None => println!("Fail!"),

}

{{out}}

<pre>

=={{header|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")

<pre>

a1b3a5b7c5a4b2c4a3b1c3a2b4a6b8c6a7b5c7a8b6c8d6e4d2f1e3c2d4e2c1d3e1g2f4d5e7g8h6f5h4g6h8f7d8e6f8d7e5g4h2f3g1h3g5h7f6e8g7h5g3h1f2d1

=={{header|Scheme}}==

;;/usr/bin/petite

;;encoding:utf-8

(display (map (lambda(x) (decode x)) result)))

(go (renew position))))

{{out}}

<pre>

=={{header|SequenceL}}==

Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_rule|Warnsdorffs rule]] (No Backtracking)

import <Utilities/Sequence.sl>;

import <Utilities/Conversion.sl>;

value when x = i and y = j else

board[i,j] foreach i within 1 ... size(board), j within 1 ... size(board[1]);

{{out}}

8 X 8 board:

=={{header|Sidef}}==

{{trans|Raku}}

var I = 8

var J = 8

}

print "\n"

=={{header|Swift}}==

{{trans|Rust}}

public var x: Int

public var y: Int

}

{{out}}

=={{header|Tcl}}==

oo::class create KnightsTour {

expr {$a in [my ValidMoves $b]}

}

Demonstrating:

$kt constructRandom

$kt print

} else {

puts "This is an open tour"

Sample output:

<pre>

</pre>

The above code supports other sizes of boards and starting from nominated locations:

$kt constructFrom {0 0}

$kt print

} else {

puts "This is an open tour"

Which could produce this output:

<pre>

=={{header|Wren}}==

{{trans|Kotlin}}

construct new(x, y) {

_x = x

System.write((col == 7) ? "\n" : " ")

col = (col + 1) % 8

{{out}}

=={{header|XPL0}}==

int LegalX, LegalY; \arrays of legal moves

def IntSize=4; \number of bytes in an integer (4 or 2)

]

else Text(0, "No Solution.^M^J");

Example output:

First we build a generic package for solving any kind of tour over the chess board. Here it is…

<xsl:package xsl:version="3.0"

xmlns:xsl="http://www.w3.org/1999/XSL/Transform"

</xsl:package>

And now for the style-sheet to solve the Knight’s tour…

<xsl:stylesheet version="3.0"

xmlns:xsl="http://www.w3.org/1999/XSL/Transform"

</xsl:stylesheet>

So an input like this…

<tt>

<knight>

</knight>

</tt>

…should be transformed in something like this…

<tt>

<knight>

</knight>

</tt>

=={{header|zkl}}==

// linear time.

// See Pohl, Ira (July 1967),

fcn(ns){ vm.arglist.apply("%2s".fmt).concat(",")+"\n" });

}

{{out}}

<pre>

</pre>

Check that a solution for all squares is found:

{{out}}Nada