Sudoku-jaki algorytm??

Nail · Gość

Cześć wszystkim.

Przed świętami miałem pierwsze ćwiczenia z algorytmiki(do tej pory wykłady) i gość wymyślil, że na 6.01.2006 mamy napisać grę Sudoku w Delphi. Niestety nie podal jakich użyć algorytmów.
Informacji szukam od tygodnia w necie, ale kompletne dno:( - nie wiem może nie umiem szukać??

Dlatego proszę was o nakierowanie mnie jakich, algorytmów należało by użyć lub ewentualnie zarzucić jakiś kod źródłowy. Bo z Delphi to ja raczej noga jestem, a jak już programuje to tylko c++.

Marcin_Miga · Dołączył: 09 Lis 2005 Posty: 1540 Skąd: 127.0.0.1

Jeśli umiesz rozwiązywać SUDOKU na papierze, to zastosuj ten sam algorytm w programie. Ja bym zrobił to na kolekcjach elementów i zdarzeniach. Np. Plansza składa się z 81 POL, 9 RZEDOW, 9 KOLUMN, 9 OBSZAROW. I jeśli w jednym z POL uda ci się ustalić występowanie jakijś cyfry, to wiadomo, że w RZEDZIE, który zawiera to POLE, oraz KOLUMNIE i OBSZARZE dana cyfra już nie wystąpi. Więc POLE musi o tym swoich 'rodzicow' powiadomić.

pozdrawiaMM

jelcyn · Wysłany: Pon Sty 02, 2006 10:31 am Temat postu:

Nie wiem czy to takie proste. Bo są łatwe sudoku w których wystarczy dobrze się popatrzeć i cyfry same się "dopisują" ale są też takie trudne w których np. natrafiasz że można wpisać 2 różne cyfry w 1 pole, nie ma już dodatkowych wskazówek i wtedy trzeba jakby sprawdzić co by było gdybym tutaj wpisał którąś z tych liczb. A niektóre sudoku są tak trudne, że jest jakby kilka takich "rozgałęzień"

Rozwiązałem kiedyś kilka(naście) sudoku i nie zabierałem się za takie przypadki, ale po rozwiązaniu kilku sudoku człowiek zaczyna jakby skuteczniej je rozwiązywać tj. np. domyśla się jaki fragment najpierw sprawdzić bo np. tam jest największe prawodpodobieństwo odkrycia cyfry polecam rozwiązanie kilku sudoku, łatwiej wtedy będzie pisać program

Andrey · Wysłany: Pon Sty 02, 2006 11:39 am Temat postu:

Jezeli chcesz pisac bardzo typowy bruteforce to napewno przyda ci sie jakis algorytm z rekurencja z powrotami, aby w przypadku niepowodzenia algorytm wrocil do najlepiej dopasowanego miejsca musiasz byc jednak swiadom ze taki algorytm nie ma liniowego czasu wykonywania i w najbardziej zlych przypadkach moze wykonywac sie bardzo dlugo. Az mi sie nie chce wierzyc ze nigdzie nie znalazles sudoku-solvera :/
http://www.sudokusolver.co.uk/ <- chyba cos w JavaScript
http://www.sudoku-solver.com/free.htm <- w C++
http://www.di-mgt.com.au/sudoku.html <- w Excelu
http://www.scanraid.com/sudoku.htm <- krok po kroku w JavaScript chyba
http://sudoku.sourceforge.net/ <- tu napewno znajdziesz kod źródłowy bo to sourceforge aplet w Java
http://homepage.ntlworld.com/valleyway/solver.html <- brute force w javaScript
http://rightside.fissure.org/sudoku.cgi <- sudoku jako CGI
http://www.c-digital-art.co.uk/ <- nie wiem czy sa zordla ale podobniez VB

Do wyboru do koloru.
Pozdrawiam

p4welo · Wysłany: Nie Sty 08, 2006 2:59 pm Temat postu:

Wskazówka:
W każdym rzędzie i kolumnie iloczyn liczb musi wynosić
1*2*3*4*5*6*7*8*9 = 362880

Gość · Wysłany: Nie Sty 08, 2006 3:09 pm Temat postu:

czyli 9!

;-)

samolot · Dołączył: 26 Sty 2006 Posty: 3195 Skąd: Toruń

