Solve a Holy Knight's tour: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 2,954: | Line 2,954: | ||
53 49 |
53 49 |
||
</pre> |
</pre> |
||
=={{header|Nim}}== |
|||
{{trans|Go}} |
|||
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! |
|||
<lang Nim>import sequtils, strformat |
|||
const Moves = [[-1, -2], [1, -2], [-2, -1], [2, -1], [-2, 1], [2, 1], [-1, 2], [1, 2]] |
|||
proc solve(pz: var seq[seq[int]]; sx, sy, idx, count: Natural): bool = |
|||
if idx > count: return true |
|||
var x, y: int |
|||
for move in Moves: |
|||
x = sx + move[0] |
|||
y = sy + move[1] |
|||
if x in 0..pz.high and y in 0..pz.high and pz[x][y] == 0: |
|||
pz[x][y] = idx |
|||
if pz.solve(x, y, idx + 1, count): return true |
|||
pz[x][y] = 0 |
|||
proc findSolution(board: openArray[string]) = |
|||
let sz = board.len |
|||
var pz = newSeqWith(sz, repeat(-1, sz)) |
|||
var count = 0 |
|||
var x, y: int |
|||
for i in 0..<sz: |
|||
for j in 0..<sz: |
|||
case board[i][j] |
|||
of 'x': |
|||
pz[i][j] = 0 |
|||
inc count |
|||
of 's': |
|||
pz[i][j] = 1 |
|||
inc count |
|||
(x, y) = (i, j) |
|||
else: |
|||
discard |
|||
if pz.solve(x, y, 2, count): |
|||
for i in 0..<sz: |
|||
for j in 0..<sz: |
|||
if pz[i][j] != -1: |
|||
stdout.write &"{pz[i][j]:02} " |
|||
else: |
|||
stdout.write "-- " |
|||
stdout.write '\n' |
|||
when isMainModule: |
|||
const |
|||
Board1 = [" xxx ", |
|||
" x xx ", |
|||
" xxxxxxx", |
|||
"xxx x x", |
|||
"x x xxx", |
|||
"sxxxxxx ", |
|||
" xx x ", |
|||
" xxx "] |
|||
Board2 = [".....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....."] |
|||
Board1.findSolution() |
|||
echo() |
|||
Board2.findSolution()</lang> |
|||
{{out}} |
|||
<pre>-- 13 06 15 -- -- -- -- |
|||
-- 08 -- 12 31 -- -- -- |
|||
-- 05 14 07 16 27 32 29 |
|||
09 02 11 -- -- 30 -- 26 |
|||
04 -- 22 -- -- 17 28 33 |
|||
01 10 03 18 21 34 25 -- |
|||
-- -- 36 23 -- 19 -- -- |
|||
-- -- -- 20 35 24 -- -- |
|||
-- -- -- -- -- 01 -- 55 -- -- -- -- -- |
|||
-- -- -- -- -- 50 -- 48 -- -- -- -- -- |
|||
-- -- -- -- 02 47 54 51 56 -- -- -- -- |
|||
-- -- -- -- -- 52 49 46 -- -- -- -- -- |
|||
-- -- 14 -- -- 03 -- 53 -- -- 44 -- -- |
|||
09 06 11 04 13 -- -- -- 45 38 33 40 43 |
|||
-- -- 08 15 -- -- -- -- -- 35 42 -- -- |
|||
07 10 05 12 17 -- -- -- 37 32 39 34 41 |
|||
-- -- 16 -- -- 23 -- 31 -- -- 36 -- -- |
|||
-- -- -- -- -- 18 21 24 -- -- -- -- -- |
|||
-- -- -- -- 22 25 28 19 30 -- -- -- -- |
|||
-- -- -- -- -- 20 -- 26 -- -- -- -- -- |
|||
-- -- -- -- -- 27 -- 29 -- -- -- -- -- </pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |