Hamiltonian Bitmask DP
Euler paths visit every edge. Hamiltonian paths visit every vertex. That one-word swap -- edge to vertex -- rockets the problem from polynomial to NP-hard. No one knows a polynomial algorithm. But when \(N \le 20\), bitmask DP solves it in \(O(2^N \cdot N^2)\), which is fast enough.
Euler vs Hamilton: The Complexity Gap
| Euler | Hamilton | |
|---|---|---|
| Visit every... | Edge | Vertex |
| Existence check | Degree conditions, \(O(V + E)\) | NP-complete |
| Finding the path | Hierholzer's, \(O(V + E)\) | NP-hard |
| Best known for small \(N\) | \(O(V + E)\) | \(O(2^N \cdot N^2)\) bitmask DP |
The key difference: edges can be consumed independently, but vertices interact. Visiting vertex \(v\) affects which other vertices are reachable. You need to track the entire set of visited vertices.
Key insight. Bitmask DP works because the state is "which vertices have I visited?" plus "where am I now?" A bitmask of \(N\) bits encodes the visited set. There are \(2^N \cdot N\) states total. Each transition checks one edge. Total: \(O(2^N \cdot N^2)\).
The DP Formulation
Define:
Base case: \(dp[1 \ll s][s] = 1\) where \(s\) is the starting vertex.
Transition: For each state \((mask, u)\) with \(dp[mask][u] > 0\), for each neighbor \(v\) of \(u\) such that \(v \notin mask\):
Answer: \(dp[(1 \ll N) - 1][t]\) where \(t\) is the target vertex. The mask \((1 \ll N) - 1\) has all \(N\) bits set, meaning all vertices visited.
CSES Hamiltonian Flights
Problem. Given a directed graph with \(N\) cities (\(N \le 20\)) and \(M\) flights, count the number of routes from city 1 to city \(N\) that visit every city exactly once. Output modulo \(10^9 + 7\).
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
adj[a - 1].push_back(b - 1);
}
vector<vector<long long>> dp(1 << n, vector<long long>(n, 0));
dp[1][0] = 1; // start at node 0, mask = {0}
for (int mask = 1; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if (!(mask & (1 << u))) continue;
if (!dp[mask][u]) continue;
for (int v : adj[u]) {
if (mask & (1 << v)) continue;
int nm = mask | (1 << v);
dp[nm][v] = (dp[nm][v] + dp[mask][u]) % MOD;
}
}
}
printf("%lld\n", dp[(1 << n) - 1][n - 1]);
}
Trace on a Small Example
Graph: 4 nodes. Edges: 0→1, 0→2, 1→2, 1→3, 2→3. Start = 0, end = 3.
Masks are 4-bit: bit \(i\) means node \(i\) is visited. Mask 0001 = {0}, mask 1111 = {0,1,2,3}.
| Step | mask (binary) | Node | dp value | Transitions |
|---|---|---|---|---|
| Init | 0001 | 0 | 1 | → node 1 (mask 0011), → node 2 (mask 0101) |
| 1 | 0011 | 1 | 1 | → node 2 (mask 0111), → node 3 (mask 1011) |
| 2 | 0101 | 2 | 1 | → node 3 (mask 1101) |
| 3 | 0111 | 2 | 1 | → node 3 (mask 1111) |
| 4 | 1011 | 3 | 1 | no unvisited neighbors (3 is the end) |
| 5 | 1101 | 3 | 1 | partial path, node 1 not visited -- stuck |
| 6 | 1111 | 3 | 1 | answer |
Wait -- mask 1101 has nodes {0, 2, 3} visited but not node 1. Since we end at 3 and node 1 isn't visited, this path doesn't reach the full mask. So it contributes nothing.
Answer: 1 (the path 0 → 1 → 2 → 3).
Gotcha. Pruning matters for speed. If bit 0 is not set in the mask, skip it -- we always start at node 0. If the full mask doesn't include the end node, skip it. These checks prevent wasting time on unreachable states.
Optimization: Pruning Dead States
Two easy prunings cut runtime significantly:
- Start node must be in the mask. Skip any mask where bit 0 is unset.
- End node appears only in the full mask. If \(v = N-1\) and mask \(\ne (1 \ll N) - 1\), don't transition into that state.
for (int mask = 1; mask < (1 << n); mask++) {
if (!(mask & 1)) continue; // node 0 must be visited
for (int u = 0; u < n; u++) {
if (!(mask & (1 << u)) || !dp[mask][u]) continue;
for (int v : adj[u]) {
if (mask & (1 << v)) continue;
if (v == n - 1 && __builtin_popcount(mask) != n - 1) continue;
dp[mask | (1 << v)][v] = (dp[mask | (1 << v)][v] + dp[mask][u]) % MOD;
}
}
}
CSES Knight's Tour: Backtracking + Warnsdorff's
Problem. Find a sequence of knight moves on an \(8 \times 8\) board that visits every square exactly once, starting from a given square.
This is a Hamiltonian path on the knight's-move graph. With 64 nodes, bitmask DP is impossible (\(2^{64}\) states). Instead, use backtracking with Warnsdorff's heuristic: always move to the square with the fewest onward moves.
#include <bits/stdc++.h>
using namespace std;
int dx[] = {-2,-2,-1,-1,1,1,2,2};
int dy[] = {-1,1,-2,2,-2,2,-1,1};
int board[8][8];
int onward(int x, int y) {
int cnt = 0;
for (int d = 0; d < 8; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8 && board[nx][ny] == 0)
cnt++;
}
return cnt;
}
bool solve(int x, int y, int move) {
board[x][y] = move;
if (move == 64) return true;
vector<tuple<int,int,int>> next;
for (int d = 0; d < 8; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8 && board[nx][ny] == 0) {
next.push_back({onward(nx, ny), nx, ny});
}
}
sort(next.begin(), next.end()); // Warnsdorff: fewest onward first
for (auto [deg, nx, ny] : next) {
if (solve(nx, ny, move + 1)) return true;
}
board[x][y] = 0;
return false;
}
int main() {
int r, c;
scanf("%d%d", &r, &c);
memset(board, 0, sizeof(board));
solve(r - 1, c - 1, 1);
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
printf("%d%c", board[i][j], " \n"[j == 7]);
}
}
}
Key insight. Warnsdorff's heuristic works because moving to the most constrained square first avoids creating isolated dead ends. It's a greedy heuristic, not a guarantee, but on the standard \(8 \times 8\) board it finds a solution almost instantly with no backtracking needed.
Connection to TSP
The Traveling Salesman Problem asks for the minimum-weight Hamiltonian cycle. The bitmask DP is identical in structure:
Transition: \(dp[mask \mid (1 \ll v)][v] = \min(dp[mask][v], dp[mask][u] + w(u, v))\).
Same \(O(2^N \cdot N^2)\) time. Same \(N \le 20\) constraint. The only difference is min instead of count and adding edge weights.
Complexity Summary
| Approach | Time | Space | \(N\) limit |
|---|---|---|---|
| Bitmask DP | \(O(2^N \cdot N^2)\) | \(O(2^N \cdot N)\) | ~20 |
| Brute-force permutations | \(O(N!)\) | \(O(N)\) | ~12 |
| Backtracking + heuristic | Varies | \(O(N^2)\) | Problem-dependent |
For \(N = 20\): \(2^{20} \cdot 400 \approx 4 \times 10^8\). Tight but feasible with fast constant factors.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CSES Hamiltonian Flights | cses.fi/problemset/task/1690 | Medium |
| CSES Knight's Tour | cses.fi/problemset/task/1202 | Hard |