Solve a Hidato puzzle: Difference between revisions
m
no edit summary
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
mNo edit summary |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 26:
* [[N-queens problem]]
* [[Solve a Holy Knight's tour]]
* [[
* [[Solve a Hopido puzzle]]
* [[Solve a Numbrix puzzle]]
Line 3,003:
{{out}}
Outputs a graphical version of the solved hidato.
=={{header|MiniScript}}==
<syntaxhighlight lang="miniscript">
string.splitBySpaces = function
s = self.split
while s.indexOf("") != null
s.remove(s.indexOf(""))
end while
return s
end function
Hidato = {"board": [], "given": [], "start": [], "maxNum": 0}
Hidato.__emptyBoard = function(nRows, nCols)
self.board = []
emptyRow = []
for c in range(1,nCols + 2)
emptyRow.push(-1)
end for
for r in range(1,nRows + 2)
self.board.push(emptyRow[:])
end for
end function
Hidato.setup = function(s)
lines = s.split(char(13))
cols = lines[0].splitBySpaces.len
rows = lines.len
// create empty board with room
// for the wall at the edge
self.__emptyBoard(rows,cols)
board = self.board
// fill board with start puzzle
for r in range(0, rows - 1)
for c in range(0, cols - 1)
cell = (lines[r].splitBySpaces)[c]
if cell == "__" then
board[r+1][c+1] = 0 // unknown
else if cell == "." then
continue // -1 for blocked
else
num = cell.val
board[r+1][c+1] = num
self.given.push(num)
if num == 1 then
self.start = [r+1,c+1]
end if
if num > self.maxNum then self.maxNum = num
end if
end for
end for
self.given.sort
end function
Hidato.solve = function(n, pos = null, next = 0)
if n > self.given[-1] then return true
if pos == null then pos = self.start
r = pos[0]
c = pos[1]
board = self.board
if board[r][c] and board[r][c] != n then return false
if board[r][c] == 0 and self.given[next] == n then return false
back = 0
if board[r][c] == n then
next += 1
back = n
end if
board[r][c] = n
for i in range(-1, 1)
for j in range(-1,1)
if self.solve(n + 1, [r + i, c + j], next) then return true
end for
end for
board[r][c] = back
return false
end function
Hidato.print = function
board = self.board
maxLen = str(self.maxNum).len + 1
padding = " " * maxLen
for row in board[1:-1]
s = ""
for cell in row[1:-1]
c = padding + "__" * (cell == 0) + str(cell) * (cell > 0)
s += c[-maxLen:]
end for
print s
end for
end function
puzzle = "__ 33 35 __ __ . . ." + char(13)
puzzle += "__ __ 24 22 __ . . ." + char(13)
puzzle += "__ __ __ 21 __ __ . ." + char(13)
puzzle += "__ 26 __ 13 40 11 . ." + char(13)
puzzle += "27 __ __ __ 9 __ 1 ." + char(13)
puzzle += " . . __ __ 18 __ __ ." + char(13)
puzzle += " . . . . __ 7 __ __" + char(13)
puzzle += " . . . . . . 5 __"
Hidato.setup(puzzle)
print "The initial puzzle board:"
Hidato.print
print
Hidato.solve(1)
print "The puzzle solved:"
Hidato.print</syntaxhighlight>
{{out}}
<pre>
The initial puzzle board:
__ 33 35 __ __
__ __ 24 22 __
__ __ __ 21 __ __
__ 26 __ 13 40 11
27 __ __ __ 9 __ 1
__ __ 18 __ __
__ 7 __ __
5 __
The puzzle solved:
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|Nim}}==
Line 4,770 ⟶ 4,901:
. . . . __ 7 __ __
. . . . . . 5 __';
templates hidato
composer setup
data givenInput <n´1:[<´{}´ ={}|{row: <row>, col: <col>}>*]> local
@: {row: 1, col: 1, givenInput:n´1:[]};
{ board: row´1:[ <line>+ ], given: $@.givenInput -> \[i](<~´{}´ ={}> { n: $i, $...} !\) }
rule line: col´1:[ <cell>+ ] (<'\n '>?) (..|@: {row: $@.row::raw + 1, col: 1};)
rule cell: <open|blocked|given> (<' '>?) (@.col: $@.col::raw + 1;)
rule open: <'__'> -> n´0
rule blocked: <' \.'> -> n´-1
rule given: (<' '>?) (def given: <n´INT>;)
($given -> ..|@.givenInput: $@.givenInput::length+1..$::raw -> {};)
($given -> @.givenInput($): { row: $@.row, col: $@.col };)
$given
end setup
templates solve
when <~{row: <1..$@hidato.board::length>, col: <1..$@hidato.board(row´1)::length>}> do !VOID
when <{ n: <=$@hidato.given(last).n>, row: <=$@hidato.given(last).row>, col: <=$@hidato.given(last).col> }> do $@hidato.board !
when <?($@hidato.board($.row; $.col) <~=n´0|=$.n
when <?($@hidato.board($.row; $.col) <=n´0>)?($@hidato.given($.next) <{n: <=$.n
otherwise
def guess: $;
def back: $@hidato.board($.row; $.col);
def next: $ -> \(when <{n: <=$back>}> do n´($.next::raw + 1)! otherwise $.next!\);
@hidato.board($.row; $.col): $.n
0..8 -> { next: $next, n: $guess.n::raw + 1, row: $guess.row::raw + $ ~/ 3 - 1, col: $guess.col::raw + $ mod 3 - 1 } -> #
@hidato.board($.row; $.col): $back;
end solve
@: $ -> setup;
{ next: n´1, $@.given(
end hidato
$input -> hidato -> '$... -> '$... -> ' $ -> \(when <=n´-1> do ' .' ! when <n´10..> do '$;' ! otherwise ' $;' !\);';
';
' ->!OUT::write
Line 4,972 ⟶ 5,103:
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
var board = []
| |||