Source

python-ai / src / sudoku / csp_test.py

Full commit
#!/usr/bin/env python

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())
        self.assertTrue(c.satisfied({0: 0}))
    def testUnivariateAllDiff(self):
        c = AllDiffConstraint([0])
        self.assertTrue(c.satisfied({0: 6}))
    def testAllDiff(self):
        c = AllDiffConstraint([0, 1, 2, 3])
        self.assertTrue(c.satisfied({0: 4, 1: 7, 2: 5, 3: 6}))
    def testAllSame(self):
        c = AllDiffConstraint([0, 1, 2, 3])
        self.assertFalse(c.satisfied({0: 6, 1: 6, 2: 6, 3: 6}))
    def testSomeSame(self):
        c = AllDiffConstraint([0, 1, 2, 3])
        self.assertFalse(c.satisfied({0: 4, 1: 7, 2: 3, 3: 7}))
    def testNotInMapping(self):
        c = AllDiffConstraint([0, 1, 2, 3])
        self.assertFalse(c.satisfied({0: 4, 1: 7}))


class TestCSPSolver(unittest.TestCase):
    def testTriviallySolveNoConstraintsNoVariables(self):
        vs = []
        ds = {}
        cs = []
        s = CSPSolver(vs, ds, cs)
        self.assertEqual(s.solve(), {})
    def testTriviallyUnsolvableUnspecifiedDomain(self):
        vs = [0,1,2]
        ds = {0: [0], 1: [1]}
        cs = []
        s = CSPSolver(vs, ds, cs)
        with self.assertRaises(SolutionNotFound):
            s.solve()
    def testTriviallyUnsolvableEmptyDomain(self):
        vs = [0,1,2]
        ds = {0: [0], 1: [1], 2: []}
        cs = []
        s = CSPSolver(vs, ds, cs)
        with self.assertRaises(SolutionNotFound):
            s.solve()


class TestBacktrackingSolver(unittest.TestCase):
    def testNoConstraintsLimitedDomain(self):
        vs = [0,1,2]
        ds = {0: [0], 1: [1], 2: [2]}
        cs = []
        s = BacktrackingSolver(vs, ds, cs)
        self.assertEqual(s.solve(), {0:0, 1:1, 2:2})
    def testNoConstraintsWideDomain(self):
        vs = [0,1,2]
        ds = {0: [0,1,2], 1: [0,1,2], 2: [0,1,2]}
        cs = []
        s = BacktrackingSolver(vs, ds, cs)
        solution = s.solve()
        self.assertIn(solution[0], [0,1,2])
        self.assertIn(solution[1], [0,1,2])
        self.assertIn(solution[2], [0,1,2])
    def testAllDiffConstraintsLimitedDomain(self):
        vs = [0,1,2]
        ds = {0: [0], 1: [1], 2: [2]}
        cs = [AllDiffConstraint([0,1,2])]
        s = BacktrackingSolver(vs, ds, cs)
        self.assertEqual(s.solve(), {0:0, 1:1, 2:2})
    def testImpossibleAllDiffConstraint(self):
        vs = [0,1,2]
        ds = {0: [0], 1: [0,2], 2: [0]}
        cs = [AllDiffConstraint([0,1,2])]
        s = BacktrackingSolver(vs, ds, cs)
        with self.assertRaises(SolutionNotFound):
            s.solve()
    def testOneBacktrack(self):
        vs = [0,1,2]
        ds = {0: [0], 1: [1], 2: [1,2]}
        cs = [AllDiffConstraint([0,1,2])]
        s = BacktrackingSolver(vs, ds, cs)
        self.assertEqual(s.solve(), {0:0, 1:1, 2:2})
    def testTwoBacktrack(self):
        vs = [0,1,2]
        ds = {0: [0], 1: [1,2], 2: [1]}
        cs = [AllDiffConstraint([0,1,2])]
        s = BacktrackingSolver(vs, ds, cs)
        self.assertEqual(s.solve(), {0:0, 1:2, 2:1})
    def testThreeBacktrack(self):
        vs = [0,1,2]
        ds = {0: [0,1], 1: [1,2], 2: [0]}
        cs = [AllDiffConstraint([0,1,2])]
        s = BacktrackingSolver(vs, ds, cs)
        self.assertEqual(s.solve(), {0:1, 1:2, 2:0})


if __name__ == "__main__":
    unittest.main()