Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

The Knight’s Tour in Java: Choose a Move, Explore, Undo

Find a complete knight tour with legal L moves, visited-state backtracking, success-preserving returns, a board example and tested Java.

HardRecursion and backtrackingPattern: recursion, backtracking

Problem statement

Starting at the supplied square of a rectangular board, visit every square exactly once with knight moves. Return a board where 0 marks the starting visit, 1 the next, and so on through rows×cols−1. Any valid tour is accepted; it need not match a sample board exactly.

The supplied task allows 1–5 rows/columns, a valid zero-based start and guarantees at least one solution. LeetCode The Knight’s Tour may require Premium. This is not Minimum Knight Moves: we need a path covering every square, not a shortest path to one target.

For exploratory unsolvable boards, the teaching method returns an empty board instead of a partially numbered board. That is a defensive extension, not an expected official input.

Constraints & requirements

CONTRACT
Original task: 1–5 rows/columns, valid zero-based start, and at least one tour guaranteed. The teaching method also returns an empty board for an unsolvable valid-size input. LeetCode may require Premium.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    rows=3; cols=4; start=(0,0)
    Output
    Any complete tour; one is [[0,3,6,9],[7,10,1,4],[2,5,8,11]]

    Verify successive squares form an L move; a different valid board is equally correct.

  2. Example 2 Case 2

    Input
    rows=1; cols=1; start=(0,0)
    Output
    [[0]]

    The initial visit already covers the entire board.

  3. Example 3 Case 3

    Input
    rows=3; cols=4; start=(0,3)
    Output
    Any complete tour; one is [[9,6,3,0],[4,1,10,7],[11,8,5,2]]

    The starting square must contain zero, not a fixed corner.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Mark a chosen square so this path cannot revisit it.

02Hint 2

Try only in-bounds, unvisited L-shaped moves.

03Hint 3

Undo a mark only after failure; preserve the successful complete path.

How to think before coding

The board stores visit order; −1 means unused, not visit zero. The starting square is already marked 0. A call asks whether the next move number can finish the tour. Mark a valid destination, recurse with move+1, and restore −1 only after failure. If all V squares are numbered, return true and retain the successful board.

Brute force and the improvement

Enumerate sequences of V−1 knight moves after the starting visit, where V is the number of squares, and validate each full sequence for bounds, repeats and full coverage. At most eight choices per move give a loose O(V·8^V) checking bound and O(V) sequence storage. The backtracker rejects an illegal or visited destination BEFORE extending it and stops after one complete tour. Trying promising moves first can speed the search, but neither the baseline nor this backtracking method has a polynomial worst-case guarantee.

Intuition: a visit blocks the square only on this path

A knight moves two squares in one direction and one perpendicular: offsets (±2,±1) or (±1,±2). Some offsets leave the board; others reach a square already used on the current path. Reject them before recursion.

Marking a square makes it unavailable to descendants. If that continuation fails, clear its mark so a different route can use it. This temporary-state restoration is why ordinary visited-once graph DFS is not enough.

Algorithm

  1. Fill the board with −1 for unvisited squares.
  2. Mark the supplied start 0 and recurse with next move number 1.
  3. Return true when the next number equals the total square count.
  4. For each legal unvisited destination, mark it and recurse.
  5. If the child succeeds, return immediately without undoing the successful tour.
  6. If it fails, reset that destination to −1 and try the next move.

Java solution

An unsuccessful search returns an empty board, not an unfinished board presented as a tour. A successful path retains its move numbers.

Java
import java.util.*;

class Solution {
    private static final int[] KNIGHT_DR = {2, 2, -2, -2, 1, -1, 1, -1};
    private static final int[] KNIGHT_DC = {1, -1, 1, -1, 2, 2, -2, -2};
    public static int[][] knightTour(int rows, int cols, int row, int col) {
        int[][] board = new int[rows][cols];
        for (int[] line : board) Arrays.fill(line, -1); // -1 means not yet visited.
        board[row][col] = 0; // Starting square is the first visit, numbered zero.
        return visitKnight(board, row, col, 1) ? board : new int[0][0]; // Defensive failure, never a partial tour.
    }
    private static boolean visitKnight(int[][] board, int row, int col, int move) {
        if (move == board.length * board[0].length) return true; // All squares already have visit numbers.
        for (int i = 0; i < 8; i++) {
            int nr = row + KNIGHT_DR[i], nc = col + KNIGHT_DC[i]; // Offset the POSITION, not dimensions.
            if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) continue;
            if (board[nr][nc] != -1) continue; // Never revisit a square on the active path.
            board[nr][nc] = move; // Choose the square and record its visit order.
            if (visitKnight(board, nr, nc, move + 1)) return true; // Preserve a successful complete tour.
            board[nr][nc] = -1; // Failed continuation: undo this visit before trying another move.
        }
        return false; // None of the eight moves completed the remaining tour.
    }

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(knightTour(3, 4, 0, 0))); // Any valid complete numbered tour.
    }
}

