Skip to content

Instantly share code, notes, and snippets.

@mbrenig
Created September 13, 2018 20:45
Show Gist options
  • Save mbrenig/a4a9c66ce50e9a018dbda3be99518081 to your computer and use it in GitHub Desktop.
Save mbrenig/a4a9c66ce50e9a018dbda3be99518081 to your computer and use it in GitHub Desktop.
sumation sodoku solver - with python-constraint
# pip install python-constraint
from constraint import Problem, AllDifferentConstraint, ExactSumConstraint
DIGITS = range(1, 10)
COLS = "ABCDEFGHI"
ROWS = "123456789"
COL_GRP = ["ABC", "DEF", "GHI"]
ROW_GRP = ["123", "456", "789"]
CELLS = []
for cg in COL_GRP:
for rg in ROW_GRP:
CELLS.append([f"{col}{row}" for col in cg for row in rg])
# Set up a blank board....
problem = Problem()
for col in COLS:
for row in ROWS:
problem.addVariable(f"{col}{row}", DIGITS)
# Set up the basic sodoku rules...
for col in COLS:
problem.addConstraint(
AllDifferentConstraint(), variables=[f"{col}{row}" for row in ROWS]
)
for row in ROWS:
problem.addConstraint(
AllDifferentConstraint(), variables=[f"{col}{row}" for col in COLS]
)
for cellmembers in CELLS:
problem.addConstraint(AllDifferentConstraint(), variables=cellmembers)
# Print the solution in a nice way....
def print_soln(solution):
for row in ROWS:
row_str = " ".join([str(solution[f"{col}{row}"]) for col in COLS])
print(row_str)
# Add the summation rules...
problem.addConstraint(ExactSumConstraint(17), variables=["A1", "A2"])
problem.addConstraint(ExactSumConstraint(13), variables=["B1", "B2", "C1"])
problem.addConstraint(ExactSumConstraint(21), variables=["D1", "E1", "E2", "F2"])
problem.addConstraint(
ExactSumConstraint(32), variables=["F1", "G1", "G2", "G3", "F3", "F4"]
)
problem.addConstraint(ExactSumConstraint(20), variables=["H1", "I1", "H2", "H3", "H4"])
problem.addConstraint(ExactSumConstraint(12), variables=["C2", "D2"])
problem.addConstraint(ExactSumConstraint(18), variables=["I2", "I3", "I4", "I5"])
problem.addConstraint(ExactSumConstraint(13), variables=["A3", "A4", "B3"])
problem.addConstraint(ExactSumConstraint(10), variables=["C3", "D3"])
problem.addConstraint(ExactSumConstraint(19), variables=["E3", "E4", "E5", "E6", "E7"])
problem.addConstraint(ExactSumConstraint(35), variables=["B4", "B5", "C4", "C5", "C6"])
problem.addConstraint(ExactSumConstraint(11), variables=["D4", "D5"])
problem.addConstraint(ExactSumConstraint(28), variables=["G4", "G5", "G6", "H5", "H6"])
problem.addConstraint(ExactSumConstraint(11), variables=["A5", "A6", "A7", "A8"])
problem.addConstraint(ExactSumConstraint(11), variables=["F5", "F6"])
problem.addConstraint(ExactSumConstraint(24), variables=["B6", "B7", "B8", "B9", "A9"])
problem.addConstraint(
ExactSumConstraint(24), variables=["D6", "D7", "C7", "C8", "C9", "D9"]
)
problem.addConstraint(ExactSumConstraint(14), variables=["I7", "I6", "H7"])
problem.addConstraint(ExactSumConstraint(12), variables=["F7", "G7"])
problem.addConstraint(ExactSumConstraint(22), variables=["D8", "E8", "E9", "F9"])
problem.addConstraint(ExactSumConstraint(8), variables=["G8", "F8"])
problem.addConstraint(ExactSumConstraint(15), variables=["H9", "H8", "G9"])
problem.addConstraint(ExactSumConstraint(15), variables=["I9", "I8"])
print("This takes a while...")
solutions = problem.getSolution()
print_soln(solutions)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment