n皇后问题

今天做leetcode遇到的。
感慨颇多。
第一次做这个题，好像是大一，在一本数据结构上看到的，8皇后问题。书的本意是通过这个题引出回朔的概念，可我用了个8重循环，解决后沾沾自喜，也没继续往下看。
第二次遇到好像是大二做usaco的时候了，磕磕绊绊用了各种方式加参考别人代码总算过去，当时感觉这种回朔好难写。
然后，就是现在了。
好多好多年过去了， 我早已忘记了当时在各种OJ刷题的种种。只是依然记得，某一天深夜的晚上，提交成功后正在发呆的时候，qq音乐切换到了一首《kiss the rain》。那温柔的，恬静的，细腻的，忧伤的旋律在耳边缓缓流淌，好像在一片如镜般的湖面上荡起的圈圈涟漪.....
也是从那一刻起，我喜欢上了写程序。

贴一下现在的代码吧，多少还是有点进步的：

import java.util.ArrayList;
import java.util.List;
public class NQueens1 {
    private String[] queensToString(int[] queens) {
        String[] strArray = new String[queens.length];
        int index = 0;
        
        //System.out.println("start");
        
        for (int num : queens) {
            char[] row = new char[queens.length];
        
            for (int i = 0; i < row.length; i++ ) {
                if (i == num) {
                row[i] = 'Q';
                } else {
                    row[i] = '.';
                }
            }
            
            strArray[index++] = new String(row);
            //System.out.println(strArray[index-1]);
        }
        
        //System.out.println("end");
        
        return strArray;
    }
    
    private void setRow(int curI, int curJ, int[][] flag) {
        for (int row = 0; row < flag.length; row++) {
            flag[row][curJ]++;
        }
        
        for (int i = curI+1, j = curJ+1; i<flag.length && j<flag.length; i++, j++) {
            flag[i][j]++;
        }
        
        for (int i = curI-1, j = curJ-1; i>=0 && j>=0; i--, j--) {
            flag[i][j]++;
        }
        
        for (int i = curI+1, j = curJ-1; i<flag.length && j>=0; i++, j--) {
            flag[i][j]++;
        }
        
        for (int i = curI-1, j = curJ+1; i>=0 && j<flag.length; i--, j++) {
            flag[i][j]++;
        }
    }
    
    private void unSetRow(int curI, int curJ, int[][] flag) {
        for (int row = 0; row < flag.length; row++) {
            flag[row][curJ]--;
        }
        
        for (int i = curI+1, j = curJ+1; i<flag.length && j<flag.length; i++, j++) {
            flag[i][j]--;
        }
        
        for (int i = curI-1, j = curJ-1; i>=0 && j>=0; i--, j--) {
            flag[i][j]--;
        }
        
        for (int i = curI+1, j = curJ-1; i<flag.length && j>=0; i++, j--) {
            flag[i][j]--;
        }
        
        for (int i = curI-1, j = curJ+1; i>=0 && j<flag.length; i--, j++) {
            flag[i][j]--;
        }
    }
    
    public List<String[]> solveNQueens(int n) {
        int[] queens = new int[n];
        int[][] flag = new int[n][n];
        //int sum = 0;
        List<String[]> resList = new ArrayList<String[]>();
        
        for (int i = 0; i < n; i++) {
            queens[i] = -1;
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                flag[i][j] = 0;
            }
        }
        
        int index = 0;
        
        while (true) {
            int preQueen = queens[index];
            
            if (preQueen >= 0) {
                unSetRow(index, preQueen, flag);
            }
            
            int newQueen = preQueen+1;
            
            for (; newQueen < n; newQueen++) {
                if (flag[index][newQueen] == 0) {
                    queens[index] = newQueen;
                    setRow(index, newQueen, flag);
                    break;
                }
            }
            
            if (index == 0 
                    && newQueen == n) {
                break;
            } else if (newQueen == n) {
                queens[index] = -1;
                index--;
            } else {
                index++;
                
                if (index == n) {
                    index--;
                    //sum++;
                    resList.add(queensToString(queens));
                }
            }
        }
        
        //System.out.println(sum);
        
        return resList;
    }
    
    public static void main(String[] args) {
        NQueens1 test = new NQueens1();
        
        test.solveNQueens(4);
    }
}

(原文时间2015-4-9 )