Hidato Puzzle Solver using DFS (see: https://en.wikipedia.org/wiki/Hidato)

hidato.py

# -*- coding: utf-8 -*-
"""
Created on Wed Jan 10 08:43:47 2018
@title: Hidato Puzzle Solver
@author: Ritoban
"""

import csv
import numpy as np


puzzle_in = []
with open('puzzle1.csv', 'rt') as csvfile:
    csv_reader = csv.reader(csvfile, delimiter=',')
    for row in csv_reader:
        puzzle_in.append(row)
        
given = []


puzzle = np.ones_like(puzzle_in, dtype=int) * -1


def isint(value):
    try:
        int(value)
        return True
    except ValueError:
        return False

        
for i in range(len(puzzle_in)):
    for j in range(len(puzzle_in[i])):
        val = puzzle_in[i][j]
        if val.startswith('-'):
            endX = i
            endY = j
            endVal = int(val) * -1
            given.append(endVal)
            puzzle[i][j] = endVal
        elif isint(val):
            given.append(int(val))
            puzzle[i][j] = int(val)
        elif val == '_':
            puzzle[i][j] = 0
        if val == '1':
            startX = i
            startY = j
        
given.sort()
        

print('\n'.join([''.join(['{:4}'.format(item) for item in row]) 
      for row in puzzle]))
print("Starting at: (", startX, ",", startY, ")")
print("Ending at: (", endX, ",", endY, "), Value: ", endVal)
print("Given: ", given)

'''
    Solves a hidato/hikodu puzzle
    x: the x position to look at
    y: the y positive to look at
    n: index. also, the value to consider putting into the x/y position
    next_given: the index of the next target value in the given array
'''


def solve(x, y, n=1, next_given=0):
    # if we have gone gotten to the end (index > last)
    if x >= len(puzzle) or y >= len(puzzle[x]):
        return False
    if n > given[-1]:
        return True
    if puzzle[x][y] != 0 and puzzle[x][y] != n:
        return False
    if puzzle[x][y] == 0 and given[next_given] == n:
        return False

    backup = 0  # in case the algorithm messes up later, we keep a backup variable to set this location back to.
    if puzzle[x][y] == n:  # we are at a given location, it's already on the board
        next_given += 1
        # if we know we're right for certain, we can set the backup to the correct value, instead of a blank
        backup = n

    puzzle[x][y] = n # we assume we're right. that's why we hav ethe backup value

    # look at the 8 squares around this tile. Range is non-inclusive, so go up to 2
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i == 0 and j == 0:
                continue;
            if solve(x + i, y + j, n + 1, next_given):
                return True

    puzzle[x][y] = backup
    return False


solve(startX, startY)
print('\n'.join([''.join(['{:4}'.format(item) for item in row])
      for row in puzzle]))

puzzle1.csv