Knight tour with optional Warnsdorff ordering: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Build an open tour visiting each square once. Optionally try squares with the fewest unused onward moves first; backtrack when a choice fails.

Visit every square exactly once using knight moves. Try neighbors in a fixed offset order, optionally sorting choices by the number of unused onward moves. Backtrack when a partial path cannot be extended.

Open the 3D visualization

Knight tour with optional Warnsdorff ordering example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Knight tour with optional Warnsdorff ordering

Comparing exhaustive search and heuristic move ordering on a small Hamiltonian-path puzzle.

Choosing an alternative

Warnsdorff ordering tries constrained squares first but is not itself a proof that every start has a tour. This view retains backtracking and reports search-budget exhaustion separately from proven failure.

Worked example: input and state changes

Example input

5 | 0 | 1 | 2000

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: -1 unvisited; numbers show visit order. This is an open tour.

    State at this checkpoint
    {
      "values": [
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1
      ],
      "active": [],
      "kind": "matrix",
      "columns": 5,
      "result": 0,
      "output": [
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1
      ],
      "moves": 0
    }
  2. Step 7: Try the lowest-onward-degree available square.

    State at this checkpoint
    {
      "values": [
        0,
        -1,
        -1,
        -1,
        2,
        -1,
        -1,
        1,
        -1,
        -1,
        -1,
        -1,
        -1,
        3,
        -1,
        -1,
        -1,
        5,
        -1,
        -1,
        6,
        -1,
        -1,
        -1,
        4
      ],
      "active": [
        20
      ],
      "kind": "matrix",
      "columns": 5,
      "result": 0,
      "output": [
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1
      ],
      "moves": 6
    }
  3. Step 13: Try the lowest-onward-degree available square.

    State at this checkpoint
    {
      "values": [
        0,
        -1,
        8,
        -1,
        2,
        -1,
        -1,
        1,
        -1,
        9,
        12,
        7,
        -1,
        3,
        -1,
        -1,
        -1,
        5,
        10,
        -1,
        6,
        11,
        -1,
        -1,
        4
      ],
      "active": [
        10
      ],
      "kind": "matrix",
      "columns": 5,
      "result": 0,
      "output": [
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1
      ],
      "moves": 12
    }
  4. Step 20: Try the lowest-onward-degree available square.

    State at this checkpoint
    {
      "values": [
        0,
        13,
        8,
        19,
        2,
        -1,
        18,
        1,
        14,
        9,
        12,
        7,
        -1,
        3,
        -1,
        17,
        -1,
        5,
        10,
        15,
        6,
        11,
        16,
        -1,
        4
      ],
      "active": [
        3
      ],
      "kind": "matrix",
      "columns": 5,
      "result": 0,
      "output": [
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1
      ],
      "moves": 19
    }
  5. Step 26: Found an open tour of 25 squares.

    State at this checkpoint
    {
      "values": [
        0,
        13,
        8,
        19,
        2,
        23,
        18,
        1,
        14,
        9,
        12,
        7,
        22,
        3,
        20,
        17,
        24,
        5,
        10,
        15,
        6,
        11,
        16,
        21,
        4
      ],
      "active": [],
      "kind": "matrix",
      "columns": 5,
      "result": 1,
      "output": [
        0,
        7,
        4,
        13,
        24,
        17,
        20,
        11,
        2,
        9,
        18,
        21,
        10,
        1,
        8,
        19,
        22,
        15,
        6,
        3,
        14,
        23,
        12,
        5,
        16
      ],
      "moves": 24
    }

Expected final state

Found an open tour of 25 squares.

Complexity and input bounds

Family: Backtracking. Time complexity: Exponential search, bounded to 2,000 moves.

Implementation detail: Boards have side length one through five and at most 2,000 attempted moves after the start. The optional heuristic orders by unused onward degree with stable clockwise-offset ties. Downloads return solved, exhausted/no tour, budget exhausted, or invalid input separately, and serialize the full row-major cell path on success.

Space complexity: O(board cells) move tables and traversal state excluding saved frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

board size 1..5 | starting row-major cell | heuristic 0 or 1 | move budget 0..2000. An exhausted budget means unknown, not impossible.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

