python solution


  • 0
    
    
    
    
    
    class Solution(object):
    
    
    	def __init__(self):
    
    		self.ansVector=[]
    
    		self.used=[]
    
    		self.ansL=[]
    
    
    	def genMap(self,ansVector):
    
    		board=[]
    
    		for i in range(self.nQueen):
    			board.append(["."]*self.nQueen)
    		
    		for i in range(len(ansVector)):
    			board[ansVector[i]][i]="Q"
    
    		boardStr=[]
    		for i in range(self.nQueen):
    			boardStr.append("".join(board[i]))
    		
    
    
    		return boardStr
    
    
    
    	def printBoard(self,board):
    
    		for row in board:
    
    			print row
    
    	def inbound(self,x,y):
    
    		if 0<=x and x< self.nQueen and 0<=y and y< self.nQueen:
    			return True
    		return False
    
    	def isValidPos(self,idx):
    
    		
    		posDic=[]
    
    		#idx to x y
    
    		vaildPosX=len(self.ansVector)
    		vaildPosY=idx
    
    		for i in range(len(self.ansVector)):
    			posDic.append((i,self.ansVector[i]))
    
    		#check row
    		if idx in self.ansVector:
    
    			return False
    
    		#check diagonal
    		
    
    		
    		for i in range(1,self.nQueen-len(self.ansVector)):
    			ptrX=vaildPosX+i
    			ptrY=vaildPosY+i
    			if self.inbound(ptrX,ptrY) is True and (ptrX,ptrY) in posDic:
    				return False
    
    		for i in range(1,self.nQueen-len(self.ansVector)):
    			ptrX=vaildPosX+i
    			ptrY=vaildPosY-i
    			if self.inbound(ptrX,ptrY) is True and (ptrX,ptrY) in posDic:
    				return False
    
    		for i in range(1,len(self.ansVector)+1):
    			ptrX=vaildPosX-i
    			ptrY=vaildPosY-i
    			if self.inbound(ptrX,ptrY) is True and (ptrX,ptrY) in posDic:
    				return False
    
    		for i in range(1,len(self.ansVector)+1):
    			ptrX=vaildPosX-i
    			ptrY=vaildPosY+i
    			if self.inbound(ptrX,ptrY) is True and (ptrX,ptrY) in posDic:
    				return False
    
    		return True
    
    
    	def BT(self,n):
    
    
    		if n==0:
    			self.ansL.append(self.ansVector[:])
    
    		for i in range(self.nQueen):
    			
    			if self.used[i]==False and self.isValidPos(i):
    				self.used[i]=True
    				self.ansVector.append(i)
    				self.BT(n-1)
    				self.ansVector.pop()
    				self.used[i]=False
    
    
    
    	def solveNQueens(self, n):
    		"""
    		:type n: int
    		:rtype: List[List[str]]
    		"""
    		
    		self.nQueen=n
    		self.used=[False]*n
    
    		ans=[]
    
    		self.BT(n)
    
    		for v in self.ansL:
    			ans.append(self.genMap(v))
    		'''	
    		i=0
    
    		for m in ans:
    			self.printBoard(m)
    			i+=1
    		'''
    
    		return ans
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.