The Knights tour problem

The problem, simply

A knight in chess jumps in an L shape: two squares in one direction, then one square to the side. From the middle of the board it has 8 possible jumps. Near the edges it has fewer.

You get a board size n and a starting square. Find an order of jumps so the knight lands on every square exactly once. Return the board with each square numbered by the move that reached it (the start is 0), or say there is no tour.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try the 8 jumps in a fixed order. Number each square you land on. If you get stuck before all squares are numbered, erase the last number and try the next jump from the square before.

1. Fill the board with -1 and put 0 on the start.
2. From the current square, try each of the 8 jumps that stays on the board and lands on a -1.
3. Write the move number there and continue. If that leads to a full tour, return true.
4. Otherwise write -1 back and try the next jump.

import java.util.*;

class Solution {
    private static final int[] DX = {2, 1, -1, -2, -2, -1, 1, 2};
    private static final int[] DY = {1, 2, 2, 1, -1, -2, -2, -1};

    public int[][] knightsTour(int n, int sx, int sy) {
        int[][] board = new int[n][n];
        for (int[] row : board) Arrays.fill(row, -1);
        board[sx][sy] = 0;
        return jump(sx, sy, 1, board) ? board : null;    // null means no tour
    }

    private boolean jump(int x, int y, int move, int[][] board) {
        int n = board.length;
        if (move == n * n) return true;                  // every square is numbered
        for (int i = 0; i < 8; i++) {
            int nx = x + DX[i], ny = y + DY[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == -1) {
                board[nx][ny] = move;
                if (jump(nx, ny, move + 1, board)) return true;
                board[nx][ny] = -1;                      // erase and try the next jump
            }
        }
        return false;
    }
}

How long it takes: up to 8 choices at each of n^2 squares, so O(8^(n^2)) in the worst case. In practice: 8840 calls for 5 by 5, about 250 thousand for 6 by 6, and about 8 million for 8 by 8. Extra room: the board, O(n^2).

Way 2: the clever way

Keep the same search, but change the order of the jumps. Before jumping, count for every free target square how many free squares it could jump to next. Try the target with the smallest count first. This is Warnsdorff's rule.

Why does it work? A square with few ways out is in danger of being cut off. Visiting it now, while it is still reachable, avoids the classic dead end where one lonely corner is left at the very end.

1. List every legal jump from the current square.
2. For each target, count its own free onward jumps.
3. Sort the targets by that count, smallest first.
4. Try them in that order, with the same write, go deeper, erase logic as Way 1.

import java.util.*;

class Solution {
    private static final int[] DX = {2, 1, -1, -2, -2, -1, 1, 2};
    private static final int[] DY = {1, 2, 2, 1, -1, -2, -2, -1};

    public int[][] knightsTour(int n, int sx, int sy) {
        int[][] board = new int[n][n];
        for (int[] row : board) Arrays.fill(row, -1);
        board[sx][sy] = 0;
        return jump(sx, sy, 1, board) ? board : null;
    }

    private boolean jump(int x, int y, int move, int[][] board) {
        int n = board.length;
        if (move == n * n) return true;
        List<int[]> targets = new ArrayList<>();          // {ways out, x, y}
        for (int i = 0; i < 8; i++) {
            int nx = x + DX[i], ny = y + DY[i];
            if (free(nx, ny, board)) targets.add(new int[]{waysOut(nx, ny, board), nx, ny});
        }
        targets.sort((a, b) -> a[0] - b[0]);              // fewest ways out first
        for (int[] t : targets) {
            board[t[1]][t[2]] = move;
            if (jump(t[1], t[2], move + 1, board)) return true;
            board[t[1]][t[2]] = -1;                       // still backtrack if the rule fails
        }
        return false;
    }

    private int waysOut(int x, int y, int[][] board) {
        int count = 0;
        for (int i = 0; i < 8; i++) {
            if (free(x + DX[i], y + DY[i], board)) count++;
        }
        return count;
    }

    private boolean free(int x, int y, int[][] board) {
        int n = board.length;
        return x >= 0 && x < n && y >= 0 && y < n && board[x][y] == -1;
    }
}

How long it takes: in the worst case it is still exponential, because the rule is a good guess, not a proof. In practice it almost never goes back: 25 calls for 5 by 5 and 64 for 8 by 8, each costing up to 64 checks, so about O(n^2). Extra room: the board, O(n^2).

Watch out for

• Starting the move counter at 0 for the first jump. The start square is move 0, so the first jump writes 1, and the tour is done when move == n * n.
• Checking the board bounds after reading board[nx][ny]. Check bounds first.
• Not resetting the square to -1. Later branches then think it is taken.

What interviewers ask next

• Does a tour always exist? For n = 1 yes, for n = 2, 3, 4 no, and for every n >= 5 yes. On 5 by 5 it only works from some starting squares, and the corners are among them.
• What is a closed tour? One where the last square is a knight jump away from the start, so the knight could loop forever. Check that when move == n * n.
• Is this a famous graph problem? Yes. Squares are dots and knight jumps are lines. A tour is a path that visits every dot once, a Hamiltonian path, which is NP-hard in general. Knight graphs are special, which is why the simple rule works so well.
• How do you break ties? Look one step deeper: among tied squares, pick the one whose own best target has the fewest ways out. Or start with the jump that heads toward the edge.

Remember this

Grown-up words: the board is a knight graph, the tour is a Hamiltonian path, erasing is backtracking, and choosing the most cut off square first is Warnsdorff's heuristic (a form of most constrained first).