107 lines
2.4 KiB
Text
107 lines
2.4 KiB
Text
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
|