Complex Techniques
Level 4: Advanced Mastery - Master sophisticated algorithmic techniques and optimization methods
Complex Techniques
Advanced Backtracking with Optimization
Optimized Backtracking
Advanced backtracking involves sophisticated pruning techniques, memoization, and optimization strategies to reduce the search space dramatically.
🌳 Real-Life Analogy:
Think of exploring a maze with smart techniques: instead of blindly trying every path, you use landmarks, keep notes of dead ends, and employ strategic shortcuts to find solutions faster.
TypeScript
// N-Queens with advanced optimizations
class NQueensOptimized {
private n: number;
private solutions: number[][];
private cols: Set;
private diag1: Set; // row + col
private diag2: Set; // row - col
constructor(n: number) {
this.n = n;
this.solutions = [];
this.cols = new Set();
this.diag1 = new Set();
this.diag2 = new Set();
}
solveNQueens(): number[][] {
const board: number[] = new Array(this.n).fill(-1);
this.backtrack(board, 0);
return this.solutions;
}
private backtrack(board: number[], row: number): void {
if (row === this.n) {
this.solutions.push([...board]);
return;
}
for (let col = 0; col < this.n; col++) {
if (this.isSafe(row, col)) {
// Place queen
board[row] = col;
this.cols.add(col);
this.diag1.add(row + col);
this.diag2.add(row - col);
this.backtrack(board, row + 1);
// Remove queen (backtrack)
this.cols.delete(col);
this.diag1.delete(row + col);
this.diag2.delete(row - col);
board[row] = -1;
}
}
}
private isSafe(row: number, col: number): boolean {
return !this.cols.has(col) &&
!this.diag1.has(row + col) &&
!this.diag2.has(row - col);
}
}
// Sudoku Solver with constraint propagation
class SudokuSolver {
private board: number[][];
private rows: Set[];
private cols: Set[];
private boxes: Set[];
constructor(board: number[][]) {
this.board = board.map(row => [...row]);
this.rows = Array.from({length: 9}, () => new Set());
this.cols = Array.from({length: 9}, () => new Set());
this.boxes = Array.from({length: 9}, () => new Set());
// Initialize constraints
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (this.board[r][c] !== 0) {
const num = this.board[r][c];
const boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3);
this.rows[r].add(num);
this.cols[c].add(num);
this.boxes[boxIndex].add(num);
}
}
}
}
solve(): boolean {
const emptyCell = this.findBestEmptyCell();
if (!emptyCell) return true; // Solved
const [row, col] = emptyCell;
const possibleValues = this.getPossibleValues(row, col);
for (const num of possibleValues) {
if (this.isValid(row, col, num)) {
this.placeNumber(row, col, num);
if (this.solve()) return true;
this.removeNumber(row, col, num);
}
}
return false;
}
private findBestEmptyCell(): [number, number] | null {
let minOptions = 10;
let bestCell: [number, number] | null = null;
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (this.board[r][c] === 0) {
const options = this.getPossibleValues(r, c).length;
if (options < minOptions) {
minOptions = options;
bestCell = [r, c];
if (minOptions === 1) return bestCell; // Early termination
}
}
}
}
return bestCell;
}
private getPossibleValues(row: number, col: number): number[] {
const possible: number[] = [];
for (let num = 1; num <= 9; num++) {
if (this.isValid(row, col, num)) {
possible.push(num);
}
}
return possible;
}
private isValid(row: number, col: number, num: number): boolean {
const boxIndex = Math.floor(row / 3) * 3 + Math.floor(col / 3);
return !this.rows[row].has(num) &&
!this.cols[col].has(num) &&
!this.boxes[boxIndex].has(num);
}
private placeNumber(row: number, col: number, num: number): void {
this.board[row][col] = num;
const boxIndex = Math.floor(row / 3) * 3 + Math.floor(col / 3);
this.rows[row].add(num);
this.cols[col].add(num);
this.boxes[boxIndex].add(num);
}
private removeNumber(row: number, col: number, num: number): void {
this.board[row][col] = 0;
const boxIndex = Math.floor(row / 3) * 3 + Math.floor(col / 3);
this.rows[row].delete(num);
this.cols[col].delete(num);
this.boxes[boxIndex].delete(num);
}
}
// Word Break with memoization
class WordBreak {
private memo: Map = new Map();
wordBreak(s: string, wordDict: string[]): boolean {
if (this.memo.has(s)) return this.memo.get(s)!;
if (s.length === 0) return true;
for (const word of wordDict) {
if (s.startsWith(word)) {
const remaining = s.substring(word.length);
if (this.wordBreak(remaining, wordDict)) {
this.memo.set(s, true);
return true;
}
}
}
this.memo.set(s, false);
return false;
}
// Word Break II - return all possible sentences
wordBreakII(s: string, wordDict: string[]): string[] {
const memoSentences: Map = new Map();
const backtrack = (remaining: string): string[] => {
if (memoSentences.has(remaining)) {
return memoSentences.get(remaining)!;
}
if (remaining.length === 0) return [''];
const result: string[] = [];
for (const word of wordDict) {
if (remaining.startsWith(word)) {
const suffix = remaining.substring(word.length);
const suffixSentences = backtrack(suffix);
for (const sentence of suffixSentences) {
const newSentence = sentence.length === 0 ? word : word + ' ' + sentence;
result.push(newSentence);
}
}
}
memoSentences.set(remaining, result);
return result;
};
return backtrack(s);
}
}
Python
from typing import List, Set, Dict, Optional, Tuple
from functools import lru_cache
class NQueensOptimized:
def __init__(self, n: int):
self.n = n
self.solutions = []
self.cols = set()
self.diag1 = set() # row + col
self.diag2 = set() # row - col
def solve_n_queens(self) -> List[List[int]]:
"""Solve N-Queens with optimized backtracking"""
board = [-1] * self.n
self._backtrack(board, 0)
return self.solutions
def _backtrack(self, board: List[int], row: int) -> None:
if row == self.n:
self.solutions.append(board[:])
return
for col in range(self.n):
if self._is_safe(row, col):
# Place queen
board[row] = col
self.cols.add(col)
self.diag1.add(row + col)
self.diag2.add(row - col)
self._backtrack(board, row + 1)
# Remove queen (backtrack)
self.cols.remove(col)
self.diag1.remove(row + col)
self.diag2.remove(row - col)
board[row] = -1
def _is_safe(self, row: int, col: int) -> bool:
return (col not in self.cols and
(row + col) not in self.diag1 and
(row - col) not in self.diag2)
class SudokuSolver:
def __init__(self, board: List[List[int]]):
self.board = [row[:] for row in board]
self.rows = [set() for _ in range(9)]
self.cols = [set() for _ in range(9)]
self.boxes = [set() for _ in range(9)]
# Initialize constraints
for r in range(9):
for c in range(9):
if self.board[r][c] != 0:
num = self.board[r][c]
box_index = (r // 3) * 3 + (c // 3)
self.rows[r].add(num)
self.cols[c].add(num)
self.boxes[box_index].add(num)
def solve(self) -> bool:
"""Solve Sudoku with constraint propagation"""
empty_cell = self._find_best_empty_cell()
if not empty_cell:
return True # Solved
row, col = empty_cell
possible_values = self._get_possible_values(row, col)
for num in possible_values:
if self._is_valid(row, col, num):
self._place_number(row, col, num)
if self.solve():
return True
self._remove_number(row, col, num)
return False
def _find_best_empty_cell(self) -> Optional[Tuple[int, int]]:
"""Find empty cell with minimum possible values (MRV heuristic)"""
min_options = 10
best_cell = None
for r in range(9):
for c in range(9):
if self.board[r][c] == 0:
options = len(self._get_possible_values(r, c))
if options < min_options:
min_options = options
best_cell = (r, c)
if min_options == 1:
return best_cell # Early termination
return best_cell
def _get_possible_values(self, row: int, col: int) -> List[int]:
possible = []
for num in range(1, 10):
if self._is_valid(row, col, num):
possible.append(num)
return possible
def _is_valid(self, row: int, col: int, num: int) -> bool:
box_index = (row // 3) * 3 + (col // 3)
return (num not in self.rows[row] and
num not in self.cols[col] and
num not in self.boxes[box_index])
def _place_number(self, row: int, col: int, num: int) -> None:
self.board[row][col] = num
box_index = (row // 3) * 3 + (col // 3)
self.rows[row].add(num)
self.cols[col].add(num)
self.boxes[box_index].add(num)
def _remove_number(self, row: int, col: int, num: int) -> None:
self.board[row][col] = 0
box_index = (row // 3) * 3 + (col // 3)
self.rows[row].remove(num)
self.cols[col].remove(num)
self.boxes[box_index].remove(num)
class WordBreak:
def __init__(self):
self.memo = {}
def word_break(self, s: str, word_dict: List[str]) -> bool:
"""Word Break with memoization"""
if s in self.memo:
return self.memo[s]
if not s:
return True
for word in word_dict:
if s.startswith(word):
if self.word_break(s[len(word):], word_dict):
self.memo[s] = True
return True
self.memo[s] = False
return False
def word_break_ii(self, s: str, word_dict: List[str]) -> List[str]:
"""Word Break II - return all possible sentences"""
memo_sentences = {}
def backtrack(remaining: str) -> List[str]:
if remaining in memo_sentences:
return memo_sentences[remaining]
if not remaining:
return ['']
result = []
for word in word_dict:
if remaining.startswith(word):
suffix = remaining[len(word):]
suffix_sentences = backtrack(suffix)
for sentence in suffix_sentences:
new_sentence = word if not sentence else word + ' ' + sentence
result.append(new_sentence)
memo_sentences[remaining] = result
return result
return backtrack(s)
# Combination Sum with pruning
def combination_sum_optimized(candidates: List[int], target: int) -> List[List[int]]:
"""Combination Sum with advanced pruning"""
candidates.sort() # Sort for pruning
result = []
def backtrack(path: List[int], remaining: int, start: int) -> None:
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
candidate = candidates[i]
# Pruning: if current candidate is too large, all subsequent will be too
if candidate > remaining:
break
path.append(candidate)
backtrack(path, remaining - candidate, i) # i (not i+1) for reuse
path.pop()
backtrack([], target, 0)
return result
# Palindrome Partitioning with memoization
class PalindromePartitioning:
def __init__(self):
self.palindrome_memo = {}
def partition(self, s: str) -> List[List[str]]:
"""Partition string into palindromes"""
result = []
def is_palindrome(string: str) -> bool:
if string in self.palindrome_memo:
return self.palindrome_memo[string]
result = string == string[::-1]
self.palindrome_memo[string] = result
return result
def backtrack(path: List[str], start: int) -> None:
if start == len(s):
result.append(path[:])
return
for end in range(start + 1, len(s) + 1):
substring = s[start:end]
if is_palindrome(substring):
path.append(substring)
backtrack(path, end)
path.pop()
backtrack([], 0)
return result
OCaml
(* N-Queens with optimized backtracking *)
module NQueensOptimized = struct
type state = {
cols: bool array;
diag1: (int, bool) Hashtbl.t;
diag2: (int, bool) Hashtbl.t;
}
let create_state n = {
cols = Array.make n false;
diag1 = Hashtbl.create n;
diag2 = Hashtbl.create n;
}
let is_safe state row col =
not state.cols.(col) &&
not (Hashtbl.mem state.diag1 (row + col)) &&
not (Hashtbl.mem state.diag2 (row - col))
let place_queen state row col =
state.cols.(col) <- true;
Hashtbl.add state.diag1 (row + col) true;
Hashtbl.add state.diag2 (row - col) true
let remove_queen state row col =
state.cols.(col) <- false;
Hashtbl.remove state.diag1 (row + col);
Hashtbl.remove state.diag2 (row - col)
let solve_n_queens n =
let solutions = ref [] in
let board = Array.make n (-1) in
let state = create_state n in
let rec backtrack row =
if row = n then
solutions := (Array.copy board) :: !solutions
else
for col = 0 to n - 1 do
if is_safe state row col then begin
board.(row) <- col;
place_queen state row col;
backtrack (row + 1);
remove_queen state row col;
board.(row) <- -1
end
done
in
backtrack 0;
!solutions
end
(* Word Break with memoization *)
module WordBreak = struct
let word_break s word_dict =
let memo = Hashtbl.create 100 in
let rec can_break remaining =
if Hashtbl.mem memo remaining then
Hashtbl.find memo remaining
else begin
let result =
if String.length remaining = 0 then true
else
List.exists (fun word ->
let word_len = String.length word in
let remaining_len = String.length remaining in
if word_len <= remaining_len &&
String.sub remaining 0 word_len = word then
can_break (String.sub remaining word_len (remaining_len - word_len))
else false
) word_dict
in
Hashtbl.add memo remaining result;
result
end
in
can_break s
(* Word Break II - return all possible sentences *)
let word_break_ii s word_dict =
let memo_sentences = Hashtbl.create 100 in
let rec backtrack remaining =
if Hashtbl.mem memo_sentences remaining then
Hashtbl.find memo_sentences remaining
else begin
let result =
if String.length remaining = 0 then [""]
else
List.fold_left (fun acc word ->
let word_len = String.length word in
let remaining_len = String.length remaining in
if word_len <= remaining_len &&
String.sub remaining 0 word_len = word then begin
let suffix = String.sub remaining word_len (remaining_len - word_len) in
let suffix_sentences = backtrack suffix in
List.fold_left (fun acc2 sentence ->
let new_sentence =
if String.length sentence = 0 then word
else word ^ " " ^ sentence
in
new_sentence :: acc2
) acc suffix_sentences
end else acc
) [] word_dict
in
Hashtbl.add memo_sentences remaining result;
result
end
in
backtrack s
end
(* Combination Sum with pruning *)
let combination_sum candidates target =
let sorted_candidates = List.sort compare candidates in
let result = ref [] in
let rec backtrack path remaining start =
if remaining = 0 then
result := (List.rev path) :: !result
else
let rec try_candidates i candidates_rest =
match candidates_rest with
| [] -> ()
| candidate :: rest ->
if candidate > remaining then () (* Pruning *)
else begin
backtrack (candidate :: path) (remaining - candidate) i;
try_candidates (i + 1) rest
end
in
try_candidates start (List.drop sorted_candidates start)
in
backtrack [] target 0;
!result
(* Sudoku Solver with constraint propagation *)
module SudokuSolver = struct
type sudoku = int array array
let is_valid board row col num =
(* Check row *)
let row_valid = not (Array.exists (fun x -> x = num) board.(row)) in
(* Check column *)
let col_valid =
let rec check r =
if r >= 9 then true
else if board.(r).(col) = num then false
else check (r + 1)
in
check 0
in
(* Check 3x3 box *)
let box_start_row = (row / 3) * 3 in
let box_start_col = (col / 3) * 3 in
let box_valid =
let rec check_box r c =
if r >= box_start_row + 3 then true
else if c >= box_start_col + 3 then check_box (r + 1) box_start_col
else if board.(r).(c) = num then false
else check_box r (c + 1)
in
check_box box_start_row box_start_col
in
row_valid && col_valid && box_valid
let find_best_empty_cell board =
let min