java backtracking

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, especially constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate (backtracks) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Backtracking can be implemented in Java using recursion. Essentially, the backtracking algorithm tries all possible solutions and returns a solution if it is found, or backtracks and tries another solution if it is not.

Here is a simple example of a backtracking algorithm in Java that solves the 8-queens problem:

public class BacktrackingExample {

    static final int N = 8;

    static boolean isSafe(int[][] board, int row, int col) {
        // check row
        for (int i = 0; i < col; i++) {
            if (board[row][i] == 1) {
                return false;
            }
        }
        // check upper diagonal on left side
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }
        // check lower diagonal on left side
        for (int i = row, j = col; i < N && j >= 0; i++, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }
        return true;
    }

    static boolean solve(int[][] board, int col) {
        // base case: if all queens are placed, return true
        if (col >= N) {
            return true;
        }
        // try all rows for this column
        for (int i = 0; i < N; i++) {
            // check if the queen can be placed here
            if (isSafe(board, i, col)) {
                // place the queen
                board[i][col] = 1;
                // recurse for the next column
                if (solve(board, col + 1)) {
                    return true;
                }
                // backtrack and remove the queen
                board[i][col] = 0;
            }
        }
        // no solution found
        return false;
    }

    static void printSolution(int[][] board) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] board = new int[N][N];
        if (solve(board, 0)) {
            printSolution(board);
        } else {
            System.out.println("No solution found");
        }
    }
}