Solve a Holy Knight's tour: Difference between revisions

m
m (elided the superfluous "1" for the example.)
m (→‎{{header|Wren}}: Minor tidy)
 
(4 intermediate revisions by 3 users not shown)
Line 39:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">V moves = [
[-1, -2], [1, -2], [-1, 2], [1, 2],
[-2, -1], [-2, 1], [2, -1], [2, 1]
Line 89:
find_solution(‘.xxx.....x.xx....xxxxxxxxxx..x.xx.x..xxxsxxxxxx...xx.x.....xxx..’, 8)
print()
find_solution(‘.....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)</langsyntaxhighlight>
 
{{out}}
Line 121:
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.
 
<langsyntaxhighlight Adalang="ada">with Knights_Tour, Ada.Text_IO, Ada.Command_Line;
procedure Holy_Knight is
Line 156:
Ada.Text_IO.Put_Line("Tour:");
KT.Tour_IO(KT.Warnsdorff_Get_Tour(Start_X, Start_Y, Board));
end Holy_Knight;</langsyntaxhighlight>
 
{{out}}
Line 219:
=={{header|ALGOL 68}}==
Uses a modified version of the [[Knight's Tour#ALGOL 68]] solution.
<langsyntaxhighlight lang="algol68"># directions for moves #
INT nne = 1, ne = 2, se = 3, sse = 4;
INT ssw = 5, sw = 6, nw = 7, nnw = 8;
Line 395:
FI;
print( ( iterations, " iterations, ", backtracks, " backtracks", newline ) )
)</langsyntaxhighlight>
{{out}}
<pre>
Line 414:
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.
<langsyntaxhighlight lang="bracmat">( ( Holy-Knight
= begin colWidth crumbs non-empty pairs path parseLine
, display isolateStartCell minDistance numberElementsAndSort
Line 626:
& whl'(!boards:%?board ?boards&Holy-Knight$!board)
& done
);</langsyntaxhighlight>
Output:
<pre>
Line 681:
If there are cells that require more characters, then a 2-dimensional array of ints must be used. Any number < 0 indicates a no-go.<br/>
The puzzle can be made circular (the end cell must connect to the start cell). In that case, no start cell needs to be given.
<langsyntaxhighlight lang="csharp">using System.Collections;
using System.Collections.Generic;
using static System.Console;
Line 824:
}
 
}</langsyntaxhighlight>
{{out}}
<pre>
Line 852:
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">
#include <vector>
#include <sstream>
Line 988:
return system( "pause" );
}
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,019:
{{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.
<langsyntaxhighlight lang="d">import std.stdio, std.conv, std.string, std.range, std.algorithm,
std.typecons, std.typetuple;
 
Line 1,151:
writefln("One solution:\n%(%-(%2s %)\n%)\n", solution);
}
}</langsyntaxhighlight>
{{out}}
<pre>One solution:
Line 1,183:
{{trans|Ruby}}
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#Elixir | here]]
<langsyntaxhighlight lang="elixir"># require HLPsolver
adjacent = [{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}]
Line 1,214:
_ _ _ _ _ 0 _ 0
"""
|> HLPsolver.solve(adjacent)</langsyntaxhighlight>
 
{{out}}
Line 1,271:
=={{header|Go}}==
{{trans|Python}}
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 1,364:
fmt.Println()
findSolution(board2, 13)
}</langsyntaxhighlight>
 
{{out}}
Line 1,393:
 
=={{header|Haskell}}==
<langsyntaxhighlight Haskelllang="haskell">import Data.Array
(Array, (//), (!), assocs, elems, bounds, listArray)
import Data.Foldable (forM_)
Line 1,507:
case solveKnightTour $ toBoard board of
Nothing -> putStrLn "No solution.\n"
Just solution -> putStrLn $ showBoard solution ++ "\n")</langsyntaxhighlight>
{{out}}
<pre> 19 26 17
Line 1,532:
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).
<langsyntaxhighlight Haskelllang="haskell">{-# LANGUAGE FlexibleContexts #-}
 
import Control.Monad (forM_)
Line 1,677:
case solveKnightTour $ toBoard board of
Nothing -> putStrLn "No solution.\n"
Just solution -> putStrLn $ showBoard solution ++ "\n")</langsyntaxhighlight>
 
This version is similar to the previous one but:
Line 1,686:
This results in 117x speedup over the very first version. This speed up comes from a smarter traversal rather than from minor code optimisations.
 
<syntaxhighlight lang="haskell">
<lang Haskell>
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE LambdaCase #-}
Line 1,817:
Just solution -> putStrLn $ showBoard solution ++ "\n")
 
</syntaxhighlight>
</lang>
 
==Icon and {{header|Unicon}}==
This is a Unicon-specific solution:
<langsyntaxhighlight lang="unicon">global nCells, cMap, best
record Pos(r,c)
 
Line 1,918:
QMouse(puzzle, visit(loc.r+1,loc.c-2), self, val)
QMouse(puzzle, visit(loc.r-1,loc.c-2), self, val)
end</langsyntaxhighlight>
 
Sample run:
Line 1,955:
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):
 
<langsyntaxhighlight Jlang="j">9!:21]2^34
 
unpack=:verb define
Line 1,987:
moves=. (#~ (0{a.)={&y) moves
moves y adverb def (':';'y x} m')"0 (x+1){a.
)</langsyntaxhighlight>
 
Letting that cook:
 
<langsyntaxhighlight Jlang="j"> $~.sol
48422 8 8</langsyntaxhighlight>
 
That's 48422 solutions. Here's one of them:
 
<langsyntaxhighlight Jlang="j"> (a.i.{.sol){(i.255),__
__ 11 28 13 __ __ __ __
__ 22 __ 10 29 __ __ __
Line 2,004:
1 24 3 34 5 18 7 __
__ __ 36 19 __ 33 __ __
__ __ __ 4 35 6 __ __</langsyntaxhighlight>
 
and here's a couple more:
 
<langsyntaxhighlight Jlang="j"> (a.i.{:sol){(i.255),__
__ 5 8 31 __ __ __ __
__ 32 __ 6 9 __ __ __
Line 2,025:
1 36 17 30 27 4 23 __
__ __ 2 21 __ 29 __ __
__ __ __ 28 3 22 __ __</langsyntaxhighlight>
 
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.
Line 2,031:
So, let's just find one solution:
 
<langsyntaxhighlight Jlang="j">unpack=:verb define
mask=. +./' '~:y
board=. __ 0 1 {~ {.@:>:@:"."0 mask#"1 y
Line 2,073:
moves=. (#~ 0={&y) moves
moves y adverb def (':';'y x} m')"0 x+1
)</langsyntaxhighlight>
 
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):
 
<langsyntaxhighlight Jlang="j"> solve1 ex1
__ 11 28 13 __ __ __ __
__ 22 __ 10 29 __ __ __
Line 2,085:
1 24 3 34 5 18 7 __
__ __ 36 19 __ 33 __ __
__ __ __ 4 35 6 __ __</langsyntaxhighlight>
 
[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.]
Line 2,091:
With this tool in hand, we can now attempt bigger problems:
 
<langsyntaxhighlight Jlang="j">ex2=:unpack ];._2]0 :0
1 0
0 0
Line 2,105:
0 0
0 0
)</langsyntaxhighlight>
 
Finding a solution for this looks like:
 
<langsyntaxhighlight Jlang="j"> solve1 ex2
__ __ __ __ __ 1 __ 5 __ __ __ __ __
__ __ __ __ __ 6 __ 46 __ __ __ __ __
Line 2,122:
__ __ __ __ 24 21 26 17 28 __ __ __ __
__ __ __ __ __ 18 __ 20 __ __ __ __ __
__ __ __ __ __ 25 __ 27 __ __ __ __ __</langsyntaxhighlight>
 
=={{header|Java}}==
{{works with|Java|8}}
<langsyntaxhighlight lang="java">import java.util.*;
 
public class HolyKnightsTour {
Line 2,229:
}
}
}</langsyntaxhighlight>
<pre> 19 26 21
28 18 25
Line 2,242:
===ES6===
By composition of generic functions, cacheing degree-sorted moves for each node.
<langsyntaxhighlight JavaScriptlang="javascript">(() => {
'use strict';
 
Line 2,652:
// TEST -------------------------------------------------------------------
return unlines(map(solutionString, problems));
})();</langsyntaxhighlight>
{{Out}}
(Executed in Atom editor, using 'Script' package).
Line 2,715:
=={{header|Julia}}==
Uses the Hidato puzzle solver module, which has its source code listed [[Solve_a_Hidato_puzzle#Julia | here]] in the Hadato task.
<langsyntaxhighlight lang="julia">using .Hidato # Note that the . here means to look locally for the module rather than in the libraries
 
const holyknight = """
Line 2,733:
hidatosolve(board, maxmoves, knightmoves, fixed, starts[1][1], starts[1][2], 1)
printboard(board)
</langsyntaxhighlight>{{output}}<pre>
0 0 0
0 0 0
Line 2,755:
=={{header|Kotlin}}==
{{trans|Python}}
<langsyntaxhighlight lang="scala">// version 1.1.3
 
