Homework 14: Sudoku数独求解问题_美国留学生作业assignment代做

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

本人已完成数独作业,有需要请和本人联系,微信pythonxia。

Test Format

There are 6 questions, but not all of them require you to write code:

  • Question 1 asks you to complete the code for propagating a single cell.
  • Question 2 asks you to write the code to propagate all cells.
  • For Question 3, you just need to copy your solution to Question 2 in another place.
  • Question 4 asks you to implement a helper function that detects elements that occur in only one of a list of sets.
  • Question 5 asks you to implement the where can it go heuristic.
  • Question 6 simply checks that your code is efficient; you don’t need to write any code.

There are a total of 70 points.

Let us write a Sudoku solver. We want to get as input a Sudoku with some cells filled with values, and we want to get as output a solution, if one exists, and otherwise a notice that the input Sudoku puzzle has no solutions.

You will wonder, why spend so much time on Sudoku?

For two reasons.

First, the way we go about solving Sudoku is prototypical of a very large number of problems in computer science. In these problems, the solution is attained through a mix of search (we attempt to fill a square with a number and see if it works out), and constraint propagation (if we fill a square with, say, a 1, then there can be no 1’s in the same row, column, and 3×3 square).

Second, and related, the way we go about solving Sudoku puzzles is closely related to how SAT solvers work. So closely related, in fact, that while we describe for you how a Sudoku solver works, you will have to write a SAT solver as exercise.

Sudoku representation

First, let us do some grunt work and define a representation for a Sudoku problem.

One initial idea would be to represent a Sudoku problem via a 9×99×9 matrix, where each entry can be either a digit from 1 to 9, or 0 to signify “blank”. This would work in some sense, but it would not be a very useful representation. If you have solved Sudoku by hand (and if you have not, please go and solve a couple; it will teach you a lot about what we need to do), you will know that the following strategy works:

Repeat:

  • Look at all blank spaces. Can you find one where only one digit fits? If so, write the digit there.
  • If you cannot find any blank space as above, try to find one where only a couple or so digits can fit. Try putting in one of those digits, and see if you can solve the puzzle with that choice. If not, backtrack, and try another digit.

Thus, it will be very useful to us to remember not only the known digits, but also, which digits can fit into any blank space. Hence, we represent a Sudoku problem via a 9×99×9 matrix of sets: each set contains the digits that can fit in a given space. Of course, a known digit is just a set containing only one element. We will solve a Sudoku problem by progressively “shrinking” these sets of possibilities, until they all contain exactly one element.

Let us write some code that enables us to define a Sudoku problem, and display it for us; this will be very useful both for our fun and for debugging.

First, though, let’s write a tiny helper function that returns the only element from a singleton set.

def getel(s):
    """Returns the unique element in a singleton set (or list)."""
    assert len(s) == 1
    return list(s)[0]

import json

class Sudoku(object):

    def __init__(self, elements):
        """Elements can be one of:
        Case 1: a list of 9 strings of length 9 each.
        Each string represents a row of the initial Sudoku puzzle,
        with either a digit 1..9 in it, or with a blank or _ to signify
        a blank cell.
        Case 2: an instance of Sudoku.  In that case, we initialize an
        object to be equal (a copy) of the one in elements.
        Case 3: a list of list of sets, used to initialize the problem."""
        if isinstance(elements, Sudoku):
            # We let self.m consist of copies of each set in elements.m
            self.m = [[x.copy() for x in row] for row in elements.m]
        else:
            assert len(elements) == 9
            for s in elements:
                assert len(s) == 9
            # We let self.m be our Sudoku problem, a 9x9 matrix of sets.
            self.m = []
            for s in elements:
                row = []
                for c in s:
                    if isinstance(c, str):
                        if c.isdigit():
                            row.append({int(c)})
                        else:
                            row.append({1, 2, 3, 4, 5, 6, 7, 8, 9})
                    else:
                        assert isinstance(c, set)
                        row.append(c)
                self.m.append(row)


    def show(self, details=False):
        """Prints out the Sudoku matrix.  If details=False, we print out
        the digits only for cells that have singleton sets (where only
        one digit can fit).  If details=True, for each cell, we display the
        sets associated with the cell."""
        if details:
            print("+-----------------------------+-----------------------------+-----------------------------+")
            for i in range(9):
                r = '|'
                for j in range(9):
                    # We represent the set {2, 3, 5} via _23_5____
                    s = ''
                    for k in range(1, 10):
                        s += str(k) if k in self.m[i][j] else '_'
                    r += s
                    r += '|' if (j + 1) % 3 == 0 else ' '
                print(r)
                if (i + 1) % 3 == 0:
                    print("+-----------------------------+-----------------------------+-----------------------------+")
        else:
            print("+---+---+---+")
            for i in range(9):
                r = '|'
                for j in range(9):
                    if len(self.m[i][j]) == 1:
                        r += str(getel(self.m[i][j]))
                    else:
                        r += "."
                    if (j + 1) % 3 == 0:
                        r += "|"
                print(r)
                if (i + 1) % 3 == 0:
                    print("+---+---+---+")


    def to_string(self):
        """This method is useful for producing a representation that
        can be used in testing."""
        as_lists = [[list(self.m[i][j]) for j in range(9)] for i in range(9)]
        return json.dumps(as_lists)


    @staticmethod
    def from_string(s):
        """Inverse of above."""
        as_lists = json.loads(s)
        as_sets = [[set(el) for el in row] for row in as_lists]
        return Sudoku(as_sets)


    def __eq__(self, other):
        """Useful for testing."""
        return self.m == other.m

