c++ sudoku solver

Jak się odwołujesz do jakiegoś filmiku to powinieneś dać do niego linka.

Jest i link

Co to jest?
Zera w Sudoku?
Może są eksperci potrafiący napisać Sudoku w tylu liniach... Ja ptrzebowałem 10x tyle i to tylko na - przyznam - rozbudowaną logikę. Interfejs i prezentacja swoją drogą.

tak, zero to puste miejsce.
Ja piszę program okienkowy, ale najpierw chce samą esencje napisać w konsoli. Może jakieś wskazówki, jak napisać taki program?

Dokładnie zapoznac się z logiką gry.
Próbowałeś czegoś prostszego?

Rekman napisał(a):

Próbowałeś czegoś prostszego?

Co masz na myśli?

Coś łatwiejszego. Jak chociażby nieśmiertejne kółko i krzyżyk.

Może są eksperci potrafiący napisać Sudoku w tylu liniach... Ja ptrzebowałem 10x tyle i to tylko na - przyznam - rozbudowaną logikę. Interfejs i prezentacja swoją drogą.

Ja kiedyś napisałem w kilku linijkach, i kod jest gdzieś na tym forum.
Oczywiście oszukiwałem: wprowadzasz reguły i odpalasz Microsoft Solver Foundation.
Od zera (czyli bez gotowego kombajnu matematycznego) rozwiązywacza Sudoku nie pisałem jeszcze nigdy ;-)

Rekman napisał(a):

Coś łatwiejszego. Jak chociażby nieśmiertejne kółko i krzyżyk.

To właśnie wczoraj skończyłem.

Mam napisane dwie wersje:

• jedna - c++, brutal force - mniej wierszy niż w poście wyżej.
• druga - delphi, kombajn do zgadywania/tworzenia sudoku 3x3,4x4,5x5 do wyboru - 1829 wierszy.
  

Można prosić o wersję pierwszą:D
O algorytm rozwiązywania, albo o podpowiedź co zmienić w istniejącym kodzie.?

Algorytm brutal force jest prosty.
Rekurencyjny z nawrotami w każde wolne miejsce podstawiasz wszystkie możliwe liczby i patrzysz czy nie ma kolizji.
Warto zaimplementować wszystkie znane reguły pochodne przynajmniej do trzeciego poziomu - poczytaj na stronach o rozwiązywaniu sudoku.

Damianek napisał(a):

Można prosić o wersję pierwszą:D
O algorytm rozwiązywania, albo o podpowiedź co zmienić w istniejącym kodzie.?

Najlepiej zrób implementacje własnego pomysłu i nie przejmuj się, że kod zajmuje znacznie więcej linii kodu :)

Chyba umiesz sprawdzić, czy rozwiązałeś sudoku poprawnie? Jeśli tak, to co za przeszkoda :)

Pozdrawiam

Niekonstruktywni jesteście, dwie strony i nikt nie spróbował podać rozwiązania : P.

Ja zacząłem czyścić kod pod moje chore upodobania, i po drodze przypadkowo naprawiłem błąd widocznie, bo teraz działa ;) (nie chce mi się już sprawdzać co było źle, obstawiam nieczyszczenie tablicy b/curr, trzecia w nocy prawie ;/) - cały kod solvera:

bool can_input(int x, int y, int value) {
    for(int i = 0; i < 9; i++) {
        if (value == curr[x][i] || value == curr[i][y]) { return false; }
    }
    for (int i = (x/3)*3; i <= ((x/3)*3)+2; i++) {
        for (int j = (y/3)*3; j <= ((y/3)*3)+2; j++) {
            if (curr[i][j] == value) { return false; }
        }
    } return true;
}

bool next(int x, int y) {
    if (x == 8 && y == 8) return true;
    else if (x == 8) return solve(0, y + 1);
    else return solve(x + 1, y);
}

bool solve(int x, int y) {
    if (sudoku[x][y] == 0) {
        for(int i = 1; i <= 9; i++) {
            if (can_input(x, y, i)) {
                curr[x][y] = i;
                if (next(x, y)) return true;
            }
        } curr[x][y] = 0; return false;
    } return next(x, y);
}

Btw. przemianowałem 'a' na sudoku oraz b na curr, imo jest czytelniej.

