# Homework 15: The Holy Queens Problem神圣皇后问题(类八皇后问题)美国留学生作业assignment代作 ## 如本文章标有价格,需议价或其它事情商议请加微信pythonxia

A chess queen can strike along the row, column, and the two diagonals. The classical 𝑛-queens problem consists in placing 𝑛 queens on the chess board, so that no queen can eat another queen. 国际像棋上的皇后能攻击同行，同列，同斜线方向上的其它棋子。

We will study here the holy queen problem: the chessboard can have holes, and in fact, can have an arbitrary shape. The ability of a queen to move and attack is limited by the holes, and in general by the borders of the board: a queen cannot “jump” across a hole. Your goal is to check whether you can place 𝑛 queens on a given board, which may contain holes.

The board
For a board, we will use a Numpy representation as a matrix, with the following conventions for the content of each square:

0: the cell is available for a queen.
1: a queen is in the cell.
2: the cell is under attack from some queen (and thus not available).
3: the cell contains a wall/hole, and a queen cannot traverse it.
We provide for you here a function show_board that visualizes a board, using a Q for a queen, a dot for an empty location, a # for a hole or wall, and a * for a cell under attack.

```QUEEN = 1
EMPTY = 0
FORBIDDEN = 2
WALL = 3

def show_board(board):
rows, cols = board.shape
for r in range(rows):
s = ""
for c in range(cols):
if board[r, c] == QUEEN:
s += "Q"
elif board[r, c] == FORBIDDEN:
s += "*"
elif board[r, c] == WALL:
s += "#"
elif board[r, c] == EMPTY:
s += "."
else:
s += "?"
print(s)

import numpy as np

board=np.array([
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 3, 3, 0],
[0, 0, 0, 3, 3, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0]
])
show_board(board)

rows = len(string_list)
cols = len(string_list)
board = np.zeros((rows, cols))
for r, row in enumerate(string_list):
assert len(row) == cols
for c, s in enumerate(row):
if s == "Q":
board[r, c] = QUEEN
elif s == "#":
board[r, c] = WALL
elif s == "*":
board[r, c] = FORBIDDEN
return board

bs = [
"......",
".Q.##.",
"...##.",
"..Q...",
"......"
]
```

## Question 1

Here is the class `HolyQueens`. You must define two methods:

The method `propagate` propagates the constraints, marking with `FORBIDDEN` all the locations that can be reached by the queens on the board.

The method `search` searches for a solution with a given number of queens. If a solution is found, it returns the board. If no solution is found, it returns `None`. The method `search` should implement the propagate-guess-recur framework: if not enough queens are present on the board, it first propagates the constraints from the current queens if any, then it guesses the position for a new queen, and then it recurs, looking for a solution in which one fewer queen needs to be placed.

We advise you to implement `propagate` first, and then `search`.

```class HolyQueens(object):

def __init__(self, board):
self.board = board
self.num_rows, self.num_cols = self.board.shape
# Current number of queens in the board.
self.num_queens = np.sum(self.board == QUEEN)

def show(self):
show_board(self.board)

def propagate(self):
"""Propagates the information on the board, marking with 2 the
positions where a queen cannot be."""
# The solution can be written concisely in about 20 lines of code,
# but if you brute force it, it might be quite long.

def search(self, total_num_queens):
"""Searches for a solution, starting from the given board,
which contains exactly num_queens.  It returns the board,
if such a solution is found, or None, if none could be found
after exhaustive search."""
pass

## 5 points. Propagation.

# Propagating this
bs = [
"......",
".Q.##.",
"...##.",
"..Q...",
"......"
]
# should give this:
bs_prop = [
"***...",
"*Q*##.",
"***##.",
"**Q***",
".****."]

hq.propagate()
hq.show()

## 5 points. Propagation.

# Propagating this
bs = [
".....Q",
"..Q##.",
"...##.",
".#....",
".Q...."
]
# should give this:
bs_prop = [
"*****Q",
"**Q##*",
".**##*",
"*#*..*",
"*Q****"]

hq.propagate()
hq.show()

bs = [
"......",
"...##.",
"...##.",
"......",
"......"
]
r = hq.search(4)
assert r is not None
# You should get a solution with 4 non-interfering queens.
show_board(r)

## 5 points: tests for search function

bs = [
"......",
"...##.",
"...##.",
"......",
"......"
] 