Skip to content

Instantly share code, notes, and snippets.

@Tarliton
Created August 23, 2020 02:40
Show Gist options
  • Save Tarliton/0620941c4383085d8ebf10bcf115e0e4 to your computer and use it in GitHub Desktop.
Save Tarliton/0620941c4383085d8ebf10bcf115e0e4 to your computer and use it in GitHub Desktop.
solve sudoku with python constraint
from collections import defaultdict
from constraint import *
example = """.......92
...1...4.
9..24...7
8..7..15.
65.9.1.78
.74..8..6
3...95..1
.8...6...
79.......
"""
example = """.3..78...
....5.3..
6.2..1.7.
7.....12.
.5.....3.
.91.....6
.4.8..6.7
..7.4....
...73..5.
"""
variables_with_value = {}
for i, line in enumerate(example.splitlines()):
for j, val in enumerate(line):
if val != '.':
variables_with_value[f'm{i}{j}'] = int(val)
problem = Problem()
variables = []
groups = []
lines = defaultdict(list)
columns = defaultdict(list)
for q in range(3):
for k in range(3):
group = []
for i in range(3):
for j in range(3):
var = f'm{(q*3)+i}{(k*3)+j}'
variables.append(var)
group.append(var)
lines[f'{q*3 + i}'].append(var)
columns[f'{k*3 + j}'].append(var)
groups.append(group)
variables_pos = {v: i for i, v in enumerate(variables)}
for v in variables:
value = variables_with_value.get(v)
if value is None:
problem.addVariable(v, range(1, 10))
else:
problem.addVariable(v, [value])
for group in groups:
problem.addConstraint(AllDifferentConstraint(), group)
for _, line in lines.items():
problem.addConstraint(AllDifferentConstraint(), line)
for _, column in columns.items():
problem.addConstraint(AllDifferentConstraint(), column)
solution = problem.getSolution()
for i in range(9):
line = []
for j in range(9):
line.append(solution[f'm{i}{j}'])
print(line)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment