285 lines
10 KiB
Python
285 lines
10 KiB
Python
from typing import Final, Generator, Iterator, Optional
|
||
import random
|
||
from dataclasses import dataclass
|
||
|
||
# Use a cryptographically secure random number generator
|
||
rnd = random.SystemRandom()
|
||
|
||
# Sentinel value to represent an empty/unfilled cell in the grid during solving
|
||
EMPTY: Final = -1
|
||
|
||
# Predefined 8x8 grid of integers (0–6), representing a domino puzzle board
|
||
tableau = [
|
||
[0, 5, 1, 3, 2, 2, 3, 1],
|
||
[0, 5, 5, 0, 5, 2, 4, 6],
|
||
[4, 3, 0, 3, 6, 6, 2, 0],
|
||
[0, 6, 2, 3, 5, 1, 2, 6],
|
||
[1, 1, 3, 0, 0, 2, 4, 5],
|
||
[2, 1, 4, 3, 3, 4, 6, 6],
|
||
[6, 4, 5, 1, 5, 4, 1, 4]
|
||
]
|
||
# Randomly generated 8x8 grid using values 0–6 for testing alternative puzzles
|
||
customTableau = [[rnd.randint(0, 6) for _ in range(8)] for _ in range(8)]
|
||
|
||
# # Represents a domino tile with two ends (a and b).
|
||
# It is treated as unordered (i.e., (1,2) == (2,1)) via custom hash and equality.
|
||
@dataclass(frozen=True)
|
||
class Domino:
|
||
a: int
|
||
b: int
|
||
|
||
# Hash based on sorted tuple so (a,b) and (b,a) are considered the same domino
|
||
def __hash__(self) -> int:
|
||
return hash(tuple(sorted((self.a, self.b))))
|
||
|
||
# String representation for debugging/printing
|
||
def __repr__(self) -> str:
|
||
return f"({self.a},{self.b})"
|
||
|
||
# Represents a coordinate (x, y) on the grid
|
||
@dataclass
|
||
class Point:
|
||
x: int
|
||
y: int
|
||
|
||
def __repr__(self) -> str:
|
||
return f"({self.x},{self.y})"
|
||
|
||
# Bundles a solved layout: the filled grid, list of placed dominoes, and their positions
|
||
@dataclass
|
||
class Pattern:
|
||
tableau: list[list[int]] # Final filled grid (copied from solver state)
|
||
dominoes: list[Domino] # List of dominoes used (in placement order)
|
||
points: list[Point] # Paired list of points indicating domino placements
|
||
|
||
def findPatterns(
|
||
source: list[list[int]],
|
||
*,
|
||
maxSolutions: Optional[int] = None,
|
||
asGenerator: bool = False
|
||
) -> Iterator[Pattern] | list[Pattern]:
|
||
"""
|
||
Solves a domino tiling puzzle where each domino must be unique (unordered pair),
|
||
and every cell must be covered exactly once.
|
||
|
||
Args:
|
||
source: 2D grid of integers (0-6) representing the puzzle.
|
||
maxSolutions: Optional limit on number of solutions to find.
|
||
asGenerator: If True, returns a generator yielding solutions one by one;
|
||
otherwise returns a list of all found solutions (up to maxSolutions).
|
||
|
||
Returns:
|
||
Either a list of Pattern objects or a generator yielding them.
|
||
"""
|
||
nRows = len(source)
|
||
assert nRows > 0
|
||
nCols = len(source[0])
|
||
# Ensure all rows have the same length
|
||
for row in source:
|
||
if len(row) != nCols:
|
||
raise ValueError("All rows must have same length")
|
||
|
||
# Total number of dominoes needed to cover the board
|
||
dominoGoal = (nRows * nCols) // 2
|
||
# If total cells is odd, tiling is impossible
|
||
if (nRows * nCols) % 2 != 0:
|
||
return []
|
||
|
||
# Working grid: EMPTY (-1) means not yet covered
|
||
grid = [[EMPTY for _ in range(nCols)] for _ in range(nRows)]
|
||
usedDominoes: set[Domino] = set() # For O(1) uniqueness checks
|
||
usedDominoesList: list[Domino] = [] # To preserve order of placement
|
||
points: list[Point] = [] # Stores paired coordinates of domino placements
|
||
solutions: list[Pattern] = [] # Accumulates found solutions
|
||
|
||
def findFirstEmpty(startIndex: int = 0) -> Optional[int]:
|
||
"""Find the first empty cell in row-major order starting from `startIndex`."""
|
||
total = nRows * nCols
|
||
for i in range(startIndex, total):
|
||
r = i // nCols
|
||
c = i % nCols
|
||
if grid[r][c] == EMPTY:
|
||
return i
|
||
return # No empty cell found
|
||
|
||
def collectSolution() -> Pattern:
|
||
"""Create a deep copy of the current solution state."""
|
||
tableauCopy = [row[:] for row in grid]
|
||
return Pattern(tableauCopy, usedDominoesList.copy(), points.copy())
|
||
|
||
def dfs(startIndex: int = 0):
|
||
"""
|
||
Depth-first search to place dominoes recursively.
|
||
Stops early if `maxSolutions` is reached.
|
||
"""
|
||
if maxSolutions is not None and len(solutions) >= maxSolutions:
|
||
return
|
||
|
||
index = findFirstEmpty(startIndex)
|
||
if index is None:
|
||
# All cells filled — check if we used exactly the right number of dominoes
|
||
if len(usedDominoesList) == dominoGoal:
|
||
solutions.append(collectSolution())
|
||
return
|
||
|
||
r = index // nCols
|
||
c = index % nCols
|
||
|
||
# Try placing a vertical domino (downwards)
|
||
if r + 1 < nRows and grid[r+1][c] == EMPTY:
|
||
d = Domino(source[r][c], source[r+1][c])
|
||
if d not in usedDominoes:
|
||
# Place domino
|
||
grid[r][c] = source[r][c]
|
||
grid[r+1][c] = source[r+1][c]
|
||
usedDominoes.add(d)
|
||
usedDominoesList.append(d)
|
||
points.extend([Point(r, c), Point(r+1, c)])
|
||
|
||
dfs(index+1)
|
||
|
||
# Backtrack
|
||
points.pop()
|
||
points.pop()
|
||
usedDominoesList.pop()
|
||
usedDominoes.remove(d)
|
||
grid[r][c] = EMPTY
|
||
grid[r+1][c] = EMPTY
|
||
|
||
# Early exit if enough solutions found
|
||
if maxSolutions is not None and len(solutions) >= maxSolutions:
|
||
return
|
||
|
||
# Try placing a horizontal domino (rightwards)
|
||
if c + 1 < nCols and grid[r][c+1] == EMPTY:
|
||
d = Domino(source[r][c], source[r][c+1])
|
||
if d not in usedDominoes:
|
||
# Place domino
|
||
grid[r][c] = source[r][c]
|
||
grid[r][c+1] = source[r][c+1]
|
||
usedDominoes.add(d)
|
||
usedDominoesList.append(d)
|
||
points.extend([Point(r, c), Point(r, c+1)])
|
||
|
||
dfs(index+1)
|
||
|
||
# Backtrack
|
||
points.pop()
|
||
points.pop()
|
||
usedDominoesList.pop()
|
||
usedDominoes.remove(d)
|
||
grid[r][c] = EMPTY
|
||
grid[r][c+1] = EMPTY
|
||
|
||
# Early exit if enough solutions found
|
||
if maxSolutions is not None and len(solutions) >= maxSolutions:
|
||
return
|
||
|
||
# If requested, return a generator instead of collecting all solutions upfront
|
||
if asGenerator:
|
||
def gen() -> Generator:
|
||
def dfsGen(startIndex: int = 0) -> Generator:
|
||
"""Generator version of DFS that yields solutions as they are found."""
|
||
index = findFirstEmpty(startIndex)
|
||
if index is None:
|
||
if len(usedDominoesList) == dominoGoal:
|
||
yield collectSolution()
|
||
return
|
||
r = index // nCols
|
||
c = index % nCols
|
||
|
||
# Vertical placement
|
||
if r + 1 < nRows and grid[r+1][c] == EMPTY:
|
||
d = Domino(source[r][c], source[r+1][c])
|
||
if d not in usedDominoes:
|
||
grid[r][c] = source[r][c]
|
||
grid[r+1][c] = source[r+1][c]
|
||
usedDominoes.add(d)
|
||
usedDominoesList.append(d)
|
||
points.extend([Point(r, c), Point(r+1, c)])
|
||
|
||
yield from dfsGen(index+1)
|
||
|
||
# Backtrack
|
||
points.pop()
|
||
points.pop()
|
||
usedDominoesList.pop()
|
||
usedDominoes.remove(d)
|
||
grid[r][c] = EMPTY
|
||
grid[r+1][c] = EMPTY
|
||
|
||
# Horizontal placement
|
||
if c + 1 < nCols and grid[r][c+1] == EMPTY:
|
||
d = Domino(source[r][c], source[r][c+1])
|
||
if d not in usedDominoes:
|
||
grid[r][c] = source[r][c]
|
||
grid[r][c+1] = source[r][c+1]
|
||
usedDominoes.add(d)
|
||
usedDominoesList.append(d)
|
||
points.extend([Point(r, c), Point(r, c+1)])
|
||
|
||
yield from dfsGen(index+1)
|
||
|
||
# Backtrack
|
||
points.pop()
|
||
points.pop()
|
||
usedDominoesList.pop()
|
||
usedDominoes.remove(d)
|
||
grid[r][c] = EMPTY
|
||
grid[r][c+1] = EMPTY
|
||
|
||
yield from dfsGen(0)
|
||
|
||
return gen()
|
||
|
||
# Run standard DFS and return collected solutions
|
||
dfs(0)
|
||
return solutions
|
||
|
||
def printLayout(pattern: Pattern):
|
||
"""
|
||
Pretty-prints a solved domino layout with ASCII art:
|
||
- Numbers represent tile values.
|
||
- '-' connects horizontally adjacent domino halves.
|
||
- '|' connects vertically adjacent domino halves.
|
||
"""
|
||
nRows = len(pattern.tableau)
|
||
nCols = len(pattern.tableau[0]) if nRows > 0 else 0
|
||
|
||
# Create a character grid large enough to show connections
|
||
output = [[" " for _ in range(nCols*3-1)] for _ in range(nRows*2-1)]
|
||
|
||
# Place numbers in the output grid
|
||
for i in range(nRows):
|
||
for j in range(nCols):
|
||
val = pattern.tableau[i][j]
|
||
ch = "?" if val == EMPTY else str(val)
|
||
output[i*2][j*3] = ch
|
||
|
||
# Draw connections between paired points (domino halves)
|
||
for k in range(0, len(pattern.points), 2):
|
||
if k + 1 >= len(pattern.points):
|
||
break
|
||
|
||
p0 = pattern.points[k]
|
||
p1 = pattern.points[k+1]
|
||
|
||
# Horizontal domino: same row, adjacent columns
|
||
if p0.x == p1.x and p0.y + 1 == p1.y:
|
||
output[p0.x*2][p0.y*3+1] = "-"
|
||
output[p0.x*2][p0.y*3+2] = "-"
|
||
# Vertical domino: same column, adjacent rows
|
||
elif p0.y == p1.y and p0.x+1 == p1.x:
|
||
output[p0.x*2+1][p0.y*3] = "|"
|
||
|
||
# Print the final layout line by line
|
||
for line in output:
|
||
print("".join(line))
|
||
|
||
# Entry point: solve both the predefined and random tableaus, print first solution if found
|
||
if __name__ == "__main__":
|
||
for t in [tableau, customTableau]:
|
||
sols = findPatterns(t, maxSolutions=1)
|
||
print(f"Layouts found: {len(sols)}")
|
||
if len(sols) > 0:
|
||
printLayout(sols[0])
|