52. N-Queens II(待改进)
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
image
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
My Solution:
import copy
class Solution:
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
result = []
board = [[0 * m for m in range(n)] for m in range(n)]
row = 0
self.get_board(n, row, result, board)
return len(result)
def get_board(self, n, row, result, board):
if row >= n:
result.append(board)
return
for column in range(n):
if board[row][column] == 0:
board, temp_board = self.new_board(n, row, column, board)
self.get_board(n, row+1, result, board)
board = temp_board.copy()
def new_board(self, n, x, y, board):
temp_board = copy.deepcopy(board)
# 方向数组，对于8个方向
board[x][y] = 'Q'
dx = [0, 0, -1, 1, -1, 1, -1, 1] # 上 下 左 右 左上 右上 左下 右下
dy = [-1, 1, 0, 0, -1, -1, 1, 1] # 上 下 左 右 左上 右上 左下 右下
for i in range(8):
for j in range(1, n):
new_x = x + dx[i] * j
new_y = y + dy[i] * j
if (new_x >= 0 and new_x < n) and (new_y >= 0 and new_y < n):
board[new_x][new_y] = '.'
return board, temp_board
