Saturday, May 10, 2014

Leetcode (Python): N-Queens II

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


Solution:

class Solution:
    # @return an integer
    def totalNQueens(self, n):
        board = []
        for i in range(0,n):
            temp = []
            for j in range(0,n):
                temp.append(False)
            board.append(temp)
        return self.countQueens(board,0)
        
    def countQueens(self, board, row):
        if row == len(board):
            return 1
        solutions = 0
        for i in range(0,len(board)):
            if self.canPutQueen(board,row,i):
                board[row][i] = True
                solutions += self.countQueens(board, row+1)
                board[row][i] = False
        return solutions
        
    def canPutQueen(self, board, row,column):
        for i in range(0,row):
            if board[i][column]:
                return False
            if column-(row-i)>=0 and board[i][column-(row-i)]:
                return False
            if column+(row-i)<len(board) and board[i][column+(row-i)]:
                return False
        return True

No comments :

Post a Comment