sudoku - ilość rozwiązań

0

dostałem nietypowe zadanie.
dostaje sudoku w którym jest wypełniona pewna ilość pól (w tym moim przypadku jest 21 wypełnionych pól) i mam napisać program który obliczy ilość rozwiązań. nie jest powiedziane aby je podawał, ma jedynie wywalić jedną liczbę informującą o ilości.
wydaje mi się że pisanie programu rozwiązującego to sudoku będzie nie tylko czasochłonne i relatywnie trudne ale i nie przyniesie efektu... bo jeśli jest ich 1000 różnych rozwiązań to automatycznie będzie to trwało baaardzo długo :/
więc pytanie jak by to zrobić?

0

Ja bym nie komplikował, spróbował dfsa, sprawdził dla ekstremalnego przypadku (zero pól wypełnionych), a potem dopiero kombinował z bardziej zaawansowanymi algorytmami.

0

a jak dfsa użyć akurat w tym przypadku?

0

Dla zera pól może trwać dość długo, ale z 21 znanymi polami powinno działać w sensownym czasie. W skrócie: idziesz po planszy wypełniając kolejne wolne pola najmniejszą możliwą liczbą. Jeżeli nie możesz wypełnić pola, wypełniasz poprzednie pole (oryginalnie puste) najmniejszą możliwą liczbą, większą niż liczba która wcześniej tam była. Jeżeli wypełniłeś wszystkie pola, dodajesz jeden do licznika rozwiązań i wracasz do poprzedniego pola (jak w zdaniu wcześniej).

0

to zadanie nie jest czasochłonne właśnie przez to że niektóre pola masz wypełnione.
Moje rozwiązanie metodą rekurencji:
http://www.2shared.com/file/-2Na0K5m/sudoku_sol.html?

0

Twoj program dal mi 321 rozwiazan, natomiast na tej stronce http://www.sudoku-solutions.com/ moj przyklad ma tych rozwiazan 1917 :/ (moze oni licza wszystkie, a Ty faktycznie rozne rozwiazania).
No to ciekaw jestem czy podzielisz sie kodem albo chociaz algorytmem.

0

no to podaj ten przykład.

0

rozwiązanie jest proste - wystarczy napisać sobie program rozwiązujący sudoku no i przy każdym rozwiązaniu zwiększać licznik rozwiązań...

0

060020040
500300000
080010000
600007000
037000280
020800030
000000000
700400001
000060020

to jaka metoda rozwiazujesz?

0

jaką metodą rozwiązuję? - rekurencja i backtracing...

PS.
Tylko uważaj czy ten plik ci się dobrze wczytał na tej stronce bo ja próbowałem wczytać mój plik i pojawiły się problemy.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0