N-Queens with backtracking

Source: LeetCode.
Genre: Hard
Problem:

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Problem:
Let's understand the problem first! On a chase board a queen can move,

• Horizontally
• Vertically
• Diagonally

 The problem says, on a nxn chase board, we've to place n queens on n different places of that chase board such that no queen can attack any other queens, horizontally, vertically as well as diagonally.

The above picture of 8x8 chase board is a perfect example of an arrangement where every queens are safe from others.

Solution:

The chase board can be represented by a binary matrix (two dimensional array) where 0 means no queen and 1 means queen. Initially, every position of the matrix will be placed by 0.

Create a two dimensional array to represent the board.

static int[][] board = null;

Initialize the board.

    void init(int numberOfQueens) {
        this.board = new int[numberOfQueens][numberOfQueens];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                board[i][j] = 0;
            }
        }
    }

Check if there's already a queen in a row.

    boolean checkIfTheresAQueenInARow(int row) {
        for (int i = 0; i < board.length; i++) {
            if (board[row][i] == 1) {
                return true;
            }
        }
        return false;
    }

Check if there's already a queen in a column.

    boolean checkIfTheresAQueenInAColumn(int column) {
        for (int i = 0; i < board.length; i++) {
            if (board[i][column] == 1) {
                return true;
            }
        }
        return false;
    }

Check if there's already a queen in diagonal positions.

    boolean checkIfTheresQueenDiagonally(int row, int col) {
        int rowCarry = 0;
        int columnCarry = 0;
        boolean res = false;
        while (!res) {
            if ((row - rowCarry) > -1 && (col - columnCarry) > -1) {
                if (board[row - rowCarry][col - columnCarry] != 0) {
                    res = true;
                }
            }
            if ((row - rowCarry) > -1 && (col + columnCarry) < board.length) {
                if (board[row - rowCarry][col + columnCarry] != 0) {
                    res = true;
                }
            }
            if ((row + rowCarry) < board.length && (col - columnCarry) > -1) {
                if (board[row + rowCarry][col - columnCarry] != 0) {
                    res = true;
                }
            }
            if ((row + rowCarry) < board.length && (col + columnCarry) < board.length) {
                if (board[row + rowCarry][col + columnCarry] != 0) {
                    res = true;
                }
            }
            rowCarry++;
            columnCarry++;
            if (rowCarry > board.length - 1 && columnCarry > board.length - 1) {
                break;
            }
        }
        return res;
    }

Check if a position is safe (There's no queen row wise, column wise and diagonally).

    boolean checkIfAPositionIsSafe(int row, int col) {
        if (checkIfTheresAQueenInARow(row)) {
            return false;
        }
        if (checkIfTheresAQueenInAColumn(col)) {
            return false;
        }
        if (checkIfTheresQueenDiagonally(row, col)) {
            return false;
        }
        return true;
    }

Solve the problem by backtracking.

    private void solveNQueensHelper(int row) {
        if (row == board.length) {
            listToReturn.add(print());
        } else {
            for (int col = 0; col < board.length; col++) {
                if (checkIfAPositionIsSafe(row, col)) {
                    board[row][col] = 1;
                    row += 1;
                    solveNQueensHelper(row);
                    row = row - 1;
                    board[row][col] = 0;
                }
            }
        }
    }

Full code

class Solution {
    static int[][] board = null;
    List < List < String >> listToReturn = new ArrayList < List < String >> ();

    public List < List < String >> solveNQueens(int n) {
        init(n);

        solveNQueensHelper(0);

        return listToReturn;
    }


    private void solveNQueensHelper(int row) {
        if (row == board.length) {
            listToReturn.add(print());

        } else {
            for (int col = 0; col < board.length; col++) {
                if (checkIfAPositionIsSafe(row, col)) {
                    board[row][col] = 1;
                    row += 1;
                    solveNQueensHelper(row);
                    row = row - 1;
                    board[row][col] = 0;
                }
            }
        }

    }


    List < String > print() {
        List < String > individualMatch = new ArrayList < > ();
        for (int i = 0; i < board.length; i++) {
            StringBuffer sb = new StringBuffer();
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == 1) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }

            }
            individualMatch.add(sb.toString());
        }

        return individualMatch;
    }


    void init(int numberOfQueens) {
        this.board = new int[numberOfQueens][numberOfQueens];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                board[i][j] = 0;
            }
        }
    }

    boolean checkIfTheresAQueenInARow(int row) {
        for (int i = 0; i < board.length; i++) {
            if (board[row][i] == 1) {
                return true;
            }
        }
        return false;
    }

    boolean checkIfTheresAQueenInAColumn(int column) {
        for (int i = 0; i < board.length; i++) {
            if (board[i][column] == 1) {
                return true;
            }
        }
        return false;
    }

    boolean checkIfTheresQueenDiagonally(int row, int col) {
        int rowCarry = 0;
        int columnCarry = 0;

        boolean res = false;

        while (!res) {
            if ((row - rowCarry) > -1 && (col - columnCarry) > -1) {
                if (board[row - rowCarry][col - columnCarry] != 0) {
                    res = true;
                }
            }
            if ((row - rowCarry) > -1 && (col + columnCarry) < board.length) {
                if (board[row - rowCarry][col + columnCarry] != 0) {
                    res = true;
                }
            }
            if ((row + rowCarry) < board.length && (col - columnCarry) > -1) {
                if (board[row + rowCarry][col - columnCarry] != 0) {
                    res = true;
                }
            }
            if ((row + rowCarry) < board.length && (col + columnCarry) < board.length) {
                if (board[row + rowCarry][col + columnCarry] != 0) {
                    res = true;
                }
            }
            rowCarry++;
            columnCarry++;
            if (rowCarry > board.length - 1 && columnCarry > board.length - 1) {
                break;
            }

        }
        return res;
    }

    boolean checkIfAPositionIsSafe(int row, int col) {

        if (checkIfTheresAQueenInARow(row)) {
            return false;
        }
        if (checkIfTheresAQueenInAColumn(col)) {
            return false;
        }
        if (checkIfTheresQueenDiagonally(row, col)) {
            return false;
        }
        return true;
    }

}

hastaLaVista




You may follow me on LinkedIn, Github, facebook