Q4,5,6

Question

Q4,5,6

Swapnil · Accepted Answer

x/.ipynb_checkpoints/Final Notebook-checkpoint.ipynb{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\rightarrow$Run All).
",
    "
",
    "Make sure you fill in any place that says `YOUR CODE HERE` or "YOUR ANSWER HERE", as well as your name and collaborators below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = ""
",
    "COLLABORATORS = """
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 12: Sudoku
",
    "
",
    "Copyright Luca de Alfaro, 2019-20. License: CC-BY-NC-ND."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Submission
",
    "
",
    "Please submit to this Google Form.
",
    "
",
    "Deadline: Tuesday December 8, 11pm (check on Canvas for updated information)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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 3x3 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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 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×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×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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, though, let's write a tiny helper function that returns the only element from a singleton set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getel(s):
",
    "    assert len(s) == 1
",
    "    return list(s)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json
",
    "class Sudoku(object):
",
    "    def __init__(self, elements):
",
    "        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):
",
    "        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):
",
    "        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):
",
    "        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):
",
    "        return self.m == other.m
"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+---+---+---+
",
      "|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|
",
      "+-----------------------------+-----------------------------+-----------------------------+
"
     ]
    }
   ],
   "source": [
    "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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "sd1 = Sudoku(sd)
",
    "assert_equal(sd, sd1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 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 3x3 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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "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)  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:
",
    "            newly_singleton.update(self.ruleout(ii, j, x))
",
    "    # Same block of 3x3 cells.
",
    "    # YOUR CODE HERE
",
    "    current_i, current_j = i // 3, j // 3
",
    "    current_i, current_j = 3*current_i + 1, 3*current_j + 1
",
    "    
",
    "    for di in range(-1, 2):
",
    "        for dj in range(-1, 2):
",
    "            ni, nj = current_i + di, current_j + dj
",
    "            if i != ni and j != nj:
",
    "                newly_singleton.update(self.ruleout(ni, nj, x))
",
    "    # Returns the list of newly-singleton cells.
",
    "    return newly_singleton
",
    "
",
    "Sudoku.propagate_cell = sudoku_propagate_cell"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|____5____ __3______ _2_______|_____6___ ______7__ _______8_|________9 12_4_____ _2_______|
",
      "|_____6___ ______7__ 12_4__7__|123______ ________9 ____5____|__3______ 12_4_____ _______8_|
",
      "|12_______ ________9 _______8_|__3______ ___4_____ 12_______|____5____ _____6___ ______7__|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|_______8_ ____5____ ________9|1_____7_9 _____6___ 1__4__7_9|___4_____ _2_______ __3______|
",
      "|___4_____ _2_______ _____6___|_______8_ ____5____ __3______|______7__ ________9 1________|
",
      "|______7__ 1________ __3______|________9 _2_______ ___4_____|_______8_ ____5____ _____6___|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|1_______9 _____6___ 1___5_7_9|____5_7_9 __3______ ______7_9|_2_______ _______8_ ___4_____|
",
      "|_2______9 _______8_ _2____7_9|___4_____ 1________ _2____7_9|_____6___ __3______ ____5____|
",
      "|__3______ ___4_____ _2345____|_2__56___ _______8_ _____6___|1________ ______7__ ________9|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "Good! It was unsolvable.
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|____5____ __3______ _2_______|_____6___ ______7__ _______8_|________9 12_4_____ _23______|
",
      "|_____6___ ______7__ 12_4__7__|123______ ________9 ____5____|__3______ 12_4_____ _______8_|
",
      "|12_______ ________9 _______8_|__3______ ___4_____ 12_______|____5____ _____6___ ______7__|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|_______8_ ____5____ ________9|1_____7_9 _____6___ 1__4__7_9|___4_____ _2_______ __3______|
",
      "|___4_____ _2_______ _____6___|_______8_ ____5____ __3______|______7__ ________9 1________|
",
      "|______7__ 1________ __3______|________9 _2_______ ___4_____|_______8_ ____5____ _____6___|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|1_______9 _____6___ 1___5_7_9|____5_7_9 __3______ ______7_9|_2_______ _______8_ ___4_____|
",
      "|_2______9 _______8_ _2____7_9|___4_____ 1________ _2____7_9|_____6___ __3______ ____5____|
",
      "|__3______ ___4_____ _2345____|_2__56___ _______8_ _____6___|1________ ______7__ ________9|
",
      "+-----------------------------+-----------------------------+-----------------------------+
