Knight's tour: Difference between revisions
→{{header|jq}}
No edit summary |
|||
(6 intermediate revisions by 4 users not shown) | |||
Line 972:
1| 12 25 14 31 10 27 36 61
</pre>
=={{header|ATS}}==
Line 2,030 ⟶ 1,948:
</pre>
=={{header|
==={{header|ANSI BASIC}}===
{{trans|BBC BASIC}}
[[File:Knights_Tour.gif|right]]
{{works with|Decimal BASIC}}
ANSI BASIC does not allow function parameters to be passed by reference, so X and Y were made global variables.
<syntaxhighlight lang="basic">100 DECLARE EXTERNAL FUNCTION choosemove
110 !
120 RANDOMIZE
130 PUBLIC NUMERIC X, Y, TRUE, FALSE
140 LET TRUE = -1
150 LET FALSE = 0
160 !
170 SET WINDOW 1,512,1,512
180 SET AREA COLOR "black"
190 FOR x=0 TO 512-128 STEP 128
200 FOR y=0 TO 512-128 STEP 128
210 PLOT AREA:x+64,y;x+128,y;x+128,y+64;x+64,y+64
220 PLOT AREA:x,y+64;x+64,y+64;x+64,y+128;x,y+128
230 NEXT y
240 NEXT x
250 !
260 SET LINE COLOR "red"
270 SET LINE WIDTH 6
280 !
290 PUBLIC NUMERIC Board(0 TO 7,0 TO 7)
300 LET X = 0
310 LET Y = 0
320 LET Total = 0
330 DO
340 LET Board(X,Y) = TRUE
350 PLOT LINES: X*64+32,Y*64+32;
360 LET Total = Total + 1
370 LOOP UNTIL choosemove(X, Y) = FALSE
380 IF Total <> 64 THEN STOP
390 END
400 !
410 EXTERNAL FUNCTION choosemove(X1, Y1)
420 DECLARE EXTERNAL SUB trymove
430 LET M = 9
440 CALL trymove(X1+1, Y1+2, M, newx, newy)
450 CALL trymove(X1+1, Y1-2, M, newx, newy)
460 CALL trymove(X1-1, Y1+2, M, newx, newy)
470 CALL trymove(X1-1, Y1-2, M, newx, newy)
480 CALL trymove(X1+2, Y1+1, M, newx, newy)
490 CALL trymove(X1+2, Y1-1, M, newx, newy)
500 CALL trymove(X1-2, Y1+1, M, newx, newy)
510 CALL trymove(X1-2, Y1-1, M, newx, newy)
520 IF M=9 THEN
530 LET choosemove = FALSE
540 EXIT FUNCTION
550 END IF
560 LET X = newx
570 LET Y = newy
580 LET choosemove = TRUE
590 END FUNCTION
600 !
610 EXTERNAL SUB trymove(X, Y, M, newx, newy)
620 !
630 DECLARE EXTERNAL FUNCTION validmove
640 IF validmove(X,Y) = 0 THEN EXIT SUB
650 IF validmove(X+1,Y+2) <> 0 THEN LET N = N + 1
660 IF validmove(X+1,Y-2) <> 0 THEN LET N = N + 1
670 IF validmove(X-1,Y+2) <> 0 THEN LET N = N + 1
680 IF validmove(X-1,Y-2) <> 0 THEN LET N = N + 1
690 IF validmove(X+2,Y+1) <> 0 THEN LET N = N + 1
700 IF validmove(X+2,Y-1) <> 0 THEN LET N = N + 1
710 IF validmove(X-2,Y+1) <> 0 THEN LET N = N + 1
720 IF validmove(X-2,Y-1) <> 0 THEN LET N = N + 1
730 IF N>M THEN EXIT SUB
740 IF N=M AND RND<.5 THEN EXIT SUB
750 LET M = N
760 LET newx = X
770 LET newy = Y
780 END SUB
790 !
800 EXTERNAL FUNCTION validmove(X,Y)
810 LET validmove = FALSE
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
840 END FUNCTION</syntaxhighlight>
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
[[Image:knights_tour_bbc.gif|right]]
Line 3,171:
{{works with|Delphi|6.0}}
{{libheader|Forms,Types,SysUtils,Graphics,ExtCtrls}}
[[File:DelphiKnightsTour.png|thumb|none]]
Brute force method. Takes a long time for most solutions, so some optimization should be used. However, it has nice graphics.
<syntaxhighlight lang="Delphi">
Line 3,398 ⟶ 3,400:
</syntaxhighlight>
{{out}}
<pre>
</pre>
Line 4,413 ⟶ 4,416:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Knight%27s_tour}}
=={{header|Fortran}}==
Line 7,621 ⟶ 7,620:
63 54 35 16 61 28 33 18
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>
Line 11,526 ⟶ 11,611:
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="
construct new(x, y) {
_x = x
|