bruteforce-grid.py

#!/usr/bin/env python3


# change params here

N = 3
M = 3
PRINT_UNIQUE_ANSWERS = True


##############################################################################

def transpose(grid):
    return tuple(zip(*grid))

def rotate(grid):
    return transpose(reversed(grid))


class Grid(object):
    @staticmethod
    def slot(n, m):
        return 2*n*m - n - m

    def __init__(self, n, m):
        self.n, self.m = sorted([n, m])
        self.grid = [['. '[i%2 or j%2] for j in range(2*self.m-1)] for i in range(2*self.n-1)]

    def __str__(self):
        return '\n'.join(''.join(row) for row in self.grid)

    def iter_line(self):
        for i in range(2*self.n-1):
            for j in range(2*self.m-1):
                if i % 2 ^ j % 2:
                    yield i, j

    def iter_cell(self):
        for i in range(2*self.n-1):
            for j in range(2*self.m-1):
                if i % 2 != 0 and j % 2 != 0:
                    yield i, j

    def load(self, config):
        for c, (i, j) in zip(config, self.iter_line()):
            self.grid[i][j] = ' X'[c]
        return self

    def conflict_cell(self, i, j):
        return sum(self.grid[x][y] != ' ' for x, y in ((i-1,j), (i,j-1), (i+1,j), (i,j+1))) >= 3

    def fillable_line(self, i, j):
        if self.grid[i][j] != ' ':
            return False
        if i % 2 == 0:
            if i > 0:
                if sum(self.grid[x][y] != ' ' for x, y in ((i-1,j-1), (i-2,j), (i-1,j+1))) >= 2:
                    return False
            if i < 2*self.n-2:
                if sum(self.grid[x][y] != ' ' for x, y in ((i+1,j-1), (i+2,j), (i+1,j+1))) >= 2:
                    return False
            return True
        else:
            if j > 0:
                if sum(self.grid[x][y] != ' ' for x, y in ((i-1,j-1), (i,j-2), (i+1,j-1))) >= 2:
                    return False
            if j < 2*self.m-2:
                if sum(self.grid[x][y] != ' ' for x, y in ((i-1,j+1), (i,j+2), (i+1,j+1))) >= 2:
                    return False
            return True
        return

    def is_final(self):
        return ( all(not self.conflict_cell(i, j) for i, j in self.iter_cell())
             and all(not self.fillable_line(i, j) for i, j in self.iter_line()) )

    def is_unique(self, answers):
        tg = transpose(self.grid)
        for _ in range(2):
            for _ in range(4):
                if tg in answers:
                    return False
                tg = rotate(tg)
            tg = transpose(tg)
        return True


def compact_show(g):
    for row in g:
        print(''.join(row))


def cleary_show(g, hscale=5, vscale=3):
    for i, row in enumerate(g):
        display_row = ''.join((1 if j % 2 == 0 else hscale)*cell for j, cell in enumerate(row))
        print(display_row)
        if i % 2 != 0:
            for _ in range(vscale-1):
                print(display_row)


##############################################################################

slot = Grid.slot(N, M)
print(f'There are {2**slot:,} tasks to test.')

answers = []
for i in range(2**slot):
    if i % 2**16 == 0: print(f'progress: {i:,}/{2**slot:,}')
    config = [x == '1' for x in format(i, f'0{slot}b')]
    g = Grid(N, M).load(config)
    if g.is_final():
        answers += [g]
print('All possible answers are:', len(answers))

unique_answers = set()
for g in answers:
    if g.is_unique(unique_answers):
        unique_answers |= {transpose(transpose(g.grid))}
print('Only unique answers are:', len(unique_answers))


if PRINT_UNIQUE_ANSWERS:
    print()
    print()
    print()
    for i, g in enumerate(sorted(unique_answers)):
        print('====', i, '==================================================')
        print()
        cleary_show(g)
        print()
        print()
        print()