Anonymous user
Solve a Holy Knight's tour: Difference between revisions
→{{header|Nim}}
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 2,954:
53 49
</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}}==
| |||