N Queens Problem

Discussing a LeetCode Problem.

Photo by sk on Unsplash

Problem Statement

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle.

https://leetcode.com/problems/n-queens-ii/description/

Explanation of Approach

Make a n x n character matrix and initialise each cell with value '.' .

Traverse through each cell row-wise, for each column as in

For each row index and column index, we can place a queen in the cell if all the cells to it’s east, west, north, north-west, north-east, south , south-west and south east has no queens placed in them.

Since we are traversing through columns from left to right and rows through top to bottom, then for each cell, cells to it’s south and columns to the right are yet to be marked. It is enough to check for west, north-west and south-west. We don’t have to check the north cos if some cell in north is marked with queen it will contribute to a new sequence of cells where the queens can be places without striking each other.

For a cell (i, j) , (i-1, j-1) , … , till i or j hits 0 gives all the cells in the north-west direction.

For a cell (i, j) , (i, j-1) , … , till j hits 0 gives give all the cells in the west direction.

For a cell (i, j) , (i+1, j-1) , … , till i hits n-1 or j hits 0 gives give all the cells in the south-west direction.

If all these cells is not marked Q, then mark the current cell as Q. Then do the same for the next column. After that unmark the Queen, to fecilitate for other choices.

Implementation

    public static int count = 0;

    public static boolean north_west(int col_idx, int row_idx, char[][] board, int n){
        while(col_idx >=0 && row_idx >=0){
            if(board[row_idx][col_idx] == 'Q'){
                return false;
            }
            col_idx--;
            row_idx--;
        }
        return true;
    }
    
    public static boolean east(int col_idx, int row_idx, char[][] board, int n){
        while(col_idx >=0){
            if(board[row_idx][col_idx] == 'Q'){
                return false;
            }
            col_idx --;
        }
        return true;
    }
    
    public static boolean south_west(int col_idx, int row_idx, char[][] board, int n){
        while(col_idx >=0 && row_idx <n){
            if(board[row_idx][col_idx] == 'Q'){
                return false;
            }
            col_idx--;
            row_idx++;
        }
        return true;
    }
    
    public static void solve(int col_idx, char[][] board, int n){
        if(col_idx == n){
            count++;
            return;
        }
        for(int row_idx=0 ; row_idx<n; row_idx++){
            if(east(col_idx, row_idx, board, n) 
            && north_west(col_idx, row_idx, board, n) 
            && south_west(col_idx, row_idx, board, n) ){
                board[row_idx][col_idx] = 'Q';
                solve(col_idx+1,board, n );
                board[row_idx][col_idx] = '.';
            }
        }
    }
    
    public static void f(int n){
        char board[][] = new char[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n;j++){
                board[i][j] = '.';
            }
        }
        solve(0,board, n);
    }

    public static void main(String[] args) {
        try {
            FastReader sc=new FastReader();
            int n = sc.nextInt();
            f(n);
            System.out.println(count);
        }
        catch (Exception e) {
            e.printStackTrace() ;
            return;
        }
    }
    
}