Loading [Contrib]/a11y/accessibility-menu.js
  1. CSPLib
  2. Problems
  3. prob032
  4. Models
  5. StillLife.py

032: Maximum density still life

Download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
"""
PyCSP3 Model (see pycsp.org)
 
Examples:
  python StillLife.py
  python StillLife.py -data=[7,7]
  python StillLife.py -data=[7,7] -variant=wastage
"""
 
from pycsp3 import *
 
n, m = data or (8, 8)
 
 
if not variant():
    table = {(v, 0) for v in range(9) if v != 3} | {(2, 1), (3, 1)}
 
 
    def scope(i, j):
        return [x[k][l] for k in range(n) for l in range(m) if i - 1 <= k <= i + 1 and j - 1 <= l <= j + 1 and (k, l) != (i, j)]
 
 
    # x[i][j] is 1 iff the cell at row i and col j is alive
    x = VarArray(size=[n, m], dom={0, 1})
 
    # a[i][j] is the number of alive neighbours
    a = VarArray(size=[n, m], dom=range(9))
 
    satisfy(
        # computing the numbers of alive neighbours
        [Sum(scope(i, j)) == a[i][j] for i in range(n) for j in range(m)],
 
        # imposing rules of the game
        [(a[i][j], x[i][j]) in table for i in range(n) for j in range(m)],
 
        # imposing rules for ensuring valid dead cells around the board
        [
            [x[0][i:i + 3] != (1, 1, 1) for i in range(m - 2)],
            [x[-1][i: i + 3] != (1, 1, 1) for i in range(m - 2)],
            [x[i:i + 3, 0] != (1, 1, 1) for i in range(n - 2)],
            [x[i:i + 3, - 1] != (1, 1, 1) for i in range(n - 2)]
        ],
 
        # tag(symmetry-breaking)
        (x[0][0] >= x[n - 1][n - 1], x[0][n - 1] >= x[n - 1][0]) if n == m else None
    )
 
    maximize(
        # maximizing the number of alive cells
        Sum(x)
    )
 
elif variant("wastage"):
    assert n == m
 
 
    def condition_for_tuple(t0, t1, t2, t3, t4, t5, t6, t7, t8, wa):
        s3 = t1 + t3 + t5 + t7
        s1 = t0 + t2 + t6 + t8 + s3
        s2 = t0 * t2 + t2 * t8 + t8 * t6 + t6 * t0 + s3
        return (t4 != 1 or (2 <= s1 <= 3 and (s2 > 0 or wa >= 2) and (s2 > 1 or wa >= 1))) and \
               (t4 != 0 or (s1 != 3 and (0 < s3 < 4 or wa >= 2)) and (s3 > 1 or wa >= 1))
 
 
    table = {(*t, i) for t in product(range(2), repeat=9) for i in range(3) if condition_for_tuple(*t, i)}
 
    # x[i][j] is 1 iff the cell at row i and col j is alive (note that there is a border)
    x = VarArray(size=[n + 2, n + 2], dom=lambda i, j: {0} if i in {0, n + 1} or j in {0, n + 1} else {0, 1})
 
    # w[i][j] is the wastage for the cell at row i and col j
    w = VarArray(size=[n + 2, n + 2], dom={0, 1, 2})
 
    # ws[i] is the wastage sum for cells at row i
    ws = VarArray(size=n + 2, dom=range(2 * (n + 2) * (n + 2) + 1))
 
    satisfy(
        # ensuring that cells at the border remain dead
        [
            [x[1][j:j + 3] != (1, 1, 1) for j in range(n)],
            [x[n][j:j + 3] != (1, 1, 1) for j in range(n)],
            [x[i:i + 3, 1] != (1, 1, 1) for i in range(n)],
            [x[i:i + 3, n] != (1, 1, 1) for i in range(n)]
        ],
 
        # still life + wastage constraints
        [(x[i - 1:i + 2, j - 1:j + 2], w[i][j]) in table for i in range(1, n + 1) for j in range(1, n + 1)],
 
        # managing wastage on the border
        [
            [(w[0][j] + x[1][j] == 1, w[n + 1][j] + x[n][j] == 1) for j in range(1, n + 1)],
            [(w[i][0] + x[i][1] == 1, w[i][n + 1] + x[i][n] == 1) for i in range(1, n + 1)],
        ],
 
        # summing wastage
        [Sum(w[0] if i == 0 else [ws[i - 1], w[i]]) == ws[i] for i in range(n + 2)],
 
        # tag(redundant-constraints)
        [ws[n + 1] - ws[i] >= 2 * ((n - i) // 3) + n // 3 for i in range(n + 1)]
    )
 
    maximize(
        # maximizing the number of alive cells
        (2 * n * n + 4 * n - ws[-1]) // 4
    )