本人已完成这个作业,有需要答案,请联系本人微信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)
发表评论