Ostatnio robilem w php skrypt kwadratu magicznego, opierajacego sie na sudoku. Poszukaj tutaj na forum jakie mialem problemy/pomysly z implementacja (jakies 2 tyg. temu w Przedszkolu).
Ogolnie program opiera sie na rekurencji - sprawdzam warunek czy wszystkie pola sie zgadzaja (bo generowal losowo, a przy niektorych kombinacjach nie dalo rady zrobic) - jezeli sie nie zgadza to wywoluje sie od nowa, ale poprzednie wywolanie konczylem za pomoca break, zeby sie nie zapetlal w nieskonczonosc.
Z wydajnoscia slabo, bo nie opieralo sie to na zadnym algorytmie i przy duzych sie wieszala, ale sudoku troche inaczej sie robi, wiec bedzie latwiej.
Wpisz na google "creating of sudoku" czy cos podobnego - ja znalazlem forum, ludzi pisali/rozwiazywali sudoku w php,c,java,SQLu i innych - praktycznie w wiekszosci jezykow (nawet w prologu

) .
Co do algorytmu to tworzenie sudoku opiera sie na algorytmie Knutha (dokladnie nie pamietam jak to sie nazywalo, ale znajdziesz).
Powodzenia w pisaniu - pochwal sie efektem pracy.