val moves = arrayOf(
Line 2,841:
println()
findSolution(board2, 13)
}</langsyntaxhighlight>
 
{{out}}
Line 2,870:
 
=={{header|Lua}}==
<langsyntaxhighlight lang="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
Line 2,928:
print( "\n\n" ); fill( p2, p2W );
if solve( sx, sy, 2 ) then printSolution() end
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,958:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Outputs coordinates and a visualization of the tour:
<langsyntaxhighlight Mathematicalang="mathematica">puzzle = " 0 0 0
0 0 0
0 0 0 0 0 0 0
Line 2,976:
e = VertexList[g];
order = FindShortestTour[g][[2]]
Graphics[{Red, Disk[#, 0.2] & /@ e, Black, BlockMap[Arrow, e[[order]], 2, 1]}]</langsyntaxhighlight>
{{out}}
<pre>{{6,1},{4,2},{6,3},{8,4},{7,6},{6,4},{5,6},{3,5},{1,4},{2,2},{4,3},{5,1},{3,2},{2,4},{1,2},{3,3},{4,1},{6,2},{7,4},{8,6},{6,7},{4,8},{3,6},{5,7},{3,8},{4,6},{6,5},{5,3},{3,4},{1,3},{2,5},{3,7},{5,8},{6,6},{8,5},{7,3},{6,1}}
Line 2,985:
In this version, the board is described as an array of strings rather than a string in the Go version (so, we don’t have to specify the size). The way to initialize is also different and even if the Moves where in the same order, the solution would be different. Changing the order of the Moves may have a great impact on performance, but there is no best order. The order we have chosen provides excellent performance with the two examples: less than 20 ms on our laptop. But with another order, it took more than 2 seconds!
 
<langsyntaxhighlight Nimlang="nim">import sequtils, strformat
 
const Moves = [[-1, -2], [1, -2], [-2, -1], [2, -1], [-2, 1], [2, 1], [-1, 2], [1, 2]]
Line 3,060:
Board1.findSolution()
echo()
Board2.findSolution()</langsyntaxhighlight>
 
{{out}}
Line 3,088:
=={{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.
<langsyntaxhighlight lang="perl">package KT_Locations;
# 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
Line 3,341:
$kt->find_tour();
return;
}</langsyntaxhighlight>
{{out}}
The timings shown below were obtained on a Dell Optiplex 9020 with 4 cores.
Line 3,423:
 
=={{header|Phix}}==
Tweaked the knights tour algorithm (to use a limit variable rather than size*size). Bit slow on the second one... (hence omitted under pwa/p2js)
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>sequence board, warnsdorffs
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
 
<span style="color: #004080;">sequence</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">warnsdorffs</span>
integer size, limit, nchars
string fmt, blank
<span style="color: #004080;">integer</span> <span style="color: #000000;">size</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nchars</span>
 
<span style="color: #004080;">string</span> <span style="color: #000000;">fmt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">blank</span>
constant ROW = 1, COL = 2
constant moves = {{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}}
<span style="color: #008080;">constant</span> <span style="color: #000000;">ROW</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">COL</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span>
 
<span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}}</span>
function onboard(integer row, integer col)
return row>=1 and row<=size and col>=nchars and col<=nchars*size
<span style="color: #008080;">function</span> <span style="color: #000000;">onboard</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">row</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">size</span> <span style="color: #008080;">and</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">nchars</span> <span style="color: #008080;">and</span> <span style="color: #000000;">col</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">*</span><span style="color: #000000;">size</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure init_warnsdorffs()
integer nrow,ncol
<span style="color: #008080;">procedure</span> <span style="color: #000000;">init_warnsdorffs</span><span style="color: #0000FF;">()</span>
for row=1 to size do
<span style="color: #008080;">for</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">size</span> <span style="color: #008080;">do</span>
for col=nchars to nchars*size by nchars do
<span style="color: #008080;">for</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">=</span><span style="color: #000000;">nchars</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nchars</span><span style="color: #0000FF;">*</span><span style="color: #000000;">size</span> <span style="color: #008080;">by</span> <span style="color: #000000;">nchars</span> <span style="color: #008080;">do</span>
for move=1 to length(moves) do
<span style="color: #008080;">for</span> <span style="color: #000000;">move</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
nrow = row+moves[move][ROW]
<span style="color: #004080;">integer</span> <span style="color: #000000;">nrow</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ROW</span><span style="color: #0000FF;">],</span>
ncol = col+moves[move][COL]*nchars
<span style="color: #000000;">ncol</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">COL</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">nchars</span>
if onboard(nrow,ncol) then
<span style="color: #008080;">if</span> <span style="color: #000000;">onboard</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
-- (either of these would work)
<span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
warnsdorffs[row][col] += 1
-- <span warnsdorffs[nrow][ncol]style="color: #008080;">end</span> <span +style="color: 1#008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: if#008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
end for
end procedure
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">(),</span>
 
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
atom t0 = time()
<span style="color: #004080;">integer</span> <span style="color: #000000;">tries</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">backtracks</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
integer tries = 0, backtracks = 0
<span style="color: #008080;">function</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
atom t1 = time()+1
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
function solve(integer row, integer col, integer n)
<span style="color: #0000FF;">?{</span><span style="color: #000000;">row</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">col</span><span style="color: #0000FF;">/</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">),</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tries</span><span style="color: #0000FF;">}</span>
integer nrow, ncol
<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: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
if time()>t1 then
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
?{row,floor(col/nchars),n,tries}
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
puts(1,join(board,"\n"))
<span style="color: #000000;">tries</span><span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
t1 = time()+1
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">limit</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- if wait_key()='!' then ?9/0 end if
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ncol</span>
tries+= 1
<span style="color: #008080;">for</span> <span style="color: #000000;">move</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
if n>limit then return 1 end if
<span style="color: #000000;">nrow</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ROW</span><span style="color: #0000FF;">]</span>
sequence wmoves = {}
<span style="color: #000000;">ncol</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">COL</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">nchars</span>
for move=1 to length(moves) do
<span style="color: #008080;">if</span> <span style="color: #000000;">onboard</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">)</span>
nrow = row+moves[move][ROW]
<span style="color: #008080;">and</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span>
ncol = col+moves[move][COL]*nchars
<span style="color: #000000;">wmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">],</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">})</span>
if onboard(nrow,ncol)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
and board[nrow][ncol]=' ' then
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
wmoves = append(wmoves,{warnsdorffs[nrow][ncol],nrow,ncol})
<span style="color: #000000;">wmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #000080;font-style:italic;">-- avoid creating orphans</span>
end for
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">2</span> <span style="color: #008080;">or</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
wmoves = sort(wmoves)
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
-- avoid creating orphans
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
if length(wmoves)<2 or wmoves[2][1]>1 then
<span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
for m=1 to length(wmoves) do
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
{?,nrow,ncol} = wmoves[m]
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
warnsdorffs[nrow][ncol] -= 1
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #004080;">integer</span> <span style="color: #000000;">scol</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ncol</span><span style="color: #0000FF;">-</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
for m=1 to length(wmoves) do
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">scol</span><span style="color: #0000FF;">..</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
{?,nrow,ncol} = wmoves[m]
<span style="color: #008080;">if</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
board[nrow][ncol-nchars+1..ncol] = sprintf(fmt,n)
<span style="color: #000000;">backtracks</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
if solve(nrow,ncol,n+1) then return 1 end if
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">scol</span><span style="color: #0000FF;">..</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">blank</span>
backtracks += 1
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
board[nrow][ncol-nchars+1..ncol] = blank
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
for m=1 to length(wmoves) do
<span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
{?,nrow,ncol} = wmoves[m]
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
warnsdorffs[nrow][ncol] += 1
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
return 0
end function
<span style="color: #008080;">procedure</span> <span style="color: #000000;">holyknight</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
 
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
procedure holyknight(sequence s)
<span style="color: #000000;">size</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
integer y, ch, sx, sy
<span style="color: #000000;">nchars</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" %d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">size</span><span style="color: #0000FF;">*</span><span style="color: #000000;">size</span><span style="color: #0000FF;">))</span>
s = split(s,'\n')
<span style="color: #000000;">fmt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" %%%dd"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
size = length(s)
<span style="color: #000000;">blank</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">)</span>
nchars = length(sprintf(" %d",size*size))
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">size</span><span style="color: #0000FF;">*</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">),</span><span style="color: #000000;">size</span><span style="color: #0000FF;">)</span>
fmt = sprintf(" %%%dd",nchars-1)
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
blank = repeat(' ',nchars)
<span style="color: #004080;">integer</span> <span style="color: #000000;">sx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sy</span>
board = repeat(repeat(' ',size*nchars),size)
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">size</span> <span style="color: #008080;">do</span>
limit = 1
<span style="color: #004080;">integer</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nchars</span>
for x=1 to size do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">size</span> <span style="color: #008080;">do</span>
y = nchars
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">])?</span><span style="color: #008000;">'-'</span><span style="color: #0000FF;">:</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
for j=1 to size do
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span>
if j>length(s[x]) then
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'-'</span>
ch = '-'
<span style="color: #008080;">elsif</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">then</span>
else
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
ch = s[x][j]
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end if
<span style="color: #008080;">elsif</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'1'</span> <span style="color: #008080;">then</span>
if ch=' ' then
<span style="color: #000000;">sx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
ch = '-'
<span style="color: #000000;">sy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span>
elsif ch='0' then
<span style="color: #008080;">end</span> ch<span style="color: ' '#008080;">if</span>
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
limit += 1
<span style="color: #000000;">y</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">nchars</span>
elsif ch='1' then
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
sx = x
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
sy = y
<span style="color: #000000;">warnsdorffs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">size</span><span style="color: #0000FF;">*</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">),</span><span style="color: #000000;">size</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #000000;">init_warnsdorffs</span><span style="color: #0000FF;">()</span>
board[x][y] = ch
<span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
y += nchars
<span style="color: #000000;">tries</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
end for
<span style="color: #000000;">backtracks</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
end for
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
warnsdorffs = repeat(repeat(0,size*nchars),size)
<span style="color: #008080;">if</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
init_warnsdorffs()
<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: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">))</span>
t0 = time()
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nsolution found in %d tries, %d backtracks (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tries</span><span style="color: #0000FF;">,</span><span style="color: #000000;">backtracks</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
tries = 0
<span style="color: #008080;">else</span>
backtracks = 0
<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>
t1 = time()+1
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if solve(sx,sy,2) then
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
puts(1,join(board,"\n"))
printf(1,"\nsolution found in %d tries, %d backtracks (%3.2fs)\n",{tries,backtracks,time()-t0})
<span style="color: #008080;">constant</span> <span style="color: #000000;">board1</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
else
000
puts(1,"no solutions found\n")
0 end if00
0000000
end procedure
000 0 0
 
0 0 000
constant board1 = """
1000000
000
0 00 0
000"""</span>
0000000
000 0 0
<span style="color: #000000;">holyknight</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board1</span><span style="color: #0000FF;">)</span>
0 0 000
1000000
<span style="color: #008080;">constant</span> <span style="color: #000000;">board2</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
00 0
-----1-0-----
000"""
-----0-0-----
 
----00000----
holyknight(board1)
-----000-----
 
--0--0-0--0--
constant board2 = """
00000---00000
-----1-0-----
--00---0-0---00--
- 00000---00000----
--0--0-000-0--0--
--0--0-0000---0--
00000 ----00000----
--00---0-0---00--
-----0-0-----"""</span>
00000---00000
--0--0-0--0--
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
-----000-----
<span style="color: #000000;">holyknight</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board2</span><span style="color: #0000FF;">)</span>
----00000----
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-----0-0-----
-----0-0-----"""
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
 
