Algorithm to solve a tangram

I’m given a set of pieces and a shape, and I’ve to come up with one(any) solution. I’m totally stuck on where to begin. I’d like to get some suggestions to get me started. Particularly, I’d like to know what algorithm could I use to fit the pieces into the shape.

pieces:

<svg version="1.1" xmlns="http://www.w3.org/2000/svg">
    <path d="M 90 90 L 90 110 L 110 110 L 110 70 z" fill="yellow"/>
    <path d="M 130 80 L 170 120 L 170 80 z" fill="red"/>
    <path d="M 290 150 L 270 170 L 210 110 L 250 110  z" fill="olive"/>
    <path d="M 190 120 L 190 160 L 210 180 L 230 160 z" fill="magenta"/>
    <path d="M 320 80 L 300 100 L 280 100 L 280 80 z" fill="blue"/>
    <path d="M 320 150 L 360 150 L 320 190 z" fill="green"/>
    <path d="M 230 30 L 230 70 L 210 90 L 190 70 L 190 30 z" fill="purple"/>
</svg>

shape:

<svg version="1.1" xmlns="http://www.w3.org/2000/svg">
    <path d="M 50 10 L 90 10 L 90 50 L 130 50 L 130 90 L 90 90 L 90 130 L 50 130 L 50 90 L 10 90 L 10 50 L 50 50 z" fill="brown"/>
</svg>

sample solution:

<svg version="1.1" xmlns="http://www.w3.org/2000/svg">
    <path d="M 50 10 L 70 10 L 70 30 L 50 50 z" fill="yellow"/>
    <path d="M 70 10 L 90 10 L 90 50 L 70 30 z" fill="blue"/>
    <path d="M 10 50 L 50 50 L 10 90 z" fill="green"/>
    <path d="M 90 50 L 130 50 L 130 90 z" fill="red"/>
    <path d="M 10 90 L 70 30 L 90 50 L 50 90 z" fill="olive"/>
    <path d="M 90 50 L 130 90 L 90 90 L 70 70 z" fill="magenta"/>
    <path d="M 70 70 L 90 90 L 90 130 L 50 130 L 50 90 z" fill="purple"/>
</svg>

Did you mean to post this in the Python category?

yes, I did.

OK, cool. So do you have a starting point? Presumably if you’re using Python, you’ve thought about how you might approach this. Where have you gotten with it so far? Or why are you approaching it with Python?

I’m using python because it’s the only programming language that I know. I know that in order for all the pieces to fit into the shape, the total area of all the pieces should equal to the area of the shape, and if the pieces are outside the parameter of the shape, I need to move them in. However, my biggest problem is not knowing how to put the different pieces together. Thanks.

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.