Knight's tour: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
m (→{{header|C++}}) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 291:
16 31 12 41 26 29 10 63
</pre>
=={{header|Ada}}==
Line 873 ⟶ 872:
1| 12 25 14 31 10 27 36 61
</pre>
=={{header|ANSI Standard BASIC}}==
{{trans|BBC BASIC}}
Line 1,421:
return 0;
}</lang>
=={{header|C sharp}}==
<lang csharp>using System;
using System.Collections.Generic;
namespace prog
{
class MainClass
{
const int N = 8;
readonly static int[,] moves = { {+1,-2},{+2,-1},{+2,+1},{+1,+2},
{-1,+2},{-2,+1},{-2,-1},{-1,-2} };
struct ListMoves
{
public int x, y;
public ListMoves( int _x, int _y ) { x = _x; y = _y; }
}
public static void Main (string[] args)
{
int[,] board = new int[N,N];
board.Initialize();
int x = 0, // starting position
y = 0;
List<ListMoves> list = new List<ListMoves>(N*N);
list.Add( new ListMoves(x,y) );
do
{
if ( Move_Possible( board, x, y ) )
{
int move = board[x,y];
board[x,y]++;
x += moves[move,0];
y += moves[move,1];
list.Add( new ListMoves(x,y) );
}
else
{
if ( board[x,y] >= 8 )
{
board[x,y] = 0;
list.RemoveAt(list.Count-1);
if ( list.Count == 0 )
{
Console.WriteLine( "No solution found." );
return;
}
x = list[list.Count-1].x;
y = list[list.Count-1].y;
}
board[x,y]++;
}
}
while( list.Count < N*N );
int last_x = list[0].x,
last_y = list[0].y;
string letters = "ABCDEFGH";
for( int i=1; i<list.Count; i++ )
{
Console.WriteLine( string.Format("{0,2}: ", i) + letters[last_x] + (last_y+1) + " - " + letters[list[i].x] + (list[i].y+1) );
last_x = list[i].x;
last_y = list[i].y;
}
}
static bool Move_Possible( int[,] board, int cur_x, int cur_y )
{
if ( board[cur_x,cur_y] >= 8 )
return false;
int new_x = cur_x + moves[board[cur_x,cur_y],0],
new_y = cur_y + moves[board[cur_x,cur_y],1];
if ( new_x >= 0 && new_x < N && new_y >= 0 && new_y < N && board[new_x,new_y] == 0 )
return true;
return false;
}
}
}</lang>
Line 1,623 ⟶ 1,709:
</pre>
=={{header|
Using warnsdorff's rule
<lang Clojure>
(defn isin? [x li]
(not= [] (filter #(= x %) li)))
(defn options [movements pmoves n]
(let [x (first (last movements)) y (second (last movements))
op (vec (map #(vector (+ x (first %)) (+ y (second %))) pmoves))
vop (filter #(and (>= (first %) 0) (>= (last %) 0)) op)
vop1 (filter #(and (< (first %) n) (< (last %) n)) vop)]
(vec (filter #(not (isin? % movements)) vop1))))
(defn next-move [movements pmoves n]
(let [op (options movements pmoves n)
sp (map #(vector % (count (options (conj movements %) pmoves n))) op)
m (apply min (map last sp))]
(first (rand-nth (filter #(= m (last %)) sp)))))
(defn jumps [n pos]
(let [movements (vector pos)
pmoves [[1 2] [1 -2] [2 1] [2 -1]
[-1 2] [-1 -2] [-2 -1] [-2 1]]]
(loop [mov movements x 1]
(if (= x (* n n))
mov
(let [np (next-move mov pmoves n)]
(recur (conj mov np) (inc x)))))))
</lang>
{{out}}
<pre>
(jumps 5 [0 0])
[[0 0] [1 2] [0 4] [2 3] [4 4] [3 2] [4 0] [2 1] [1 3] [0 1] [2 0] [4 1] [3 3] [1 4] [0 2] [1 0] [3 1] [4 3] [2 4] [0 3] [1 1] [3 0] [4 2] [3 4] [2 2]]
(jumps 8 [0 0])
[[0 0] [2 1] [4 0] [6 1] [7 3] [6 5] [7 7] [5 6] [3 7] [1 6] [0 4] [1 2] [2 0] [0 1] [1 3] [0 5] [1 7] [2 5] [0 6] [2 7] [4 6] [6 7] [7 5] [6 3] [7 1] [5 0] [3 1] [1 0] [0 2] [1 4] [3 5] [4 7] [6 6] [7 4] [6 2] [7 0] [5 1] [7 2] [6 0] [4 1] [5 3] [3 2] [4 4] [5 2] [3 3] [5 4] [4 2] [2 3] [1 1] [3 0] [2 2] [0 3] [2 4] [4 3] [6 4] [4 5] [2 6] [0 7] [1 5] [3 4] [5 5] [7 6] [5 7] [3 6]]
(let [j (jumps 40 [0 0])] ;; are
(and (distinct? j) ;; all squares only once? and
(= (count j) (* 40 40)))) ;; 40*40 squares?
true
</pre>
=={{header|CoffeeScript}}==
Line 1,857 ⟶ 1,900:
sys 0m0.253s
</lang>
=={{header|D}}==
Line 2,782:
*** Trovata la soluzione! ***
</pre>
=={{header|FreeBASIC}}==
Line 2,872 ⟶ 2,864:
Pulsa cualquier tecla para finalizar...
</pre>
=={{header|Fōrmulæ}}==
In [http://wiki.formulae.org/Knight%27s_tour this] page you can see the solution of this task.
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text ([http://wiki.formulae.org/Editing_F%C5%8Drmul%C3%A6_expressions more info]). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition.
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
=={{header|Go}}==
Line 4,407:
62 51 54 41 60 39 56 43
</pre>
=={{header|Kotlin}}==
Line 4,978 ⟶ 4,976:
[[File:perl_knights_tour.png]]
=={{header|Phix}}==
Line 5,770 ⟶ 5,689:
29 26 7 62 21 24 5 2
</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Perl}}
{{works with|rakudo|2015-09-17}}
<lang perl6>my @board;
my $I = 8;
my $J = 8;
my $F = $I*$J > 99 ?? "%3d" !! "%2d";
# Choose starting position - may be passed in on command line; if
# not, choose random square.
my ($i, $j);
if my $sq = shift @*ARGS {
die "$*PROGRAM_NAME: illegal start square '$sq'\n" unless ($i, $j) = from_algebraic($sq);
}
else {
($i, $j) = (^$I).pick, (^$J).pick;
}
# Move sequence
my @moves = ();
for 1 .. $I * $J -> $move {
# Record current move
push @moves, to_algebraic($i,$j);
# @board[$i] //= []; # (uncomment if autoviv is broken)
@board[$i][$j] = $move;
# Find move with the smallest degree
my @min = (9);
for possible_moves($i,$j) -> @target {
my ($ni, $nj) = @target;
my $next = possible_moves($ni,$nj);
@min = $next, $ni, $nj if $next < @min[0];
}
# And make it
($i, $j) = @min[1,2];
}
# Print the move list
for @moves.kv -> $i, $m {
print ',', $i %% 16 ?? "\n" !! " " if $i;
print $m;
}
say "\n";
# And the board, with move numbers
for ^$I -> $i {
for ^$J -> $j {
# Assumes (1) ANSI sequences work, and (2) output
# is light text on a dark background.
print "\e[7m" if $i % 2 == $j % 2;
printf $F, @board[$i][$j];
print "\e[0m";
}
print "\n";
}
# Find the list of positions the knight can move to from the given square
sub possible_moves($i,$j) {
grep -> [$ni, $nj] { $ni ~~ ^$I and $nj ~~ ^$J and !@board[$ni][$nj] },
[$i-2,$j-1], [$i-2,$j+1], [$i-1,$j-2], [$i-1,$j+2],
[$i+1,$j-2], [$i+1,$j+2], [$i+2,$j-1], [$i+2,$j+1];
}
# Return the algebraic name of the square identified by the coordinates
# i=rank, 0=black's home row; j=file, 0=white's queen's rook
sub to_algebraic($i,$j) {
chr(ord('a') + $j) ~ ($I - $i);
}
# Return the coordinates matching the given algebraic name
sub from_algebraic($square where /^ (<[a..z]>) (\d+) $/) {
$I - $1, ord(~$0) - ord('a');
}</lang>
(Output identical to Perl's above.)
=={{header|REXX}}==
Line 6,091 ⟶ 6,090:
a1b3a5b7c5a4b2c4a3b1c3a2b4a6b8c6a7b5c7a8b6c8d6e4d2f1e3c2d4e2c1d3e1g2f4d5e7g8h6f5h4g6h8f7d8e6f8d7e5g4h2f3g1h3g5h7f6e8g7h5g3h1f2d1
</pre>
=={{header|Scheme}}==
<lang scheme>
Line 6,235:
256 191 30 189 274 265 28 269 272 291 26 319 328 325 24 337 330 391 22 19
</pre>
=={{header|Sidef}}==
{{trans|Perl 6}}
| |||