Commits

Geoff Hill committed 120416c

added sudoku work from plane ride

Comments (0)

Files changed (9)

src/sudoku/EECS 348 PS2.docx

Binary file added.

src/sudoku/boards/mandatory/16x16.sudoku

+16
+103
+1	1	13
+1	3	2
+1	4	8
+1	10	6
+1	13	12
+1	14	5
+1	16	15
+2	1	12
+2	2	3
+2	3	16
+2	4	9
+2	7	5
+2	8	11
+2	9	2
+2	12	15
+2	13	1
+3	2	1
+3	3	11
+3	5	12
+3	6	6
+3	7	14
+3	10	16
+3	13	3
+3	16	8
+4	11	1
+4	13	11
+4	14	2
+4	16	16
+5	3	14
+5	11	2
+5	15	3
+5	16	10
+6	1	3
+6	2	8
+6	3	10
+6	4	13
+6	5	11
+6	7	1
+6	8	4
+6	12	6
+7	1	5
+7	3	9
+7	4	2
+7	6	7
+7	10	1
+7	11	14
+7	13	6
+8	2	7
+8	3	15
+8	4	4
+8	6	2
+8	13	5
+8	16	12
+9	1	11
+9	2	9
+9	4	14
+9	5	2
+9	6	5
+9	9	1
+9	12	3
+9	15	12
+10	3	3
+10	5	13
+10	8	6
+10	12	16
+10	13	8
+10	14	11
+10	15	5
+11	7	11
+11	8	9
+11	10	7
+11	12	2
+11	15	6
+11	16	1
+12	3	13
+12	4	5
+12	7	12
+12	8	1
+12	12	4
+12	13	15
+12	16	14
+13	2	13
+13	11	9
+13	12	8
+13	13	16
+13	15	4
+13	16	5
+14	1	2
+14	9	16
+14	12	1
+14	13	7
+14	16	6
+15	2	16
+15	5	4
+15	11	7
+15	13	9
+15	14	10
+16	2	10
+16	7	16
+16	8	8
+16	12	5
+16	13	2
+16	14	12

src/sudoku/boards/mandatory/25x25.sudoku

