本人已完成数独作业，有需要请和本人联系，微信scratch8。
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 3×3 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 3×3 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
本作业还有更多问题，在此不再列举出。
发表评论