Solve a Hidato puzzle: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
(Replaced "split" with "splitWhiteSpace". Created a Hidato type to manage context. Changed to allocate the board dynamically. Change indentation to conform to style guide. Many other changes.) |
||
Line 2,653: | Line 2,653: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
<lang nim>import strutils, algorithm |
<lang nim>import strutils, algorithm, sequtils, strformat |
||
type Hidato = object |
|||
var board: array[0..19, array[0..19, int]] |
|||
board: seq[seq[int]] |
|||
given: seq[int] |
|||
var rows, cols: int = 0 |
|||
start: (int, int) |
|||
proc setup(s: string) = |
|||
var lines = s.splitLines() |
|||
cols = lines[0].split().len() |
|||
rows = lines.len() |
|||
proc initHidato(s: string): Hidato = |
|||
for i in 0 .. rows + 1: |
|||
var lines = s.splitLines() |
|||
for j in 0 .. cols + 1: |
|||
let cols = lines[0].splitWhitespace().len() |
|||
board[i][j] = -1 |
|||
let rows = lines.len() |
|||
result.board = newSeqWith(rows + 2, newSeq[int](cols + 2)) # Make room for borders. |
|||
for r, row in pairs(lines): |
|||
for c, cell in pairs(row.split()): |
|||
case cell |
|||
of "__" : |
|||
board[r + 1][c + 1] = 0 |
|||
continue |
|||
of "." : continue |
|||
else : |
|||
var val = parseInt(cell) |
|||
board[r + 1][c + 1] = val |
|||
given.add(val) |
|||
if (val == 1): |
|||
start.add(r + 1) |
|||
start.add(c + 1) |
|||
given.sort(cmp[int], Ascending) |
|||
proc solve(r, c, n: int, next: int = 0): bool = |
|||
if n > given[high(given)]: |
|||
return true |
|||
if board[r][c] < 0: |
|||
return false |
|||
if (board[r][c] > 0 and board[r][c] != n): |
|||
return false |
|||
if (board[r][c] == 0 and given[next] == n): |
|||
return false |
|||
for i in 0 .. result.board.high: |
|||
board[ |
for j in 0 .. result.board[0].high: |
||
result.board[i][j] = -1 |
|||
for j in -1 .. 1: |
|||
if back == n: |
|||
if (solve(r + i, c + j, n + 1, next + 1)): return true |
|||
else: |
|||
if (solve(r + i, c + j, n + 1, next)): return true |
|||
board[r][c] = back |
|||
result = false |
|||
for r, row in lines: |
|||
for c, cell in row.splitWhitespace().pairs(): |
|||
proc printBoard() = |
|||
case cell |
|||
of "__" : |
|||
for cellid,c in pairs(board[r]): |
|||
result.board[r + 1][c + 1] = 0 |
|||
continue |
|||
of "." : |
|||
continue |
|||
else : |
|||
write(stdout, "__ ") |
|||
let val = parseInt(cell) |
|||
result.board[r + 1][c + 1] = val |
|||
write(stdout, "$# " % align($c,2)) |
|||
result.given.add(val) |
|||
if val == 1: |
|||
result.start = (r + 1, c + 1) |
|||
result.given.sort() |
|||
proc solve(hidato: var Hidato; r, c, n: int; next = 0): bool = |
|||
if n > hidato.given[^1]: |
|||
return true |
|||
if hidato.board[r][c] < 0: |
|||
return false |
|||
if hidato.board[r][c] > 0 and hidato.board[r][c] != n: |
|||
return false |
|||
if hidato.board[r][c] == 0 and hidato.given[next] == n: |
|||
return false |
|||
let back = hidato.board[r][c] |
|||
hidato.board[r][c] = n |
|||
for i in -1 .. 1: |
|||
for j in -1 .. 1: |
|||
if back == n: |
|||
if hidato.solve(r + i, c + j, n + 1, next + 1): return true |
|||
else: |
|||
if hidato.solve(r + i, c + j, n + 1, next): return true |
|||
hidato.board[r][c] = back |
|||
result = false |
|||
proc print(hidato: Hidato) = |
|||
for row in hidato.board: |
|||
for val in row: |
|||
stdout.write if val == -1: " . " elif val == 0: "__ " else: &"{val:2} " |
|||
writeLine(stdout, "") |
|||
var hi = """ |
|||
__ 33 35 __ __ . . . |
|||
__ __ 24 22 __ . . . |
__ __ 24 22 __ . . . |
||
__ __ __ 21 __ __ . . |
__ __ __ 21 __ __ . . |
||
Line 2,726: | Line 2,725: | ||
. . . . __ 7 __ __ |
. . . . __ 7 __ __ |
||
. . . . . . 5 __""" |
. . . . . . 5 __""" |
||
var hidato = initHidato(hi) |
|||
setup(hi) |
|||
hidato.print() |
|||
printBoard() |
|||
echo("") |
echo("") |
||
echo("Found:") |
echo("Found:") |
||
discard solve(start[0], start[1], 1) |
discard hidato.solve(hidato.start[0], hidato.start[1], 1) |
||
hidato.print()</lang> |
|||
{{out}} |
{{out}} |
||
<pre> . . . . . . . . . . |
<pre> . . . . . . . . . . |