Átfogó problémák

Az alább felsorolt problémák teljes megoldása akár egy szakdolgozaton is túlmutathat.

Az alábbi feladatok mindegyikében meg kell alkotnia a megfelelő állapotleíró osztályt, a célfüggvényt, valamint a lehetséges lépéseket. Ha ezek mind elkészültek, akkor tesztelje, hogy hogyan teljesítenek az általános módszerek, majd próbáljon az adott feladatra illeszkedő speciális megoldási módszereket adni.

  1. A kockakígyó egy gyerekjáték, melyben a kígyó formájú láncból egy kockát kell hajtogatni. Implementálja a problémát!

  2. Implementálja a Rubik-kocka feladatát! Hasonlítsa össze az egyes módszerekhez szükséges lépések számát az optimálissal, valamint a kirakási receptek követésével kapott lépésszámmal!

  3. Implementálja a Rubik-kocka valamely variánsát: 2x3x3 (dominó), 4x4x4 vagy 5x5x5!

  4. A felhőkarcolók rejtvényében egy nxn-es latin négyzetet kell készíteni, melyben minden egyes érték azt jelzi, hogy a szóban forgó felhőkarcoló hány emelet magas. A megoldás meghatározásához minden sor és oszlop esetén adott, hogy hány felhőkarcoló látszik abból az irányból. Ha például a legmagasabb szerepel elől, akkor ez az érték csak 1, míg ha az épületek növekvő sorrendben rendezettek, akkor n. Implementálja a feladatot!

  5. Az ABC-út rejtvényben egy 5x5-ös mátrixban úgy kell elhelyezni az angol ábécé első 25 betűjét, hogy azok bármelyike érintse az előzőt és a rákövetkezőt. További megszorítás, hogy az sorokban, oszlopokban és átlókban megkötések vannak, hogy melyik betűnek hol kell elhelyezkednie. Implementálja a feladatot!

  6. A hidak rejtvényben a szigetek számai jelzik, hogy hány híd vezet a szigetre. A mi feladatunk meghatározni a hidak elhelyezkedését, ahol két szigetet maximum két híd köthet össze, a hidak a rajzon függőleges vagy vízszintes irányban állnak, és nem keresztezhetik egymást. Implementálja a feladatot!

  7. A Hitori rejtvényben a feltöltött nxn-es mátrixból kell elemeket törölni, hogy az eredményül kapott mátrix soraiban és oszlopaiban ne szerepeljen ugyanazon érték. Az törölt mezők nem érinthetik egymást vízszintesen vagy függőlegesen, és a nem törölt mezőnek összefüggőeknek kell lenniük. Implementálja a feladatot!

  8. A domináns királynők problémájában úgy kell az nxn-es sakktáblára felrakni a királynőket, hogy azok a tábla minden mezőjét üthessék a sakk szabályai szerint. Mennyi a királynők minimális száma, és hova kell helyezni őket? Implementálja a feladatot!

  9. Készítse el az előbbi feladat variánsát futókra, valamint lovagokra is külön-külön.

  10. A Klotski rejtvényben az elemek ide-oda tologatásával kell elmozdítani egy adott elemet egy előre megadott helyre. Implementálja a feladatot!

  11. Az amőba egyszemélyes türelemjáték variánsa a morpion solitaire. Itt minden egyes lépésben egy újabb ötös kialakítása a feladat, és ha ez nem lehetséges, véget ér a játék. A célfüggvény értéke a kialakított ötösök száma. Implementálja a feladatot!