Thursday, January 16, 2014

Leetcode: N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.


Solution:

public class Solution {
    public int totalNQueens(int n) 
    {
        return totalNQueens(new boolean[n][n], 0);
    }
    
    public int totalNQueens(boolean[][] board, int row)
    {
        if (row==board.length)
            return 1;
        int solutions = 0;
        for(int i=0; i < board.length; i++)
        {
            if(canPutQueen(board,row,i))
            {
                board[row][i] = true;
                solutions += totalNQueens(board, row+1);
                board[row][i] = false;
            }
        }
        return solutions;
    }
    
    public boolean canPutQueen(boolean[][] board, int row, int column)
    {
        for(int i=0; i<row; i++)   
        {
            if(board[i][column])
                return false;
            if(column+i-row >=0 && board[i][column+i-row])
                return false;
            if(column+row-i < board.length && board[i][column+row-i])
                return false;
        }
        return true;
    }
}

No comments :

Post a Comment