Let us input a problem (the Sudoku example found on this Wikipedia page) and check that our serialization and deserialization works.

# Let us ensure that nose is installed.
try:
    from nose.tools import assert_equal, assert_true
    from nose.tools import assert_false, assert_almost_equal
except:
    !pip install nose
    from nose.tools import assert_equal, assert_true
    from nose.tools import assert_false, assert_almost_equal

Collecting nose
Downloading https://files.pythonhosted.org/packages/15/d8/dd071918c040f50fa1cf80da16423af51ff8ce4a0f2399b7bf8de45ac3d9/nose-1.3.7-py3-none-any.whl (154kB)
|████████████████████████████████| 163kB 5.1MB/s eta 0:00:01
Installing collected packages: nose
Successfully installed nose-1.3.7

from nose.tools import assert_equal

sd = Sudoku([
    '53__7____',
    '6__195___',
    '_98____6_',
    '8___6___3',
    '4__8_3__1',
    '7___2___6',
    '_6____28_',
    '___419__5',
    '____8__79'
])
sd.show()
sd.show(details=True)
s = sd.to_string()
sdd = Sudoku.from_string(s)
sdd.show(details=True)
assert_equal(sd, sdd)

+---+---+---+
|53.|.7.|...|
|6..|195|...|
|.98|...|.6.|
+---+---+---+
|8..|.6.|..3|
|4..|8.3|..1|
|7..|.2.|..6|
+---+---+---+
|.6.|...|28.|
|...|419|..5|
|...|.8.|.79|
+---+---+---+
+-----------------------------+-----------------------------+-----------------------------+
|____5____ __3______ 123456789|123456789 ______7__ 123456789|123456789 123456789 123456789|
|_____6___ 123456789 123456789|1________ ________9 ____5____|123456789 123456789 123456789|
|123456789 ________9 _______8_|123456789 123456789 123456789|123456789 _____6___ 123456789|
+-----------------------------+-----------------------------+-----------------------------+
|_______8_ 123456789 123456789|123456789 _____6___ 123456789|123456789 123456789 __3______|
|___4_____ 123456789 123456789|_______8_ 123456789 __3______|123456789 123456789 1________|
|______7__ 123456789 123456789|123456789 _2_______ 123456789|123456789 123456789 _____6___|
+-----------------------------+-----------------------------+-----------------------------+
|123456789 _____6___ 123456789|123456789 123456789 123456789|_2_______ _______8_ 123456789|
|123456789 123456789 123456789|___4_____ 1________ ________9|123456789 123456789 ____5____|
|123456789 123456789 123456789|123456789 _______8_ 123456789|123456789 ______7__ ________9|
+-----------------------------+-----------------------------+-----------------------------+
+-----------------------------+-----------------------------+-----------------------------+
|____5____ __3______ 123456789|123456789 ______7__ 123456789|123456789 123456789 123456789|
|_____6___ 123456789 123456789|1________ ________9 ____5____|123456789 123456789 123456789|
|123456789 ________9 _______8_|123456789 123456789 123456789|123456789 _____6___ 123456789|
+-----------------------------+-----------------------------+-----------------------------+
|_______8_ 123456789 123456789|123456789 _____6___ 123456789|123456789 123456789 __3______|
|___4_____ 123456789 123456789|_______8_ 123456789 __3______|123456789 123456789 1________|
|______7__ 123456789 123456789|123456789 _2_______ 123456789|123456789 123456789 _____6___|
+-----------------------------+-----------------------------+-----------------------------+
|123456789 _____6___ 123456789|123456789 123456789 123456789|_2_______ _______8_ 123456789|
|123456789 123456789 123456789|___4_____ 1________ ________9|123456789 123456789 ____5____|
|123456789 123456789 123456789|123456789 _______8_ 123456789|123456789 ______7__ ________9|
+-----------------------------+-----------------------------+-----------------------------+

