Knight Tour Count

Count all valid knight tours on a 5x5 board starting from (0,0), visiting every square exactly once.

backtracking dfs board counting

Write a function `knight_tour_count(board_size: int) -> int` that returns the number of distinct knight tours on a `board_size` x `board_size` board.

A **knight tour** is a sequence of moves that:
- Starts at the top-left cell (0, 0).
- Visits every cell on the board **exactly once** (so a tour consists of exactly `board_size * board_size` moves, covering all squares).
- Uses only legal knight moves (an L-shape: 2 squares in one direction and 1 square perpendicular, or 1 and 2).

For a 1x1 board, there is exactly one tour: just stand on the only cell. For board sizes 0 or negative, return 0 (invalid input).

The order of moves matters: two tours that visit the same squares in a different order are considered different.

The function signature is:
```python
def knight_tour_count(board_size: int) -> int:
```

Your solution should work efficiently for `board_size` up to 5 (the count for 5x5 is 1728), but you do not need to handle sizes above 5 (you may return any non-negative number for those, but the tests only check sizes 0–5).

Constraints

- `board_size` is an integer, `0 <= board_size <= 5` for the tests.
- The returned value is a positive integer (except for invalid inputs, where it is 0).
- Your algorithm should be able to compute the count for 5x5 within a few seconds.

Example

>>> knight_tour_count(1)
1
>>> knight_tour_count(2)
0
>>> knight_tour_count(3)
0
>>> knight_tour_count(4)
0
>>> knight_tour_count(5)
1728

40 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think recursion with backtracking: at each cell, try all 8 possible knight moves, but skip those that go off-grid or revisit a visited cell.

Keep track of visited cells with a boolean grid (or a set of coordinates).

Base case: if you have visited all `board_size * board_size` cells, count this as 1 valid tour.

For 5x5, a naive DFS is fast enough; use memoization or symmetry to speed up if needed.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.