solve.py

import sys
sys.path.append("/tmp/Numberjack.0.1.10-11-24/local_lib")
from Numberjack import *
import Mistral

class Puzzle(object):
    def __init__(self, w, h):
        self.model = Model()
        self.width  = w
        self.height = h
        self.vert   = Matrix(w + 1, h)
        self.horiz  = Matrix(w, h + 1)
        self.holes  = [[False] * h for i in xrange(w)]

        self.model  += self.vert[0,h-1] == 1
        self.model  += self.vert[w,0] == 1
        for y in xrange(h):
            if y != h-1:
                self.model += self.vert[0,y] == 0
            if y != 0:
                self.model += self.vert[w,y] == 0

        for x in xrange(w):
            self.model += self.horiz[x,0] == 0
            self.model += self.horiz[x,h] == 0

        for x in xrange(0, w):
            for y in xrange(0, h):
                vars = self.boundaries(x, y)
                self.model += (Sum(vars) == 0) | (Sum(vars) == 2)

    def boundaries(self, x, y):
        return [self.horiz[x,y],
                self.horiz[x,y+1],
                self.vert[x,y],
                self.vert[x+1,y]]

    def all_vars(self):
        return ([v for r in self.horiz for v in r] +
                [v for r in self.vert for v in r])

    def hole(self, x, y):
        self.holes[x][y] = True
        for v in self.boundaries(x, y):
            self.model += (v == 0)

    def rows(self, vals):
        assert(len(vals) == self.height)
        for y, val in enumerate(vals):
            if val is None:
                continue
            self.row(0, y, val)

    def row(self, x0, y, val):
        assert(x0 == 0 or self.holes[x0][y])
        if x0 != 0: x0 += 1
        row = []
        for x in xrange(x0, self.width):
            if self.holes[x][y]: break
            row.append(reduce(lambda a,b: a|b, self.boundaries(x, y)))
        self.model += Sum(row) == val

    def cols(self, vals):
        assert(len(vals) == self.width)
        for x, val in enumerate(vals):
            if val is None:
                continue
            self.col(x, self.height, val)

    def col(self, x, y0, val):
        assert(y0 == self.height or self.holes[x][y0])
        col = []
        for y in xrange(y0 - 1, -1, -1):
            if self.holes[x][y]: break
            col.append(reduce(lambda a,b: a|b, self.boundaries(x, y)))
        self.model += Sum(col) == val

    def solve(self):
        self.solver = Mistral.Solver(self.model,
                                     self.all_vars())
        assert(self.solver.solve())
        self.show()

    def next(self):
        assert(self.solver.getNextSolution())
        self.show()

    def printh(self, y):
        for x in xrange(self.width):
            sys.stdout.write("+")
            if self.horiz[x][y].get_value():
                sys.stdout.write(" ")
            else:
                sys.stdout.write("-")
        sys.stdout.write("-")
        sys.stdout.write(str(y))
        sys.stdout.write("\n")

    def printv(self, y):
        for x in xrange(self.width + 1):
            if self.vert[x][y].get_value():
                sys.stdout.write(" ")
            else:
                sys.stdout.write("|")
            if x == self.width:
                break
            if self.holes[x][y]:
                sys.stdout.write("X")
            else:
                sys.stdout.write(" ")
        sys.stdout.write("\n")

    def show(self):
        print
        self.printh(self.height)
        for i in xrange(self.height):
            self.printv(self.height - 1 - i)
            self.printh(self.height - 1 - i)

# p = Puzzle(8, 8)
# p.rows([4, 3, 3, 6, 4, 4, 5, 4])
# p.cols([3, 4, 3, 3, 6, 3, 5, 6])
# p.solve()

###########################################################

# p = Puzzle(12, 12)
# p.hole(3,6)
# p.hole(3,7)
# 
# p.hole(4,3)
# p.hole(5,3)
# 
# p.hole(8,4)
# p.hole(8,5)
# 
# p.hole(6,8)
# p.hole(7,8)
# 
# p.rows([10, 5, 8, 4, 2, 6, 1, 2, 4, 6, 7, 8])
# p.cols([5, 7, 6, 2, 5, 5, 2, 3, 4, 8, 6, 6])
# 
# 
# p.row(5, 3, 3)
# 
# p.row(3, 6, 6)
# p.row(3, 7, 3)
# 
# p.row(7, 8, 2)
# 
# p.row(8, 4, 2)
# p.row(8, 5, 2)
# 
# p.col(3, 6, 6)
# 
# p.col(4, 3, 1)
# p.col(5, 3, 3)
# 
# p.col(6, 8, 5)
# p.col(7, 8, 4)
# 
# p.col(8, 4, 3)
# 
# p.solve()

###########################################################

# p = Puzzle(12, 12)
# 
# for x in range(3):
#     p.hole(x, 6)
# 
# for x in range(9, 12):
#     p.hole(x, 5)
# 
# for y in range(3):
#     p.hole(6, y)
# 
# for y in range(9, 12):
#     p.hole(5, y)
# 
# p.rows([4, 5, 3, 10, 8, 5, None, 9, 7, 3, 4, 2])
# p.cols([3, 4, 4, 7, 8, None, 6, 9, 10, 3, 5, 2])
# 
# p.row(5, 9,  5)
# p.row(5, 10, 2)
# p.row(5, 11, 5)
# 
# p.row(6, 0, 4)
# p.row(6, 1, 4)
# p.row(6, 2, 3)
# 
# p.row(2, 6, 4)
# 
# p.col(0, 6, 4)
# p.col(1, 6, 3)
# p.col(2, 6, 2)
# 
# p.col(5, 9, 5)
# 
# p.col(9,  5, 4)
# p.col(10, 5, 3)
# p.col(11, 5, 5)
# 
# p.solve()

###########################################################

# p = Puzzle(14, 14)
# 
# p.hole(0, 8)
# p.hole(1, 8)
# 
# p.hole(5, 0)
# p.hole(5, 1)
# 
# p.hole(8, 12)
# p.hole(8, 13)
# 
# p.hole(12, 5)
# p.hole(13, 5)
# 
# p.hole(7, 4)
# p.hole(4, 6)
# p.hole(9, 7)
# p.hole(6, 9)
# 
# p.rows([3, 3, 12, 6, 4, 6, 4, 2, None, 3, 7, 8, 5, 4])
# p.cols([4, 2, 3, 10, 2, 9, 2, 6, None, 4, 7, 4, 6, 5])
# 
# p.row(5, 0, 4)
# p.row(5, 1, 3)
# 
# p.row(7, 4, 1)
# p.row(4, 6, 4)
# p.row(6, 9, 6)
# p.row(9, 7, 4)
# 
# p.row(1, 8, 4)
# 
# p.row(8, 12, 3)
# p.row(8, 13, 5)
# 
# 
# p.col(0, 8, 5)
# p.col(1, 8, 4)
# 
# p.col(4, 6, 4)
# p.col(6, 9, 6)
# p.col(7, 4, 3)
# p.col(9, 7, 3)
# 
# p.col(8, 12, 7)
# 
# p.col(12, 5, 2)
# p.col(13, 5, 3)
# 
# p.solve()


###########################################################