Created
August 5, 2021 06:50
-
-
Save dimaqq/31b1545bed0d834ae3aca235c3cba760 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from collections import Counter | |
from pprint import pprint | |
BOARD = """ | |
a a a a b | |
c c c a b | |
d d c b b | |
d e c c c | |
d e e e c | |
""".strip().splitlines() | |
BOARD = [s.strip().split() for s in BOARD] | |
BLOCKS = {} | |
for y, line in enumerate(BOARD): | |
for x, c in enumerate(line): | |
BLOCKS.setdefault(c, []) | |
BLOCKS[c].append((x, y)) | |
def debug(): | |
for k, block in BLOCKS.items(): | |
print() | |
print(k) | |
for x, y in block: | |
print(x, y, BOARD[y][x]) | |
board = [[None] * 5 for _ in range(5)] | |
def row(y): | |
return [(x, y) for x in range(5)] | |
def column(x): | |
return [(x, y) for y in range(5)] | |
def unique(blocks): | |
d = Counter(board[y][x] for x, y in blocks) | |
del d[None] | |
return all(v == 1 for v in d.values()) | |
def shape(i): | |
return list(BLOCKS.values())[i] | |
def total(blocks): | |
low = sum(board[y][x] or 1 for x, y in blocks) | |
high = sum(board[y][x] or 5 for x, y in blocks) | |
return low <= 15 <= high | |
def check(): | |
return all( | |
unique(row(i)) and | |
total(row(i)) and | |
unique(column(i)) and | |
total(column(i)) and | |
total(shape(i)) for i in range(5)) | |
INDICES = tuple((x, y) for x in range(5) for y in range(5)) | |
def recur(indices): | |
if not indices: | |
return solution() | |
x, y = indices[0] | |
for v in range(1, 6): | |
board[y][x] = v | |
if check(): | |
recur(indices[1:]) | |
board[y][x] = None | |
def solution(): | |
assert all(board[y][x] is not None for x in range(5) for y in range(5)) | |
pprint(board) | |
recur(INDICES) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Generates a single result: