Solve a Hidato puzzle: Difference between revisions
Content added Content deleted
(Added Go) |
|||
Line 1,904: | Line 1,904: | ||
. . . . . . . 5 4 . |
. . . . . . . 5 4 . |
||
. . . . . . . . . .</pre> |
. . . . . . . . . .</pre> |
||
=={{header|Julia}}== |
|||
<lang julia>function hidatoconfigure(str) |
|||
if match(r"[^\s\.\_\d]", str) != nothing |
|||
throw("Bad Hidato: ($str) Characters must be whitespace, _, ., or digit") |
|||
end |
|||
lines = map(x -> x * " ", split(str, "\n")) |
|||
lengths = map(length, lines) |
|||
nrows, ncols = length(lines), lengths[1] |
|||
if ncols % 3 != 0 || maximum(map(length, lines)) != minimum(map(length, lines)) |
|||
throw("Bad Hidato: ($str) Nonrectangular or line length not multiple of 3") |
|||
end |
|||
board = fill(-1, (nrows, div(ncols, 3))) |
|||
presets = Vector{Int}() |
|||
startpos = [0, 0] |
|||
for i in 1:nrows, j in 1:div(ncols, 3) |
|||
ch = lines[i][3 * (j-1) + 2] |
|||
if ch == '_' |
|||
board[i, j] = 0 |
|||
elseif ch == '.' |
|||
continue |
|||
else # numeral, get 2 digits |
|||
board[i, j] = parse(Int, lines[i][3*(j-1)+1:3*(j-1)+2]) |
|||
push!(presets, board[i, j]) |
|||
if board[i, j] == 1 |
|||
startpos = [i, j] |
|||
end |
|||
end |
|||
end |
|||
board, sort!(presets), startpos |
|||
end |
|||
function hidatosolve(board, fixed, row, col, sought, next) |
|||
if sought > fixed[end] |
|||
return true |
|||
elseif (board[row, col] != 0 && board[row, col] != sought) || |
|||
(board[row, col] == 0 && fixed[next] == sought) |
|||
return false |
|||
end |
|||
backnum = 0 |
|||
if board[row, col] == sought |
|||
backnum = sought |
|||
next += 1 |
|||
end |
|||
board[row, col] = sought # try board with this cell set to next number |
|||
maxrow, maxcol = size(board) |
|||
for i in max(row - 1, 1):min(row + 1, maxrow), j in max(col -1, 1):min(col + 1, maxcol) |
|||
if i == row && j == col |
|||
continue |
|||
elseif hidatosolve(board, fixed, i, j, sought +1, next) |
|||
return true |
|||
end |
|||
end |
|||
board[row, col] = backnum # return board to original state |
|||
false |
|||
end |
|||
function printboard(board) |
|||
d = Dict(-1 => " ", 0 => "__ ", -2 => "\n") |
|||
bmax = maximum(board) |
|||
map(x -> d[x] = rpad(lpad(string(x), 2), 3), 1:bmax) |
|||
println(join([d[i] for i in hcat(board, fill(-2, size(board)[1]))'], "")) |
|||
end |
|||
hidat = """ |
|||
__ 33 35 __ __ . . . |
|||
__ __ 24 22 __ . . . |
|||
__ __ __ 21 __ __ . . |
|||
__ 26 __ 13 40 11 . . |
|||
27 __ __ __ 9 __ 1 . |
|||
. . __ __ 18 __ __ . |
|||
. . . . __ 7 __ __ |
|||
. . . . . . 5 __""" |
|||
board, fixed, start = hidatoconfigure(hidat) |
|||
printboard(board) |
|||
hidatosolve(board, fixed, start[1], start[2], 1, 1) |
|||
printboard(board) |
|||
</lang>{{output}}<pre> |
|||
__ 33 35 __ __ |
|||
__ __ 24 22 __ |
|||
__ __ __ 21 __ __ |
|||
__ 26 __ 13 40 11 |
|||
27 __ __ __ 9 __ 1 |
|||
__ __ 18 __ __ |
|||
__ 7 __ __ |
|||
5 __ |
|||
32 33 35 36 37 |
|||
31 34 24 22 38 |
|||
30 25 23 21 12 39 |
|||
29 26 20 13 40 11 |
|||
27 28 14 19 9 10 1 |
|||
15 16 18 8 2 |
|||
17 7 6 3 |
|||
5 4 |
|||
</pre> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |