Knight's tour: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
Line 7,620: | Line 7,620: | ||
63 54 35 16 61 28 33 18 |
63 54 35 16 61 28 33 18 |
||
36 15 64 55 34 17 30 27 |
36 15 64 55 34 17 30 27 |
||
</pre> |
|||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
'''Works with jq, the C implementation of jq''' |
|||
'''Works with gojq, the Go implementation of jq''' except that |
|||
_nwise/1 must be provided. |
|||
In the following program, the board size is specified by the top-level function named `boardSize` |
|||
so that it can readily be changed, e.g. to a variable set on the command-line. |
|||
In calculating algebraic notation, however, it is assumed that the board size is no larger than |
|||
26x26. |
|||
<syntaxhighlight lang="jq"> |
|||
# The number of columns |
|||
def boardSize: 8; |
|||
# {x,y} with .x >= 0 and .y >= 0 |
|||
def Square($x; $y): {$x, $y}; |
|||
# Input: a Square assuming .x <= 25 |
|||
def notate: |
|||
.x as $x |
|||
| "abcdefghijklmnopqrstuvwxyz"[$x:$x+1] + "\(.y + 1)"; |
|||
# Input: a Square |
|||
# Output: a stream of possible Squares reachable from . |
|||
def knightMoves: |
|||
def axisMoves: [1, 2, -1, -2]; |
|||
# Is the input Square on the board? |
|||
def onBoard: |
|||
0 <= .x and .x < boardSize and 0 <= .y and .y < boardSize; |
|||
. as $s |
|||
| axisMoves |
|||
| combinations(2) |
|||
| select( (.[0]|length) != (.[1]|length) ) # abs |
|||
| Square($s.x + .[0]; $s.y + .[1]) |
|||
| select(onBoard) ; |
|||
# $moves should be a non-empty array specifying an initial fragment of a possible tour |
|||
def knightTour($moves): |
|||
# Find the array of relevant possible one-step moves from the Square specified by . |
|||
def findMoves: |
|||
[ knightMoves | select( IN($moves[]) | not) ] ; |
|||
($moves[-1] | findMoves) as $fm |
|||
| if $fm == [] then $moves |
|||
else ($fm | min_by( findMoves|length )) as $next |
|||
| knightTour($moves + [$next]) |
|||
end ; |
|||
def knightTourFrom($start): |
|||
knightTour([$start]) ; |
|||
def example($square): |
|||
knightTourFrom($square) |
|||
| (_nwise(boardSize) | map("\(.x),\(.y)") | join(" ")), |
|||
"\nAlgebraic notation:", |
|||
(_nwise(boardSize) | map( notate ) | join(" ")) |
|||
; |
|||
example(Square(1; 1)) |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
1,1 3,0 5,1 7,0 6,2 7,4 6,6 4,7 |
|||
2,6 0,7 1,5 0,3 2,2 1,0 0,2 1,4 |
|||
0,6 2,7 3,5 1,6 3,7 5,6 7,7 6,5 |
|||
7,3 6,1 4,0 2,1 0,0 1,2 0,4 2,3 |
|||
3,1 5,0 7,1 6,3 7,5 6,7 4,6 5,4 |
|||
4,2 3,4 5,5 7,6 5,7 3,6 1,7 0,5 |
|||
1,3 0,1 2,0 3,2 4,4 2,5 3,3 4,1 |
|||
5,3 7,2 6,0 5,2 6,4 4,5 2,4 4,3 |
|||
Algebraic notation: |
|||
b2 d1 f2 h1 g3 h5 g7 e8 |
|||
c7 a8 b6 a4 c3 b1 a3 b5 |
|||
a7 c8 d6 b7 d8 f7 h8 g6 |
|||
h4 g2 e1 c2 a1 b3 a5 c4 |
|||
d2 f1 h2 g4 h6 g8 e7 f5 |
|||
e3 d5 f6 h7 f8 d7 b8 a6 |
|||
b4 a2 c1 d3 e5 c6 d4 e2 |
|||
f4 h3 g1 f3 g5 e6 c5 e4 |
|||
</pre> |
</pre> |
||