# The knights tour

Given two positive integers m and n which are the height and width of a **0-indexed** 2D-array board, a pair of positive integers (r, c) which is the starting position of the knight on the board.

Your task is to find an order of movements for the knight, in a manner that every cell of the board gets visited **exactly** once (the starting cell is considered visited and you **shouldn't** visit it again).

Return *the array* board *in which the cells' values show the order of visiting the cell starting from 0 (the initial place of the knight).*

Note that a **knight** can **move** from cell (r1, c1) to cell (r2, c2) if 0 <= r2 <= m - 1 and 0 <= c2 <= n - 1 and min(abs(r1 - r2), abs(c1 - c2)) = 1 and max(abs(r1 - r2), abs(c1 - c2)) = 2.

```
class Solution {
private int[][] g;
private int m;
private int n;
private boolean ok;
public int[][] tourOfKnight(int m, int n, int r, int c) {
this.m = m;
this.n = n;
this.g = new int[m][n];
for (var row : g) {
Arrays.fill(row, -1);
}
g[r][c] = 0;
dfs(r, c);
return g;
}
private void dfs(int i, int j) {
if (g[i][j] == m * n - 1) {
ok = true;
return;
}
int[] dirs = {-2, -1, 2, 1, -2, 1, 2, -1, -2};
for (int k = 0; k < 8; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == -1) {
g[x][y] = g[i][j] + 1;
dfs(x, y);
if (ok) {
return;
}
g[x][y] = -1;
}
}
}
}
```

```
class Solution:
def tourOfKnight(self, m: int, n: int, r: int, c: int) -> list[list[int]]:
dirs = ((1, 2), (2, 1), (2, -1), (1, -2),
(-1, -2), (-2, -1), (-2, 1), (-1, 2))
ans = [[-1] * n for _ in range(m)]
def dfs(i: int, j: int, step: int) -> bool:
if step == m * n:
return True
if i < 0 or i >= m or j < 0 or j >= n:
return False
if ans[i][j] != -1:
return False
ans[i][j] = step
for dx, dy in dirs:
if dfs(i + dx, j + dy, step + 1):
return True
ans[i][j] = -1
return False
dfs(r, c, 0)
return ans
```

The Knight's Tour problem is a classic in algorithms and combinatorics, (also leetcode 2664) where the challenge is to find a sequence of moves for a knight on a chessboard that visits every square exactly once. The knight moves in an L-shape: two squares in one direction and then one square perpendicular to it, or vice versa. Solving this problem efficiently usually requires backtracking or a heuristic such as Warnsdorff's rule, which suggests moving the knight to the square that has the fewest onward moves. This minimizes the risk of getting stuck before visiting all the cells.

The goal in this problem is to populate the board with the order in which the knight visits each square, starting from the initial position. You’ll need to recursively explore all possible moves, marking each cell as visited in a specific order, while ensuring that no cell is revisited. If a move leads to a dead-end, the algorithm should backtrack and try different moves until all cells are covered. The complexity increases with the size of the board, making optimization techniques crucial for larger grids.

## Related Problems

A **transformation sequence** from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.

Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return *all the ***shortest transformation sequences*** from* beginWord *to* endWord*, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words *[beginWord, s1, s2, ..., sk].

Given an array of **distinct** integers candidates and a target integer target, return *a list of all ***unique combinations*** of *candidates* where the chosen numbers sum to *target*.* You may return the combinations in **any order**.

The **same** number may be chosen from candidates an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you **must** take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Given an integer array nums and an integer k, return *the* kth *largest element in the array*.

Note that it is the kth largest element in the sorted order, not the kth distinct element.