+25
+245
+1	1	10
+1	2	22
+1	3	14
+1	8	13
+1	10	18
+1	12	20
+1	13	25
+1	17	21
+1	19	1
+1	24	12
+2	4	12
+2	6	17
+2	7	15
+2	8	1
+2	9	25
+2	10	10
+2	12	3
+2	13	13
+2	15	7
+2	18	16
+2	21	11
+2	22	18
+2	23	24
+2	24	4
+3	11	24
+3	12	12
+3	19	2
+3	21	10
+3	22	25
+3	23	6
+3	24	1
+4	4	9
+4	8	23
+4	10	5
+4	13	19
+4	18	12
+4	21	17
+4	23	20
+5	3	5
+5	5	16
+5	6	12
+5	7	6
+5	8	20
+5	9	8
+5	16	10
+5	22	2
+5	23	19
+6	1	5
+6	4	20
+6	8	9
+6	9	14
+6	10	6
+6	15	17
+6	16	1
+6	22	23
+6	23	16
+6	24	11
+7	1	24
+7	3	16
+7	8	19
+7	9	15
+7	12	5
+7	13	18
+7	14	1
+7	16	8
+7	18	25
+7	19	6
+7	23	12
+8	3	12
+8	4	14
+8	9	17
+8	14	24
+8	15	20
+8	16	13
+8	19	3
+8	25	4
+9	2	18
+9	3	19
+9	4	13
+9	8	10
+9	10	3
+9	11	2
+9	13	9
+9	14	6
+9	16	16
+9	18	23
+9	20	21
+9	24	24
+10	3	1
+10	4	6
+10	5	9
+10	7	24
+10	10	12
+10	12	16
+10	13	22
+10	16	20
+10	17	19
+10	19	17
+10	23	2
+11	8	21
+11	12	24
+11	14	3
+11	15	13
+11	16	18
+11	17	11
+11	18	17
+11	23	22
+11	25	1
+12	10	9
+12	13	8
+12	15	1
+12	22	24
+12	24	7
+13	5	12
+13	6	18
+13	14	14
+13	15	2
+13	16	21
+13	17	8
+13	19	13
+13	20	1
+13	21	19
+13	23	9
+14	2	14
+14	6	15
+14	7	3
+14	8	4
+14	9	7
+14	11	5
+14	17	6
+14	20	22
+14	21	8
+14	23	21
+14	25	2
+15	2	16
+15	3	3
+15	5	25
+15	10	1
+15	13	12
+15	14	9
+15	15	21
+15	17	2
+15	18	15
+15	19	7
+15	20	20
+16	6	23
+16	10	15
+16	14	16
+16	16	7
+16	17	14
+16	21	3
+16	23	13
+17	4	4
+17	5	7
+17	6	9
+17	8	14
+17	12	1
+17	14	8
+17	19	24
+17	21	6
+17	22	22
+18	2	5
+18	4	1
+18	5	6
+18	8	12
+18	9	11
+18	12	25
+18	13	14
+18	18	13
+18	20	19
+18	21	24
+19	2	9
+19	6	4
+19	7	13
+19	10	8
+19	11	19
+19	14	7
+19	18	21
+19	19	20
+19	21	25
+19	22	1
+19	25	11
+20	1	16
+20	3	11
+20	7	20
+20	8	3
+20	10	25
+20	12	23
+20	15	9
+20	16	22
+20	17	1
+20	18	6
+20	19	15
+20	21	4
+20	22	7
+20	23	14
+21	4	16
+21	6	3
+21	13	4
+21	16	6
+21	17	12
+21	18	8
+21	20	13
+22	1	14
+22	2	20
+22	4	7
+22	5	22
+22	7	16
+22	8	5
+22	9	12
+22	13	21
+22	14	23
+22	15	25
+22	16	4
+22	18	1
+22	23	3
+23	2	1
+23	4	15
+23	6	20
+23	9	4
+23	11	8
+23	20	16
+23	21	14
+23	22	12
+23	23	17
+23	24	19
+23	25	24
+24	4	25
+24	10	7
+24	13	3
+24	15	22
+24	16	14
+24	23	10
+25	1	3
+25	5	5
+25	6	14
+25	7	25
+25	8	15
+25	9	18
+25	10	13
+25	12	7
+25	14	17
+25	17	20
+25	19	22
+25	22	11

src/sudoku/boards/mandatory/4x4.sudoku

+4
+5
+2	3	4
+3	2	2
+3	4	4
+4	2	3
+4	4	2

src/sudoku/boards/mandatory/9x9.sudoku

+9
+26
+1	1	7
+1	2	5
+1	6	8
+2	6	4
+2	8	9
+3	4	5
+3	5	7
+3	7	6
+4	1	9
+4	5	8
+4	9	3
+5	3	5
+5	4	4
+5	6	2
+5	7	1
+6	1	4
+6	5	3
+6	9	2
+7	3	3
+7	5	4
+7	6	7
+8	2	2
+8	4	8
+9	4	2
+9	8	3
+9	9	8

src/sudoku/csp.py

     def __str__(self):
         return "Max solution depth exceeded %d." % (self.depth,)
 
-class NotZeroConstraint(object):
-    def __init__(self, variable):
-        self.variable = variable
-    def satisfied(self, m):
-        v = self.variable
-        return v in m and m[v] != 0
-
 class AllDiffConstraint(object):
     def __init__(self, variables):
         self.variables = variables
     def satisfied(self, m):
+        """Given a full mapping `m`, tests whether or not the constraint is
+        fully satisfied. In this case, tests whether the values assigned
+        to every specified variable are different."""
         vs = set()
         for v in self.variables:
             if not v in m: return False
             vs.add(m[v])
         return len(vs) == len(self.variables)
+    def possible(self, m):
+        """Given a partial mapping `m`, tests whether or not there exists an
+        extension of `m` that satisfied the constraint. In this case, if two
+        values are ever the same, the constraint cannot be satisfied."""
+        vs = [m[v] for v in m if v in self.variables]
+        return len(vs) == len(set(vs))
 
 class CSPSolver(object):
-    MAX_CHECKS = 1e7
+    MAX_CHECKS = 1e6
     def __init__(self, variables, domains, constraints):
         self.variables = variables
         self.domains = domains
     def searchSolution(self):
         last_var = self.variables[-1]
         var = self.variables[0]
+        domains = self.prunedDomains()
         mapping = {var: self.domains[var][0]}
-        for exps in count():
-            if self.solved(mapping):
-                return mapping, exps
-            elif var == last_var:
-                while mapping[var] == self.domains[var][-1]:
+        exps = 0
+        while True:
+            if exps > self.MAX_CHECKS:
+                raise MaxDepthExceeded(self.MAX_CHECKS)
+            elif var == last_var or self.mustBacktrack(domains, mapping, var):
+                if self.solved(mapping):
+                    return mapping, exps
+                exps += 1
+                while mapping[var] == domains[var][-1]:
                     del mapping[var]
                     idx = self.variables.index(var)
                     if idx == 0:
                         raise SolutionNotFound
                     var = self.variables[idx-1]
                 last_val = mapping[var]
-                val = self.domains[var][self.domains[var].index(last_val)+1]
+                val = domains[var][domains[var].index(last_val)+1]
                 mapping[var] = val
             else:
                 var = self.variables[self.variables.index(var)+1]
-                if len(self.domains[var]) == 0:
+                if len(domains[var]) == 0:
                     raise SolutionNotFound
-                mapping[var] = self.domains[var][0]
-    def getNextVar(self, remaining):
-        for r in remaining: return r
-    def getNextVal(self, remaining):
-        for r in remaining: return r
+                mapping[var] = domains[var][0]
+    def prunedDomains(self):
+        return self.domains
+    def mustBacktrack(self, domains, mapping, var):
+        return False
+
+
+class ForwardCheckingSolver(BacktrackingSolver):
+    def mustBacktrack(self, domains, mapping, var):
+        forwards = [v for v in self.variables if v not in mapping]
+        for var in forwards:
+            legal_vals = set(domains[var])
+            for val in domains[var]:
+                hypo_mapping = dict(mapping)
+                hypo_mapping[var] = val
+                for c in self.constraints:
+                    if not c.possible(hypo_mapping):
+                        legal_vals.discard(val)
+                        break
+            if len(legal_vals) == 0:
+                return True
+        return False
 
 
+class ArcConsistencySolver(BacktrackingSolver):
+    def prunedDomains(self):
+        domains = {v: list() for v in self.domains}
+        for varA in self.domains:
+            for valA in self.domains[varA]:
+                if self.compatibleWithAllOthers(varA, valA):
+                    domains[varA].append(valA)
+        return domains
+    
+    def compatibleWithAllOthers(self, varA, valA):
+        for varB in self.domains:
+            if varA == varB: continue
+            if not self.existsPossibleValue(varA, valA, varB):
+                return False
+        return True
+    
+    def existsPossibleValue(self, varA, valA, varB):
+        for valB in self.domains[varB]:
+            if self.compatibleWithConstraints(varA, valA, varB, valB):
+                return True
+        return False
+    
+    def compatibleWithConstraints(self, varA, valA, varB, valB):
+        for c in self.constraints:
+            if not c.possible({varA: valA, varB: valB}):
+                return False
+        return True
+        

src/sudoku/csp_test.py

 import unittest
 from csp import *
 
-class TestNotZeroConstraint(unittest.TestCase):
-    def testNotZero(self):
-        c = NotZeroConstraint(4)
-        self.assertTrue(c.satisfied({4: 3}))
-    def testZero(self):
-        c = NotZeroConstraint(2)
-        self.assertFalse(c.satisfied({2: 0}))
-    def testNotInMapping(self):
-        c = NotZeroConstraint(4)
-        self.assertFalse(c.satisfied({2: 3}))
-
 class TestAllDiffConstraint(unittest.TestCase):
     def testEmpty(self):
         c = AllDiffConstraint(list())
     def testNotInMapping(self):
         c = AllDiffConstraint([0, 1, 2, 3])
         self.assertFalse(c.satisfied({0: 4, 1: 7}))
+    def testEmptyPossible(self):
+        c = AllDiffConstraint([0, 1, 2, 3])
+        self.assertTrue(c.possible({}))
+    def testAllDiffPossible(self):
+        c = AllDiffConstraint([0, 1, 2, 3])
+        self.assertTrue(c.possible({0: 0, 1: 1, 2: 2, 3: 3}))
+    def testPartialDiffPossible(self):
+        c = AllDiffConstraint([0, 1, 2, 3])
+        self.assertTrue(c.possible({0: 0, 1: 1}))
+    def testPartialSameImpossible(self):
+        c = AllDiffConstraint([0, 1, 2, 3])
+        self.assertFalse(c.possible({0: 0, 1: 1, 2: 0}))
 
 
 class TestCSPSolver(unittest.TestCase):
         cs = [AllDiffConstraint([0,1,2])]
         s = BacktrackingSolver(vs, ds, cs)
         self.assertEqual(s.solve(), {0:0, 1:1, 2:2})
+    def testImpossibleEmptyDomain(self):
+        vs = [0,1,2]
+        ds = {0: [0], 1: [], 2: [0]}
+        cs = [AllDiffConstraint([0,1,2])]
+        s = BacktrackingSolver(vs, ds, cs)
+        with self.assertRaises(SolutionNotFound):
+            s.solve()
     def testImpossibleAllDiffConstraint(self):
         vs = [0,1,2]
         ds = {0: [0], 1: [0,2], 2: [0]}

src/sudoku/sudoku.py

 #!/usr/bin/env python
 
