Ot izvestno vreme nasam se chudya kak bi tryabvalo da se podhodi, za da se generirat sudoku kombinacii v/u tablo 9x9 sus 9 malki 3x3 kvardatcheta.

Celta na zadachata e da pokaje razlichni reshenia za generiraneto na kombinaciite. Predpolagam, che ima poveche ot edin nachin da se postigne celta.

Tuj kato ima mnogo opensource programi, koito ia generirat, ia reshavat igrata, shte pomolya da ne gi poglejdate. Po-interesno bi bilo da se dade intuitivno reshenie.

Predpolagam, che nyakoi biha namerili prilika s 8-queens problema, koeto pone za men beshe hint za tova kak bi tryabvalo da se podhodi.

е то това иска ровене в нета поне за да се разбере какво е судоку какво се комбинира, по какви правила и т.н.

Pravilata sa slednite..
Ima reshetka 9x9. Tryabva da se razpolojat cifrite ot 1 do 9 po vseki edin vertikal i horizontal, kato ne e dopustimo na edna linia (vertikal ili horizontal) da ima 2 ednakvi chisla.
Dopulnitelno, tazi 9x9 reshetka e razdelena na 9 po-malki reshetki s razmer 3x3.
Vuv vsyaka edna ot po-malkite reshetki tryabva da figurirat chislata ot 1 do 9, bez da ima povtorenia.

Posle, (izvun tazi zadachka), komputera izbira koi chisla da pokaje, a ostanalite chisla, koito ne sa pokazani, tryabva da se vuvedat ot igracha. Tova obache veche ne e interesno za zadachata. Po-interesnoto e kak da se generirat 9x9 reshetki, koito da otgovaryat na gornite uslovia.

Eto edin primer:
http://en.wikipedia.org/wiki/Image:Sudoku-...2G-20050714.gif
(otdolu pod snimkata se vijda i reshenie na zadachata)

struva mi se che generiraneto na tablichkata e tiasno svyrzano s reshenieto na gotovo sudoku, zatova pyrvo shte predlozha algoritym za reshavane (kogato imate pokazani niakolko cifri v kletki) na dva etapa:

1) lesen etap - namirane na lipsvashtite cifri chrez eliminirane na nevyzmozhnite im pozicii; da kazhem che v pyrvoto 3x3 pole imate pokazani 3, 5 i 8 - sledovatelno triabva da razpolozhite 1, 2, 4, 6, 7 i 9 - pochvate s 1 - ako se okazhe che 1 ne mozhe da byde v 5 ot svobodnite kletki poradi tova che na syotvetnia red ili stylb v cialata tablica veche ima druga edinica, ostava da e v 6-tata (posledna) svobodna kletka na pyrvoto 3x3 pole; dejstvate analogichno za drugite cifri i 3x3 poleta dotogava dokogato veche ne e vyzmozhno da razpolagate cifri chrez eliminirane

2) truden etap - razpolagane na ostavashtite cifri chrez posledovatelno izprobvane na razlichni kombinacii na vyzmozhnite cifri v ostavashtite prazni poleta po slednia metod: primerno v niakoja prazna kletka na niakoe 3x3 pole mogat da sa cifrite 6 ili 9 - slagate 6 i posle dejstvate po etap (1) da razpolozhite oshte cifri po mestata im; ako na niakoja stypka ot tozi algoritym stignete do nevyzmozhna pozicia, t.e. okazva se che za niakoja cifra niama miasto v 3x3 poleto, se vryshtate edna stypka nazad i probvate drugata cifra (t.e. 9); programistite znajat che tova se naricha depth first search

ta, ideata za generiraneto na sudoku-to e prosto da se reshi sudoku s nula na broj pokazani cifri

tova estestveno predpolaga sluchajno izbirane na path v search tree, za da mogat vseki pyt da se generirat razlichni konfiguracii (ot samo sebe si se razbira che v sluchaj na generirane se zapochva napravo s depth first search)

Прочетох тъз тема преди няколко дена и не спирам да мисля по въпроса... за жалост не измислям много. Първото което ми дойде на акъла беше това, което demond е описал, т.е. решаване чрез рекурсия и елминации. След време ми дойдоха още идеи за алгоритми.. но за жалост не могат генерират всички възможни комбинации(което ми е целта )

Алгоритъм първи: Кодиране
Като за начало имаме готова въведена sudoku таблица. Нека я наречем базова таблица. След това правим масив(да кажем) в който за всяко число - въвеждаме ново число(ем не съм добър в обясненията)... ето пример.

Идеята е да се кодира всеки един блок(квадратче с число) от базовата таблица според зададения масив с кодове. Получената таблица, след като се кодира базовата е винаги валидна(стига данните в масива да са валидни). Работейки по този начин, алгоритъма може да генерира до 9!(девет факториел) валидни sudoku таблици(което е доста далеч от всичките възможни ).

Алгоритъм втори: Разместване(тък също имаме базова таблица)
По ено време забелязах, че като се разместят редовете в таблицата - валидността и не се променя. Естествено ако се разместват в границите на решетките(т.е ред първи може да се размества само с ред втори и трети, а ред четвърти - само с пети и шести). Освен това, колоните също могат така. А още освен туй редовете от решетки могат да се разместват с други редове от решетки. И отвново -> същото важи и за колоните от решетки.
Възможните комбинации, които генерира този алгоритъм са 6^3*6^3*6^2 = 6^8. Което също е далеч от всичките възможни.

Не съм сигурен, но мисля, че ако се съчетаят двата алгоритма ще генерира много еднакви резултати.

А всъщност дори не знам и колко са всичките възможни резултати.. Бях направил една програмка да ги проброи. Като си лягах една вечер я пуснах, и на сутринта гледам беше стигнала до 500 и нещо милиона... След туй я напрайх да брои таблиците, без да променя първия ред(което би трябвало да намали вариантите със 9 факториел), и пак като са сабудих беше на 500 и нещо милиона ... накрая са отказах да ги броя.

The number of classic 9×9 Sudoku solution grids was shown in 2005 by Bertram Felgenhauer and Frazer Jarvis to be 6,670,903,752,021,072,936,960 [5] (sequence A107739 in OEIS) : this is roughly 0.00012% the number of 9×9 Latin squares.

[5] http://www.afjarvis.staff.shef.ac.uk/sudoku/