算法:N皇后二

  • 时间:
  • 浏览:
  • 来源:互联网

题目:
leetcode 52题。
在 n×n 的国际象棋棋盘上,放置n个皇后。有几种方法,可以使得n个皇后不能互相攻击。
在这里插入图片描述在国际象棋中,皇后可以如图的4个方向。

解法:
回溯法。
遍历n,
定义一个行的数组 columns,用于保存已有皇后的行
定义一个左斜线的数组 left_line,用于保存已有皇后的左斜线
定义一个右斜线的数组 right_line,用于保存已有皇后的右斜线

对于一列中的每一个数值i,判断i的行,左斜线,右斜线是否已存在上述3个数组中。
如果存在,则继续。
否则,将其存入对应的数组。
直到遍历完所有的列。
此时,返回1.
递归判断所有的行。

代码

class Solution {
    Set<Integer> columns = new HashSet<Integer>();   // 列
    Set<Integer> left_line = new HashSet<Integer>(); // 左斜线
    Set<Integer> right_line = new HashSet<Integer>();// 右斜线
    public int totalNQueens(int n) {
        int res = backtrack(n,0);
        return res;
    }

    public int backtrack(int n,int row) {
        if (row==n) {
            return 1;
        } else {
            int count=0;
            for (int i = 0; i < n; i++) {
                if (columns.contains(i))
                    continue;
                if (left_line.contains(row - i))
                    continue;
                if (right_line.contains(row + i))
                    continue;
                columns.add(i);
                left_line.add(row - i);
                right_line.add(row + i);
                count += backtrack(n, row + 1);
                columns.remove(i);
                left_line.remove(row - i);
                right_line.remove(row + i);
            }
            return count;
        }
    }
}

本文链接http://element-ui.cn/article/show-218949.aspx