Wooden cube solver

pieces1.txt

0 0 0 0 0 1 1 0 1 1 1 1 1 1 2
0 0 0 0 1 0 0 1 1 1 0 0 2 0 0
0 0 0 0 1 0 1 0 0 1 0 1 2 0 0
0 0 0 0 1 0 0 1 1 1 0 0
0 0 0 0 1 0 1 0 0 1 0 1
0 0 0 0 1 0 1 0 0 2 0 0

pieces2.txt

0 0 0 1 0 0 1 1 0 1 1 1 2 1 1
0 0 0 1 0 0 2 0 0 0 1 0 0 1 1
0 0 0 1 0 0 2 0 0 0 1 0 0 1 1
0 0 0 1 0 0 2 0 0 0 1 0
0 0 0 0 0 1 0 1 0 1 1 0
0 0 0 0 1 0 0 1 1 1 0 0

pieces3.txt

0 0 0 1 0 0 0 0 1 0 1 0
0 0 0 1 0 0 1 0 1 2 0 1
0 0 0 1 0 0 2 0 0 1 0 1
0 0 0 1 0 0 0 0 1 0 1 1
0 0 0 1 0 0 1 0 1 1 1 1
0 0 0 0 0 1 1 0 0 2 0 0
0 0 0 1 0 0 1 0 1

pieces4.txt

0 0 0 0 0 1 0 0 2 0 1 2 1 0 2 1 0 3 2 0 3 3 0 3 1 1 3 1 2 3 1 3 3 2 3 3
0 0 0 1 0 0 2 0 0 0 0 1 0 0 2 1 0 2 1 0 3 2 0 3 3 0 3 2 1 3
0 2 1 1 2 1 1 2 2 1 1 1 1 0 1 1 0 0 2 0 0 3 0 0
0 1 0 1 1 0 2 1 0 3 1 0 3 2 0 3 3 0 0 2 0 2 0 0  
0 3 0 0 2 0 0 1 0 1 1 0 1 0 0 2 0 0 3 0 0
0 0 0 1 0 0 2 0 0 3 0 0 3 1 0 0 1 0
0 0 0 1 0 0 2 0 0 2 1 0 3 1 0
0 0 0 1 0 0 2 0 0 3 0 0
0 0 0 1 0 0 1 0 1
0 0 0

solver.py

import sys
import random
import functools
import itertools
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.colors as mcolors

from numpy.linalg import matrix_power

# Cube size
CUBE_SIZE = 3

# Define axes to avoid copy/paste and other errors
X, Y, Z = 0, 1, 2

# Read coordinates for each block of each piece
def readPieces(in_file):
    lines = [l.strip().split() for l in open(in_file).readlines()]
    pieces = [np.array([int(c) for c in l]).reshape(-1, 3) for l in lines]

    return pieces

# Create a volumetric piece from a piece coordinates matrix
def getPiece(piece_coords):
    # Number of blocks in a piece
    numBlocks = len(piece_coords)

    x, y, z = np.indices((CUBE_SIZE, CUBE_SIZE, CUBE_SIZE))
    x_vals, y_vals, z_vals = piece_coords[ :,X], piece_coords[ :,Y], piece_coords[ :,Z]

    piece_blocks = [(x == x_vals[i]) & (y == z_vals[i]) & (z == y_vals[i]) for i in range(numBlocks)]
    piece = functools.reduce(lambda a, b: a + b, piece_blocks)

    return piece

# Plot a list of pieces with a volumetric 3D plot
def plotPieces(pieces):
    # Combine the pieces
    voxelarray = functools.reduce(lambda a, b: a | b, pieces)

    # Colour each piece
    all_colors = [name.split('tab:')[1]
        for i, name in enumerate(list(mcolors.TABLEAU_COLORS))]
    colors = np.empty(voxelarray.shape, dtype = object)
    for p in range(len(pieces)):
        colors[pieces[p]] = all_colors[p]

    # Configure the axes
    ax = plt.figure().add_subplot(projection = '3d')

    ax.voxels(voxelarray, facecolors = colors, edgecolor = 'k')

    # Set axes labels
    ax.set_xlabel('x')
    ax.set_ylabel('y')
    ax.set_zlabel('z')

    # Show the plot
    plt.show()

# Rotation matrixes
R = [
    # Rotate by 90 about the x axis
    np.array([[1, 0, 0], [0, 0, -1], [0, 1, 0]]),
    # Rotate by 90 about the y axis
    np.array([[0, 0, 1], [0, 1, 0], [-1, 0, 0]]),
    # Rotate by 90 about the z axis
    np.array([[0, -1, 0], [1, 0, 0], [0, 0, 1]])
]

