Posted By: martas (Ach jo , no jo :-))) on 'CZriddles'
Title:     Re: Sudoku pro machry
Date:      Tue Aug 15 12:23:19 2006

> http://mener.jinak.cz/sudoku.pdf

O dovolene jsem si udelal trochu casu a napsal si programek na reseni sudoku. 
Vyse uvedene sudoku poslouzilo velmi dobre na odladeni chyb. Kazdopadne zatim 
se mi nepovedlo tohle sudoku vyresit bez rekurze, postup vyzaduje rekurzi do 
hloubky 1 az 2 v zavislosti na tom pro ktere policko se rozhodnu spocitat 
vsechny vetve. Povedlo se nekomu z vas tohle sudoku vyresit bez toho ze by 
jste museli sahnout po rekurzi?

Drobnou modifikaci programu jsem se dostal taky k pocitani vsech moznych 
sudoku. Zda se nekomu neco spatne na nasledujici uvaze?

1/ Necham program spocitat vsechna reseni pro nasledujici vstup:

123|   |   
456|   |   
789|   |   
-----------
   |123|   
   |456|   
   |789|   
-----------
   |   |123
   |   |456
   |   |789

Program mi vratil 283576 moznych reseni, predpokladam ze nedoslo k zadne chybe 
a ze vysledek obsahuje vsechna mozna reseni pro zadany vstup a ze zadne 
reseni se neopakuje. 

2/ Mnozinu vsech moznych sudoku potom dostanu tak, ze pro kazde reseni 
nejdrive najdu vsechny permutace prvnich 3 radku, pro vysledek delam 
permutace druhych 3 radku, potom permutace tretich 3 radku. To same pote 
provedu se sloupcema. Pote bych mel provest jeste permutace trojic radku a 
trojic sloupcu.  Dohromady je to 283576*(3!^3)*(3!^3)*3!*3!. 
Kazdy z uvedenych kroku by mel zachovat spravnost reseni a zaroven by nemelo 
dojit k opakovani. Takze otazka - dostanu timto zpusobem vsechna reseni?
Vysledek ktery mi vysel (476 298 786 816) se lisi od toho co bylo uvedeno v 
jednom z predchozich postu na toto tema.

Martas