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

如本文章标有价格,需议价或其它事情商议请加微信pythonxia

本人已完成数独作业,有需要请和本人联系,微信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代做
scratch

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

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