Skip to content

Instantly share code, notes, and snippets.

@MHenderson
Last active November 13, 2016 21:14
Show Gist options
  • Save MHenderson/375a2122f1b77f90e5df to your computer and use it in GitHub Desktop.
Save MHenderson/375a2122f1b77f90e5df to your computer and use it in GitHub Desktop.
Generator of PSSSODLS(n) for Minion 3.
#!/usr/bin/env python
"""PSSSODLS generator.
Usage:
psssodls.py [options] [--] <size>
Options:
-h --help Show this screen.
--version Show version.
-b Include box constraints.
"""
import sys
from math import sqrt
from docopt import docopt
def ell(p):
"""This function takes a pair p = [p[0], p[1]] and returns the string
'l[p[0],p[1]]'."""
return 'l[{},{}]'.format(p[0], p[1])
def ellell(p):
return '[{},{}]'.format(ell(p[0]),ell(p[1]))
def alldiff(p):
"""Returns a string representing an all_different constraint over the
variables in the vector v."""
return 'alldiff({})'.format(ell(p))
def vecneq(p, q):
"""Returns a string representing an vectorised inequality constraint between
the two vectors p and q."""
return 'watchvecneq({}, {})'.format(ellell(p), ellell(q))
def begin(n):
return """\
MINION 3
**VARIABLES**
DISCRETE l[{},{}] {{0..{}}}
**SEARCH**
PRINT ALL
**CONSTRAINTS**
""".format(n, n, n - 1)
def end():
return "**EOF**"
def latin_constraints_str(n):
"""Returns a string containing the latin constraints for a square of size
n."""
s = '# Latin constraints. \n\n'
s += "".join([alldiff([i,'_']) + '\n' + alldiff(['_',i]) + '\n' for i in range(n)])
return s + '\n'
def sdk_positions_box(i,j,p):
row_offset = p * (i-1)
column_offset = p * (j-1)
return [(row_offset + r, column_offset + c) for r in range(p) for c in range(p)]
def box_constraints_str(n):
p = int(sqrt(n))
F = [sdk_positions_box(i,j,p) for i in range(1, p + 1) for j in range(1, p + 1)]
s = '# Box constraints. \n\n'
for p in F:
s += 'alldiff([' + ",".join(ell(q) for q in p) + '])' + '\n'
return s + '\n'
def pandiagonal_sum_a(n, w):
return ",".join([ell([i % n, (i + w) % n]) for i in range(n)])
def pandiagonal_sum_b(n, w):
return ",".join([ell([i % n, (w - i) % n]) for i in range(n)])
def pandiagonality_constraints_str(n):
"""Returns a string containing the pandiagonality constraints for a square
of size n."""
s = '# Pandiagonality constraints. \n\n'
pandiagonal_sum_s = str(n*(n - 1)/2)
for w in range(n):
s += 'sumgeq([{}],{})\n'.format(pandiagonal_sum_a(n, w), pandiagonal_sum_s)
s += 'sumleq([{}],{})\n'.format(pandiagonal_sum_a(n, w), pandiagonal_sum_s)
s += 'sumgeq([{}],{})\n'.format(pandiagonal_sum_b(n, w), pandiagonal_sum_s)
s += 'sumleq([{}],{})\n\n'.format(pandiagonal_sum_b(n, w), pandiagonal_sum_s)
return s
def strongly_symmetric_constraints_str(n):
s = '# Strongly symmetric constraints. \n\n'
for i in range(n):
for j in range(n):
s += 'sumgeq({}, {})\n'.format(ellell([[i,j],[n - 1 - i, n - 1 - j]]), n - 1)
s += 'sumleq({}, {})\n'.format(ellell([[i,j],[n - 1 - i, n - 1 - j]]), n - 1)
s += '\n'
return s
def orthogonality_constraints_str(n):
"""Returns a string containing the orthogonality constraints for a square
of size n."""
F = [[(i,j), (j,i)] for i in range(n) for j in range(n)]
s = '# Orthogonality constraints. \n\n'
s += "".join([vecneq(p, q) + '\n' for p in F for q in F if p > q])
return s + '\n'
def psssodls_string(n, boxes):
"""Returns a string which is the entire Minion 3 format constraint program
for PSSSODLS(n)."""
s = begin(n)
s += latin_constraints_str(n)
if boxes:
s += box_constraints_str(n)
s += pandiagonality_constraints_str(n)
s += strongly_symmetric_constraints_str(n)
s += orthogonality_constraints_str(n)
s += end()
return s
if __name__ == '__main__':
arguments = docopt(__doc__, version='PSSSODLS 1.0')
print(psssodls_string(int(arguments['<size>']), arguments['-b']))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment