Check if a set of puzzle pieces is forms a valid puzzle

Question

I have a set of puzzle pieces (triangles and squares) of e.g. the form

{[1, 2, 3, 4], [2, 4, 5], [1 , 3, 6]}

Now, I want to check if these pieces can be put together on a grid.

A valid layout would e.g be:

A set of puzzles that would not have a valid mapping would be

{[1, 2, 3, 4], [2, 4, 5], [1 , 5, 6]}

My first ansatz is to put all numbers in the set of puzzle pieces (in the above examples it would be 1, 2, 3, 4, 5, 6) as nodes in a graph and connect them according to the puzzle pieces (if a connection occurs several times, consider it only ones). Then I check if the resulting graph is planar (this is cheap, it scales with the number of edges to the power of 2).

However, the planarity is only necessary for a valid mapping but not sufficient, since it does not take into account that the puzzle pieces have to form a square or a triangle (nothing stretched or similar).

So I thought about a list of forbidden edges, which is appended by looping over the set of puzzles, however, I am stuck. Does someone have a clever idea to answer the question: Does a given set of puzzles form a valid layout on a grid (at best in polynomial time).

The length of the set is arbitrary

Edit: For a puzzle piece such as [1, 2, 3, 4], the four numbers must form a square, and it does not matter in which order these numbers appear on the grid. The same applies to triangles. Therefore, swapping e.g. 2 and 4 in the figure above would still be a valid assignment

Answer 1

I hesitate to post this, because it doesn't completely meet your requirements, but perhaps this can be a start.

This does as I suggested in my comments, by building up a big polygon through accretion of the individual pieces. For triangles, this is easy, but if the points of the squares are not in rotational order, then this fails. You'll see that I changed the rectangle to [1,2,4,3] to get this to pass. In that case, you would need to remember where the squares were added, and if a piece doesn't attach, try it again after flipping those points.

def check(data):
    # Pick the first triangle to start our polygon
    poly = [p for p in data if len(p)==3][0]
    data.remove(poly)

    while data:
        undone = []
        for unit in data:
            print(poly)
            # How many sides are in common with our master polygon?

            common = [p for p in unit if p in poly]
            if len(common) > 2:
                # Impossible.
                return False
            if len(common) < 2:
                # Can't attach this one yet.
                undone.append( unit )
                continue

            # We extend the polygon by inserting the one or two new points
            # between the two known ones.

            # For a triangle, it's easy.  For a square, we can't know
            # the orientation of the other two sides.

            other = [p for p in unit if p not in poly]
            print(unit, common,other)
            for i in range(len(poly)-1):
                if poly[i] in common:
                    if poly[i+1] in common:
                        poly = poly[:i+1]+other+poly[i+1:]
                    elif i == 0 and poly[-1] in common:
                        poly.extend( other )
                    else:
                        return False
                    break
        if undone == data:
            return False
        data = undone
    print(poly)
    return True

data = [[1,2,4,3],[2,4,5],[1,3,6]]
print(check(data))
data = [[1,2,4,3],[2,4,5],[1,5,6]]
print(check(data))

Answer 2

If all you want to know is whether a feasible mapping exists (true or false result) and doesn't care about its details (an assignment of numbers to the grid), then I think a good starting point would be to check every piece of puzzle against every other piece in the following way.

If the intersection of sets of vertices for two pieces has size of:

• 0: then the pieces are not adjacent, continue checking,
• 1: then a valid mapping cannot be created because two pieces share only a single vertex and not edge (it's only my assumption that it's invalid),
• 2: then the pieces are adjacent and the edge is specified by the two vertices, continue checking,
• 3: or more, then a valid mapping cannot be created because a piece is contained withinside of the other.

The above method has complexity of O(n^2), where n is the number of pieces. It might be sufficient for your needs but it really depends on what are the formal criteria for a layout to be considered valid.

Answer 3

I have an approach would run in linear time. It’s not a complete solution, but may be a suitable foundation. I’m not a python developer, so pardon the sketchy pseudocode.

Create a shape object, with the following structure:

Shape {
   id: int,
   points: [int…],
   edges: [[point,point]...]
   diagonals: [[point,point]...]
   function cornerSize(point) {
     if (points.length==4) return 2;
     if (exists(diagonals[0]) && point!=diagonals[0][0] && point!=diagonals[0] [1]) return 2;
     return 1;
  }
}

Within that structure, assume all point pairs are consistently ordered smallest to largest, and can be represented as a string if needed, such as “1,5” instead of [1,5]-- the goal is just a consistent unique identifier for an unordered pair. The shape.id is determined by the ordinal position in your input array of puzzle pieces. When you construct a Shape object, you’ll assign the puzzle piece to points, and populate the Shape’s id, and will initially leave edges and diagonals empty.

You will maintain a placedPoints map, where each point is a key to lookup an array of all known shapes connected to that point.

placedPoints[point] = [Shape…]

You’ll also maintain a joinedEdges map, with a point pair as key, and a list of associated Shapes as the value.

joinedEdges[point,point] = [Shape…]

Iterate through your list of pieces, constructing a shape for each and updating your two maps. You consider your puzzle valid if it runs through all pieces without throwing an exception (which can be caught by the caller)..

function processPieces(pieces) {
    for (int p=0; p<pieces.length; p++) {
        shapes[p]=new Shapes(p, pieces[p]);
        for (int i=0; i<pieces[p].length; i++) {
            if (exists(placedPoints[pieces[p][i]])) {
                placedPoints[pieces[p][i]].append(shapes[p]);
                int cornerSum=sumOfCornerSizes(placedPoints[pieces[p][i]]);
                if (cornerSum > 8) throw “Too many shapes share the same point.”
            } else {
                placedPoints[pieces[p][i]]=[shapes[p]];
            }
            commonEdges = findCommonEdges(shapes[p], placedPoints[pieces[p][i]]);
        # findCommonEdges should throw if any 2 shapes share more than 2 points in common
        for (commonEdge : commonEdges) {
            if (exists(joinedEdges[commonEdge])) {
                throw “Too many shapes share the same edge.”                
            } else {
                For each point in commonEdge 
                    For each shape in placedPoints[point]
                         Commit commonEdge into shape.edges and shape.diagonals
                          # Shape will keep track of known edges until you can
                          # determine a diagonal, at which point you should be
                          # able to determine all its remaining edges and diagonals.
                          
                         If inconsistency found, throw exception. 
                          # A triangle diagonal may only pair with another triangle diagonal.
                          # A square diagonal may not pair with any other shape.
            }
        }
    }
}

Summary of criteria for consistency:

• A shape’s orthogonal edge may be shared with at most one other shape’s orthogonal edge.
• A triangle’s diagonal edge may be only shared with another triangle’s diagonal edge.
• A square’s diagonal edge my not be shared with another shape.
• A point may intersect with no more than 8 units of other shapes, where a 45 degree angle counts as one unit and a 90 degree angle counts as two.