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

Python海龟宝典含200多个原创的用turtle模块制作的创意程序,原名《Python趣味编程200例》。准备参加全国创意编程与智能设计大赛的同学们可以用来做参考。

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

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)
本站所有作品,教程等皆为原创,版权所有。只供个人及单位内部研究使用,对外展示或传播必需经本站同意,且注明来自本站。培训机构等用本站资源培训学生,需经本站授权。一旦付款,表示同意本站知识付费原则:数字商品,不支持退款。亦可直接向微信号scratch8付款购买。入住QQ群:225792826 和爱好者共同交流,并且能下载免费提供的Python资源(需提供真实姓名才可入群)
李兴球的博客_Python创意编程技术前沿_pygame » Homework 15: The Holy Queens Problem神圣皇后问题(类八皇后问题)美国留学生作业assignment代作

李兴球Python微信公众号文章列表

Python编程家长会花絮_萍乡中小学Python家长会现场

火星路上等着你_少儿从小学什么最好呢?

国家大力整顿教育培训机构,Scratch或Python少儿编程还有得教吗?

鸿蒙系统支持Python开发_可视化编程特别兴趣小组

Scratch作品转Python作品_小猴接桃

python海龟数据可视化。第七次全国人口普查历年数据图表

你的孩子Python编程学到哪个阶段了?给孩子报编程的家长,务必仔细一读。

五一神女来对话,看看她们聊什么?赠Python教案等。

五一快乐有大礼,告诉大家我是如何上Python课的。

Python名堂多,趣味到处有,劈开机械手,帧帧是图片。速算达人之猫狮大战正在进行。 逐字动画不独享,自动生成皆有它。2行代码自动生成字幕gif动画。 Python之潮来临,我在安源区教师科技创新能力的Python讲座

小心你的Python程序,它会是你的一面镜子。小方块闯迷宫.py源代码简析。送Scratch算法集。?

铃儿响钉铛_音效怎能忘_Python配音之Pygame混音器

人面桃花相映红_winsound模块简介

《Python昨晚我想你了》_开源的游戏海龟模块实例案例浅析

《八猫联动初体验》_来自游戏海龟模块的问候

喜爱春天的人儿啊 心地纯洁的人_Python逐行像素显示

旋转之三叶炫彩扇_蟒蛇与海龟的表演

彩虹欢迎字幕_三模合体滚图形

《Python海龟宝典》简介

100%错误的算法还在用,明明没有错别字,说我有11个错别字

奇怪的Python代码,谁能帮我解释一下??

人造地球系统让人类文明充满整个宇宙之Python32768版

深夜,是什么把你的大脑搞成一团浆糊!再谈少儿编程!

5线城市萍乡的少儿Python寒假班学的是什么内容?

关于纯少儿编程课程进化的自然选择

Python海龟画图经典作品_国庆中秋双重喜庆源代码免费下载

海龟为什么要自杀!turtle制作游戏秘籍之一

朋友,你是否知道我在仰望着你_Python神笔马良案例集

酷酷的爆炸效果_Python海龟画图不仅仅是画图

虫子满屏爬_三bug多线程示例程序浅析 少儿Python视频课程A级简介

给的gif图片加文字水印_拆帧与合帧(免费下载180个Python创意源码

用Python制作酷炫图形之如意金箍棒_颜色增加模块应用

简单的用Python做酷炫图形与动画

sb3转exe,sb3素材提取器,编程小子apk, 未公开的pygame游戏集/scratch/python少儿编程免费下载集合

夜幕下的霓虹

学本领,探索更大的世界!

李兴球博客 风火轮编程主页