Constraint propagation

When the set in a Sudoku cell contains only one element, this means that the digit at that cell is known. We can then propagate the knowledge, ruling out that digit in the same row, in the same column, and in the same 3×3 cell.

We first write a method that propagates the constraint from a single cell. The method will return the list of newly-determined cells, that is, the list of cells who also now (but not before) are associated with a 1-element set. This is useful, because we can then propagate the constraints from those cells in turn. Further, if an empty set is ever generated, we raise the exception Unsolvable: this means that there is no solution to the proposed Sudoku puzzle.

We don’t want to steal all the fun from you; thus, we will give you the main pieces of the implemenetation, but we ask you to fill in the blanks. We provide tests so you can catch any errors right away.

Question 1: Propagating a single cell

 

class Unsolvable(Exception):
    pass


def sudoku_ruleout(self, i, j, x):
    """The input consists in a cell (i, j), and a value x.
    The function removes x from the set self.m[i][j] at the cell, if present, and:
    - if the result is empty, raises Unsolvable;
    - if the cell used to be a non-singleton cell and is now a singleton
      cell, then returns the set {(i, j)};
    - otherwise, returns the empty set."""
    c = self.m[i][j]
    n = len(c)
    c.discard(x)
    self.m[i][j] = c
    if len(c) == 0:
        raise Unsolvable()
    return {(i, j)} if 1 == len(c) < n else set()

Sudoku.ruleout = sudoku_ruleout

The method propagate_cell(ij) takes as input a pair ij of coordinates. If the set of possible digits self.m[i][j] for cell i,j contains more than one digit, then no propagation is done. If the set contains a single digit x, then we:

Remove x from the sets of all other cells on the same row, column, and 3x3 block.
Collect all the newly singleton cells that are formed, due to the digit x being removed, and we return them as a set.
We give you an implementation that takes care of removing x from the same row, and we ask you to complete the implementation to take care of the column and 3x3 block as well.

### Exercise: define cell propagation

def sudoku_propagate_cell(self, ij):
    """Propagates the singleton value at cell (i, j), returning the list
    of newly-singleton cells."""
    i, j = ij
    if len(self.m[i][j]) > 1:
        # Nothing to propagate from cell (i,j).
        return set()
    # We keep track of the newly-singleton cells.
    newly_singleton = set()
    x = getel(self.m[i][j]) # Value at (i, j).
    # Same row.
    for jj in range(9):
        if jj != j: # Do not propagate to the element itself.
            newly_singleton.update(self.ruleout(i, jj, x))
    # Same column.
    ### YOUR CODE HERE
    for ii in range(9):
        if ii != i: # Do not propagate to the element itself.
            newly_singleton.update(self.ruleout(ii, j, x))
    # Same block of 3x3 cells.
    ### YOUR CODE HERE
    # Returns the list of newly-singleton cells.
    return newly_singleton

Sudoku.propagate_cell = sudoku_propagate_cell

本作业还有更多问题,在此不再列举出。

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

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

Python游戏海龟模块教程说明书与案例若干免费发放

爱的纪念_Python创意情景动画源代码解析

少儿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少儿编程免费下载集合

夜幕下的霓虹

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

李兴球博客 风火轮编程主页
error: Content is protected !!