# knights-q1
# Aakash Pal
# Exs for Section 46, Q.1
# Knight Tour using backtracking
# https://www.geeksforgeeks.org/the-knights-tour-problem/

import time

N = 8   # board Size
# xMoves and yMoves define next (x,y) move of a knight
xMoves = [2, 1, -1, -2, -2, -1,  1,  2]
yMoves = [1, 2,  2,  1, -1, -2, -2, -1]

def isValid(x, y, board):
  return  x >= 0 and y >= 0 and \
          x < N and y < N and \
          board[x][y] == -1

def printSolution(board):
  for i in range(N):
    for j in range(N):
      print(f"{board[i][j]:2}", end=' ')
    print()

def solve(board, x, y, step):
  if step == N*N:
    return True
  # Try all moves from x, y
  for i in range(8):
    newX = x + xMoves[i]
    newY = y + yMoves[i]
    if isValid(newX, newY, board):
      board[newX][newY] = step
      if solve(board, newX, newY, step+1):
        return True
      board[newX][newY] = -1   # Backtracking
  return False

board = [[-1 for i in range(N)] for i in range(N)]
board[0][0] = 0   # Place the knight at (0,0)
start = time.time()
print("Searching...")
if not solve(board, 0, 0, 1):
  print("No Solution")
else:
  printSolution(board)
print(f"\nElapsed time: {time.time() - start:.2f} secs")