Edit 2
Wzięło mnie na 'codegolf', więc jeszcze dam 'ambitniejszą' wersja can_input - takiego kodu /nie/ należy pisać (no ale krótsza i solver zajmuje efektywnie 18 linijek kodu) ;)

bool can_input(int x, int y, int v) {
    for(int i = 0; i < 9; i++) {
        if (v == curr[x][i] || v == curr[i][y] || v == curr[x/3*3+i%3][y/3*3+i/3]) return false;
    } return true;
}

Testowane dla:

int sudoku[9][9]= {
    {0,1,0,0,5,6,2,7,0},
    {0,0,0,0,8,0,0,0,9},
    {0,7,8,0,0,3,6,0,5},
    {0,0,0,0,0,4,5,0,1},
    {8,5,2,0,0,0,7,3,4},
    {6,0,1,7,0,0,0,0,0},
    {1,0,6,4,0,0,9,5,0},
    {3,0,0,0,6,0,0,0,0},
    {0,2,7,3,9,0,0,8,0}
};

/*
413956278
265187349
978243615
739824561
852619734
641735892
186472953
394568127
527391486
*/

int sudoku[9][9]={{0,4,5,0,9,0,0,7,0},
             {1,0,7,3,0,6,5,0,8},
             {0,9,0,2,7,0,0,6,1},
             {0,1,0,0,2,0,3,8,0},
             {2,0,8,4,1,9,6,0,7},
             {0,6,9,0,5,0,0,4,0},
             {4,5,0,0,8,2,0,3,0},
             {9,0,6,5,0,1,7,0,4},
             {0,7,0,0,6,0,8,1,0}};

/*
645198273
127346598
893275461
514627389
238419657
769853142
451782936
986531724
372964815
*/

Na pierwszy rzut oka OK.

Może są eksperci potrafiący napisać Sudoku w tylu liniach... Ja ptrzebowałem 10x tyle i to tylko na - przyznam - rozbudowaną logikę. Interfejs i prezentacja swoją drogą.

Nie widzę związku między tym w ilu linijkach Ty napisałeś sudoku a tym czy ten kod ma szanse być poprawny ;). Na pewno można by to napisać wydajniej (constraint propagation z oczywistych rzeczy - seealso np. http://norvig.com/sudoku.html) ale dobry bruteforce z nawrotami nie jest zły.

Edit - w sumie słowo komentarza (chociaż to Ty oglądałeś film, ja go nawet nie uruchamiałem ;) ) do kodu.
can_input (dawniej inputvalue) - przyjmuje parametry x, y, i. Sprawdza czy na pozycji [x, y] można wstawić wartość i. Czyli po prostu sprawdza czy nie występuje w wierszu/kolumnie/kwadracie.

Funkcja next to taki mały helper na powtarzający się kawałek kodu, jej zadanie to wywołanie solve dla następnego pola w kolejności - zasada jest taka że najpierw zgadujemy co może być na pozycji (0,0), potem (1, 0), potem (2, 0), ... (8, 0), (0, 1), (1, 1), (2, 1) etc. np. next(2, 0) po prostu wywołuje solve(3, 0) (następne w kolejności) i zwraca wynik.

No a solve. Jeśli sudoku[x, y] != 0, przechodzi do następnego pola (za pomocą next).
Jeśli sudoku[x, y] == 0, solve(x, y) próbuje dopasować wszystkie możliwe wartości od 1-9 do tego pola, i rekurencyjnie wywołuje się dla następnego (czy ze zgadnięta wartością uda się ułożyć sudoku). I w sumie tyle, działa.

@msm - podejście jest nierozsądnie czasochłonne.
Przy każdym polu oznacz które cyfry są jeszcze możliwe, czyli 9-bitowa informacja.
Po każdym wstawieniu odznaczasz wybraną cyfrę w pionie, poziomie i kwadracie za wyjątkiem wstawionego miejsca oczywiście.
Jeżeli po jakimś odznaczeniu gdzieś wyszło że nie zostało żadnego bitu to znaczy że trzeba się cofnąć.
Wybór które pole zmieniamy teraz powinien zależeć od ilości możliwości w nim (na pierwszy strzał - większe możliwości).
Warto te bity odwrócić czyli 1-ka oznacza że cyfra nie jest możliwa do wstawienia.
Zamiast tego potworka:

