Find a path from the top-left to the bottom-right through open cells (1), never through walls (0). Walk depth-first, trying down, right, up, left in that order, and retreat from any cell with no way forward.
The code
Backtracking, in Python
def solve_queens(n, row=0, cols=None):
if cols is None: cols = [0] * n # a fresh board for the outermost call
if row == n: return True # every row has a queen
for c in range(n):
if safe(cols, row, c): # no queen in this column or diagonal
cols[row] = c # choose
if solve_queens(n, row + 1, cols): return True # recurse
# undo is implicit: the next c overwrites
return False # no square works: caller backtracks
def solve_maze(g, r, c, path):
if not 0 <= r < len(g) or not 0 <= c < len(g[0]) or g[r][c] != 1:
return False # wall or outside
path.append((r, c))
g[r][c] = 2 # visited, so no cycles
if r == len(g) - 1 and c == len(g[0]) - 1: return True
for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
if solve_maze(g, r + dr, c + dc, path): return True
path.pop() # dead end: retreat
return False
def search(g, w, r, c, k, used):
if k == len(w): return True # every letter matched
if not 0 <= r < len(g) or not 0 <= c < len(g[0]) or used[r][c] or g[r][c] != w[k]:
return False
used[r][c] = True # choose: this cell spells w[k]
for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
if search(g, w, r + dr, c + dc, k + 1, used): return True
used[r][c] = False # undo: the cell may serve another path
return False
def solve_sudoku(g, n):
cell = first_empty(g)
if cell is None: return True # no empty cell left: solved
r, c = cell
for d in range(1, n + 1):
if allowed(g, r, c, d): # not already in the row, column or box
g[r][c] = d # choose
if solve_sudoku(g, n): return True # recurse
g[r][c] = 0 # undo
return False # every digit failed: caller backtracks
Backtracking, in JavaScript
function solveQueens(n, row = 0, cols = new Array(n).fill(0)) {
if (row === n) return true; // every row has a queen
for (let c = 0; c < n; c++) {
if (safe(cols, row, c)) { // no queen in this column or diagonal
cols[row] = c; // choose
if (solveQueens(n, row + 1, cols)) return true; // recurse
} // undo is implicit: the next c overwrites
}
return false; // no square works: caller backtracks
}
function solveMaze(g, r, c, path) {
if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] !== 1) return false; // wall or outside
path.push([r, c]);
g[r][c] = 2; // visited, so no cycles
if (r === g.length - 1 && c === g[0].length - 1) return true;
for (const [dr, dc] of [[1, 0], [0, 1], [-1, 0], [0, -1]]) {
if (solveMaze(g, r + dr, c + dc, path)) return true;
}
path.pop(); // dead end: retreat
return false;
}
function search(g, w, r, c, k, used) {
if (k === w.length) return true; // every letter matched
if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || used[r][c] || g[r][c] !== w[k]) return false;
used[r][c] = true; // choose: this cell spells w[k]
for (const [dr, dc] of [[1, 0], [0, 1], [-1, 0], [0, -1]]) {
if (search(g, w, r + dr, c + dc, k + 1, used)) return true;
}
used[r][c] = false; // undo: the cell may serve another path
return false;
}
function solveSudoku(g, n) {
const cell = firstEmpty(g);
if (cell === null) return true; // no empty cell left: solved
const [r, c] = cell;
for (let d = 1; d <= n; d++) {
if (allowed(g, r, c, d)) { // not already in the row, column or box
g[r][c] = d; // choose
if (solveSudoku(g, n)) return true; // recurse
g[r][c] = 0; // undo
}
}
return false; // every digit failed: caller backtracks
}
Backtracking, in Kotlin
fun solveQueens(n: Int, row: Int = 0, cols: IntArray = IntArray(n)): Boolean {
if (row == n) return true // every row has a queen
for (c in 0 until n) {
if (safe(cols, row, c)) { // no queen in this column or diagonal
cols[row] = c // choose
if (solveQueens(n, row + 1, cols)) return true // recurse
} // undo is implicit: the next c overwrites
}
return false // no square works: caller backtracks
}
fun solveMaze(g: Array<IntArray>, r: Int, c: Int, path: MutableList<Pair<Int, Int>>): Boolean {
if (r !in g.indices || c !in g[0].indices || g[r][c] != 1) return false // wall or outside
path += r to c
g[r][c] = 2 // visited, so no cycles
if (r == g.lastIndex && c == g[0].lastIndex) return true
for ((dr, dc) in listOf(1 to 0, 0 to 1, -1 to 0, 0 to -1)) {
if (solveMaze(g, r + dr, c + dc, path)) return true
}
path.removeLast() // dead end: retreat
return false
}
fun search(g: Array<CharArray>, w: String, r: Int, c: Int, k: Int, used: Array<BooleanArray>): Boolean {
if (k == w.length) return true // every letter matched
if (r !in g.indices || c !in g[0].indices || used[r][c] || g[r][c] != w[k]) return false
used[r][c] = true // choose: this cell spells w[k]
for ((dr, dc) in listOf(1 to 0, 0 to 1, -1 to 0, 0 to -1)) {
if (search(g, w, r + dr, c + dc, k + 1, used)) return true
}
used[r][c] = false // undo: the cell may serve another path
return false
}
fun solveSudoku(g: Array<IntArray>, n: Int): Boolean {
val (r, c) = firstEmpty(g) ?: return true // no empty cell left: solved
for (d in 1..n) {
if (allowed(g, r, c, d)) { // not already in the row, column or box
g[r][c] = d // choose
if (solveSudoku(g, n)) return true // recurse
g[r][c] = 0 // undo
}
}
return false // every digit failed: caller backtracks
}