Skip to content

Instantly share code, notes, and snippets.

@lucaswiman
Last active November 4, 2019 05:52
Show Gist options
  • Save lucaswiman/f6769d2e866407dd784d1f29d3556771 to your computer and use it in GitHub Desktop.
Save lucaswiman/f6769d2e866407dd784d1f29d3556771 to your computer and use it in GitHub Desktop.
python-constraint sudoku solver
from constraint import *
ROWS = 'abcdefghi'
COLS = '123456789'
DIGITS = range(1, 10)
VARS = [row + col for row in ROWS for col in COLS]
ROWGROUPS = [[row + col for col in COLS] for row in ROWS]
COLGROUPS = [[row + col for row in ROWS] for col in COLS]
SQUAREGROUPS = [
[ROWS[3 * rowgroup + k] + COLS[3 * colgroup + j]
for j in range(3) for k in range(3)]
for colgroup in range(3) for rowgroup in range(3)
]
def solve(hints):
problem = Problem()
for var, hint in zip(VARS, hints):
problem.addVariables([var], [hint] if hint in DIGITS else DIGITS)
for vargroups in [ROWGROUPS, COLGROUPS, SQUAREGROUPS]:
for vargroup in vargroups:
problem.addConstraint(AllDifferentConstraint(), vargroup)
return problem.getSolution()
def pretty(var_to_value):
board = ''
for rownum, row in enumerate('abcdefghi'):
for colnum, col in enumerate('123456789'):
board += str(var_to_value[row+col])
if colnum % 3 == 2:
board += ' '
board += '\n'
if rownum % 3 == 2:
board += '\n'
return board
hints = (
0, 0, 8, 0, 0, 6, 0, 0, 0,
0, 0, 4, 3, 7, 9, 8, 0, 0,
5, 7, 0, 0, 1, 0, 3, 2, 0,
0, 5, 2, 0, 0, 7, 0, 0, 0,
0, 6, 0, 5, 9, 8, 0, 4, 0,
0, 0, 0, 4, 0, 0, 5, 7, 0,
0, 2, 1, 0, 4, 0, 0, 9, 8,
0, 0, 9, 6, 2, 3, 1, 0, 0,
0, 0, 0, 9, 0, 0, 7, 0, 0,
)
print pretty(solve(hints))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment