# 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. If the knight
ends on a square that is one knight's move from the beginning
square (so that it could tour the board again immediately,
following the same path), the tour is **closed**, otherwise it
is **open**.

The **knight's tour problem** is the mathematical problem of
finding a knight's tour. Creating a program to find a knight's
tour is a common problem given to computer science students.
Variations of the knight's tour problem involve chessboards of
different sizes than the usual `8×8`

, as well as irregular
(non-rectangular) boards.

## Solutions

**Backtracking**

### Implementation

```
class KnightsTour:
def solve(self, chessboard_size):
n = chessboard_size
chessboard = {(x,y):0 for y in range(n) for x in range(n)}
moves = []
first_move = (0, 0)
moves.append(first_move)
chessboard[first_move] = 1
solution_was_found = self.recursive(chessboard, moves, chessboard_size)
return moves if solution_was_found else []
def recursive(self, chessboard, moves, chessboard_size):
if self.is_tour_over(chessboard, moves):
return True
last_move = moves[len(moves)-1]
possible_moves = self.get_possible_moves(chessboard_size, last_move)
for move in possible_moves:
if self.is_move_allowed(chessboard, move):
moves.append(move)
chessboard[move] = 1
if self.recursive(chessboard, moves, chessboard_size):
return True
moves.pop()
chessboard[move] = 0
return False
def get_possible_moves(self, chessboard_size, position):
all_moves = [
(position[0] - 1, position[1] - 2),
(position[0] - 2, position[1] - 1),
(position[0] + 1, position[1] - 2),
(position[0] + 2, position[1] - 1),
(position[0] - 2, position[1] + 1),
(position[0] - 1, position[1] + 2),
(position[0] + 1, position[1] + 2),
(position[0] + 2, position[1] + 1)
]
n = chessboard_size
possible_moves = [m for m in all_moves if \
m[0]>=0 and m[1]>=0 and m[0]<n and m[1]<n]
return possible_moves
def is_tour_over(self, chessboard, moves):
return len(chessboard) == len(moves)
def is_move_allowed(self, chessboard, move):
return chessboard[move] != 1
```