Programozás‎ > ‎Feladatok‎ > ‎

KöMaL fórum feladat

A következő feladatot a Kömal Fórum "Találjunk jobb megoldást!" témájának [109]-es bejegyzése, és az utána kibontakozó eszmecsere ihlette.

Egy sakktábla néhány mezője közé "falat" rajzoltunk, majd le kell fedni hézagmentesen és átfedés nélkül a táblát L-alakokkal úgy, hogy a "falakon" nem mehet keresztül L-alak.


Kérdések

  1. Adott néhány fal helye. Döntsük el, lefedhető-e L-alakokkal a tábla és ha igen, adjunk is meg egy helyes lefedést!
  2. Adott néhány fal helye. Határozzuk meg, hányféle módon fedhető le L-alakokkal a tábla!
  3. (*) Határozzuk meg azt a legkisebb F számot, amire elhelyezhető F darab fal a táblán úgy, hogy a kapott feladatnak pontosan egy megoldása van!
Az utolsó kérdés volt lényegében a fórumon felvetett feladat. Két idézet a hozzászólásokból:

[119] Csináltam egyet 5 fallal. Egyébként azt csodálom, hogy még senki nem írta meg a programot, ami kidobja a jó választ. Kár, hogy én nem értek hozzá. :)

[120] Öt falra szerintem reménytelennek tűnik az összes eset végigpróbálgatása, és még négy falra is valami jó hatékony heurisztikus parkettázó kéne, ami előállítja az összes megfelelő lefedést, ezt pedig nem könnyű megcsinálni, ezért nem írta még meg senki a programot. 

Címkék

A feladat forrása: saját feladat
Algoritmusok: visszalépéses keresés, backtrack

megoldás