《算法之美》---DFS--n皇后

/** * 请设计一种算法，解决著名的n皇后问题。这里的n皇后问题指在一个n*n的棋盘上放置n个棋子， * 使得每行每列和每条对角线上都只有一个棋子，求其摆放的方法数。 给定一个int n，请返回方法数，保证n小于等于15 */
public class Dfs_4n皇后问题 {
  static int n;
  static int cnt;

  static int[] rec;

  public static void main(String[] args) {
    n = 4;
    rec = new int[4];
    dfs(0);
    System.out.println(cnt);
  }

  /** * * @param row 当前正在处理的行 */
  private static void dfs(int row) {
    if (row == n) {
      cnt++;
      return;
    }
    //依次尝试在某列上放一个皇后
    for (int col = 0; col < n; col++) {
      boolean ok = true;
      //检验这个皇后是否和之前已经放置的皇后有冲突
      for (int i = 0; i < row; i++) {
        if (rec[i] == col || i + rec[i] == row + col || rec[i] - i == col - row) {
          ok = false;
          break;
        }
      }
      /*=======这里可以认为是剪枝=======*/
      //这一行的这一列可以放
      if (ok) {
        rec[row] = col; //标记
        dfs(row + 1); //继续找下一行
        // rec[row]=0; //恢复原状，这种解法这里是否恢复状态都行，为什么？
      }
    }
  }

}

leetcode–面试题 08.12. 八皇后

class Solution {
     List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        int[] rec = new int[n + 1];
        dfs(rec, 1);
        return res;
    }



    private void dfs(int[] rec, int row) {
        if (row==rec.length){
            List<String> strings = new ArrayList<>();

            for (int i = 1; i < rec.length; i++) {
                StringBuilder stringBuilder = new StringBuilder();
                for (int j = 1; j < rec.length-1; j++) {
                    stringBuilder.append('.');
                }
                String string = stringBuilder.toString();
                String a = string.substring(0,rec[i]-1) + "Q" + string.substring(rec[i]-1);
                strings.add(a);
            }
            res.add(strings);
            return;
        }
        for (int i = 1; i < rec.length; i++) {
            if (check(rec, row, i)) {
                rec[row] = i;
                dfs(rec, row + 1);
// rec[row] = 0;
            }
        }


    }

    private boolean check(int[] rec, int row, int i) {

        for (int j = 1; j < row; j++) {
            if (rec[j] == i) {
                return false;
            }
            if (j + rec[j] == row + i) {
                return false;
            }
            if (j - rec[j] == row - i) {
                return false;
            }
        }

        return true;
    }
}