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.
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.
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 }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 }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 }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 }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.
- How good is the Warnsdorff's knight's tour heuristic?
Samuel L. Marateck (2008). Research preprint on heuristic ordering. - Estimating the efficiency of backtrack programs
Donald E. Knuth (1975). Related research paper.