## A Knight's Tour

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once.

https://en.wikipedia.org/wiki/Knight%27s_tour

Traditional chess boards are 8x8 grids, but for this kata we are interested in generating tours for any square board sizes.

You will be asked to find a knight's path for any NxN board from any start position.

I have provided a tool to visualize the output of your code at the following link: http://jsfiddle.net/7sbyya59/2/

EDIT: The expected output is a 2D array `(n x 2)` comprised of the `[x,y]` coordinates of the Knight's path taken in sequential order. (e.g. `[[2,3],[4,4],...,[x,y]]`)

All test cases will have a passing solution.

-dg

Difficulty: MEDIUM_HARD

Starter code:
def knights_tour(start, size):
	

Solutions:
def knights_tour(start, size):
	MOVES = [(-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2)]

	def genNeighs(pos):
		return ((pos[0] + dx, pos[1] + dy) for (dx, dy) in MOVES if (pos[0] + dx, pos[1] + dy) in Warnsdorf_DP)

	def travel(pos):
		neighs = sorted(((Warnsdorf_DP[n], n) for n in genNeighs(pos)))
		for (nSubNeighs, neigh) in neighs:
			del Warnsdorf_DP[neigh]
			path.append(neigh)
			subNeighs = list(genNeighs(neigh))
			for n in subNeighs:
				Warnsdorf_DP[n] -= 1
			travel(neigh)
			if not Warnsdorf_DP:
				break
			else:
				for n in subNeighs:
					Warnsdorf_DP[n] += 1
				Warnsdorf_DP[path.pop()] = nSubNeighs
	(path, Warnsdorf_DP) = ([start], {(x, y): 0 for x in range(size) for y in range(size) if (x, y) != start})
	for pos in Warnsdorf_DP:
		Warnsdorf_DP[pos] = sum((1 for _ in genNeighs(pos)))
	travel(start)
	return path


def knights_tour(start, size):

	def next_moves(pos):
		eight_moves = ((pos[0] + i, pos[1] + j) for (i, j) in ((-2, -1), (-2, 1), (-1, -2), (-1, 2), (2, -1), (2, 1), (1, -2), (1, 2)))
		return [(r, c) for (r, c) in eight_moves if 0 <= r and r < size and (0 <= c) and (c < size) and board[r][c]]

	def solve(pos):
		if len(moves) == size * size:
			return moves
		for (r, c) in sorted(next_moves(pos), key=lambda m: len(next_moves(m))):
			board[r][c] = False
			moves.append((r, c))
			try:
				return solve((r, c))
			except ValueError:
				board[r][c] = True
				moves.pop()
		raise ValueError('Not possible')
	board = [[True] * size for _ in xrange(size)]
	board[start[0]][start[1]] = False
	moves = [start]
	return solve(start)


from heapq import *
MOVES = [(-1, -2), (-1, 2), (-2, -1), (-2, 1), (1, -2), (1, 2), (2, -1), (2, 1)]

def knights_tour(start, size):
	seen = set([start])
	path = [start]
	for i in range(size * size):
		q = []
		(x, y) = start
		for (dx, dy) in MOVES:
			xx = x + dx
			yy = y + dy
			if (xx, yy) not in seen and (0 <= xx < size and 0 <= yy < size):
				c = 0
				for (a, b) in MOVES:
					xxx = xx + a
					yyy = yy + b
					if (xxx, yyy) not in seen and (0 <= xxx < size and 0 <= yyy < size):
						c += 1
				heappush(q, (c, (xx, yy)))
		if q:
			start = heappop(q)[1]
			path.append(start)
			seen.add(start)
	return path


def knights_tour(p, n):
	((x, y), b, r) = (p, [[0] * n for _ in range(n)], [None] * n ** 2)
	(b[x][y], r[0]) = (1, p)
	d = ((-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1))
	f = lambda x, y: ((X, Y) for (dx, dy) in d for (X, Y) in ((x + dx, y + dy),) if 0 <= X < n and 0 <= Y < n and (not b[X][Y]))
	for i in range(2, n ** 2 + 1):
		(x, y) = min(f(x, y), key=lambda x: sum((1 for _ in f(x[0], x[1]))))
		(b[x][y], r[i - 1]) = (i, (x, y))
	return r


import heapq

class Knight:

	def __init__(self, start, size):
		(self.i, self.j) = start
		self.size = size
		self.board = [[0 for _ in range(size)] for _ in range(size)]
		self.moves = [(2, 1), (2, -1), (1, -2), (1, 2), (-2, 1), (-2, -1), (-1, 2), (-1, -2)]

	def valid(self, x, y):
		return 0 <= x < self.size and 0 <= y < self.size and (not self.board[x][y])

	def find_neighbour(self, x, y):
		heap = []
		for (i, j) in self.moves:
			(ni, nj) = (x + i, y + j)
			if self.valid(ni, nj):
				neighbours = self.find_neighbour_of_neighbour(ni, nj)
				heapq.heappush(heap, (neighbours, (i, j)))
		return heap

	def find_neighbour_of_neighbour(self, x, y):
		return sum((self.valid(x + i, y + j) for (i, j) in self.moves))

	def get_path(self):
		(i, j) = (self.i, self.j)
		path = [(i, j)]
		for n in range(self.size * self.size):
			self.board[i][j] = n + 1
			avl = self.find_neighbour(i, j)
			if not avl:
				break
			(_, (ni, nj)) = heapq.heappop(avl)
			i += ni
			j += nj
			path.append((i, j))
		return path

