Megoldás

1. megoldás: módszeres próbálgatás

Megkeressük (balról jobbra, fentről lefelé) az első olyan fedetlen mezőt, amelyre vízszintesen vagy függőlegesen elhelyezhető egy "csempe" bal felső sarka. (Azt kell ellenőrizni, hogy a csempe elfér-e a táblán, és azt, hogy nem lóg-e bele korábban lehelyezett csempébe.)

Ezután megpróbáljuk mindkét módon letenni a csempét a megtalált mezőre, és a kapott részlegesen lefedett táblákra rekurzív módon meghívjuk a lefedő eljárásunkat. A rekurzió azt is ellenőrzi, hogy nem talált-e megoldást, és ha igen, akkor leállítja a programot a megoldás kiírása után.

Kód

Forrás Bence (java): FB_Kitoltes.java
Fehér Balázs (java): Teglalapok2.java     animációt készít a visszalépéses keresésről, előállítja a kitöltéseket PNG formátumban
Czövek Márton (java): kitoltes.java

2. módszer: matematika

A feladat egy nagyon meglepő matematikai tétel ismeretében végtelenül egyszerűsödik. 

de Bruijn - Klarner: Ha egy téglalapot lefedtünk olyan téglalapokkal, amelyeknek legalább az egyik oldala egész, akkor az eredeti téglalapnak is van egész oldala.

Néhány csodaszép bizonyítás: Stan Wagon Fourteen Proofs of a Result About Tilling a Rectangle

Következmény: Ha egy n, m oldalú téglalapot lefedtünk a, b oldalú téglalapokkal (a,b,n,m egész), akkor szükségszerű, hogy a is és b is osztója n és m valamelyikének.

Az eredeti feladat megoldásához a következő feltételek teljesülése szükséges és elégséges:
  • ab | nm
  • n = ax+by és m = ax+by megoldható xy nemnegatív egészekkel
  • a is és b is osztója n és m valamelyikének

Kód

Erben Péter (java): ep_teglalap.java