Try → Check → Recurse → Backtrack
Click "Solve" to start the backtracking algorithm
Hard
Place N queens on an N×N chessboard so no two attack each other.
Solve on LeetCode →Medium
Generate all valid combinations of N pairs of parentheses.
Solve on LeetCode →The universal pattern for all backtracking problems:
function backtrack(state) {
// Base case: solution found
if (isComplete(state)) {
result.push(copy(state));
return;
}
// Try all possible choices
for (let choice of getChoices(state)) {
// Make choice
state.add(choice);
// Check if valid
if (isValid(state)) {
// Recurse
backtrack(state);
}
// Backtrack: undo choice
state.remove(choice);
}
}Place queens row by row, checking safety at each step:
function solveNQueens(n) {
const board = Array(n).fill().map(() => Array(n).fill('.'));
const result = [];
function isSafe(row, col) {
// Check column
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') return false;
}
// Check diagonal (top-left)
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === 'Q') return false;
}
// Check diagonal (top-right)
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] === 'Q') return false;
}
return true;
}
function backtrack(row) {
if (row === n) {
result.push(board.map(r => r.join('')));
return;
}
for (let col = 0; col < n; col++) {
if (isSafe(row, col)) {
board[row][col] = 'Q';
backtrack(row + 1);
board[row][col] = '.'; // Backtrack
}
}
}
backtrack(0);
return result;
}Try digits 1-9 in each empty cell, backtrack if invalid:
function solveSudoku(board) {
function isValid(row, col, num) {
// Check row
for (let j = 0; j < 9; j++) {
if (board[row][j] === num) return false;
}
// Check column
for (let i = 0; i < 9; i++) {
if (board[i][col] === num) return false;
}
// Check 3x3 box
const boxRow = Math.floor(row / 3) * 3;
const boxCol = Math.floor(col / 3) * 3;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[boxRow + i][boxCol + j] === num) {
return false;
}
}
}
return true;
}
function solve() {
for (let row = 0; row < 9; row++) {
for (let col = 0; col < 9; col++) {
if (board[row][col] === 0) {
for (let num = 1; num <= 9; num++) {
if (isValid(row, col, num)) {
board[row][col] = num;
if (solve()) return true;
board[row][col] = 0; // Backtrack
}
}
return false;
}
}
}
return true;
}
solve();
}