<!--</syntaxhighlight>-->
holyknight(board2)
 
{} = wait_key()</lang>
{{out}}
<pre>
Line 3,597 ⟶ 3,595:
- - - - - 27 - 29 - - - - -
solution found in 61341542 tries, 61341486 backtracks (180.56s)
</pre>
 
=={{header|Picat}}==
<syntaxhighlight lang="picat">import sat.
 
main =>
S = {".000....",
".0.00...",
".0000000",
"000..0.0",
"0.0..000",
"1000000.",
"..00.0..",
"...000.."},
MaxR = len(S),
MaxC = len(S[1]),
M = new_array(MaxR,MaxC),
StartR = _, % make StartR and StartC global
StartC = _,
foreach (R in 1..MaxR)
fill_row(R, S[R], M[R], 1, StartR, StartC)
end,
NZeros = len([1 : R in 1..MaxR, C in 1..MaxC, M[R,C] == 0]),
M :: 0..MaxR*MaxC-NZeros,
Vs = [{(R,C),1} : R in 1..MaxR, C in 1..MaxC, M[R,C] !== 0],
Es = [{(R,C),(R1,C1),_} : R in 1..MaxR, C in 1..MaxC, M[R,C] !== 0,
neibs(M,MaxR,MaxC,R,C,Neibs),
(R1,C1) in Neibs, M[R1,C1] !== 0],
hcp(Vs,Es),
foreach ({(R,C),(R1,C1),B} in Es)
B #/\ (R1 #!= StartR #\/ C1 #!= StartC) #=> M[R1,C1] #= M[R,C]+1
end,
solve(M),
foreach (R in 1..MaxR)
foreach (C in 1..MaxC)
if M[R,C] == 0 then
printf("%4c", '.')
else
printf("%4d", M[R,C])
end
end,
nl
end.
 
