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