Permutation Generation

Generating permutations is a foundational DFS application. By treating each selection step as a level in a tree, we can explore all possible orderings.

import java.util.Scanner;

public class Permutations {
    private static int[] sequence = new int[12];
    private static boolean[] selected = new boolean[12];

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int size = input.nextInt();
        generate(1, size);
    }

    private static void generate(int depth, int limit) {
        if (depth > limit) {
            for (int i = 1; i <= limit; i++) System.out.printf("%5d", sequence[i]);
            System.out.println();
            return;
        }
        for (int i = 1; i <= limit; i++) {
            if (!selected[i]) {
                selected[i] = true;
                sequence[depth] = i;
                generate(depth + 1, limit);
                selected[i] = false;
            }
        }
    }
}

N-Queens Constraint Solving

The N-Queens problem extends permutation logic by adding geometric constraints. We must ensure no two queens share a column, a 45-degree diagonal, or a 135-degree diagonal.

public class NQueensSolver {
    private int totalWays = 0;
    private int size;
    private boolean[] colUsed, diag1, diag2;

    public void solve(int n) {
        this.size = n;
        colUsed = new boolean[n];
        diag1 = new boolean[2 * n];
        diag2 = new boolean[2 * n];
        backtrack(0);
        System.out.println(totalWays);
    }

    private void backtrack(int row) {
        if (row == size) {
            totalWays++;
            return;
        }
        for (int col = 0; col < size; col++) {
            if (!colUsed[col] && !diag1[row + col] && !diag2[row - col + size]) {
                colUsed[col] = diag1[row + col] = diag2[row - col + size] = true;
                backtrack(row + 1);
                colUsed[col] = diag1[row + col] = diag2[row - col + size] = false;
            }
        }
    }
}

State-Space Partitioning

When partitioning tasks into multiple groups to minimize the maximum load, we can treat each task as a branching decision between two processors.

public class TaskScheduler {
    private int minMaxLoad = Integer.MAX_VALUE;
    private int[] tasks;

    private void distribute(int index, int leftLoad, int rightLoad) {
        if (index == tasks.length) {
            minMaxLoad = Math.min(minMaxLoad, Math.max(leftLoad, rightLoad));
            return;
        }
        distribute(index + 1, leftLoad + tasks[index], rightLoad);
        distribute(index + 1, leftLoad, rightLoad + tasks[index]);
    }
}

Breadth-First Search for Shortest Paths

BFS is ideal for finding the shortest path in unweighted graphs, such as the movement of a knight on a chessboard.

import java.util.*;

public class KnightPath {
    public void compute(int rows, int cols, int startX, int startY) {
        int[][] board = new int[rows][cols];
        for(int[] row : board) Arrays.fill(row, -1);
        Queue<int[]> queue = new LinkedList<>();
        
        queue.add(new int[]{startX, startY});
        board[startX][startY] = 0;
        
        int[][] moves = {{1,2}, {1,-2}, {-1,2}, {-1,-2}, {2,1}, {2,-1}, {-2,1}, {-2,-1}};
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int[] move : moves) {
                int nx = curr[0] + move[0], ny = curr[1] + move[1];
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && board[nx][ny] == -1) {
                    board[nx][ny] = board[curr[0]][curr[1]] + 1;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
    }
}

Implementation Insights

• DFS vs. BFS: Use DFS for ehxaustive search or pathfinding where memory is constrained; use BFS for shortest path discovery in graphs.
• State Management: Always use visited arrays or sets to prevent infinite loops when cycles exist in your state spacce.
• Graph Abstraction: Define the state clearly. If the problem involves hierarchical choices, treat it as a tree. If it involves re-visiting states, treat it as a graph.