LeetCode: N-Queens I&II

八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同一列，或同意斜线上。可以把八皇后问题拓展为n皇后问题，即在n*n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。


This is a typical recursive problem.

不难，有几点注意的问题：

1.关于数组的问题
2.容易出错的点：用临时变量 tempForRec 消除下一层递归所带来的影响
3.判断两个点是否在同一斜线上 Math.abs(x1-x2) == Math.abs(y1-y2)
4.有其他节省空间的算法：用一个数组来记录有效位置比如j=A[i] means row i and column j has been placed a queen.

My Solution:

  public ArrayList solveNQueens(int n) {
        
        ArrayList ret = new ArrayList();
        String[] tempResult = new String[n];
        
        if(n<=0) return ret;
        
        findPossibleResultNextRow(n, 0, tempResult, ret);
        
        return ret;
    }
    
    
    void findPossibleResultNextRow(int totalNum, int curRow, String[] tempResult, ArrayList ret){
        
        if(curRow == totalNum){//find a solution
            //String[] oneSolution = tempResult.toArray(); 
            ret.add(tempResult);
            return;
        }
        
        for(int col=0; col<totalNum; col++){
            
            if(isValidPosition(curRow, col, tempResult)){
                
                StringBuilder sb = new StringBuilder(totalNum);
                
                for(int i =0; i<totalNum; i++){
                    
                    if(i==col) 
                        sb.append('Q');
                    else
                        sb.append('.');
                }
                tempResult[curRow] = sb.toString();
                
                String[] tempForRec = new String[totalNum];
                
                for(int j = 0; j<=curRow; j++)
                    tempForRec[j] = tempResult[j];
                
                findPossibleResultNextRow(totalNum, curRow+1, tempForRec, ret);
 
            }
        }
        
    }
    
    boolean isValidPosition(int curRow, int curCol, String[] tempResult){
        
        for(int i =0; i< curRow; i++){
            String str = tempResult[i];
            int col = str.indexOf('Q');
            if(Math.abs(curRow-i)==Math.abs(curCol-col) || curCol == col)// Math.abs(curRow-i)/Math.abs(curCol-col)==1 /by zeor exception
                return false;
        }
        return true;
    
    }