Ja napisałem programik do rozwiązywania sudoku latem 2005r. Nie jest skończony, bo to mozolna praca , trochę brak czasu i cierpliwości.
Robiłem to chaotycznie i na wyczucie. Mój kolega jest fanem sudoku i to on mnie zainspirował.
Na temat metod rozwiązywania można przeczytać w książce Sudoku 1 i Sudoku 2 autorstwa Michaela Mepham, jest tam też zawarta partia diagramów do rozwiązania , podzielonych na łagodne, umiarkowane, trudne i diaboliczne. Ostatnio wróciłem do tematu i napisałem sobie taki schemat blokowy, który ma mi ułatwić pisanie procedur do tego programu. Założyłem ,że będzie kilka etapów rozwiązywania:
1- łatwy
2 -średnio trudny
3- trudny
Tu wymieniłem trzy ,ale jeśli diagram będzie bardzo trudny do rozwiązania to na pewno będą konieczne dalsze etapy.
Mój schemat blokowy na razie zawiera opis pierwszego etapu (patrz załącznik):

Maniek · Gość

Czy ktoś wie jak tworzone są plansze Sudoku? Narazie napisałem program sudoku, w którym plansze wczytywane są z pliku. Ale to troche męczące zapisywanie tych plansz w pliku. Jest jakiś algorytm który potrafi stworzyć plansze w Sudoku?

samolot · Dołączył: 26 Sty 2006 Posty: 3195 Skąd: Toruń

Ponieważ też napisałem taki programik (nie skończony) to jakieś tam przemyślenia mam. Zastosowałem kilka metod rozwiązywania sudoku krok po kroku, od łatwiejszych do coraz trudniejszych , ale na pewno nie wszystkich. Starałem się także rozwiązać jak najwięcej ręcznie, korzystając z kilku popularnych książek. Doszedłem do wniosku,że jeśli napisałbym program do końca (marzenie ściętej głowy) , który umiałby rozwiązać większość plansz sudoku (nie mówię wszystkich), to można by go wykorzystać do weryfikacji przypadkowo wstawionych cyfr i te , które mają rozwiązanie (a rozwiązanie jest tylko jedno)- można by kwalifikować jako gotowe sudoku do rozwiązania.

marcin_an · Wysłany: Sro Cze 28, 2006 10:11 pm Temat postu:

Dla danej planszy sudoku może być więcej niż jedno prawidłowe
rozwiązanie, dlatego algorytm rozwiązujący jako test poprawności może nie być najlepszym pomysłem. Jeżeli wylosujemy pewną wypełnioną planszę i usuniemy z niej pewne liczby, to wersja rozwiazana może różnić się od pierwotnej i w ten sposób plansza zostanie odrzucona. Równocześnie stwierdzenie przez algorytm, że nie może rozwiazać planszy może być wewnętrznym problemem samego algorytmu. Przy złożoności samych algorytmów rozwiazujących nie widzę w tym sposobu na generowanie map.

W tym roku jako projekt semestralny musiałem przygotować kod generujący zadanie programowania liniowego reprezentujące sudoku i przekazać do programu rozwiazującego tego typu zadania. To zainspirowało mnie do napisania algorytmu rozwiązującego sudoku. Nie interesuje mnie tutaj akurat napisanie zawsze działającego i bezbłędnego algorytmu - takie już, z tego co wiem, są. Bardziej mnie zastanawiał algorytm ewolucyjny. Podstawową rzeczą jest tutaj ograniczenie warunków wejściowych oraz stworzenie dobrej funkcji oceniającej i właśnie to było moim celem. Algorytm narazie nie powstał (projekt broniłem zaledwie tydzień temu), ale na podstawie przemyśleń dochodzę do wniosku, że podobny sposób działania możnaby wykorzystać do tworzenia planszy sudoku.

Przepraszam za mało formalny język, ale chciałbym, by zrozumiały to także osoby, dla których wyrażenia w formie "Mamy macierz R, w której R_ij (i=1,2,...,9, j=1,2,...,9) to podzbiór M..." mogą być mniej jasne. Załóżmy, że każde pole planszy to zbiór, który może zawierać cyfry od '1' do '9'. Początkowo wszystkie 81 pól zawiera wszystkie cyfry. W pierwszym kroku dla któregoś pola wybieramy losowo pewną cyfrę, a następnie w odpowiednim wierszu, kolumnie i kwadracie usuwamy wszystkie wystąpienia tej cyfry. Operację powtarzamy, aż na każdym polu pozostanie tylko jedna cyfra. W kolejnym kroku usuwamy część liczb (pozostawiamy część pół pustymi) i otrzymujemy gotową planszę.