def knights_tour(start, size):
	return Knight(start, size).get_path()


import copy

def knights_tour(start, size):
	print(start, size)
	board = []
	for i in range(size):
		board.append([0 for _ in range(size)])
	board[start[0]][start[1]] = 1
	(_, result) = tour(board, start[0], start[1], 2)
	return list(reversed(result))

def tour(board, last_x, last_y, move_number):
	if move_number == len(board) ** 2 + 1:
		return (True, [(last_x, last_y)])
	x = [2, 1, -1, -2, -2, -1, 1, 2]
	y = [1, 2, 2, 1, -1, -2, -2, -1]
	moves = list(zip(x, y))
	legal_moves = [(x, y) for (x, y) in moves if is_move_legal(board, len(board), last_x + x, last_y + y)]
	priorities = dict()
	for move in legal_moves:
		priorities[move] = count_possible_moves(board, last_x + move[0], last_y + move[1])
	for (move, _) in sorted(list(priorities.items()), key=by_value):
		board_copy = copy.deepcopy(board)
		board_copy[last_x][last_y] = move
		(result, trace) = tour(board_copy, last_x + move[0], last_y + move[1], move_number + 1)
		if result:
			return (True, trace + [(last_x, last_y)])
	return (False, None)

def is_move_legal(board, size, new_x, new_y):
	return size > new_x >= 0 and size > new_y >= 0 and (board[new_x][new_y] == 0)

def count_possible_moves(board, cx, cy):
	x = [2, 1, -1, -2, -2, -1, 1, 2]
	y = [1, 2, 2, 1, -1, -2, -2, -1]
	moves = list(zip(x, y))
	return sum([1 for (nx, ny) in moves if is_move_legal(board, len(board), cx + nx, cy + ny)])

def by_value(item):
	return item[1]

def __starting_point():
	print(knights_tour((0, 2), 6))
__starting_point()


from itertools import product

def knights_tour(start, size):
	m = [[0] * size for i in range(size)]
	d = [[0] * size for i in range(size)]
	directions = [1, 2, -1, -2]
	directions = [(y, x) for (y, x) in product(directions, directions) if abs(y) != abs(x)]

	def inside(y, x):
		return not (y < 0 or x < 0 or y >= size or (x >= size)) and m[y][x] == 0

	def search(start, step):
		if step > size ** 2:
			return []
		(y, x) = start
		m[y][x] = 1
		for (yy, xx) in product(range(size), range(size)):
			d[yy][xx] = [(yy + dy, xx + dx) for (dx, dy) in directions if inside(yy + dy, xx + dx)]
		(s, nxt) = min([(len(d[ny][nx]), (ny, nx)) for (ny, nx) in d[y][x]] + [(int(1000000000.0), start)])
		return [start] + search(nxt, step + 1)
	return search(start, 1)


from typing import Tuple, Iterable, List
Position = Tuple[int, int]
Positions = List[Position]
MOVES: Tuple[Position, ...] = ((-1, -2), (1, -2), (-2, -1), (2, -1), (-2, 1), (2, 1), (-1, 2), (1, 2))

def knights_tour(start: Position, size: int) -> Positions:
	board = [[False] * size for _ in range(size)]

	def moves(x: int, y: int) -> Iterable[Position]:
		for (xd, yd) in MOVES:
			(xx, yy) = (x + xd, y + yd)
			if 0 <= xx < size and 0 <= yy < size and (not board[xx][yy]):
				yield (xx, yy)

	def dfs(path: Positions) -> Iterable[Positions]:
		if len(path) == size ** 2:
			yield path
			return
		(x, y) = path[-1]
		board[x][y] = True
		for vv in sorted(moves(x, y), key=lambda n: len([*moves(*n)])):
			path.append(vv)
			yield from dfs(path)
			path.pop()
		board[x][y] = False
	return next(dfs([start]), [])


Offsets = ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2))

def knights_tour(start, size):
	visited = {}
	peers = {}
	path = [start]
	for y in range(size):
		for x in range(size):
			visited[y, x] = 0
			peers[y, x] = [(oy + y, ox + x) for (oy, ox) in Offsets if 0 <= oy + y < size and 0 <= ox + x < size]
	size **= 2
	visited[start] = 1

	def find(curr):
		if len(path) == size:
			return path
		for peer in sorted((p for p in peers[curr] if not visited[p]), key=lambda p: sum((not visited[p2] for p2 in peers[p]))):
			visited[peer] = 1
			path.append(peer)
			if find(peer):
				return path
			visited[peer] = 0
			path.pop()
	return find(start)