[LintCode 33] N Queens (N 皇后问题)

Author Avatar
DataLeoZ 6月 18, 2019
  • 在其它设备中阅读本文章

Description

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

n皇后问题是将n个皇后放置在n*n的棋盘上,皇后彼此之间不能相互攻击。
给定一个整数n,返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局,其中“Q”和“.”分别表示一个女王和一个空位置。

https://www.lintcode.com/problem/n-queens/description

Example:

<!-- Input:4 -->
<!-- Output: -->
[
  // Solution 1
  [".Q..",
   "...Q",
   "Q...",
   "..Q."
  ],
  // Solution 2
  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."
  ]
]

Note

皇后间不能相互攻击的条件是:

  1. 任何一行/列只能有一个皇后
  2. 任何一个斜边(对角线,45度斜边

对于第一种情况,增加取值时直接判定对应横/纵坐标是否被占用即可,
X Q X X
X X X Q
Q X X X
X X Q X
由[1, 3, 0, 2]表示,求(0, 1, 2, 3)满足条件的全排列,该表示方式决定不会有行冲突

对于第二种情况,需要检查列冲突(对角线)冲突,在对角线上:横/纵 坐标之 和/差 相等。

Update Review

Code

Python3 on LintCode
PS: cols[i]中存储的是第i行中应该在第几列摆放皇后

class Solution:
    """
    @param: n: The number of queens
    @return: All distinct solutions
    """
    def solveNQueens(self, n):
        results = []
        cols = []
        self.search(n, cols, results)
        return results
    #DFS Recursion
    def search(self, n, cols, results):
        row = len(cols)
        if row == n:
            results.append(self.draw_result(cols))
        for col in range(n):
            if self.is_valid(col, cols, row):
                cols.append(col)
                self.search(n, cols, results)
                cols.pop()
    #Judge whether the append mark is valid or not
    def is_valid(self, col, cols, row):
        for x, y in enumerate(cols):
            if y == col:
                return False
            if x + y == col + row or x - y == row - col:
                return False
        return True
    #add one success permutation
    def draw_result(self, cols):
        print(cols)
        new_result = []
        n = len(cols)
        for i in range(n):
            row = []
            for j in range(n):
                if cols[j] == i:
                    row.append('Q')
                else:
                    row.append('.')
            new_result.append(''.join(row))
        return new_result

Ref Code

本参考程序来自九章算法,由 @令狐冲 提供

用 visited 来标记 列号,横纵坐标之和,横纵坐标之差 有没有被用过

class Solution:
    """
    @param: n: The number of queens
    @return: All distinct solutions
    """
    def solveNQueens(self, n):
        boards = []
        visited = {
            'col': set(),
            'sum': set(),
            'diff': set(),
        }
        self.dfs(n, [], visited, boards)
        return boards

    def dfs(self, n, permutation, visited, boards):
        if n == len(permutation):
            boards.append(self.draw(permutation))
            return

        row = len(permutation)
        for col in range(n):
            if not self.is_valid(permutation, visited, col):
                continue
            permutation.append(col)
            visited['col'].add(col)
            visited['sum'].add(row + col)
            visited['diff'].add(row - col)
            self.dfs(n, permutation, visited, boards)
            visited['col'].remove(col)
            visited['sum'].remove(row + col)
            visited['diff'].remove(row - col)
            permutation.pop()

    # O(1)
    def is_valid(self, permutation, visited, col):
        row = len(permutation)
        if col in visited['col']:
            return False
        if row + col in visited['sum']:
            return False
        if row - col in visited['diff']:
            return False
        return True

    def draw(self, permutation):
        board = []
        n = len(permutation)
        for col in permutation:
            row_string = ''.join(['Q' if c == col else '.' for c in range(n)])
            board.append(row_string)
        return board

This blog is under a CC BY-NC-SA 3.0 Unported License
本文使用 CC BY-NC-SA 3.0 中国 协议许可
署名-非商业性使用-相同方式共享(BY-NC-SA):使用者可以对本创作进行共享、演绎,但使用时须进行署名(同时标明是否(对原始作品)作了修改),且不得运用于商业目的,采用本创作的内容必须同样采用本协议进行授权。详情请参考协议细则。

本文链接:https://dataleoz.com/lintcode-n-queens/