基于Python约束满足库Numberjack的彩色方块拼图问题求解求助

Hey there! Your initial idea of using four matrices for the tile sides is spot-on—let's turn that into a concrete, working solution with Numberjack for your colored tile puzzle. Here's a step-by-step breakdown tailored to your problem:

1. Core Problem Modeling #

First, let's formalize the variables we need for each grid cell (i,j):

• Tile(i,j): A variable representing which tile (from 0 to n*m-1) is placed at this cell. Each tile can only be used once.
• Rotate(i,j): A variable representing the rotation of the tile (0 = 0°, 1 = 90° clockwise, 2 = 180°, 3 = 270° clockwise).

Instead of defining separate matrices for north/south/east/west sides directly, we'll derive their colors from the Tile and Rotate variables. This keeps the model lean and avoids redundant variables. For each original tile, we'll store its four side colors as a tuple (north, east, south, west), then calculate rotated colors on the fly.

2. Key Constraints to Implement #

We need three types of constraints to enforce the puzzle rules:

Uniqueness Constraint #

Every tile must be used exactly once. Use Numberjack's AllDifferent constraint to ensure all Tile(i,j) variables have distinct values.

Adjacent Color Matching Constraints #

• Horizontal Neighbors: For any cell (i,j) and its right neighbor (i,j+1), the east side color of the left tile must equal the west side color of the right tile.
• Vertical Neighbors: For any cell (i,j) and its bottom neighbor (i+1,j), the south side color of the top tile must equal the north side color of the bottom tile.

Rotation-to-Color Mapping #

To translate rotation values into actual side colors, we'll precompute all possible (tile, rotation) color combinations. This lets us use Numberjack's Element constraint to fetch the correct color for any variable combination.

3. Full Code Implementation #

Here's a ready-to-use code framework with comments explaining each part:

import Numberjack

def solve_color_tile_puzzle(n, m, original_tiles):
    num_tiles = n * m
    # Initialize variables for each grid cell: tile index and rotation
    Tile = [[Numberjack.Variable(0, num_tiles-1) for j in range(m)] for i in range(n)]
    Rotate = [[Numberjack.Variable(0, 3) for j in range(m)] for i in range(n)]
    
    # Flatten variables for easier constraint setup
    all_tiles = [Tile[i][j] for i in range(n) for j in range(m)]
    
    # Precompute color values for every (tile, rotation) pair
    north_colors = []
    east_colors = []
    south_colors = []
    west_colors = []
    for tile_idx in range(num_tiles):
        n_orig, e_orig, s_orig, w_orig = original_tiles[tile_idx]
        # Rotate clockwise 0-3 times and store resulting side colors
        for rot in range(4):
            # Rotation shifts the original sides: 0° → original, 90° → west becomes north, etc.
            north_colors.append([n_orig, w_orig, s_orig, e_orig][rot])
            east_colors.append([e_orig, n_orig, w_orig, s_orig][rot])
            south_colors.append([s_orig, e_orig, n_orig, w_orig][rot])
            west_colors.append([w_orig, s_orig, e_orig, n_orig][rot])
    
    # Build the CSP model
    model = Numberjack.Model()
    
    # Add uniqueness constraint: all tiles are used exactly once
    model.add(Numberjack.AllDifferent(all_tiles))
    
    # Add horizontal adjacency constraints (left east == right west)
    for i in range(n):
        for j in range(m - 1):
            left_key = Tile[i][j] * 4 + Rotate[i][j]
            right_key = Tile[i][j+1] * 4 + Rotate[i][j+1]
            model.add(Numberjack.Element(east_colors, left_key) == Numberjack.Element(west_colors, right_key))
    
    # Add vertical adjacency constraints (top south == bottom north)
    for i in range(n - 1):
        for j in range(m):
            top_key = Tile[i][j] * 4 + Rotate[i][j]
            bottom_key = Tile[i+1][j] * 4 + Rotate[i+1][j]
            model.add(Numberjack.Element(south_colors, top_key) == Numberjack.Element(north_colors, bottom_key))
    
    # Choose a solver (Mistral, MiniSat, or Gecode work well)
    solver = model.load('Mistral')
    # Optional: Set heuristic to speed up solving (min domain, max degree)
    solver.setHeuristic(Numberjack.Heuristic.MinDomain, Numberjack.Heuristic.MaxDegree)
    
    # Run the solver
    solver.solve()
    
    # Output results
    if solver.is_sat():
        print("Solution found! 🎉")
        for row_idx in range(n):
            tile_values = [Tile[row_idx][col].get_value() for col in range(m)]
            rot_values = [Rotate[row_idx][col].get_value() for col in range(m)]
            print(f"Row {row_idx + 1}: Tiles = {tile_values}, Rotations = {rot_values}")
            # Optional: Print side colors to verify
            row_north = [north_colors[t*4 + r] for t, r in zip(tile_values, rot_values)]
            row_south = [south_colors[t*4 + r] for t, r in zip(tile_values, rot_values)]
            print(f"  North colors: {row_north}")
            print(f"  South colors: {row_south}\n")
    else:
        print("No valid solution exists for this puzzle.")

# Example usage: 2x2 puzzle with sample tiles
if __name__ == "__main__":
    # Each tile is (north, east, south, west) color values
    sample_tiles = [
        (1, 2, 3, 4),
        (3, 2, 1, 4),
        (4, 1, 2, 3),
        (2, 3, 4, 1)
    ]
    solve_color_tile_puzzle(2, 2, sample_tiles)

4. Tips for Optimization #

• Solver Choice: For larger grids (e.g., 4x4 or bigger), use the Gecode solver instead of Mistral—it's faster for complex CSPs.
• Symmetry Breaking: If your puzzle has rotational symmetry (e.g., rotating the entire grid gives another valid solution), add a constraint like fixing the first tile's rotation to 0. This reduces the search space significantly.
• Variable Ordering: The heuristic set in the code (MinDomain, MaxDegree) helps the solver pick the most constrained variables first, which speeds up solving for tough puzzles.

内容的提问来源于stack exchange，提问作者Lorenzo Pisaneschi