for (int i = (x/3)*3; i <= ((x/3)*3)+2; i++) {
        for (int j = (y/3)*3; j <= ((y/3)*3)+2; j++)

Warto zastanowić się nad tabliczką:

unsigned squares[9*9]=
  {
   1,1,1,2,2,2,3,3,3,
   1,1,1,2,2,2,3,3,3,
   1,1,1,2,2,2,3,3,3,
   4,4,4,5,5,5,6,6,6,
   4,4,4,5,5,5,6,6,6,
   4,4,4,5,5,5,6,6,6,
   7,7,7,8,8,8,9,9,9,
   7,7,7,8,8,8,9,9,9,
   7,7,7,8,8,8,9,9,9,
  };

oraz nad jej odwróconą postacią.

@msm, to jest hard:

5-- --6 9-4
3-- --- 8--
-7- 4-- -1-
--- 952 ---
--9 --- 2--
--- 87- ---
-6- --1 ---
--1 --- --5
7-8 2-- --3

co do eliminacji dzielenia to może jakiemuś kompilatorowi udaje się to sensownie optymalizować.

W kwestii rozwiązania, pogoogluj 'problem 8 hetmanów', bo rozwiązanie jest analogiczne

hard:

...|...|.1.
4..|...|...
.2.|...|...
---+---+---
...|.5.|4.7
..8|...|3..
..1|.9.|...
---+---+---
3..|4..|2..
.5.|1..|...
...|8.6|...

Witam po przerwie.
Jaki jeszcze algorytm można zastosować do rozwiązywania sudoku?
Ten Brute Force na Intel Core i5 działa bardzo szybko, ale z ciekawości uruchomiłem na Celeronie 633MHz, to najtrudniejsze potworki rozwiązuje do 30 sekund. Jaki algorytm będzie szybszy?

Poszukaj na forum, był tu kiedyś wątek, w którym wielu z nas zamieszało kod liczący możliwe rozwiązania dla niepełnego sudoku (takiego które ma więcej rozwiązań).
Testowane to było planszy z około 1200 rozwiązaniami. Większość kodów zliczyło rozwiązania poniżej sekundy.

jeśli dobrze pamiętam to dawałem w tedy kod python-a, który sobie radził na dość starym sprzęcie w 10 sekund (wersja w C++ byłaby pewnie 10 razy szybsza).

Dzięki, poszukam.
@_13th_Dragon
Rozwiązanie sudoku, które podał krwq zajęło ok 20 sekund.

To dalej ja.
Zacząłem modyfikować kod podany prze użytkownika @msm, stosując się do rad @_13th_Dragon.
Dodałem funkcję która zapsuje w tablicy trójwymiarowej jaki liczby można wstawić w danym polu sudoku. To znacznie przyspieszyło rozwiązywanie. Teraz próbuję zrobić to:

Po każdym wstawieniu odznaczasz wybraną cyfrę w pionie, poziomie i kwadracie za wyjątkiem wstawionego miejsca oczywiście.
Jeżeli po jakimś odznaczeniu gdzieś wyszło że nie zostało żadnego bitu to znaczy że trzeba się cofnąć.

Ale zastanawia mnie gdzie trzeba się cofnąć? jedno miejsce wstecz, tak próbowałem i nie rozwiązuje to poprawnie sudoku.
Dodałem takie dwie funkcje

 
bool remove_value(int x, int y, int value)
{
	// na początek usuwamy tylko w poziomie.
	for(int i=0; i<9; i++)
	{
		int max = tab_insert[x][i][9];
		for(int k=0; k<max; k++)
		{
			if(tab_insert[x][i][k]==value)
			{
				tab_insert[x][i][k]=0;
				tab_insert[x][i][9]-=1;
				if(tab_insert[x][i][9]==0) return prev(x, y);
			}
		}
	}
	return true;
}

bool prev(int x, int y)
{
   if (x == 0 && y == 0) return solve(8, 8);
    else if (x == 0) return solve(8, y - 1);
    else return solve(x - 1, y);

}

remove_value() wywołuję po wstawieniu liczby ale to chyba nie o to chodzi, co miał na myśli @_13th_Dragon.

Ile z takiego kodu można jeszcze wycisnąć, bo znalazłem jakiś co rozwiązuje te najtrudniejsze sudoku do 100ms.

... poniżej 5ms na niezbyt szybkim komputerze.

a kod zły jest?