Neoptimální řešení permutačních hlavolamů rozkladem na podproblémy

• Thesis title in Czech: Neoptimální řešení permutačních hlavolamů rozkladem na podproblémy
• Thesis title in English: Non-optimal solver of permutational puzzles using divide and conquer technique
• Academic year of topic announcement: 2005/2006
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Supervisor: Mgr. Vladan Majerech, Dr.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 15.11.2005
• Date of assignment: 15.11.2005
• Date and time of defence: 18.09.2006 00:00
• Date of electronic submission: 18.09.2006
• Date of submission of printed version: 18.09.2006
• Date of proceeded defence: 18.09.2006
• Opponents: Mgr. Marta Vomlelová, Ph.D.

Guidelines

Cílem práce je program, který z definice permutačního hlavolamu vytvoří algoritmus, řešící daný hlavolam z libovolné počáteční pozice (případně rozhodne, že hlavolam nemá řešení). Program by si měl poradit i s hlavolamy s nerozlišitelnými díly, i s blokačními hlavolamy (hlavolamy, kde je možnost provést pohyb vázaná na aktuální permutaci dílů).

Práce má navrhnout vhodný formát definice hlavolamu.

Vzhledem k počtu konfigurací netriviálních hlavolamů není šance řešit úlohu na grafu všech konfigurací. Typicky je ale možno díly permutačního hlavolamu rozdělit na vzájemně se neovlivňující skupinky. Nalezení posloupnosti P tahů, ovlivňující jednu ze skupinek a neovlivňující druhou vede k možnostem generovat tahy PQP'Q' řešící menší hlavolam (u permutačních hlavolamů předpokládáme, že ke každému tahu X existuje inverzní tah X').

References

http://www.hlavolamy-puzzles.cz
http://www.geocities.com/jaapsch/puzzles/cube3.htm