An open tour does not require the final square to connect to the start. Ties in onward degree depend on move order. A limit reached during search means unknown, not impossible.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// Open knight tour on a size by size board, size 1..5; start is row-major index 0..size^2-1; heuristic 0 fixed move order or 1 Warnsdorff minimum-unused-onward-degree order; budget 0..2000 attempted moves after the initial square. Ties preserve offsets (-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2). Returns 1 solved, 0 exhausted/no tour, -2 budget exhausted/unknown, -1 invalid arguments. Output capacity size^2: tour cell indices on success, all -1 on 0/-2; unspecified on invalid arguments. A one-square board succeeds with zero moves. Exponential bounded search, O(size^2) traversal/move storage. Does not require the last square to connect back to the start. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(size, start, heuristic, budget, output) {
    if (size < 1 || size > 5 || start < 0 || start >= size*size || heuristic < 0 || heuristic > 1 || budget < 0 || budget > 2000) { return -1; }
    let cells = size*size; let dr = Array(256).fill(0); let dc = Array(256).fill(0); let moves = Array(256).fill(0); let path = Array(256).fill(0); let used = Array(256).fill(0); let order = Array(256).fill(0); let scores = Array(256).fill(0); let count = Array(256).fill(0); let next = Array(256).fill(0); let nr = 0; let nc = 0; let vertex = 0; let candidate = 0; let degree = 0; let neighbor = 0; let slot = 0; let depth = 0; let steps = 0;
    dr[0] = -2; dc[0] = -1; dr[1] = -2; dc[1] = 1; dr[2] = -1; dc[2] = 2; dr[3] = 1; dc[3] = 2; dr[4] = 2; dc[4] = 1; dr[5] = 2; dc[5] = -1; dr[6] = 1; dc[6] = -2; dr[7] = -1; dc[7] = -2;
    for (let r = 0; r < size; r++) { for (let c = 0; c < size; c++) { vertex = r*size+c; output[vertex] = -1; for (let move = 0; move < 8; move++) { nr = r+dr[move]; nc = c+dc[move]; moves[vertex*8+move] = -1; if (nr >= 0 && nr < size && nc >= 0 && nc < size) { moves[vertex*8+move] = nr*size+nc; } } } }
    path[0] = start; used[start] = 1;
    vertex = path[depth]; count[depth] = 0; next[depth] = 0;
    for (let move = 0; move < 8; move++) { candidate = moves[vertex*8+move]; if (candidate >= 0 && used[candidate] == 0) { degree = 0; if (heuristic != 0) { for (let onward = 0; onward < 8; onward++) { neighbor = moves[candidate*8+onward]; if (neighbor >= 0 && used[neighbor] == 0) { degree++; } } } slot = count[depth]; while (slot > 0 && scores[depth*8+slot-1] > degree) { scores[depth*8+slot] = scores[depth*8+slot-1]; order[depth*8+slot] = order[depth*8+slot-1]; slot--; } scores[depth*8+slot] = degree; order[depth*8+slot] = candidate; count[depth]++; } }
    
    while (depth >= 0) { if (depth == cells-1) { for (let i = 0; i < cells; i++) { output[i] = path[i]; } return 1; }
     if (next[depth] == count[depth]) { used[path[depth]] = 0; depth--; }
     else { if (steps >= budget) { return -2; } candidate = order[depth*8+next[depth]]; next[depth]++; steps++; used[candidate] = 1; depth++; path[depth] = candidate; vertex = path[depth]; count[depth] = 0; next[depth] = 0;
    for (let move = 0; move < 8; move++) { candidate = moves[vertex*8+move]; if (candidate >= 0 && used[candidate] == 0) { degree = 0; if (heuristic != 0) { for (let onward = 0; onward < 8; onward++) { neighbor = moves[candidate*8+onward]; if (neighbor >= 0 && used[neighbor] == 0) { degree++; } } } slot = count[depth]; while (slot > 0 && scores[depth*8+slot-1] > degree) { scores[depth*8+slot] = scores[depth*8+slot-1]; order[depth*8+slot] = order[depth*8+slot-1]; slot--; } scores[depth*8+slot] = degree; order[depth*8+slot] = candidate; count[depth]++; } }
     }
    }
    return 0;
}

Source

The preprint analyzes Warnsdorff ordering and tie choices on 8x8 boards; it is not the original 1823 source. This playground uses smaller boards, optional degree ordering and bounded backtracking rather than the paper enumeration study.