Skip to content

Instantly share code, notes, and snippets.

@ttencate
Created August 20, 2016 11:50
Show Gist options
  • Save ttencate/906d4a6466b12d2c84288af344a2fcc0 to your computer and use it in GitHub Desktop.
Save ttencate/906d4a6466b12d2c84288af344a2fcc0 to your computer and use it in GitHub Desktop.
Finds arrangements of rooms in a 4x4 grid using all possible room types, where each wall either has a door or not
#!/usr/bin/python3
class Piece:
def __init__(self, mask):
self.up = bool(mask & 1)
self.down = bool(mask & 2)
self.left = bool(mask & 4)
self.right = bool(mask & 8)
def line(self, i):
if i == 0:
return ' %s ' % ('|' if self.up else ' ')
if i == 1:
return '%s+%s' % ('-' if self.left else ' ', '-' if self.right else ' ')
if i == 2:
return ' %s ' % ('|' if self.down else ' ')
Piece.EMPTY = Piece(0)
class Grid:
def __init__(self, rows, cols):
self.rows = rows
self.cols = cols
self.cells = [[None for col in range(cols)] for row in range(rows)]
def get(self, row, col):
if row < 0 or row >= self.rows or col < 0 or col >= self.cols:
return Piece.EMPTY
return self.cells[row][col] or Piece.EMPTY
def set(self, row, col, piece):
self.cells[row][col] = piece
def is_symmetric(self):
for row in range(self.rows):
for col in range(self.cols):
a = self.get(row, col)
b = self.get(col, row)
if a.up != b.left or a.down != b.right:
return False
return True
def __str__(self):
lines = []
for row in range(self.rows):
for i in range(3):
line = []
for col in range(self.cols):
line.append(self.get(row, col).line(i))
lines.append(''.join(line))
return '\n'.join(lines)
def solve(pieces, grid, row, col):
if row >= grid.rows:
if grid.is_symmetric():
print(grid)
return 1
count = 0
for i in range(len(pieces)):
piece = pieces[i]
if piece is None:
continue
if (piece.left == grid.get(row, col - 1).right and
piece.up == grid.get(row - 1, col).down):
pieces[i] = None
grid.set(row, col, piece)
if col == grid.cols - 1:
next_row = row + 1
next_col = 0
else:
next_row = row
next_col = col + 1
count += solve(pieces, grid, next_row, next_col)
grid.set(row, col, None)
pieces[i] = piece
return count
count = solve([Piece(i) for i in range(16)], Grid(4, 4), 0, 0)
print('%d solutions found' % count)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment