Safra, do háje! Teď se mi to nepodařilo odeslat, tak jsem musel napsat všechno znovu.Nerozumím těm 8^8. Zjednodušeně řečeno je 8! možností, jak postavit 8 královen tak, aby každá zabírala jeden sloupec a jeden řádek. Porovnání, zda se neohrožují, musím udělat u každé s každou, čili 8x7/2, fakticky však jsou ta porovnání dvě, protože musím zjišťovat, zda nejsou na stejné diagonále vlevo dole směrem doprava nahoru, nebo vlevo nahoře směrem doprava dolů; čili 8x7/2x2=8x7. Složitost počítání by tedy byla přinejhorším 8!x8x7 krát nějaká ta konstanta, protože i generování permutací a samotné porovnání, zda nejsem na stejné diagonále, není za jednu instrukci, řekněme "to celé krát 5". Fakticky však bude potřeba při prohledávání do hloubky mnohem méně porovnání, protože já ty permutace kontroluji na nekoliznost průběžně, čili postavím první královnu na první řádek a první sloupec (zapíšu jako 1). Pak přidám druhou královnu na druhý řádek a druhý sloupec, čili 1 2, ale ihned zjistím, že koliduje, tak se rovnou posunu na další permutaci, čili 1 3 (první královna na prvním řádku a prvním sloupci, druhá královna na druhém řádku a třetím sloupci). Tím, že jsem odřízl celou větev "1 2" jsem ušetřil ohromné množství operací, protože permutací začínajících na 1 2 je celkem 6!, což rozhodně není málo. A pokračuji dále: k "1 3" nemohu přidat ani 2 a ani 4, protože oba případy kolidují, přidávám tedy třetí královnu až na pátý sloupec (1 3 5). Jen pro úplnost, to, že třetí královnu nemohu přidat na první nebo třetí sloupec je zjevné již jen z procesu generování permutace, protože 1 a 3 jsou již zabrané, a ani tedy nemusím nikde nic porovnávat, abych tyto varianty nebral v úvahu.Zkusil jsem si dát pod cygwinem time, a pro n=8 mi prográmek našel všechna řešení za 0,03 vteřiny, čili pod hranicí detekovatelnosti (něco zabere i samotná inicializace programu). Pro srovnání, n=12 bylo za 0.30 vteřiny, n=13 trvalo přes vteřinu, n=14 zhruba 10 vteřin, n=15 již přes minutu, a dále hezky přibližně exponenciálně. Vlastně do nějakého n=20 zabírá nejvíce času nikoli prohledávání, ale výpis nalezených řešení, teprve pro vyšší n se situace začíná komplikovat a je nutné prohledat veliký počet možností než se najde alespoň první nekolizní.Toto vše píšu z 11 let starého notebooku, před těmi 15+ lety jsem však měl desktop, a měl nejspíš stejný výkon jako můj dnešní book, takže jsou časy srovnatelné...