neibs(M,MaxR,MaxC,R,C,Neibs) =>
Connected = [(R+1, C+2),
(R+1, C-2),
(R-1, C+2),
(R-1, C-2),
(R+2, C+1),
(R+2, C-1),
(R-2, C+1),
(R-2, C-1)],
Neibs = [(R1,C1) : (R1,C1) in Connected,
R1 >= 1, R1 =< MaxR, C1 >= 1, C1 =< MaxC,
M[R1,C1] !== 0].
 
fill_row(_R, [], _Row, _C, _StartR, _StartC) => true.
fill_row(R, ['.'|Str], Row, C, StartR, StartC) =>
Row[C] = 0,
fill_row(R,Str, Row, C+1, StartR, StartC).
fill_row(R, ['0'|Str], Row, C, StartR, StartC) =>
fill_row(R, Str, Row, C+1, StartR, StartC).
fill_row(R, ['1'|Str], Row, C, StartR, StartC) =>
Row[C] = 1,
StartR = R,
StartC = C,
fill_row(R, Str, Row, C+1, StartR, StartC).
</syntaxhighlight>
{{out}}
<pre>
. 7 4 25 . . . .
. 26 . 8 5 . . .
. 29 6 3 24 9 18 11
27 2 23 . . 12 . 16
30 . 28 . . 17 10 19
1 22 31 34 13 20 15 .
. . 36 21 . 33 . .
. . . 32 35 14 . .
</pre>
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">
from sys import stdout
moves = [
Line 3,655 ⟶ 3,733:
print()
find_solution(".....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)
</syntaxhighlight>
</lang>
{{out}}<pre>
17 14 29
Line 3,689 ⟶ 3,767:
It solves the tasked problem, as well as the "extra credit" from [[#Ada]].
 
<langsyntaxhighlight lang="racket">#lang racket
(require "hidato-family-solver.rkt")
 
Line 3,726 ⟶ 3,804:
#(- - - - 0 0 0 0 0 - - - -)
#(- - - - - 0 - 0 - - - - -)
#(- - - - - 0 - 0 - - - - -)))))</langsyntaxhighlight>
 
{{out}}
Line 3,763 ⟶ 3,841:
* [[Solve the no connection puzzle#Raku|Solve the no connection puzzle]]
 
<syntaxhighlight lang="raku" perl6line>my @adjacent =
[ -2, -1], [ -2, 1],
[-1,-2], [-1,+2],
Line 3,864 ⟶ 3,942:
say "$tries tries";
}</langsyntaxhighlight>
 
{{out}}
Line 3,883 ⟶ 3,961:
 
This is an &nbsp; ''open tour'' &nbsp; solution. &nbsp; (See this task's &nbsp; ''discussion'' &nbsp; page for an explanation &nbsp; [in the first section]).
<langsyntaxhighlight lang="rexx">/*REXX program solves the holy knight's tour problem for a (general) NxN 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. */
Line 3,946 ⟶ 4,024:
end /*try a different move. */
end /*t*/ /* [↑] all moves tried.*/
return 0 /*tour isn't possible. */</langsyntaxhighlight>
'''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>
Line 3,998 ⟶ 4,076:
=={{header|Ruby}}==
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#With_Warnsdorff | here]]
<langsyntaxhighlight lang="ruby">require 'HLPsolver'
 
ADJACENT = [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]
Line 4,014 ⟶ 4,092:
t0 = Time.now
HLPsolver.new(boardy).solve
puts " #{Time.now - t0} sec"</langsyntaxhighlight>
 
Which produces:
Line 4,044 ⟶ 4,122:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.6
 
oo::class create HKTSolver {
Line 4,141 ⟶ 4,219:
HKTSolver create hkt $puzzle
hkt solve
showPuzzle [hkt solution] "Output"</langsyntaxhighlight>
{{out}}
<pre>
Line 4,167 ⟶ 4,245:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./fmt" for Fmt
 
var moves = [ [-1, -2], [1, -2], [-1, 2], [1, 2], [-2, -1], [-2, 1], [2, -1], [2, 1] ]
Line 4,251 ⟶ 4,329:
findSolution.call(board1, 8)
System.print()
findSolution.call(board2, 13)</langsyntaxhighlight>
 
{{out}}
9,485

edits