本人已完成这个作业，有需要答案，请联系本人微信scratch8.
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)
def read_board(string_list):
rows = len(string_list)
cols = len(string_list[0])
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...",
"......"
]
show_board(read_board(bs))
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.
### YOUR CODE HERE
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
### YOUR CODE HERE
## 5 points. Propagation.
# Propagating this
bs = [
"......",
".Q.##.",
"...##.",
"..Q...",
"......"
]
# should give this:
bs_prop = [
"***...",
"*Q*##.",
"***##.",
"**Q***",
".****."]
hq = HolyQueens(read_board(bs))
hq.propagate()
hq.show()
assert (hq.board == read_board(bs_prop)).all()
## 5 points. Propagation.
# Propagating this
bs = [
".....Q",
"..Q##.",
"...##.",
".#....",
".Q...."
]
# should give this:
bs_prop = [
"*****Q",
"**Q##*",
".**##*",
"*#*..*",
"*Q****"]
hq = HolyQueens(read_board(bs))
hq.propagate()
hq.show()
assert (hq.board == read_board(bs_prop)).all()
bs = [
"......",
"...##.",
"...##.",
"......",
"......"
]
hq = HolyQueens(read_board(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 = [
"......",
"...##.",
"...##.",
"......",
"......"
]
hq = HolyQueens(read_board(bs))
r = hq.search(6)
assert r is not None
# You should get a solution with 6 non-interfering queens.
show_board(r)
