Kombination von Rechtecken, Puzzle

Question

Ich habe eine Reihe von überlappenden Rechtecke, die alle Teilmengen des größten Rechtecks ​​(A) sind, und ich möchte Kombinationen von ihnen finden, so dass ihre Vereinigung gleich A. Dieses Bild veranschaulicht sie :

Einschränkung: Alle Rechtecke sollten nur einmal verwendet werden!

Meine bisherige Idee ist es, einen Baum mit Kanten zu erstellen, der Teilmengen des Elternrechtecks ​​bestimmt, und zu versuchen, jede Baumebene zu puzzeln, so dass die Vereinigung ihrer Knoten gleich der Wurzel ist. Dies stellt sicher, dass jedes Rechteck nur einmal verwendet wird. Da das größte Rechteck (A) die Obermenge der anderen ist, ist es die Wurzel.

So ist es das Ziel, dass die Vereinigung von so viele Ebenen wie möglich zu A gleich ist, dh D union F union H = A

Aber wie kann ich die anderen Rechtecken zusammen Rätsel, wie viele Kombinationen, die Gewerkschaften zu finden sind gleich A wie möglich?

Answer 1

Für die rätselhafte Prüfung here. Da dies ein sehr schwieriges Problem ist, summiere die Bereiche zuerst und sieh, ob die Summe gleich der Fläche von A ist; Dies schließt die meisten Teilmengen ohne irgendein Rätsel aus.

Für die Berechnung aller Sätze von Rechtecken aussehen here.