My iterative solution for reference (bit-wise operation)


  • 1
    O

    I just turn the recursive solution into an iterative one ~

    int totalNQueens(int n) {
        long ans=0,finished=1,row=0,leftDiag=0,rightDiag=0,canPlace=1;
    	finished=(finished<<n)-1;
    	stack<long> myStack;
    	myStack.push(row);
    	myStack.push(leftDiag);
    	myStack.push(rightDiag);
    	canPlace=finished&(~(row|leftDiag|rightDiag));
    	myStack.push(canPlace);
    	while(!myStack.empty()){
    		canPlace=myStack.top();
    		myStack.pop();
    		rightDiag=myStack.top();
    		myStack.pop();
    		leftDiag=myStack.top();
    		myStack.pop();
    		row=myStack.top();
    		myStack.pop();
    		while(canPlace){
    			long pos=canPlace&(-canPlace);
    			canPlace-=pos;
    			myStack.push(row);
    			myStack.push(leftDiag);
    			myStack.push(rightDiag);
    			myStack.push(canPlace);
    			row=row|pos;
    			if(row==finished)
    				ans++;
    			leftDiag=(leftDiag|pos)<<1;
    			rightDiag=(rightDiag|pos)>>1;
    			canPlace=finished&(~(row|leftDiag|rightDiag));
    		}
    	}
    	return ans;
    }

Log in to reply
 

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