Solve a Holy Knight's tour: Difference between revisions

The present task is to produce a solution to such problems. At least demonstrate your program by solving the following:

 

<pre>

0 0 0

Extra credit is available for other interesting examples.

 

* [[Solve a Hidato puzzle]]

* [[Solve a Hopido puzzle]]

* [[Solve a Numbrix puzzle]]

* [[Solve the no connection puzzle]]

 

 

=={{header|Ada}}==

This solution uses the package Knights_Tour from [[Knight's Tour#Ada]]. The board is quadratic, the size of the board is read from the command line and the board itself is read from the standard input. For the board itself, Space and Minus indicate a no-go (i.e., a coin on the board), all other characters represent places the knight must visit. A '1' represents the start point. Ill-formatted input will crash the program.

 

procedure Holy_Knight is

Ada.Text_IO.Put_Line("Tour:");

KT.Tour_IO(KT.Warnsdorff_Get_Tour(Start_X, Start_Y, Board));

 

{{out}}

=={{header|ALGOL 68}}==

Uses a modified version of the [[Knight's Tour#ALGOL 68]] solution.

INT nne = 1, ne = 2, se = 3, sse = 4;

INT ssw = 5, sw = 6, nw = 7, nnw = 8;

FI;

print( ( iterations, " iterations, ", backtracks, " backtracks", newline ) )

{{out}}

<pre>

This solution can handle different input formats: the widths of the first and the other columns are computed. The cell were to start from should have a unique value, but this value is not prescribed. Non-empty cells (such as the start cell) should contain a character that is different from '-', '.' or white space.

The puzzle solver itself is only a few lines long.

= begin colWidth crumbs non-empty pairs path parseLine

, display isolateStartCell minDistance numberElementsAndSort

& whl'(!boards:%?board ?boards&Holy-Knight$!board)

& done

Output:

<pre>

16 12

13 15</pre>

 

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

#include <vector>

#include <sstream>

return system( "pause" );

}

 

{{out}}

{{trans|C++}}

From the refactored C++ version with more precise typing, and some optimizations. The HolyKnightPuzzle struct is created at compile-time, so its pre-conditions can catch most malformed puzzles at compile-time.

std.typecons, std.typetuple;

 

writefln("One solution:\n%(%-(%2s %)\n%)\n", solution);

}

{{out}}

<pre>One solution:

{{trans|Ruby}}

This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#Elixir | here]]

adjacent = [{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}]

_ _ _ _ _ 0 _ 0

"""

 

{{out}}

12 20

17 13

</pre>

 

=={{header|Haskell}}==

import Data.Maybe

 

type Position = (Int, Int)

 

toSlot :: Char -> Maybe Int

toSlot '0' = Just 0

toSlot '1' = Just 1

 

toString :: Maybe Int -> String

toString (Just n) = replicate (3 - length nn) ' ' ++ nn

where

chunksOf :: Int -> [a] -> [[a]]

chunksOf _ [] = []

 

showBoard :: KnightBoard -> String

showBoard board =

where

 

toBoard :: [String] -> KnightBoard

where

height = length strs

 

add (a, b) (x, y) = (a + x, b + y)

 

 

-- Enumerate valid moves given a board and a knight's position.

validMoves board position = filter isValid plausible

where

 

isSolved :: KnightBoard -> Bool

 

-- Solve the knight's tour with a simple Depth First Search.

solveKnightTour board = solve board 1 initPosition

where

solve boardA depth position =

in if isSolved boardB

 

tourExA :: [String]

tourExA =

 

tourExB :: [String]

tourExB =

 

main :: IO ()

main =

{{out}}

<pre> 19 26 17

17 15 </pre>

As requested, in an attempt to make this solution faster, the following is a version that replaces the Array with an STUArray (unboxed and mutable), and yields a speedup of 4.2. No speedups were gained until move validation was inlined with the logic in `solve'. This seems to point to the list consing as the overhead for time and allocation, although profiling did show that about 25% of the time in the immutable version was spent creating arrays. Perhaps a more experienced Haskeller could provide insight on how to further optimize this or what optimizations were frivolous (barring a different algorithm or search heuristic, and jumping into C, unless those are the only way).

import qualified Data.Array.Unboxed as AU

 

type Position = (Int, Int)

type KnightBoard = AU.UArray Position Int

 

toSlot '0' = 0

toSlot '1' = 1

 

toString :: Int -> String

toString (-1) = replicate 3 ' '

where

nn = show n

chunksOf :: Int -> [a] -> [[a]]

chunksOf _ [] = []

 

showBoard :: KnightBoard -> String

showBoard board =

where

(_, (_, height)) = AU.bounds board

where

height = length strs

 

add (a, b) (x, y) = (a + x, b + y)

 

 

-- Solve the knight's tour with a simple Depth First Search.

solveKnightTour :: KnightBoard -> Maybe KnightBoard

solveKnightTour board =

 

 

 

 

 

tourExA :: [String]

tourExA =

 

tourExB :: [String]

tourExB =

 

main :: IO ()

main =

 

==Icon and {{header|Unicon}}==

This is a Unicon-specific solution:

record Pos(r,c)

 

QMouse(puzzle, visit(loc.r+1,loc.c-2), self, val)

QMouse(puzzle, visit(loc.r-1,loc.c-2), self, val)

 

Sample run:

->

</pre>

 

=={{header|J}}==

The simplest J implementation here uses a breadth first search - but that can be memory inefficient so it's worth representing the boards as characters (several orders of magnitude space improvement) and it's worth capping how much memory we allow J to use (2^34 is 16GB):

 

 

unpack=:verb define

moves=. (#~ (0{a.)={&y) moves

moves y adverb def (':';'y x} m')"0 (x+1){a.

 

Letting that cook:

 

 

That's 48422 solutions. Here's one of them:

 

__ 11 28 13 __ __ __ __

__ 22 __ 10 29 __ __ __

1 24 3 34 5 18 7 __

__ __ 36 19 __ 33 __ __

 

and here's a couple more:

 

__ 5 8 31 __ __ __ __

__ 32 __ 6 9 __ __ __

1 36 17 30 27 4 23 __

__ __ 2 21 __ 29 __ __

 

This is something of a problem, however, because finding all those solutions is slow. And even having to be concerned about a 16GB memory limit for this small of a problem is troubling (and using 64 bit integers, instead of 8 bit characters, to represent board squares, would exceed that limit). Also, you'd get bored, inspecting 48422 boards.

So, let's just find one solution:

 

mask=. +./' '~:y

board=. __ 0 1 {~ {.@:>:@:"."0 mask#"1 y

moves=. (#~ 0={&y) moves

moves y adverb def (':';'y x} m')"0 x+1

 

Here, we break our problem space up into blocks of no more than 10 boards each, and use recursion to investigate each batch of boards. When we find a solution, we stop there (for each iteration at each level of recursion):

 

__ 11 28 13 __ __ __ __

__ 22 __ 10 29 __ __ __

1 24 3 34 5 18 7 __

__ __ 36 19 __ 33 __ __

 

[Why ten boards and not just one board? Because 10 is a nice compromise between amortizing the overhead of each attempt and not trying too much at one time. Most individual attempts will fail, but by splitting up the workload after exceeding 10 possibilities, instead of investigating each possibility individually, we increase the chances that we are investigating something useful. Also, J implementations penalize the performance of algorithms which are overly serial in structure.]

With this tool in hand, we can now attempt bigger problems:

 

1 0

0 0

0 0

0 0

 

Finding a solution for this looks like:

 

__ __ __ __ __ 1 __ 5 __ __ __ __ __

__ __ __ __ __ 6 __ 46 __ __ __ __ __

__ __ __ __ 24 21 26 17 28 __ __ __ __

__ __ __ __ __ 18 __ 20 __ __ __ __ __

 

=={{header|Java}}==

{{works with|Java|8}}

 

public class HolyKnightsTour {

}

}

<pre> 19 26 21

28 18 25

4 11 14 </pre>

 

 

 

 

 

 

 

 

 

 

-----1-0-----

-----0-0-----

----00000----

-----0-0-----

 

 

{{out}}

<pre>

- - - - - 27 - 29 - - - - -

solution found in 61341542 tries, 61341486 backtracks (180.56s)

</pre>

 

It solves the tasked problem, as well as the "extra credit" from [[#Ada]].

 

(require "hidato-family-solver.rkt")

 

#(- - - - 0 0 0 0 0 - - - -)

#(- - - - - 0 - 0 - - - - -)

 

{{out}}

_ _ _ _ _ 38 _ 34 _ _ _ _ _

_ _ _ _ _ 35 _ 15 _ _ _ _ _</pre>

 

=={{header|REXX}}==

This REXX program is essentially a modified &nbsp; ''knight's tour'' &nbsp; REXX program with support to place pennies on the chessboard.

blank=pos('//', space(arg(1), 0))\==0 /*see if the pennies are to be shown. */

parse arg ops '/' cent /*obtain the options and the pennies. */

if N=='' | N=="," then N=8 /*no boardsize specified? Use default.*/

if sRank=='' | sRank=="," then sRank=N /*starting rank given? " " */

if sFile=='' | sFile=="," then sFile=1 /* " file " " " */

NN=N**2; NxN='a ' N"x"N ' chessboard' /*file [↓] [↓] r=rank */

/*[↑] create an empty NxN chessboard.*/

cents=0 /*number of pennies on the chessboard. */

do while cent\='' /* [↓] possibly place the pennies. */

if x='' then x=1 /*if number not specified, use 1 penny.*/

if cr='' then iterate /*support the "blanking" option. */

/* [↓] traipse through the chessboard.*/

/* [↑] count the number of pennies. */

parse var Kr Kr.1 Kr.2 Kr.3 Kr.4 Kr.5 Kr.6 Kr.7 Kr.8 /*parse the legal moves by hand.*/

parse var Kf Kf.1 Kf.2 Kf.3 Kf.4 Kf.5 Kf.6 Kf.7 Kf.8 /* " " " " " " */

if @.sRank.sFile\==beg then do sRank=1 for N /*find starting rank for the knight.*/

do sFile=1 for N /* " " file " " " */

@.sRank.sFile=beg /*the knight's starting position. */

leave sRank /*we have a spot, so leave all this.*/

 

end /*f*/

if blank then L=translate(L,,'¢') /*blank out the pennies on chessboard ?*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

move: procedure expose @. Kr. Kf. target; parse arg #,rank,file /*obtain move,rank,file.*/

'''output''' &nbsp; when the following is used for input:

<br><tt> , 3 1 /1,1 3 /1,7 2 /2,1 2 /2,5 /2,7 2 /3,8 /4,2 /4,4 2 /5,4 2 /5,7 /6,1 /7,1 /7,3 /7,6 3 /8,1 /8,5 4 </tt>

=={{header|Ruby}}==

This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#With_Warnsdorff | here]]

 

ADJACENT = [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]

t0 = Time.now

HLPsolver.new(boardy).solve

 

Which produces:

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

 

oo::class create HKTSolver {

HKTSolver create hkt $puzzle

hkt solve

{{out}}

<pre>

20 35 24

</pre>

[[Category:Puzzles]]