N-Queens

A very tricky problem. I am not even a chess player, apparently it took me a while to first figure out what N-Queens game is.

Basic rule: "no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. "

The problem is solved by implementing back tracking algorithm. 

1. We start by placing the queen at each column. When we iterate for the next valid column, we assume the queen will be put in the next row, since no two queens share the same row. 

2. Recursively put the queen at different columns (and different rows of course), if a solution is found, we draw a chessboard and return the solution. 

3. Since we presume queens will be placed in different rows, we only need to check if two queens are

    1. in the same column 

    2. in the same main diagonal 

    3. in the same anti diagonal 

4. The chessboard is a string array with each element represents a row of places of the chessboard.

If the question is to output the number of solutions, set a public static int rst instead of the arraylist. 

public class NQueens {
    public ArrayList solveNQueens(int n) {
        ArrayList rst = new ArrayList();
        if (n <= 0 || n == 2 || n == 3)
            return rst;
        validQueens(rst, new ArrayList (), n);
        return rst;
        
    }
    private void validQueens(ArrayList rst, ArrayList queenCols, int n)
    {
        if (queenCols.size() == n)
        {
            String[] chessBoard = drawChessBoard(queenCols);
            rst.add(chessBoard);
            return;
        }
        
        for (int column = 0; column < n; column++)
        {
            if(!isValid(queenCols, column))
                continue;
            queenCols.add(column);
            validQueens(rst, queenCols, n);
            queenCols.remove(queenCols.size() - 1);
        }
    }
    private boolean isValid(ArrayList queenCols, int col)
    {
        //The queen will be placed in the next row, if the last row is i 
        //then this row will be i + 1, which equals the size of the arraylist 
        int row = queenCols.size();
        for (int i = 0; i < queenCols.size(); i++)
        {
            //same column
            if (col == queenCols.get(i))
                return false;
            //main diagonal 
            if (i - queenCols.get(i) == row - col)
                return false;//off diagonal
            if (i + queenCols.get(i) == row + col)
                return false;
        }
        return true;
    }
    private String[] drawChessBoard(ArrayList queenCols)
    {
        //chessboard is a string array, each element represents a row
   //cols has n element, the value of the i-th element represents the column at this row
   //where the queen should be put
        String[] chessBoard = new String[queenCols.size()];
        for (int row = 0; row < queenCols.size(); row++)
        {
            chessBoard[row] = "";
            for (int col = 0; col < queenCols.size(); col++)
            {
                if (col == queenCols.get(row))
                    chessBoard[row] += "Q";
                else
                    chessBoard[row] += ".";
            }
        }
        return chessBoard;
    }
    
}

N-Queens II

public class NQueens {
    public static int sum;
    public int totalNQueens(int n) {
        if (n == 0 || n == 2 || n == 3)
            return 0;
        sum = 0;
        validQueens(new ArrayList (), n);
        return sum;
    }
    private void validQueens(List queenCols, int n) {
        if (queenCols.size() == n) {
            sum++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if(!isValid(queenCols, col))
                continue;
            queenCols.add(col);
            validQueens(queenCols, n);
            queenCols.remove(queenCols.size() - 1);
        }
    }
    private boolean isValid(List queenCols, int col) {
        int row = queenCols.size();
        for (int i = 0; i < queenCols.size(); i++) {
            if (col == queenCols.get(i))
                return false;
            if (i + queenCols.get(i) == row + col)
                return false;
            if (i - queenCols.get(i) == row - col)
                return false;
        }
        return true;
    }
}