Anonymous user
Knight's tour: Difference between revisions
+ second D entry
(Added a back tracking tie breaker) |
(+ second D entry) |
||
Line 1,075:
=={{header|D}}==
===Fast Version===
{{trans|C++}}
<lang d>import std.stdio, std.algorithm, std.random, std.range,
Line 1,200 ⟶ 1,201:
4 67 64 61 238 69 96 59 244 71 94 57 310 73 92 55 354 75 90 53 374 77 88 51 156 79 86 49 146 81 84
1 62 3 68 65 60 237 70 95 58 245 72 93 56 311 74 91 54 355 76 89 52 157 78 87 50 147 80 85 48 145</pre>
===Shorter Version===
{{trans|Haskell}}
<lang d>import std.stdio, std.math, std.algorithm, std.range, std.conv;
alias Sq = Tuple!(int,"x", int,"y"); /// Square.
enum knightMoves = (in Sq[] board, in Sq s) /*pure nothrow*/ =>
cartesianProduct([1, -1, 2, -2], [1, -1, 2, -2])
.filter!(ij => ij[0].abs != ij[1].abs)
.map!(ij => Sq(s.x + ij[0], s.y + ij[1]))
.filter!(x => board.canFind(x));
const(Sq[]) knightTour(in Sq[] board, in Sq[] moves) /*pure nothrow*/ {
enum findMoves = (Sq sq) => knightMoves(board, sq)
.filter!(s => !moves.canFind(s)).array;
auto newMoves = findMoves(moves.back);
if (newMoves.empty) return moves;
//const newSq = newMoves.reduce!(min!(m => findMoves(m).length));
immutable newSq = newMoves.map!(s => tuple(findMoves(s).length, s))
.reduce!min[1];
return board.knightTour(moves ~ newSq);
}
void main(in string[] args) {
enum toSq = (in string xy) => Sq(xy[0] - '`', xy[1] - '0');
immutable toAlg = (in Sq s) => [to!char(s.x + '`'),
to!char(s.y + '0')];
immutable sq = toSq((args.length == 2) ? args[1] : "e5");
const board = iota(1, 9).cartesianProduct(iota(1, 9)).map!Sq.array;
writefln("%(%-(%s -> %)\n%)",
board.knightTour([sq]).map!toAlg.chunks(8));
}</lang>
{{out}}
<pre>e5 -> d7 -> b8 -> a6 -> b4 -> a2 -> c1 -> b3
a1 -> c2 -> a3 -> b1 -> d2 -> f1 -> h2 -> g4
h6 -> g8 -> e7 -> c8 -> a7 -> c6 -> a5 -> b7
d8 -> f7 -> h8 -> g6 -> f8 -> h7 -> f6 -> e8
g7 -> h5 -> g3 -> h1 -> f2 -> d1 -> b2 -> a4
b6 -> a8 -> c7 -> b5 -> c3 -> d5 -> e3 -> c4
d6 -> e4 -> c5 -> d3 -> e1 -> g2 -> h4 -> f5
d4 -> e2 -> f4 -> e6 -> g5 -> f3 -> g1 -> h3</pre>
=={{header|Erlang}}==
| |||