# Rotate a piece a number of times
rotate = lambda coords, axis, times: np.dot(coords, matrix_power(R[axis], times))

# Translate for negative coordinates (returns a new array)
def translate(coords, axis, delta):
    c = np.copy(coords)
    c[:, axis] += delta

    return c

# Bring a rotated piece back into the cube boundary
def bringBack(coords):
    mins = [coords[:, axis].min() for axis in [X, Y, Z]]
    maxs = [coords[:, axis].max() for axis in [X, Y, Z]]

    for axis in [X, Y, Z]:
        m = mins[axis]
        if m < 0:
            coords = translate(coords, axis, -mins[axis])

    for axis in [X, Y, Z]:
        M = maxs[axis]
        if M >= CUBE_SIZE:
            coords = translate(coords, axis, CUBE_SIZE-maxs[axis]-1)

    return coords

# Check is a permutated piece is valid
def isValid(coords):
    return (coords.min() >= 0) and (coords.max() < CUBE_SIZE)

# Check if a numpy array (piece) is in a list of arrays
def isIn(val, list):
    # The blocks of the piece can be in different order in the array

    for el in list:
        #print(el)
        if all([row.tolist() in val.tolist() for row in el]):
            return True

    return False

# Insert a piece into the cube
def insertPiece(cube, piece):
    blocks = [block for block in piece]

    for b in blocks:
        cube[b[X]][b[Y]][b[Z]] += 1

        if cube[b[X]][b[Y]][b[Z]] > 1:
            return False

    return True

def allTransformations(coords):

    # Brute-force possible rotations
    prod = [p for p in itertools.product(range(4), repeat = 3)]
    rotations = [rotate(rotate(rotate(coords, X, p[X]), Y, p[Y]), Z, p[Z]) for p in prod]

    normalised = [bringBack(r) for r in rotations]

    # Unique elements
    unique = []
    [unique.append(n) for n in normalised if not isIn(n, unique)]

    # Only valid permutated positions
    valid = []
    [valid.append(u) for u in unique if isValid(u)]

    # Brute force all possible translations
    prod = [p for p in itertools.product(range(3), repeat = 3)]

    translations = [translate(translate(translate(v, X, p[X]), Y, p[Y]), Z, p[Z]) for p in prod for v in valid]

    normalised = [bringBack(r) for r in translations]

    # Unique elements
    unique = []
    [unique.append(n) for n in normalised if not isIn(n, unique)]

    # Only valid translations
    valid_trans = []
    [valid_trans.append(u) for u in unique if isValid(u)]

    return valid_trans

# Find a valid solution
def findSolution(combs):
    cube_full = np.full(shape = (3, 3, 3), fill_value = 1,)

    # High probability, due to mirrored configurations
    current_perms = [[0]] # [[i] for i in range(len(combs[0]))]

    step = 1                # Valid combinations of 2,3,4,.. pieces
    MAX_STEPS = len(combs)  # Number of pieces

    for step in range(1, MAX_STEPS):
        next_perms = []
        for i in range(len(current_perms)):
            cube = np.full(shape = (3, 3, 3), fill_value = 0,)

            for idx in range(len(current_perms[i])):
                insertPiece(cube, combs[idx][current_perms[i][idx]])

            tmp = np.copy(cube)
            for j in range(len(combs[step])):
                cube = np.copy(tmp)
                tmpj = np.copy(cube)
                if not insertPiece(cube, combs[step][j]):
                    cube = tmpj
                    continue
                else:
                    to_append = current_perms[i].copy()
                    to_append.append(j)
                    next_perms.append(to_append)

                    if step == (MAX_STEPS - 1):
                        print("[*] Found a solution!")
                        return next_perms[0]

        current_perms = next_perms

if __name__ == "__main__":
    # Read pieces
    pieces = readPieces(sys.argv[1])

    # brute-force all transformations
    combs = [allTransformations(p) for p in pieces]
    len_combs = [len(c) for c in combs]

    [print("[*] Unique combinations for piece %d: %3d" % (idx, len_combs[idx]))
        for idx in range(len(combs))]

    # Find and print a solution
    sol = findSolution(combs)
    pieces = [getPiece(combs[i][sol[i]]) for i in range(len(sol))]
    plotPieces(pieces)