Number of moves for chess knight to move to a position (O(1) algorithm)

knightsmove.py

from __future__ import print_function

def calc_board(limit = 9):
	board = {}
	board[(0,0)] = 0
	posToCheck = set([(0,0)])

	while len(posToCheck) > 0:
		posToCheck2 = set()
		for pos in posToCheck:

			for rel in [(2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1,-2), (-1,2), (-1,-2)]:
				move = pos[0] + rel[0], pos[1] + rel[1]
				if move in board:
					if board[pos] + 1 < board[move] and board[pos] < limit-1:
						board[move] = board[pos] + 1
						posToCheck2.add(move)
				elif board[pos] < limit-1:
					board[move] = board[pos] + 1
					posToCheck2.add(move)

		posToCheck = posToCheck2
	return board

def print_board(board):
	xvals = [pos[0] for pos in board]
	yvals = [pos[1] for pos in board]

	for y in range(min(yvals), max(yvals)+1):
		for x in range(min(xvals), max(xvals)+1):
			if (x, y) in board:
				print (board[(x,y)], end=" ")
			else:
				print (" ", end=" ")

		print ("")

def solve(x,y):
	#Adapted from http://stackoverflow.com/a/26888893/4288232
	x = abs(x)
	y = abs(y)
	if y > x:
		y, x = x, y

	#Handle special corner cases  
	if x==2 and y==2:
		return 4
	if x==1 and y==0:
		return 3

	if y == 0 or y < x//2:
		odd = (y % 2)
		x2 = x - 2 * odd
		x3 = x2 % 4
		return ((x2 - x3) // 2) + x3 + odd
	else:
		diagonal = x - ((x-y)//2)
		diag2 = diagonal % 3 != 0
		odd = (x-y)%2 != 0
		return ((diagonal//3)*2) + odd + (diag2*2*(1-odd))

if __name__ == "__main__":
	board = calc_board()
	print_board(board)
	predBoard = {}

	if 1:
		errorCount = 0
		for x, y in board:
			result = solve(x, y)
			expected = board[(x, y)]
			predBoard[(x, y)] = result
			#if result != expected:
			#	print (x, y, "Result={} Expected={}".format(result, expected))
			if result != expected:
				errorCount += 1

		if errorCount > 0:
			print ("Result:")
			print_board(predBoard)
		print ("Error count", errorCount)