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

* [[Solve the no connection puzzle]]

<br><br>

 

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

(Array, (//), (!), assocs, elems, bounds, listArray)

import Data.Foldable (forM_)

case solveKnightTour $ toBoard board of

Nothing -> putStrLn "No solution.\n"

{{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 Control.Monad (forM_)

case solveKnightTour $ toBoard board of

Nothing -> putStrLn "No solution.\n"

 

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

===ES6===

By composition of generic functions, cacheing degree-sorted moves for each node.

'use strict';

 

return unit.concat.apply(unit, xs);

})() : [];

 

// 2 or more arguments

// elem :: Eq a => a -> [a] -> Bool

const elem = (x, xs) => xs.indexOf(x) !== -1;

 

// enumFromTo :: Int -> Int -> [Int]

// foldl :: (b -> a -> b) -> b -> [a] -> b

const foldl = (f, a, xs) => xs.reduce(f, a);

 

// groupBy :: (a -> a -> Bool) -> [a] -> [[a]]

return v;

};

 

// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

// hash :: (Int, Int) -> String

const hash = ([col, row]) => col.toString() + '.' + row.toString();

 

// Start node, and degree-sorted cache of moves from each node

courseMoves = (xs, [x, y]) => intersectBy(

([a, b], [c, d]) => a === c && b === d, kmoves([x, y]), xs

return {

boardWidth: boardLines.length > 0 ? boardLines[0].length : 0,

stepCount: steps.length,

};

 

const firstSolution = (dctMoves, intTarget, strStart, strNodeKey, path) => {

const

dctModel = problemModel(trackLines),

strStart = dctModel.start;

dctModel.cache, dctModel.stepCount, strStart, strStart, []

};

 

// [(Int, Int, String)] -> String

const

blnSoln = maybeStart.nothing,

(blnSoln ? sVal : (

iRow === startRow &&

)

}), {

startXY = take(2, lstTriples[0]),

strMap = 'PROBLEM ' + (parseInt(iProblem, 10) + 1) + '.\n\n' +

nothing: false,

just: startXY

}), lstGroups)),

intMSeconds + ' milliseconds:\n\n' +

nothing: true,

just: startXY

// TEST -------------------------------------------------------------------

return unlines(map(solutionString, problems));

{{Out}}

(Executed in Atom editor, using 'Script' package).

0 0 0

 

 

25 14 23

0 0

 

 

1 3

 

 

 

=={{header|Lua}}==

local p1, p1W = ".xxx.....x.xx....xxxxxxxxxx..x.xx.x..xxxsxxxxxx...xx.x.....xxx..", 8

local p2, p2W = ".....s.x..........x.x.........xxxxx.........xxx.......x..x.x..x..xxxxx...xxxxx..xx.....xx..xxxxx...xxxxx..x..x.x..x.......xxx.........xxxxx.........x.x..........x.x.....", 13

print( "\n\n" ); fill( p2, p2W );

if solve( sx, sy, 2 ) then printSolution() end

{{out}}

<pre>

53 49

</pre>

=={{header|Perl}}==

We perform a brute-force search. As an enhancement, we unroll the search by one level and use Parallel::ForkManager to search the top-level sub-trees concurrently, subject to the number of cores of course. We implement the search with explicit recursion, which impacts performance but improves readability and provides a use case for the "local" keyword.

# A sequence of locations on a 2-D board whose order might or might not

# matter. Suitable for representing a partial tour, a complete tour, or the

$kt->find_tour();

return;

{{out}}

The timings shown below were obtained on a Dell Optiplex 9020 with 4 cores.

- - - - - 48 - 50 - - - - -

- - - - - 41 - 43 - - - - - </pre>

 

=={{header|Phix}}==

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

end /*try a different move. */

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

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