Constraint problems

1static int solve(int n, int row, int[] cols, boolean[] usedCol, boolean[] diag1, boolean[] diag2) {   // counts solutions
2    if (row == n) return 1;
3    int count = 0;
4    for (int c = 0; c < n; c++) {
5        if (usedCol[c] || diag1[row - c + n - 1] || diag2[row + c]) continue;   // attacked by a queen above
6        usedCol[c] = diag1[row - c + n - 1] = diag2[row + c] = true; cols[row] = c;   // choose
7        count += solve(n, row + 1, cols, usedCol, diag1, diag2);                        // explore
8        usedCol[c] = diag1[row - c + n - 1] = diag2[row + c] = false;                   // unchoose
9    }
10    return count;
11}
12static int queens(int n) { return solve(n, 0, new int[n], new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]); }

1static boolean solveSudoku(int[][] g) {                         // 0 = empty; returns true when solved
2    for (int r = 0; r < 9; r++)
3        for (int c = 0; c < 9; c++) {
4            if (g[r][c] != 0) continue;
5            for (int v = 1; v <= 9; v++) {
6                if (!legalDigit(g, r, c, v)) continue;
7                g[r][c] = v;                                    // choose
8                if (solveSudoku(g)) return true;                // explore
9                g[r][c] = 0;                                    // unchoose
10            }
11            return false;                                       // no digit fits this cell: dead end
12        }
13    return true;                                                // no empty cell: solved
14}
15private static boolean legalDigit(int[][] g, int r, int c, int v) {
16    for (int k = 0; k < 9; k++) if (g[r][k] == v || g[k][c] == v) return false;
17    int br = r / 3 * 3, bc = c / 3 * 3;
18    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (g[br + i][bc + j] == v) return false;
19    return true;
20}

1static boolean exist(char[][] b, String word) {
2    for (int r = 0; r < b.length; r++)
3        for (int c = 0; c < b[0].length; c++)
4            if (matchFrom(b, word, 0, r, c)) return true;       // try every cell as the start
5    return false;
6}
7private static boolean matchFrom(char[][] b, String word, int k, int r, int c) {
8    if (k == word.length()) return true;                        // matched every letter
9    if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != word.charAt(k)) return false;   // off the board or wrong letter
10    char saved = b[r][c]; b[r][c] = '#';                        // choose: mark the cell as used
11    boolean found = matchFrom(b, word, k + 1, r + 1, c) || matchFrom(b, word, k + 1, r - 1, c)
12                 || matchFrom(b, word, k + 1, r, c + 1) || matchFrom(b, word, k + 1, r, c - 1);
13    b[r][c] = saved;                                            // unchoose: restore the letter
14    return found;
15}

1static void paths(int[][] m, int r, int c, StringBuilder path, List<String> out) {     // 1 = open, 0 = wall
2    int n = m.length;
3    if (r == n - 1 && c == n - 1) { out.add(path.toString()); return; }              // reached the exit
4    m[r][c] = 0;                                                    // choose: mark as visited
5    String dirs = "DLRU"; int[] dr = {1, 0, 0, -1}, dc = {0, -1, 1, 0};
6    for (int k = 0; k < 4; k++) {
7        int nr = r + dr[k], nc = c + dc[k];
8        if (nr < 0 || nc < 0 || nr >= n || nc >= n || m[nr][nc] == 0) continue;   // outside, a wall, or already visited
9        path.append(dirs.charAt(k));
10        paths(m, nr, nc, path, out);
11        path.deleteCharAt(path.length() - 1);
12    }
13    m[r][c] = 1;                                                    // unchoose: free the cell
14}

1static boolean color(int[][] adj, int v, int[] colors, int m) {      // colors[] starts filled with -1
2    if (v == adj.length) return true;                          // every vertex is coloured
3    for (int c = 0; c < m; c++) {
4        if (conflict(adj, v, c, colors)) continue;             // a neighbour already has colour c
5        colors[v] = c;                                         // choose
6        if (color(adj, v + 1, colors, m)) return true;         // explore
7        colors[v] = -1;                                        // unchoose
8    }
9    return false;
10}
11private static boolean conflict(int[][] adj, int v, int c, int[] colors) {
12    for (int u : adj[v]) if (colors[u] == c) return true;
13    return false;
14}

1static boolean hamiltonian(int[][] adj, List<Integer> path, boolean[] seen) {      // path starts with the start vertex
2    if (path.size() == adj.length) return true;               // visited every vertex exactly once
3    int last = path.get(path.size() - 1);
4    for (int u : adj[last]) {
5        if (seen[u]) continue;                                // already on the path
6        seen[u] = true; path.add(u);                          // choose
7        if (hamiltonian(adj, path, seen)) return true;        // explore
8        path.remove(path.size() - 1); seen[u] = false;        // unchoose
9    }
10    return false;
11}