## 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: interview

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):
    """
    Finds a knight's tour from start position visiting every
    board position exactly once.
    
    A knight may make any "L" move which is valid in chess. That is:
    any rotation of "up 1 over 2" or "up 2 over 1". The problem
    description has a full explanation of valid moves.
    
    Arguments:
        start - (row, col) starting position on board.
        size - number of rows in the square board.
        
    Returns:
        List of positions beginning with the start position
        which constitutes a valid tour of the board; visiting
        each position exactly once.
    """
    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)
    """
    Finds a knight's tour from start position visiting every
    board position exactly once.

    A knight may make any "L" move which is valid in chess. That is:
    any rotation of "up 1 over 2" or "up 2 over 1". The problem
    description has a full explanation of valid moves.

    Arguments:
        start - (row, col) starting position on board.
        size - number of rows in the square board.

    Returns:
        List of positions beginning with the start position
        which constitutes a valid tour of the board; visiting
        each position exactly once.
    """
    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):


    # for move in legal_moves:
        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(1e9),start)])
        return [start]+search(nxt,step+1)
    return search(start,1)

def knights_tour(start, size):
    """
    Finds a knight's tour from start position visiting every
    board position exactly once.

    A knight may make any "L" move which is valid in chess. That is:
    any rotation of "up 1 over 2" or "up 2 over 1". The problem
    description has a full explanation of valid moves.

    Arguments:
        start - (row, col) starting position on board.
        size - number of rows in the square board.

    Returns:
        List of positions beginning with the start position
        which constitutes a valid tour of the board; visiting
        each position exactly once.
    """
    def degree(p):
        adj = [(p[0] + x, p[1] + y) for x, y in directions]
        return sum([1 for x, y in adj if 0 <= x < size and 0 <= y < size and board[x][y] == -1])

    def check_board():
        return all([sq != -1 for row in board for sq in row])

    def knight_dfs(pos, cnt):
        if check_board():
            return True
        moves = filter(lambda m: 0 <= m[0] < size and 0 <= m[1] < size and board[m[0]][m[1]] == -1,
                       [(pos[0] + x, pos[1] + y) for x, y in directions])
        moves = sorted(moves, key=degree)
        for move in moves:
            board[move[0]][move[1]] = cnt
            if knight_dfs(move, cnt + 1):
                return True
            else:
                board[move[0]][move[1]] = -1

    def print_board():
        for row in board:
            print row

    directions = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
    board = [[-1] * size for _ in range(size)]
    board[start[0]][start[1]] = 0
    knight_dfs(start, 1)
    print_board()
    return sorted([(i, j) for i in range(size) for j in range(size)], key=lambda x: board[x[0]][x[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)