Nowe oblicze SUDOKU?

[qbeu]

Skoro wszyscy zainteresowani tematem sudoku są biegli albo w rozwiązywaniu, albo we wklepywaniu do programów rozwiązujących, to może pogłowimy się nad różnymi algorytmami takich "rozwiązywaczy"? Autor poprzedniego wątku zamieszcza na stronie o podanym adresie kod źródłowy. Może ktoś ma inny, szybciej działający algorytm? Ja myślałem nad algorytmem grafowym, myślę, że taki byłby najlepszy, jeśli byłby odpowiednio dobrany graf, oraz komputer byłby biegły w algorytmach grafowych. Jak będę miał więcej czasu, to jeszcze nad tym pomyślę.
Jeszcze jedna rzecz mi się nasuwa: jakby tak znaleźć jakieś praktyczne (przynajmniej z naukowego, nie życiowego, punktu widzenia) zastosowanie dla sudoku???
____________________
-=Pokój Oraz Dobro=-

[Gość: wildwezyr]

A dlaczego grafowy ten algorytm ma być? Bo to modne słówko? Przecież algorytmy
grafowe mogą mieć bardzo różne złożoności - w zależności od problemu do
rozwiązania. A często to, co można zrealizować za pomocą grafu i jakiegoś jego
trawersowania, da się również zaimplementować na zgrabnej tablicy
(wielowymiarowej). Co często daje o niebo lepsze wyniki - nie zawsze pod
względem rzędu złożoności algorytmu, ale przynajmniej w sensie stałej algorytmu.

pl.wikipedia.org/wiki/Przechodzenie_grafu
pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa
Jakoś nie mam wizji na algorytm grafowy (taki czysto grafowy, bez innych
dominujących struktur danych). Szczególnie, że w sudoku sam problem aż prosi się
aby przetwarzać go w dwuwymiarowej tablicy (to co jest przechowywane w każdym
polu tej tablicy, może samo stanowić kolejny wymiar - np. trzymamy numerki
dozwolonych jeszcze cyfr w danym polu).

oxygene.ibspan.waw.pl/~sikorski/wi/wi_mpd06.pdf
A czy znane są górne i dolne ograniczenia złożoności algorytmów rozwiązujących
Sudoku? I czy jest to problem z luką algorytmiczną? Bo jak nie, to oczywiście
istnieje już optymalne rozwiązanie ;-).

Wie ktoś może? Ja w tej chwili tego nie wiem :-(.