The driver prints one complete 3×4 tour. Its exact numbers depend on move order. To verify a tour, check every number appears once, zero is at the supplied start, and successive positions satisfy the knight rule.

Choice branches and dry run

Numbered illustrated dry run for The Knight’s Tour; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: rows = 2, cols = 3, start = (0,0)

What to track: This small failure example traces the whole search. board holds move numbers; -1 means unused. move is the number to write into the next cell, not the current cell’s number.

  1. Reserve the start

    Java operationboard[row][col] = 0;
    Stateboard = [[0,-1,-1],[-1,-1,-1]]; call at (0,0), move = 1

    Only one of six cells has been visited. move == rows × cols is still false.

  2. Reject off-board offsets

    Java operationif (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) continue;
    Stateat (0,0), offset indices 0–3 are outside this 2×3 board

    No cell is written for a rejected coordinate. These are checks, not child calls.

  3. Try the only legal first move

    Java operationboard[nr][nc] = move;
    Statei = 4 gives (1,2); board = [[0,-1,-1],[-1,-1,1]]

    The destination is in bounds and unused. Its child receives move = 2.

  4. Find the dead end

    Java operationif (board[nr][nc] != -1) continue;
    Stateat (1,2), the only in-bounds knight destination is (0,0), already numbered 0

    The other seven destinations are outside the board. Reusing the start is forbidden, so this call returns false.

  5. Undo the failed move

    Java operationboard[nr][nc] = -1;
    Stateresumed (0,0) frame restores board[1][2] = -1; move is still 1

    The parent releases exactly the cell it chose, then checks its remaining offsets.

  6. Return failure, not a partial solution

    Java operationreturn visitKnight(board, row, col, 1) ? board : new int[0][0];
    Statethe root’s remaining offsets are invalid; root returns false; wrapper returns an empty matrix

    A successful full tour would return true without undo. This failed search never pretends that its partial path is a tour.

Final result: []: no complete tour exists for this start. The wrapper does not return a partially numbered board.

One valid 3×4 example is:

Worked example · read from top to bottom
 0   3   6   9
 7  10   1   4
 2   5   8  11

Its first moves are (0,0)→(1,2)→(2,0)→(0,1). Every move changes one coordinate by 2 and the other by 1. This is one valid example, not a claim that the code’s first explored branch produces this exact matrix.

At (0,0), the two possible destinations are (2,1) and (1,2) when those coordinates exist. The code’s move order tries (2,1) first. If a descendant runs out of moves before visiting all squares, false returns through that branch; each resumed parent removes the mark it placed. When a complete tour returns true, those marks stay.

Why it works

The board records exactly the active simple path, with distinct visit numbers. Each child adds one legal unvisited destination, preserving that invariant. A success means the active path has visited all squares. On failure, undo restores the parent’s exact state, so alternatives remain available. Trying all legal continuations therefore finds a tour whenever one exists, within the search’s runtime limits.

Complexity and alternative approaches

Let B=rows×cols. There are at most eight choices per level and at most B visited squares. A loose worst-case search bound is O(8^B); legal-move and visited checks reduce real branching but do not make plain backtracking polynomial. Initialization/output cost O(B). Board and recursive auxiliary storage are O(B).

Warnsdorff’s heuristic tries destinations with fewer onward legal moves first. It can greatly reduce practical search. Using it only as an ordering heuristic while still backtracking preserves completeness; taking one greedy choice without backtracking is not guaranteed to find a tour.

BFS for shortest paths is not a substitute: its state would need to include the entire visited subset, not only a square. Exhaustively enumerating all tours is also a different task from finding one.

Common mistakes

  • Adding offsets to board dimensions rather than the current position.
  • Using 0 to mean unvisited when 0 is the starting visit number.
  • Undoing before returning a successful board.
  • Returning a partial board after failure.
  • Comparing output to a single sample instead of validating the tour.

Practice next

Next lessonalternating-parity permutations

Back to Recursion and backtracking →