Homework 15: The Holy Queens Problem神圣皇后问题(类八皇后问题)美国留学生作业assignment代作

Homework 15: The Holy Queens Problem神圣皇后问题(类八皇后问题)美国留学生作业assignment代作

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

李兴球的博客是Python创意编程原创博客