-import math, array, copy, csp
-
-def unique(seq):
-    """Determines whether or not every element in a sequence is unique."""
-    return len(seq) == len(set(seq))
-
-
+import math
+import array
+import copy
+import csp
 
 class Board(object):
     """Class for a Sudoku board.
     get(row, col) and set(row, col, val) methods.
     
     In addition, this class can differentiate in-progress board states from
-    Sudoku goal states through the complete() method.
-    """
+    Sudoku goal states through the complete() method."""
     
-    def __init__(self, size=None, filename=None):
+    def __init__(self, size=None, filename=None, mapping=None):
         """Constructor. See class doc string."""
         if filename:
             f = open(filename, 'r')
                 val = int(chars[2])
                 self.set(row, col, val)
             f.close()
+        elif mapping:
+            size = int(math.sqrt(len(mapping)))
+            self.initBoard(size)
+            for k in mapping:
+                self.board[k] = mapping[k]
         else:
             if not size:
                 size = 9
             self.initBoard(size)
-    
     def initBoard(self, size):
         self.size = size
         self.width = int(math.sqrt(size))
         self.board = array.array('H', [0 for i in range(size*size)])
-    
     def idx(self, row, col):
         return row*self.size + col
-        
     def boxIdx(self, box):
         w = self.width
         rs = w*(box//w)
         cs = w*(box%w)
         return [(i, j) for i in range(rs, rs+w) for j in range(cs, cs+w)]
-    
     def get(self, row, col):
         return self.board[self.idx(row, col)]
-    
     def set(self, row, col, val):
         self.board[self.idx(row, col)] = val
-    
-    def toCSP(self, constructor):
-        variables = list(range(len(self.board)))
-        domains = dict()
-        for v in variables:
-            if self.board[v]:
-                domains[v] = [v]
-            else:
-                domains[v] = list(range(1,self.size+1))
-        constraints = list()
-        for row in self.size:
-            c = AllDiffConstraint([self.idx(row, col) for col in self.size])
-            constraints.add(c)
-        for col in self.size:
-            c = AllDiffConstraint([self.idx(row, col) for row in self.size])
-            constraints.add(c)
-        for box in self.size:
-            c = AllDiffConstraint([self.idx(row, col) for (row, col) in self.boxIdx(box)])
-            constraints.add(c)
-        return constructor(variables, domains, constraints)
-    
-    # binary-decision constraint tests
-    
     def complete(self):
         return self.filled() and self.valid()
-    
     def filled(self):
         return not 0 in self.board
-
     def valid(self):
         for i in range(self.size):
             if not self.rowValid(i): return False
             if not self.colValid(i): return False
             if not self.boxValid(i): return False
         return True
-
     def rowValid(self, row):
         s = self.size
         for i in range(s):
                 if self.get(row, i) == self.get(row, j):
                     return False
         return True
-
     def colValid(self, col):
         s = self.size
         for i in range(s):
                 if self.get(i, col) == self.get(j, col):
                     return False
         return True
-
     def boxValid(self, box):
         s = self.size
         w = self.width
                         if self.get(i, j) == self.get(m, n):
                             return False
         return True
-    
-    # numbered constraint tests
-    
-    def numViolations(self):
-        return self.unfilled() + self.diff()
-
-    def numUnfilled(self):
-        return self.board.count(0)
-    
-    def numDiff(self):
-        invalid = 0
-        for i in range(self.size):
-            if not self.numDiffRow(i): invalid += 1
-            if not self.numDiffColl(i): invalid += 1
-            if not self.numDiffBox(i): invalid += 1
-        return invalid
-    
-    def numDiffRow(self, row):
-        s = self.size
-        num = 0
-        for i in s:
-            for j in s:
-                if self.get(row, i) == self.get(row, j):
-                    num += 1
-        return num
-    
-    def numDiffColl(self, col):
-        return unique([self.get(i, col) for i in range(self.size)])
-    
-    def numDiffBox(self, box):
-        return unique([self.get(i, j) for (i, j) in self.boxIndices(box)])
-    
-    def boxIndices(self, box):
-        w = self.width
-        rs = w*(box//w)
-        cs = w*(box%w)
-        return [(i, j) for i in range(rs, rs+w) for j in range(cs, cs+w)]
-    
+    def toCSP(self, constructor):
+        variables = list(range(len(self.board)))
+        domains = dict()
+        for v in variables:
+            if self.board[v]:
+                domains[v] = [self.board[v]]
+            else:
+                domains[v] = list(range(1,self.size+1))
+        constraints = list()
+        for row in range(self.size):
+            c = csp.AllDiffConstraint([self.idx(row, col) for col in range(self.size)])
+            constraints.append(c)
+        for col in range(self.size):
+            c = csp.AllDiffConstraint([self.idx(row, col) for row in range(self.size)])
+            constraints.append(c)
+        for box in range(self.size):
+            c = csp.AllDiffConstraint([self.idx(row, col) for (row, col) in self.boxIdx(box)])
+            constraints.append(c)
+        return constructor(variables, domains, constraints)
     def __str__(self):
         s = self.size
         t = '+--'*s + '+\n'
                 t += '|%2d' % (self.get(i, j),)
             t += '|\n' + '+--'*s + '+\n'
         return t
-    
     def __repr__(self):
         return str(self)
-
-
-class SolutionNotFound(Exception):
-    def __str__(self):
-        return "Solution not found."
-
-class MaxSolutionDepthExceeded(Exception):
-    def __init__(self, depth):
-        self.depth = depth
-    def __str__(self):
-        return "Max solution depth exceeded %d." % (self.depth,)
-
-
-class BacktrackingSolver(object):
-
-    MAX_CHECKS = 1e7
-
-    def solve(self, b):
-        s = b._size
-        m = s*s - 1
-        domains = [self.initialDomains(b),]
-        backup = array.array('H', b._board)
-        checks = 0
-        
-        pos = 0
-        while True:
-            if pos == 0 and not domains[-1][0]:
-                b._board = backup
-                raise SolutionNotFound
-            if not domains[-1][pos]:
-                domains.pop()
-                pos -= 1
-                continue
-            val = self.valueSelect(domains[-1][pos])
-            b._board[pos] = val
-            if b.complete():
-                return checks
-            domains[-1][pos].remove(val)
-            checks += 1
-            if checks > self.MAX_CHECKS:
-                raise MaxSolutionDepthExceeded(self.MAX_CHECKS)
-            if pos == m:
-                continue
-            else:
-                new_domain = self.inference(b, domains[-1], pos)
-                domains.append(new_domain)
-                pos += 1
-    
-    def initialDomains(self, b):
-        s = b._size
-        domains = [set(range(1, s+1)) for i in range(s*s)]
-        for row in range(s):
-            for col in range(s):
-                val = b.get(row, col)
-                if val != 0:
-                    domains[row*s + col] = set([val,])
-        return domains
-
-    def valueSelect(self, s):
-        for i in s:
-            return i
-
-    def inference(self, b, domain, pos):
-        return copy.deepcopy(domain)
-
-
-class ForwardCheckingSolver(BacktrackingSolver):
-    
-    def inference(self, b, domain, pos):
-        new_domain = copy.deepcopy(domain)
-        s = b._size
-        w = b._width
-        val = b._board[pos]
-
-        row = pos // s
-        col = pos % s
-        for i in range(row+1, s):
-            idx = row*s + i
-            new_domain[idx].discard(val)
-        for i in range(col+1, s):
-            idx = i*s + col
-            new_domain[idx].discard(val)
-
-        box = w*(row//w) + col//w
-        rs = w*(box//w)
-        cs = w*(box%w)
-        for i in range(rs, rs+w):
-            for j in range(cs, cs+w):
-                if i > row and j > col:
-                    idx = i*s + j
-                    new_domain[idx].discard(val)
-        return new_domain
-    
-
+    def __eq__(self, other):
+        return self.size == other.size and self.board == other.board
+
+def cspNumChecks(board, constructor):    
+    problem = board.toCSP(constructor)
+    try:
+        (mapping, checks) = problem.solveWithCount()
+        return str(checks)
+    except csp.SolutionNotFound as e:
+        return str(e)
+    except csp.MaxDepthExceeded as e:
+        return str(e)
 
 if __name__ == "__main__":
-    pass
+    inputs = ['4x4', '9x9', '16x16', '25x25']
+    for f in inputs:
+        fname = "boards/mandatory/%s.sudoku" % (f,)
+        board = Board(filename=fname)
+        print("Test File:", f)
+        print("Board:")
+        print(board)
+        print("Backtracking Checks:", cspNumChecks(board, csp.BacktrackingSolver))
+        print("Arc Consistency Checks:", cspNumChecks(board, csp.ArcConsistencySolver))
+        print("Forward Checking Checks:", cspNumChecks(board, csp.ForwardCheckingSolver))
+            
 
 

src/sudoku/sudoku_test.py

 import tempfile
 import os
 import sudoku
+import csp
 
 class TestEmptyBoard(unittest.TestCase):
     
         self.assertFalse(b.valid())
 
 
+class TestSudokuBacktracking(unittest.TestCase):        
+    SOLVER = csp.BacktrackingSolver
+    
+    def setUp(self): 
+        b = sudoku.Board(size=4)
+        b.set(0, 0, 3)
+        b.set(0, 1, 4)
+        b.set(0, 2, 2)
+        b.set(0, 3, 1)
+        b.set(1, 0, 1)
+        b.set(1, 1, 2)
+        b.set(1, 2, 4)
+        b.set(1, 3, 3)
+        b.set(2, 0, 4)
+        b.set(2, 1, 1)
+        b.set(2, 2, 3)
+        b.set(2, 3, 2)
+        b.set(3, 0, 2)
+        b.set(3, 1, 3)
+        b.set(3, 2, 1)
+        b.set(3, 3, 4)
+        self.b = b
+    
+    def test_easy_CSP(self):
+        p = self.b.toCSP(self.SOLVER)
+        s = sudoku.Board(mapping=p.solve())
+        self.assertEquals(self.b, s)
+    
+    def test_one_removed_CSP(self):
+        self.b.set(0, 0, 0)
+        p = self.b.toCSP(self.SOLVER)
+        s = sudoku.Board(mapping=p.solve())
+        self.b.set(0, 0, 3)
+        self.assertEquals(self.b, s)
+    
+    def test_four_removed_CSP(self):
+        for col in range(4):
+            self.b.set(0, col, 0)
+        p = self.b.toCSP(self.SOLVER)
+        s = sudoku.Board(mapping=p.solve())
+        self.b.set(0, 0, 3)
+        self.b.set(0, 1, 4)
+        self.b.set(0, 2, 2)
+        self.b.set(0, 3, 1)
+        self.assertEquals(self.b, s)
+
+
+class TestSudokuForwardChecking(TestSudokuBacktracking):        
+    SOLVER = csp.ForwardCheckingSolver
+
+class TestSudokuArcConsistency(TestSudokuBacktracking):        
+    SOLVER = csp.ArcConsistencySolver
+
+
 if __name__ == "__main__":
     unittest.main()