reseni
jako inspiraci bych zkusil prave sudoku algoritmicke reseni. Po vlozeni nekolika nahodnych barev by se dopocital zbytek. Nebo naplnit obvod, to lzecelkem snadno a dopocitat vnitrek. Dopocitavat by sedalo prochazenim stavoveho prostoru, nejspise do hloubky a defacto zkouseni vsech moznosti.

Falco
Procházet celý stavový prostor by asi bylo poměrně náročné (navíc při stejném počátečním rozložení bys dostal vždy stejné výsledky - což by se jistě dalo ovlivnit nějakou lehce randomized funkcí) - stavový prostor je samozřejmé dobrý nápad, jenom by to chtělo doplnit třeba nějakou jednoduchou heuristiku a ohodnocování uzlů.

No když na d tím tak přemýšlím, tak by ten stavový prostor nebyl zas tak veliký (a se současnou výpočetní kapacitou...). Když jsem psal pro ségru nějaký štěpení molekul, tak tam možných stavů bylo mnohem víc... ale je fakt že jsem prohledával do šířky, aspoň myslím teda, už je to dávno.

Stavový prostor
No, to co nazýváte stavovým prostorem, jestli chápu dobře, zase tak moc velký není. Každé políčko totiž patří současně maximálně DO DVOU čtveřic, čili každé políčko je třeba porovnat pouze se šesti dalšími políčky! Výjimku samozřejmě tvoří rohová políčka a krajová políčka, ta patří jen do jedné čtveřice.

Čili já bych si na prvním rohovém políčku vygeneroval náhodnou posloupnost těch 4 druhů budov (aby při každém generování byla možnost jiného vygenerovaného celku díky jinému startovacímu druhu budovy - tento princip zajistí náhodnost i u dalších políček). Porovnal bych zvolenou budovu s ostatními třemi sousedícími políčky. Ta podmínka projde, protože je to první prvek v celku a ostatní jsou prázdná (zatím). Pak bych tu samou funkci rekurentně vyvolal pro vedlejší políčko, čili bych opět vygeneroval náhodné pořadí 4 druhů budov. Pokud by při porovnání zbylých tří políček nedošlo ke konfliktu, opět bych se posunul o další políčko vpravo a tak stále dokola. Pokud by na druhém políčku došlo ke shodě/konfliktu, tzn. vlatně by se jako první na tomto políčku vygenerovala stejná budova jako na políčku vlevo (víc jich tam zatím není), vzala by se druhá budova v pořadí vygenerovaném pro druhé políčko... A tak dále a tak dále. Pokud dojde ke konfliktu při všech čtyřech budovách na daném políčku, znamená to, že taková kombinace nikdy nepovede k cíli a je třeba se vrátit o políčko zpět a přestože jeho předchozí test uspěl, i tak je třeba na něm změnit druh budovy. Ale to právě elegantně řeší rekurze, protože si pamatuje poslední "stavy" před zanořením do nižší úrovně a pokud tedy při vynoření z nižší úrovně je indikován neúspěch, mechanismy rekurze samy zabezpečí, že v nadřazené úrovni dojde ke změně budovy, ačkoli předtím testem prošla!

No, tak teď si to snad už jen namaluju jako vývojový diagram a hurá do toho :-) Věřím tomu, že množina všech možných vyhovujících řešení je konečná a že je poměrně malá. Neumím to matematicky dokázat, ale něco mi říká, že jsou to permutace bez opakování, tudíž to bude hodně malá podmnožina všech kombinací.

...
mno jinak bych nezamnenoval postup s algoritmem, rekurze je pristup, vse co jde napsat normalne jde i rekurzi a naopak. Nicmene to reseni vypada rozumne. Kdyz si nastudujes stavovy prostor, urcite reseni uloh, algoritmus A*, prorezavani tak mozna najdes lepsi optimalizaci.
Nicmene kdyby se problem zdal narocny na vymysleni exaktniho postupu tak by se dal skusit geneticky algoritmus ale nehodi se uplne na tento typ ulohy.
Zkus ten postup co jsi popsal a ono by to nemelo byt tak dlouhe. Nejaka kvadratocka slozitost.

Acer1968
Je fakt, že už jsem dlouho z tohodle mimo, nicméně to co ty popisuješ není podle mého názoru rekurze, ale právě prohledávání stavového prostoru do hloubky (respektive některé části), protože když se dostaneš do slepé větve, vracíš se o úroveň výš a zkoušíš, jestli další větev nebude vhodnější. Což mě napadá, jestli náhodou samo prohledávání stavového prostoru není vlastně rekurzivní (fakt už je to mrtě dlouho, co jsem tohle dělal naposledy), potom bysme v podstatě každý jinými slovy mluvili o tom samém.

Morthe
Ve skutecnosti do hloubky muzes prohledavat primo rekurzi kdy se ti promenne ukladaji na Stack nebo si vytvoris vlastni stack a mas nerekurzivni algoritmus. A ano, mluvite o tom samem :), v zasade. Ale prislo mi ze Acer to psal jako ze to nejspise pochopil stejne.

Stavový prostor
No, už jsem ze školy hodně dlouhý čas, takže něco jako pojem "Stavový prostor" a techniky jeho prohledávání mi opravdu už z hlavy vypadly. Každopádně Wikipedie nemlčí a tak jsem si osvěžil znovu něco, co třeba budu potřebovat. Díky všem za nakopnutí správným směrem. Teď už to nějak dám do kupy.

...
To je klasika, neco se naucis, vyzkousis zapomenes. Ale pak kdyz si vzpomenes ze neco takoveho kdysi fungovalo tak se snadno dohleda a zase si vzpomenes :). Jinak se pak pochlub jak to dopadlo :).