"
     ]
    }
   ],
   "source": [
    "tsd = Sudoku.from_string('[[[5], [3], [2], [6], [7], [8], [9], [1, 2, 4], [2]], [[6], [7], [1, 2, 4, 7], [1, 2, 3], [9], [5], [3], [1, 2, 4], [8]], [[1, 2], [9], [8], [3], [4], [1, 2], [5], [6], [7]], [[8], [5], [9], [1, 9, 7], [6], [1, 4, 9, 7], [4], [2], [3]], [[4], [2], [6], [8], [5], [3], [7], [9], [1]], [[7], [1], [3], [9], [2], [4], [8], [5], [6]], [[1, 9], [6], [1, 5, 9, 7], [9, 5, 7], [3], [9, 7], [2], [8], [4]], [[9, 2], [8], [9, 2, 7], [4], [1], [9, 2, 7], [6], [3], [5]], [[3], [4], [2, 3, 4, 5], [2, 5, 6], [8], [6], [1], [7], [9]]]')
",
    "tsd.show(details=True)
",
    "try:
",
    "    tsd.propagate_cell((0, 2))
",
    "except Unsolvable:
",
    "    print("Good! It was unsolvable.")
",
    "else:
",
    "    raise Exception("Hey, it was unsolvable")
",
    "
",
    "tsd = Sudoku.from_string('[[[5], [3], [2], [6], [7], [8], [9], [1, 2, 4], [2, 3]], [[6], [7], [1, 2, 4, 7], [1, 2, 3], [9], [5], [3], [1, 2, 4], [8]], [[1, 2], [9], [8], [3], [4], [1, 2], [5], [6], [7]], [[8], [5], [9], [1, 9, 7], [6], [1, 4, 9, 7], [4], [2], [3]], [[4], [2], [6], [8], [5], [3], [7], [9], [1]], [[7], [1], [3], [9], [2], [4], [8], [5], [6]], [[1, 9], [6], [1, 5, 9, 7], [9, 5, 7], [3], [9, 7], [2], [8], [4]], [[9, 2], [8], [9, 2, 7], [4], [1], [9, 2, 7], [6], [3], [5]], [[3], [4], [2, 3, 4, 5], [2, 5, 6], [8], [6], [1], [7], [9]]]')
",
    "tsd.show(details=True)
",
    "assert_equal(tsd.propagate_cell((0, 2)), {(0, 8), (2, 0)})
"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Propagating all cells, once"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The simplest thing we can do is propagate each cell, once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sudoku_propagate_all_cells_once(self):
",
    "    for i in range(9):
",
    "        for j in range(9):
",
    "            self.propagate_cell((i, j))
",
    "
",
    "Sudoku.propagate_all_cells_once = sudoku_propagate_all_cells_once"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+---+---+---+
",
      "|53.|.7.|...|
",
      "|6..|195|...|
",
      "|.98|...|.6.|
",
      "+---+---+---+
",
      "|8..|.6.|..3|
",
      "|4..|8.3|..1|
",
      "|7..|.2.|..6|
",
      "+---+---+---+
",
      "|.6.|...|28.|
",
      "|...|419|..5|
",
      "|...|.8.|.79|
",
      "+---+---+---+
",
      "+---+---+---+
",
      "|53.|.7.|...|
",
      "|6..|195|...|
",
      "|.98|...|.6.|
",
      "+---+---+---+
",
      "|8..|.6.|..3|
",
      "|4..|853|..1|
",
      "|7..|.2.|..6|
",
      "+---+---+---+
",
      "|.6.|..7|284|
",
      "|...|419|.35|
",
      "|...|.8.|.79|
",
      "+---+---+---+
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|____5____ __3______ 12_4_____|_2___6___ ______7__ _2_4_6_8_|1__4___89 12_4____9 _2_4___8_|
",
      "|_____6___ _2_4__7__ _2_4__7__|1________ ________9 ____5____|__34__78_ _234_____ _2_4__78_|
",
      "|12_______ ________9 _______8_|_23______ __34_____ _2_4_____|1_345_7__ _____6___ _2_4__7__|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|_______8_ 12__5____ 12__5___9|____5_7_9 _____6___ 1__4__7__|___45_7_9 _2_45___9 __3______|
",
      "|___4_____ _2__5____ _2__56__9|_______8_ ____5____ __3______|____5_7_9 _2__5___9 1________|
",
      "|______7__ 1___5____ 1_3_5___9|____5___9 _2_______ 1__4_____|___45__89 ___45___9 _____6___|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|1_3_____9 _____6___ 1_345_7_9|__3_5_7__ __3_5____ ______7__|_2_______ _______8_ ___4_____|
",
      "|_23______ _2____78_ _23___7__|___4_____ 1________ ________9|__3__6___ __3______ ____5____|
",
      "|123______ 12_45____ 12345____|_23_56___ _______8_ _2___6___|1_34_6___ ______7__ ________9|
",
      "+-----------------------------+-----------------------------+-----------------------------+
"
     ]
    }
   ],
   "source": [
    "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.propagate_all_cells_once()
",
    "sd.show()
",
    "sd.show(details=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2: Propagating all cells, repeatedly
",
    "
",
    "This is a good beginning, but it's not quite enough. As we propagate the constraints, cells that did not use to be singletons may have become singletons. For eample, in the above example, the center cell has become known to be a 5: we need to make sure that also these singletons are propagated.
",
    "
",
    "This is why we have written propagate_cell so that it returns the set of newly-singleton cells.
",
    "We need now to write a method full_propagation that at the beginning starts with a set of to_propagate cells (if it is not specified, then we just take it to consist of all singleton cells). Then, it picks a cell from the to_propagate set, and propagates from it, adding any newly singleton cell to to_propagate. Once there are no more cells to be propagated, the method returns. If this sounds similar to graph reachability, it is ... because it is! It is once again the algorithmic pattern of keeping a list of work to be done, then iteratively picking an element from the list, doing it, possibly updating the list of work to be done with new work that has to be done as a result of what we just did, and continuing in this fashion until there is nothing left to do. We will let you write this function. The portion you have to write can be done in three lines of code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sudoku_full_propagation(self, to_propagate=None):
",
    "    if to_propagate is None:
",
    "        to_propagate = {(i, j) for i in range(9) for j in range(9)}
",
    "    # This code is the (A) code; will be referenced later.
",
    "    # YOUR CODE HERE
",
    "    for (i, j) in to_propagate:
",
    "        x = self.propagate_cell((i, j))
",
    "        sudoku_full_propagation(self, x)
",
    "
",
    "Sudoku.full_propagation = sudoku_full_propagation
"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|____5____ __3______ ___4_____|_____6___ ______7__ _______8_|________9 1________ _2_______|
",
      "|_____6___ ______7__ _2_______|1________ ________9 ____5____|__3______ ___4_____ _______8_|
",
      "|1________ ________9 _______8_|__3______ ___4_____ _2_______|____5____ _____6___ ______7__|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|_______8_ ____5____ ________9|______7__ _____6___ 1________|___4_____ _2_______ __3______|
",
      "|___4_____ _2_______ _____6___|_______8_ ____5____ __3______|______7__ ________9 1________|
",
      "|______7__ 1________ __3______|________9 _2_______ ___4_____|_______8_ ____5____ _____6___|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|________9 _____6___ 1________|____5____ __3______ ______7__|_2_______ _______8_ ___4_____|
",
      "|_2_______ _______8_ ______7__|___4_____ 1________ ________9|_____6___ __3______ ____5____|
",
      "|__3______ ___4_____ ____5____|_2_______ _______8_ _____6___|1________ ______7__ ________9|
",
      "+-----------------------------+-----------------------------+-----------------------------+
"
     ]
    }
   ],
   "source": [
    "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.full_propagation()
",
    "sd.show(details=True)
",
    "sdd = Sudoku.from_string('[[[5], [3], [4], [6], [7], [8], [9], [1], [2]], [[6], [7], [2], [1], [9], [5], [3], [4], [8]], [[1], [9], [8], [3], [4], [2], [5], [6], [7]], [[8], [5], [9], [7], [6], [1], [4], [2], [3]], [[4], [2], [6], [8], [5], [3], [7], [9], [1]], [[7], [1], [3], [9], [2], [4], [8], [5], [6]], [[9], [6], [1], [5], [3], [7], [2], [8], [4]], [[2], [8], [7], [4], [1], [9], [6], [3], [5]], [[3], [4], [5], [2], [8], [6], [1], [7], [9]]]')
",
    "assert_equal(sd, sdd)
"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Searching for a solution
",
    "
",
    "Many Sudoku problems can be solved entirely by constraint propagation.
",
    "They are designed to be so: they are designed to be relatively easy, so that humans can solve them while on a lounge chair at the beach -- I know this from personal experience!
",
    "
",
    "But it is by no means necessary that this is true. If we create more complex problems, or less determined problems, constraint propagation no longer suffices. As a simple example, let's just blank some cells in the previous problem, and run full propagation again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+---+---+---+
",
      "|53.|.7.|...|
",
      "|6..|.95|...|
",
      "|.98|...|.6.|
",
      "+---+---+---+
",
      "|8..|.6.|..3|
",
      "|4..|8.3|..1|
",
      "|7..|.2.|..6|
",
      "+---+---+---+
",
      "|.6.|...|28.|
",
      "|...|41.|..5|
",
      "|...|.8.|.79|
",
      "+---+---+---+
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|____5____ __3______ 12_4_____|12___6___ ______7__ 12___6_8_|___4___89 12_4_____ _2_____8_|
",
      "|_____6___ 1__4__7__ 12_4__7__|123______ ________9 ____5____|__34___8_ 12_4_____ _2____78_|
",
      "|12_______ ________9 _______8_|123______ ___4_____ 12_______|__3_5____ _____6___ _2____7__|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|_______8_ 1___5____ 1___5___9|1_____7_9 _____6___ 1__4__7_9|___45____ _2_45____ __3______|
",
      "|___4_____ _2_______ _____6___|_______8_ ____5____ __3______|______7__ ________9 1________|
",
      "|______7__ 1___5____ 1_3_5___9|1_______9 _2_______ 1__4____9|___45__8_ ___45____ _____6___|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|1_______9 _____6___ 1___5_7_9|____5_7_9 __3______ ______7_9|_2_______ _______8_ ___4_____|
",
      "|_2______9 ______78_ _2____7_9|___4_____ 1________ _2____7_9|_____6___ __3______ ____5____|
",
      "|_23______ ___45____ _2345____|_2__56___ _______8_ _2___6___|1________ ______7__ ________9|
",
      "+-----------------------------+-----------------------------+-----------------------------+
"
     ]
    }
   ],
   "source": [
    "sd = Sudoku([
",
    "    '53__7____',
",
    "    '6___95___',
",
    "    '_98____6_',
",
    "    '8___6___3',
",
    "    '4__8_3__1',
",
    "    '7___2___6',
",
    "    '_6____28_',
",
    "    '___41___5',
",
    "    '____8__79'
",
    "])
",
    "sd.show()
",
    "sd.full_propagation()
",
    "sd.show(details=True)
"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|____5____ __3______ 12_4_____|12___6___ ______7__ 12___6_8_|___4___89 12_4_____ _2_____8_|
",
      "|_____6___ 1__4__7__ 12_4__7__|123______ ________9 ____5____|__34___8_ 12_4_____ _2____78_|
",
      "|12_______ ________9 _______8_|123______ ___4_____ 12_______|__3_5____ _____6___ _2____7__|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|_______8_ 1___5____ 1___5___9|1_____7_9 _____6___ 1__4__7_9|___45____ _2_45____ __3______|
",
      "|___4_____ _2_______ _____6___|_______8_ ____5____ __3______|______7__ ________9 1________|
",
      "|______7__ 1___5____ 1_3_5___9|1_______9 _2_______ 1__4____9|___45__8_ ___45____ _____6___|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|1_______9 _____6___ 1___5_7_9|____5_7_9 __3______ ______7_9|_2_______ _______8_ ___4_____|
",
      "|_2______9 ______78_ _2____7_9|___4_____ 1________ _2____7_9|_____6___ __3______ ____5____|
",
      "|_23______ ___45____ _2345____|_2__56___ _______8_ _2___6___|1________ ______7__ ________9|
",
      "+-----------------------------+-----------------------------+-----------------------------+
"
     ]
    }
   ],
   "source": [
    "sd.show(details=True)
",
    "# Let's save this Sudoku for later.
",
    "sd_partially_solved = Sudoku(sd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What can we do when constraint propagation fails? The only thing we can do is make a guess. We can take one of the cells whose set contains multiple digits, such as cell (2, 0) (starting counting at 0, as in Python), which contains  {1,2} , and try one of the values, for instance  1 .
",
    "We can see whether assigning to the cell the singleton set  {1}  leads to the solution. If not, we try the value  {2}  instead. If the Sudoku problem has a solution, one of these two values must work.
",
    "
",
    "Classically, this way of searching for a solution has been called search with backtracking. The backtracking is because we can choose a value, say  1 , and then do a lot of work, propagating the new constraint, making further guesses, and so on and so forth. If that does not pan out, we must "backtrack" and return to our guess, choosing (in our example)  2  instead.
",
    "
",
    "Let us implement search with backtracking. What we need to do is something like this:
",
    "
",
    "search():
",
    "
",
    "- propagate constraints.
",
    "- if solved, hoorrayy!
",
    "- if impossible, raise Unsolvable()
",
    "- if not fully solved, pick a cell with multiple digits possible, and iteratively:
",
    "    - Assign one of the possible values to the cell.
",
    "    - Call search() with that value for the cell.
",
    "    - If Unsolvable is raised by the search() call, move on to the next value.
",
    "    - If all values returned Unsolvable (if we tried them all), then we raise Unsolvable.
",
    "
",
    "So we see that search() is a recursive function.
",
    "From the pseudo-code above, we see that it might be better to pick a cell with few values possible at step 4 above, so as to make our chances of success as good as possible. For instance, it is much better to choose a cell with set  {1,2}  than one with set  {1,3,5,6,7,9} , as the probability of success is  1/2  in the first case and  1/6  in the second case. Of course, it may be possible to come up with much better heuristics to guide our search, but this will have to do so far.
",
    "
",
    "One fine point with the search above is the following. So far, an object has a self.m matrix, which contains the status of the Sudoku solution. We cannot simply pass self.m recursively to search(), because in the course of the search and constraint propagation, self.m will be modified, and there is no easy way to keep track of these modifications. Rather, we will write search() as a method, and when we call it, we will:
",
    "
",
    "- First, create a copy of the current object via the Sudoku constructor, so we have a copy we can modify.
",
    "- Second, we assign one of the values to the cell, as above;
",
    "- Third, we will call the search() method of that object.
",
    "
",
    "Furthermore, when a solution is found, as in the hoorraay! above, we need to somehow return the solution. There are two ways of doing this: via standard returns, or by raising an exception."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sudoku_done(self):
",
    "    for i in range(9):
",
    "        for j in range(9):
",
    "            if len(self.m[i][j]) > 1:
",
    "                return False
",
    "    return True
",
    "
",
    "Sudoku.done = sudoku_done
",
    "
",
    "
",
    "def sudoku_search(self, new_cell=None):
",
    "    to_propagate = None if new_cell is None else {new_cell}
",
    "    self.full_propagation(to_propagate=to_propagate)
",
    "    if self.done():
",
    "        return self # We are a solution
",
    "    # We need to search.  Picks a cell with as few candidates as possible.
",
    "    candidates = [(len(self.m[i][j]), i, j)
",
    "                   for i in range(9) for j in range(9) if len(self.m[i][j]) > 1]
",
    "    _, i, j = min(candidates)
",
    "    values = self.m[i][j]
",
    "    # values contains the list of values we need to try for cell i, j.
",
    "    # print("Searching values", values, "for cell", i, j)
",
    "    for x in values:
",
    "        # print("Trying value", x)
",
    "        sd = Sudoku(self)
",
    "        sd.m[i][j] = {x}
",
    "        try:
",
    "            # If we find a solution, we return it.
",
    "            return sd.search(new_cell=(i, j))
",
    "        except Unsolvable:
",
    "            # Go to next value.
",
    "            pass
",
    "    # All values have been tried, apparently with no success.
",
    "    raise Unsolvable()
",
    "
",
    "Sudoku.search = sudoku_search
",
    "
",
    "
",
    "def sudoku_solve(self, do_print=True):
",
    "    try:
",
    "        r = self.search()
",
    "        if do_print:
",
    "            print("We found a solution:")
",
    "            r.show()
",
    "            return r
",
    "    except Unsolvable:
",
    "        if do_print:
",
    "            print("The problem has no solutions")
",
    "
",
    "Sudoku.solve = sudoku_solve
"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We found a solution:
",
      "+---+---+---+
",
      "|531|678|942|
",
      "|674|295|318|
",
      "|298|341|567|
",
      "+---+---+---+
",
      "|859|167|423|
",
      "|426|853|791|
",
      "|713|924|856|
",
      "+---+---+---+
",
      "|165|739|284|
",
      "|987|412|635|
",
      "|342|586|179|
",
      "+---+---+---+
"
     ]
    },
    {
     "data": {
      "text/plain": [
       ""
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sd = Sudoku([
",
    "    '53__7____',
",
    "    '6___95___',
",
    "    '_98____6_',
",
    "    '8___6___3',
",
    "    '4__8_3__1',
",
    "    '7___2___6',
",
    "    '_6____28_',
",
    "    '___41___5',
",
    "    '____8__79'
",
    "])
",
    "sd.solve()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The choice - constraint propagation - recursion paradigm.
",
    "
",
    "We have learned a general strategy for solving difficult problems. The strategy can be summarized thus: choice - constraint propagation - recursion.
",
    "
",
    "In the choice step, we make one guess from a set of possible guesses. If we want our search for a solution to be exhaustive, as in the above Sudoku example, we ensure that we try iteratively all choices from a set of choices chosen so that at least one of them must succeed. In the above example, we know that at least one of the digit values must be the true one, hence our search is exhaustive. In other cases, we can trade off exhaustiveness for efficiency, and we may try only a few choices, guided perhaps by an heuristic.
",
    "
",
    "The constraint propagation step propagates the consequences of the choice to the problem. Each choice thus gives rise to a new problem, which is a little bit simpler than the original one as some of the possible choices, that is, some of its complexity, has been removed. In the Sudoku case, the new problem has less indetermination, as at least one more of its cells has a known digit in it.
",
    "
",
    "The problems resulting from constraint propagation, while simpler, may not be solved yet. Hence, we recur, calling the solution procedure on them as well. As these problems are simpler (they contain fewer choices), eventually the recursion must reach a point where no more choice is possible, and whether constraint propagation should yield a completely defined problem, one of which it is possible to say whether it is solvable or not with a trivial test. This forms the base case for the recursion.
",
    "
",
    "This solution strategy applies very generally, to problems well beyond Sudoku."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: Digits must go somewhere
",
    "
",
    "If you have played Sudoku before, you might have found the way we solved Sudoku puzzles a bit odd. The constraint we encoded is:
",
    "
",
    "    - If a digit appears in a cell, it cannot appear anywhere else on the same row, column, or 3x3 block as the cell.
",
    "
",
    "This is a rule of Sudoku. Normally, however, we hear Sudoku described in a different way:
",
    "
",
    "    - Every column, row, and 3x3 block should contain all the 1...9 digits exactly once.
",
    "
",
    "There are two questions. The first is: are the two definitions equivalent? Well, no; the first definition does not say what the digits are (e.g., does not rule out 0). But in our Sudoku representation, we start by saying that every cell can contain only one of 1...9. If every row (or column, or 3x3 block) cannot contain more than one repetition of each digit, and if there are 9 digits and 9 cells in the row (or column, or block), then clearly every digit must appear exactly once in the row (or column, or block). So once the set of digits is specified, the two definitions are equivalent.
",
    "
",
    "The second question is: but still, what happens to the method we usually employ to solve Sudoku? I generally don't solve Sudoku puzzles by focusing on one cell at a time, and thinking: is it the case that this call can contain only one digit? This is the strategy employed by the solver above. But it is not the strategy I normally use. I generally solve Sudoku puzzles by looking at a block (or row, or column), and thinking: let's consider the digit  ?  ( 1≤?≤9 ). Where can it go in the block? And if I find that the digit can go in one block cell only, I write it there.
",
    "Does the solver work even without this "where can it go" strategy? And can we make it follow it?
",
    "
",
    "The solver works even without the "where can it go" strategy because it exaustively tries all possibilities. This means the solver works without the strategy; it does not say that the solver works well without the strategy.
",
    "
",
    "We can certainly implement the where can it go strategy, as part of constraint propagation; it would make our solver more efficient."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3: A better full_propagation method
",
    "
",
    "### Not a real question; just copy some previous code into a new method.
",
    "
",
    "There is a subtle point in applying the where can it go heuristics.
",
    "
",
    "Before, when our only constraint was the uniqueness in each row, column, and block, we needed to propagate only from cells that hold a singleton value. If a cell held a non-singleton set of digits, such as  {2,5} , no values could be ruled out as a consequence of this on the same row, column, or block.
",
    "
",
    "The where can it go heuristic, instead, benefits from knowing that in a cell, the set of values went for instance from  {2,3,5}  to  {2,5} : by ruling out the possibility of a  3  in this cell, it may be possibe to deduct that the digit  3  can appear in only one (other) place in the block, and place it there.
",
    "
",
    "Thus, we modify the full_propagation method. The method does:
",
    "
",
    "- Repeat:
",
    "    - first does propagation as before, based on singletons;
",
    "    - then, it applies the where can it go heuristic on the whole Sudoku board.
",
    "- until there is nothing more that can be propagated.
",
    "
",
    "Thus, we replace the full_propagation method previously defined with this new one, where the (A) block of code is what you previously wrote in full_propagation. You don't need to write new code here: just copy your solution for full_propagation into the (A) block below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sudoku_full_propagation_with_where_can_it_go(self, to_propagate=None):
",
    "    if to_propagate is None:
",
    "        to_propagate = {(i, j) for i in range(9) for j in range(9)}
",
    "    while len(to_propagate) > 0:
",
    "        # Here is your previous solution code from (A) in full_propagation.
",
    "        # Please copy it below.
",
    "        # YOUR CODE HERE
",
    "        if to_propagate is None:
",
    "          to_propagate = {(i, j) for i in range(9) for j in range(9)}
",
    "
",
    "        # Now we check whether there is any other propagation that we can
",
    "        # get from the where can it go rule.
",
    "        to_propagate = self.where_can_it_go()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 4: Implement the occurs_once_in_sets helper
",
    "
",
    "To implement the where_can_it_go method, let us write a helper function, or better, let's have you write it. Given a sequence of sets ?1,?2,…,??, we want to obtain the set of elements that appear in exactly one of the sets (that is, they appear in one set, and only in one set). Mathematically, we can write this as
",
    "
",
    "(?1∖(?2∪⋯∪??))∪(?2∖(?1∪?3∪⋯∪??))∪⋯∪(??∖(?1∪⋯∪??−1))
",
    "
",
    "even though that's certainly not the easiest way to compute it! The problem can be solved with the help of defaultdict to count the occurrences, and is 5 lines long. Of course, other solutions are possible as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict
",
    "from nose.tools import assert_equal
",
    "def occurs_once_in_sets(set_sequence):
",
    "    assert_equal(occurs_once_in_sets([{1, 2}, {2, 3}]), {1, 3})
",
    "    assert_equal(occurs_once_in_sets([]), set())
",
    "    assert_equal(occurs_once_in_sets([{2, 3, 4}]), {2, 3, 4})
",
    "    assert_equal(occurs_once_in_sets([set()]), set())
",
    "    assert_equal(occurs_once_in_sets([{2, 3, 4, 5, 6}, {5, 6, 7, 8}, {5, 6, 7}, {4, 6, 7}]), {2, 3, 8})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We found a solution:
",
      "+---+---+---+
",
      "|531|678|942|
",
      "|674|295|318|
",
      "|298|341|567|
",
      "+---+---+---+
",
      "|859|167|423|
",
      "|426|853|791|
",
      "|713|924|856|
",
      "+---+---+---+
",
      "|165|739|284|
",
      "|987|412|635|
",
      "|342|586|179|
",
      "+---+---+---+
"
     ]
    },
    {
     "data": {
      "text/plain": [
       ""
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sd = Sudoku([
",
    "    '53__7____',
",
    "    '6___95___',
",
    "    '_98____6_',
",
    "    '8___6___3',
",
    "    '4__8_3__1',
",
    "    '7___2___6',
",
    "    '_6____28_',
",
    "    '___41___5',
",
    "    '____8__79'
",
    "])
",
    "sd.solve()
"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 5: Implement where can it go.
",
    "
",
    "We are now ready to write -- or better, to have you write -- the where can it go method.
",
    "The method is global: it examines all rows, all columns, and all blocks.
",
    "If it finds that in a row (or column, or block), a value can fit in only one cell, and that cell is not currently a singleton (for otherwise there is nothing to be done), it sets the value in the cell, and it adds the cell to the newly_singleton set that is returned, just as in propagate_cell. The portion of method that you need to write is about two dozen lines of code long."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sudoku_where_can_it_go(self):
",
    "    newly_singleton = set()
",
    "    return newly_singleton
",
    "Sudoku.where_can_it_go = sudoku_where_can_it_go
"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original:
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|____5____ __3______ 12_4_____|12___6___ ______7__ 12___6_8_|___4___89 12_4_____ _2_____8_|
",
      "|_____6___ 1__4__7__ 12_4__7__|123______ ________9 ____5____|__34___8_ 12_4_____ _2____78_|
",
      "|12_______ ________9 _______8_|123______ ___4_____ 12_______|__3_5____ _____6___ _2____7__|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|_______8_ 1___5____ 1___5___9|1_____7_9 _____6___ 1__4__7_9|___45____ _2_45____ __3______|
",
      "|___4_____ _2_______ _____6___|_______8_ ____5____ __3______|______7__ ________9 1________|
",
      "|______7__ 1___5____ 1_3_5___9|1_______9 _2_______ 1__4____9|___45__8_ ___45____ _____6___|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|1_______9 _____6___ 1___5_7_9|____5_7_9 __3______ ______7_9|_2_______ _______8_ ___4_____|
",
      "|_2______9 ______78_ _2____7_9|___4_____ 1________ _2____7_9|_____6___ __3______ ____5____|
",
      "|_23______ ___45____ _2345____|_2__56___ _______8_ _2___6___|1________ ______7__ ________9|
",
      "+-----------------------------+-----------------------------+-----------------------------+
"
     ]
    },
    {
     "ename": "AssertionError",
     "evalue": "Items in the second set but not the first:
(3, 2)
(2, 6)
(7, 1)
(5, 6)
(2, 8)
(8, 0)
(1, 6)
(0, 5)
(2, 3)
(5, 1)
(3, 7)
(0, 3)
(8, 5)
(0, 8)
(5, 3)
(5, 5)
(8, 1)
(5, 7)
(3, 1)
(0, 6)
(1, 8)
(3, 6)
(5, 2)
(1, 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m\u001b[0m
\u001b[0;32m     11\u001b[0m              {(3, 2), (2, 6), (7, 1), (5, 6), (2, 8), (8, 0), (0, 5), (1, 6),
\u001b[0;32m     12\u001b[0m               \u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m3\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m7\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m3\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m5\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m8\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m8\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m5\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m5\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m3\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m5\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m5\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
\u001b[1;32m---> 13\u001b[1;33m               (8, 1), (5, 7), (3, 1), (0, 6), (1, 8), (3, 6), (5, 2), (1, 1)})
\u001b[0m\u001b[0;32m     14\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m"After where can it go:"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
\u001b[0;32m     15\u001b[0m \u001b[0msd\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mshow\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mdetails\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mTrue\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
",
      "\u001b[1;32m~\Anaconda3\lib\unittest\case.py\u001b[0m in \u001b[0;36massertEqual\u001b[1;34m(self, first, second, msg)\u001b[0m
\u001b[0;32m    837\u001b[0m         """
\u001b[0;32m    838\u001b[0m         \u001b[0massertion_func\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_getAssertEqualityFunc\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mfirst\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0msecond\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
\u001b[1;32m--> 839\u001b[1;33m         \u001b[0massertion_func\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mfirst\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0msecond\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmsg\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mmsg\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
\u001b[0m\u001b[0;32m    840\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m
\u001b[0;32m    841\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0massertNotEqual\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfirst\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0msecond\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmsg\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mNone\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
",
      "\u001b[1;32m~\Anaconda3\lib\unittest\case.py\u001b[0m in \u001b[0;36massertSetEqual\u001b[1;34m(self, set1, set2, msg)\u001b[0m
\u001b[0;32m   1097\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m
\u001b[0;32m   1098\u001b[0m         \u001b[0mstandardMsg\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m'\n'\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mjoin\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlines\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
\u001b[1;32m-> 1099\u001b[1;33m         \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mfail\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_formatMessage\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mmsg\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstandardMsg\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
\u001b[0m\u001b[0;32m   1100\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m
\u001b[0;32m   1101\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0massertIn\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmember\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mcontainer\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmsg\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mNone\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
",
      "\u001b[1;32m~\Anaconda3\lib\unittest\case.py\u001b[0m in \u001b[0;36mfail\u001b[1;34m(self, msg)\u001b[0m
\u001b[0;32m    678\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0mfail\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmsg\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mNone\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
\u001b[0;32m    679\u001b[0m         \u001b[1;34m"""Fail immediately, with the given message."""\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
\u001b[1;32m--> 680\u001b[1;33m         \u001b[1;32mraise\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mfailureException\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mmsg\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
\u001b[0m\u001b[0;32m    681\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m
\u001b[0;32m    682\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0massertFalse\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mexpr\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmsg\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mNone\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m
",
      "\u001b[1;31mAssertionError\u001b[0m: Items in the second set but not the first:
(3, 2)
(2, 6)
(7, 1)
(5, 6)
(2, 8)
(8, 0)
(1, 6)
(0, 5)
(2, 3)
(5, 1)
(3, 7)
(0, 3)
(8, 5)
(0, 8)
(5, 3)
(5, 5)
(8, 1)
(5, 7)
(3, 1)
(0, 6)
(1, 8)
(3, 6)
(5, 2)
(1, 1)"
     ]
    }
   ],
   "source": [
    "sd = Sudoku.from_string('[[[5], [3], [1, 2, 4], [1, 2, 6], [7], [1, 2, 6, 8], [4, 8, 9], [1, 2, 4], [2, 8]], [[6], [1, 4, 7], [1, 2, 4, 7], [1, 2, 3], [9], [5], [3, 4, 8], [1, 2, 4], [2, 7, 8]], [[1, 2], [9], [8], [1, 2, 3], [4], [1, 2], [3, 5], [6], [2, 7]], [[8], [1, 5], [1, 5, 9], [1, 7, 9], [6], [1, 4, 7, 9], [4, 5], [2, 4, 5], [3]], [[4], [2], [6], [8], [5], [3], [7], [9], [1]], [[7], [1, 5], [1, 3, 5, 9], [1, 9], [2], [1, 4, 9], [4, 5, 8], [4, 5], [6]], [[1, 9], [6], [1, 5, 7, 9], [5, 7, 9], [3], [7, 9], [2], [8], [4]], [[2, 9], [7, 8], [2, 7, 9], [4], [1], [2, 7, 9], [6], [3], [5]], [[2, 3], [4, 5], [2, 3, 4, 5], [2, 5, 6], [8], [2, 6], [1], [7], [9]]]')
",
    "print("Original:")
",
    "sd.show(details=True)
",
    "new_singletons = set()
",
    "while True:
",
    "    new_s = sd.where_can_it_go()
",
    "    if len(new_s) == 0:
",
    "        break
",
    "    new_singletons |= new_s
",
    "assert_equal(new_singletons,
",
    "             {(3, 2), (2, 6), (7, 1), (5, 6), (2, 8), (8, 0), (0, 5), (1, 6),
",
    "              (2, 3), (3, 7), (0, 3), (5, 1), (0, 8), (8, 5), (5, 3), (5, 5),
",
    "              (8, 1), (5, 7), (3, 1), (0, 6), (1, 8), (3, 6), (5, 2), (1, 1)})
",
    "print("After where can it go:")
",
    "sd.show(details=True)
",
    "sdd = Sudoku.from_string('[[[5], [3], [1, 2, 4], [6], [7], [8], [9], [1, 2, 4], [2]], [[6], [7], [1, 2, 4, 7], [1, 2, 3], [9], [5], [3], [1, 2, 4], [8]], [[1, 2], [9], [8], [3], [4], [1, 2], [5], [6], [7]], [[8], [5], [9], [1, 9, 7], [6], [1, 4, 9, 7], [4], [2], [3]], [[4], [2], [6], [8], [5], [3], [7], [9], [1]], [[7], [1], [3], [9], [2], [4], [8], [5], [6]], [[1, 9], [6], [1, 5, 9, 7], [9, 5, 7], [3], [9, 7], [2], [8], [4]], [[9, 2], [8], [9, 2, 7], [4], [1], [9, 2, 7], [6], [3], [5]], [[3], [4], [2, 3, 4, 5], [2, 5, 6], [8], [6], [1], [7], [9]]]')
",
    "print("The above should be equal to:")
",
    "sdd.show(details=True)
",
    "assert_equal(sd, sdd)
",
    "
",
    "sd = Sudoku([
",
    "    '___26_7_1',
",
    "    '68__7____',
",
    "    '1____45__',
",
    "    '82_1___4_',
",
    "    '__46_2___',
",
    "    '_5___3_28',
",
    "    '___3___74',
",
    "    '_4__5__36',
",
    "    '7_3_18___'
",
    "])
",
    "print("Another Original:")
",
    "sd.show(details=True)
",
    "print("Propagate once:")
",
    "sd.propagate_all_cells_once()
",
    "# sd.show(details=True)
",
    "new_singletons = set()
",
    "while True:
",
    "    new_s = sd.where_can_it_go()
",
    "    if len(new_s) == 0:
",
    "        break
",
    "    new_singletons |= new_s
",
    "print("After where can it go:")
",
    "sd.show(details=True)
",
    "sdd = Sudoku.from_string('[[[4], [3], [5], [2], [6], [9], [7], [8], [1]], [[6], [8], [2], [5], [7], [1], [4], [9], [3]], [[1], [9], [7], [8], [3], [4], [5], [6], [2]], [[8], [2], [6], [1], [9], [5], [3], [4], [7]], [[3], [7], [4], [6], [8], [2], [9], [1], [5]], [[9], [5], [1], [7], [4], [3], [6], [2], [8]], [[5], [1], [1, 2, 5, 6, 8, 9], [3], [2], [6], [1, 2, 8, 9], [7], [4]], [[2], [4], [1, 2, 8, 9], [9], [5], [7], [1, 2, 8, 9], [3], [6]], [[7], [6], [3], [4], [1], [8], [2], [5], [9]]]')
",
    "print("The above should be equal to:")
",
    "sdd.show(details=True)
",
    "assert_equal(sd, sdd)
"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Newly singleton: set()
",
      "Resulting Sudoku:
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|____5____ __3______ 12_4_____|12___6___ ______7__ 12___6_8_|___4___89 12_4_____ _2_____8_|
",
      "|_____6___ 1__4__7__ 12_4__7__|123______ ________9 ____5____|__34___8_ 12_4_____ _2____78_|
",
      "|12_______ ________9 _______8_|123______ ___4_____ 12_______|__3_5____ _____6___ _2____7__|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|_______8_ 1___5____ 1___5___9|1_____7_9 _____6___ 1__4__7_9|___45____ _2_45____ __3______|
",
      "|___4_____ _2_______ _____6___|_______8_ ____5____ __3______|______7__ ________9 1________|
",
      "|______7__ 1___5____ 1_3_5___9|1_______9 _2_______ 1__4____9|___45__8_ ___45____ _____6___|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|1_______9 _____6___ 1___5_7_9|____5_7_9 __3______ ______7_9|_2_______ _______8_ ___4_____|
",
      "|_2______9 ______78_ _2____7_9|___4_____ 1________ _2____7_9|_____6___ __3______ ____5____|
",
      "|_23______ ___45____ _2345____|_2__56___ _______8_ _2___6___|1________ ______7__ ________9|
",
      "+-----------------------------+-----------------------------+-----------------------------+
"
     ]
    }
   ],
   "source": [
    "sd = Sudoku(sd_partially_solved)
",
    "newly_singleton = sd.where_can_it_go()
",
    "print("Newly singleton:", newly_singleton)
",
    "print("Resulting Sudoku:")
",
    "sd.show(details=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "Sudoku.full_propagation = sudoku_full_propagation_with_where_can_it_go"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial:
",
      "+---+---+---+
",
      "|53.|.7.|...|
",
      "|6..|.95|...|
",
      "|.98|...|.6.|
",
      "+---+---+---+
",
      "|8..|.6.|..3|
",
      "|4..|8.3|..1|
",
      "|7..|.2.|..6|
",
      "+---+---+---+
",
      "|.6.|...|28.|
",
      "|...|41.|..5|
",
      "|...|.8.|.79|
",
      "+---+---+---+
",
      "After full propagation with where can it go:
",
      "+---+---+---+
",
      "|53.|.7.|...|
",
      "|6..|.95|...|
",
      "|.98|...|.6.|
",
      "+---+---+---+
",
      "|8..|.6.|..3|
",
      "|4..|8.3|..1|
",
      "|7..|.2.|..6|
",
      "+---+---+---+
",
      "|.6.|...|28.|
",
      "|...|41.|..5|
",
      "|...|.8.|.79|
",
      "+---+---+---+
"
     ]
    }
   ],
   "source": [
    "sd = Sudoku([
",
    "    '53__7____',
",
    "    '6___95___',
",
    "    '_98____6_',
",
    "    '8___6___3',
",
    "    '4__8_3__1',
",
    "    '7___2___6',
",
    "    '_6____28_',
",
    "    '___41___5',
",
    "    '____8__79'
",
    "])
",
    "print("Initial:")
",
    "sd.show()
",
    "sd.full_propagation()
",
    "print("After full propagation with where can it go:")
",
    "sd.show()
"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No! We still cannot! But if we compare the above with the previous attempt, we see that the heuristic led to much more progress; very few positions still remain to be determined via search."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 6: Solving some problems from example sites
",
    "
",
    "Let us see how long it takes us to solve examples found around the Web. We consider a few from this site. You should be able to complete all of these tests in a short amount of time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We found a solution:
",
      "+---+---+---+
",
      "|121|618|111|
",
      "|581|119|711|
",
      "|111|141|111|
",
      "+---+---+---+
",
      "|371|111|511|
",
      "|611|111|114|
",
      "|118|111|113|
",
      "+---+---+---+
",
      "|111|121|111|
",
      "|119|811|136|
",
      "|111|316|191|
",
      "+---+---+---+
",
      "Solved in 0.025991439819335938 seconds
"
     ]
    }
   ],
   "source": [
    "import time
",
    "sd = Sudoku([
",
    "    '_2_6_8___',
",
    "    '58___97__',
",
    "    '____4____',
",
    "    '37____5__',
",
    "    '6_______4',
",
    "    '__8____13',
",
    "    '____2____',
",
    "    '__98___36',
",
    "    '___3_6_9_'
",
    "])
",
    "t = time.time()
",
    "sd.solve()
",
    "elapsed = time.time() - t
",
    "print("Solved in", elapsed, "seconds")
",
    "
",
    "assert elapsed  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:
",
    "            newly_singleton.update(self.ruleout(ii, j, x))
",
    "    # Same block of 3x3 cells.
",
    "    # YOUR CODE HERE
",
    "    current_i, current_j = i // 3, j // 3
",
    "    current_i, current_j = 3*current_i + 1, 3*current_j + 1
",
    "    
",
    "    for di in range(-1, 2):
",
    "        for dj in range(-1, 2):
",
    "            ni, nj = current_i + di, current_j + dj
",
    "            if i != ni and j != nj:
",
    "                newly_singleton.update(self.ruleout(ni, nj, x))
",
    "    # Returns the list of newly-singleton cells.
",
    "    return newly_singleton
",
    "
",
    "Sudoku.propagate_cell = sudoku_propagate_cell
"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "deletable": false,
    "id": "Yvv_sj14K3YO",
    "nbgrader": {
     "checksum": "6cd195cd2104c42b331eeaa641745991",
     "grade": false,
     "grade_id": "cell-aaf8944cfc81c6dd",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# Here you can write your own tests if you like. 
",
    "
",
    "# YOUR CODE HERE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "deletable": false,
    "editable": false,
    "id": "ZZtJigfvK3YO",
    "nbgrader": {
     "checksum": "1d320009a9aff66baf1be3c34c9aa091",
     "grade": true,
     "grade_id": "cell-518cff90ecab53c2",
     "locked": true,
     "points": 10,
     "schema_version": 1,
     "solution": false
    },
    "outputId": "c1efe19f-a5a9-4717-da2a-04b3ccc0e2c5"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|____5____ __3______ _2_______|_____6___ ______7__ _______8_|________9 12_4_____ _2_______|
",
      "|_____6___ ______7__ 12_4__7__|123______ ________9 ____5____|__3______ 12_4_____ _______8_|
",
      "|12_______ ________9 _______8_|__3______ ___4_____ 12_______|____5____ _____6___ ______7__|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|_______8_ ____5____ ________9|1_____7_9 _____6___ 1__4__7_9|___4_____ _2_______ __3______|
",
      "|___4_____ _2_______ _____6___|_______8_ ____5____ __3______|______7__ ________9 1________|
",
      "|______7__ 1________ __3______|________9 _2_______ ___4_____|_______8_ ____5____ _____6___|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|1_______9 _____6___ 1___5_7_9|____5_7_9 __3______ ______7_9|_2_______ _______8_ ___4_____|
",
      "|_2______9 _______8_ _2____7_9|___4_____ 1________ _2____7_9|_____6___ __3______ ____5____|
",
      "|__3______ ___4_____ _2345____|_2__56___ _______8_ _____6___|1________ ______7__ ________9|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "Good! It was unsolvable.
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|____5____ __3______ _2_______|_____6___ ______7__ _______8_|________9 12_4_____ _23______|
",
      "|_____6___ ______7__ 12_4__7__|123______ ________9 ____5____|__3______ 12_4_____ _______8_|
",
      "|12_______ ________9 _______8_|__3______ ___4_____ 12_______|____5____ _____6___ ______7__|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|_______8_ ____5____ ________9|1_____7_9 _____6___ 1__4__7_9|___4_____ _2_______ __3______|
",
      "|___4_____ _2_______ _____6___|_______8_ ____5____ __3______|______7__ ________9 1________|
",
      "|______7__ 1________ __3______|________9 _2_______ ___4_____|_______8_ ____5____ _____6___|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|1_______9 _____6___ 1___5_7_9|____5_7_9 __3______ ______7_9|_2_______ _______8_ ___4_____|
",
      "|_2______9 _______8_ _2____7_9|___4_____ 1________ _2____7_9|_____6___ __3______ ____5____|
",
      "|__3______ ___4_____ _2345____|_2__56___ _______8_ _____6___|1________ ______7__ ________9|
",
      "+-----------------------------+-----------------------------+-----------------------------+
"
     ]
    }
   ],
   "source": [
    "### 10 points: Tests for cell propagation
",
    "
",
    "tsd = Sudoku.from_string('[[[5], [3], [2], [6], [7], [8], [9], [1, 2, 4], [2]], [[6], [7], [1, 2, 4, 7], [1, 2, 3], [9], [5], [3], [1, 2, 4], [8]], [[1, 2], [9], [8], [3], [4], [1, 2], [5], [6], [7]], [[8], [5], [9], [1, 9, 7], [6], [1, 4, 9, 7], [4], [2], [3]], [[4], [2], [6], [8], [5], [3], [7], [9], [1]], [[7], [1], [3], [9], [2], [4], [8], [5], [6]], [[1, 9], [6], [1, 5, 9, 7], [9, 5, 7], [3], [9, 7], [2], [8], [4]], [[9, 2], [8], [9, 2, 7], [4], [1], [9, 2, 7], [6], [3], [5]], [[3], [4], [2, 3, 4, 5], [2, 5, 6], [8], [6], [1], [7], [9]]]')
",
    "tsd.show(details=True)
",
    "try:
",
    "    tsd.propagate_cell((0, 2))
",
    "except Unsolvable:
",
    "    print("Good! It was unsolvable.")
",
    "else:
",
    "    raise Exception("Hey, it was unsolvable")
",
    "
",
    "tsd = Sudoku.from_string('[[[5], [3], [2], [6], [7], [8], [9], [1, 2, 4], [2, 3]], [[6], [7], [1, 2, 4, 7], [1, 2, 3], [9], [5], [3], [1, 2, 4], [8]], [[1, 2], [9], [8], [3], [4], [1, 2], [5], [6], [7]], [[8], [5], [9], [1, 9, 7], [6], [1, 4, 9, 7], [4], [2], [3]], [[4], [2], [6], [8], [5], [3], [7], [9], [1]], [[7], [1], [3], [9], [2], [4], [8], [5], [6]], [[1, 9], [6], [1, 5, 9, 7], [9, 5, 7], [3], [9, 7], [2], [8], [4]], [[9, 2], [8], [9, 2, 7], [4], [1], [9, 2, 7], [6], [3], [5]], [[3], [4], [2, 3, 4, 5], [2, 5, 6], [8], [6], [1], [7], [9]]]')
",
    "tsd.show(details=True)
",
    "assert_equal(tsd.propagate_cell((0, 2)), {(0, 8), (2, 0)})
",
    "
"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "id": "la3lgaFdK3YO",
    "nbgrader": {
     "checksum": "e5ed2a3a7c5ee13c35949e28b4549ce4",
     "grade": false,
     "grade_id": "cell-6bdb89884ff9de73",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Propagating all cells, once
",
    "
",
    "The simplest thing we can do is propagate each cell, once. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "deletable": false,
    "editable": false,
    "id": "a7tylyeNK3YO",
    "nbgrader": {
     "checksum": "cf75628fec88e4a7eb1336f87733579d",
     "grade": false,
     "grade_id": "cell-f01c09cb45f93a07",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def sudoku_propagate_all_cells_once(self):
",
    "    """This function propagates the constraints from all singletons."""
",
    "    for i in range(9):
",
    "        for j in range(9):
",
    "            self.propagate_cell((i, j))
",
    "
",
    "Sudoku.propagate_all_cells_once = sudoku_propagate_all_cells_once
"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "deletable": false,
    "editable": false,
    "id": "fO2u9xv6K3YO",
    "nbgrader": {
     "checksum": "ea85d958be7c22389daa6d8b5319089e",
     "grade": false,
     "grade_id": "cell-544f2797149c7f48",
     "locked": true,
     "schema_version": 1,
     "solution": false
    },
    "outputId": "04c432b2-9b85-4284-e4f8-9ed6e686a681"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+---+---+---+
",
      "|53.|.7.|...|
",
      "|6..|195|...|
",
      "|.98|...|.6.|
",
      "+---+---+---+
",
      "|8..|.6.|..3|
",
      "|4..|8.3|..1|
",
      "|7..|.2.|..6|
",
      "+---+---+---+
",
      "|.6.|...|28.|
",
      "|...|419|..5|
",
      "|...|.8.|.79|
",
      "+---+---+---+
",
      "+---+---+---+
",
      "|53.|.7.|...|
",
      "|6..|195|...|
",
      "|.98|...|.6.|
",
      "+---+---+---+
",
      "|8..|.6.|..3|
",
      "|4..|853|..1|
",
      "|7..|.2.|..6|
",
      "+---+---+---+
",
      "|.6.|..7|284|
",
      "|...|419|.35|
",
      "|...|.8.|.79|
",
      "+---+---+---+
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|____5____ __3______ 12_4_____|_2___6___ ______7__ _2_4_6_8_|1__4___89 12_4____9 _2_4___8_|
",
      "|_____6___ _2_4__7__ _2_4__7__|1________ ________9 ____5____|__34__78_ _234_____ _2_4__78_|
",
      "|12_______ ________9 _______8_|_23______ __34_____ _2_4_____|1_345_7__ _____6___ _2_4__7__|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|_______8_ 12__5____ 12__5___9|____5_7_9 _____6___ 1__4__7__|___45_7_9 _2_45___9 __3______|
",
      "|___4_____ _2__5____ _2__56__9|_______8_ ____5____ __3______|____5_7_9 _2__5___9 1________|
",
      "|______7__ 1___5____ 1_3_5___9|____5___9 _2_______ 1__4_____|___45__89 ___45___9 _____6___|
",
      "+-----------------------------+-----------------------------+-----------------------------+
",
      "|1_3_____9 _____6___ 1_345_7_9|__3_5_7__ __3_5____ ______7__|_2_______ _______8_ ___4_____|
",
      "|_23______ _2____78_ _23___7__|___4_____ 1________ ________9|__3__6___ __3______ ____5____|
",
      "|123______ 12_45____ 12345____|_23_56___ _______8_ _2___6___|1_34_6___ ______7__ ________9|
",
      "+-----------------------------+-----------------------------+-----------------------------+
"
     ]
    }
   ],
   "source": [
    "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.propagate_all_cells_once()
",
    "sd.show()
",
    "sd.show(details=True)
"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "id": "UrkX-YG_K3YO",
    "nbgrader": {
     "checksum": "c3998f1c5401444444d92ca72de4e24e",
     "grade": false,
     "grade_id": "cell-29a0e911623d5ef4",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2: Propagating all cells, repeatedly
",
    "
",
    "This is a good beginning, but it's not quite enough. 
",
    "As we propagate the constraints, cells that did not use to be singletons may have become singletons.  For eample, in the above example, the center cell has become known to be a 5: we need to make sure that also these singletons are propagated. 
",
    "
",
    "This is why we have written propagate_cell so that it returns the set of newly-singleton cells.  
",
    "We need now to write a method `full_propagation` that at the beginning starts with a set of `to_propagate` cells (if it is not specified, then we just take it to consist of all singleton cells).  Then, it picks a cell from the to_propagate set, and propagates from it, adding any newly singleton cell to to_propagate.  Once there are no more cells to be propagated, the method returns. 
",
    "If this sounds similar to graph reachability, it is ... because it is!  It is once again the algorithmic pattern of keeping a list of work to be done, then iteratively picking an element from the list, doing it, possibly updating the list of work to be done with new work that has to be done as a result of what we just did, and continuing in this fashion until there is nothing left to do. 
",
    "We will let you write this function.  The portion you have to write can be done in three lines of code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "deletable": false,
    "id": "9kPjicpKK3YP",
    "nbgrader": {
     "checksum": "6c1cc36c7e13cb95174ad15ccafde5fc",
     "grade": false,
     "grade_id": "cell-28cd5047394e6887",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "### Exercise: define full propagation
",
    "
",
    "def sudoku_full_propagation(self, to_propagate=None):
",
    "    """Iteratively propagates from all singleton cells, and from all
",
    "    newly discovered singleton cells, until no more propagation is possible.
",
    "    @param to_propagate: sets of cells from where to propagate.  If None, propagates
",
    "        from all singleton cells. 
",
    "    @return: nothing.
",
    "    """
",
    "    if to_propagate is None:
",
    "        to_propagate = {(i, j) for i in range(9) for j in range(9)}
",
    "    # This code is the (A) code; will be referenced later.
",
    "    # YOUR CODE HERE
",
    "    for (i, j) in to_propagate:
",
    "        x = self.propagate_cell((i, j))
",
    "        sudoku_full_propagation(self, x)
",
    "
",
    "Sudoku.full_propagation = sudoku_full_propagation
"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "deletable": false,
    "id": "_oxWgCLTK3YP",
    "nbgrader": {
     "checksum": "af46d0b76cf950f662c3cf238f6d257a",
     "grade": false,
     "grade_id": "cell-1c1f40d813c5b7c6",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# Here you can write your own tests if you like. 
",
    "
",
    "# YOUR CODE HERE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "deletable": false,
    "editable": false,
    "id": "HLPvVEb0K3YP",
    "nbgrader": {
     "checksum":

Q4,5,6

Answer To: Q4,5,6

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment