In this tutorial, we will learn about Backtracking algorithm in Java and its approach to solve crosswords and puzzles problem

Backtracking algorithm resolves a problem by incrementally building candidates to the solution and abandoning a candidate as soon as it can not satisfy the constraint

The N-Queen puzzle problem

Write an algorithm to place N chess queens on an NxN chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column or diagonal

Backtracking approach

public class NQueens {  
    private void printBoard(int[][] board){
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                System.out.printf(" %d", board[i][j]);
            }

            System.out.println();
        }
    }

    private boolean isValid(int[][] board, int row, int col) {
        for (int i = 0; i < col; i++) {
            if (board[row][i] == 1) return false;
        }

        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) return false;
        }

        for (int i = row, j = col; i < board.length && j >= 0 ; i++, j--) {
            if (board[i][j] == 1) return false;
        }

        return true;
    }

    public boolean enumerate(int[][] board, int col) {
        if (col == board.length) return true;

        for (int i = 0; i < board.length; i++) {
            if (isValid(board, i, col)) {
                board[i][col] = 1;

                if (enumerate(board, col+1)) return true;

                board[i][col] = 0; //backtracking
            }
        }

        return false;
    }

    public static void main(String[] args){
        NQueens nQueens = new NQueens();

        int[][] board = new int[8][8];
        if (!nQueens.enumerate(board, 0)) {
            System.out.println("Solution not found!");
        }

        nQueens.printBoard(board);
    }
}

int[][] board = new int[8][8] all cells default value are 0

isValid(board, row, col) ensures no two queens share the same row, column or diagonal

enumerate(board, col) tries all possible candidates starting from column 0 to 7, backtracks to remove the queen from the board as soon as can not build the solution

col == board.length means all queen are placed on the board

board[i][col] = 1 places a queen on the board at rows i and column col

board[i][col] = 0 removes the queen at rows i and column col from the board

Algorithm