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
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.
0
no właśnie - przed chwilą wkleiłem sobie to twoje sudoku do pliku txt i wczytałem na tej stronce no i źle się wczytało...
sam sobie sprawdź czy ta stronka poprawnie wczytuję to twoje sudoku.
0
Ty wczytujesz plik a ja tam wypełniam :)
ten link co teraz z tym kodem javy podesłałem to jest to o czym mówisz?
0
tak to rozwiązanie z backtracingiem w javie powinno być dobre...
moje rozwiązanie jest w języku C - kiedyś uczyłem się rekurencji na tego typu zadankach.
0
no ja to przerobie sobie na c++, bo javy nie trawie
0
to przerabiaj ... może w moim programie jest gdzieś błąd....
0
jak przerobisz ten kod javy to napisz na forum ile twój program daje rozwiązań dla twojego przykładu.
0
zanim go przerobie, odpale taki jaki jest w java, zobacze czy to dziala w ogole , instaluje netbeansa. zrobie to napisze ile mi daje.
0
ale po co się męczyć z javą skoro w necie jest masa rozwiązań w C++
http://edwinchan.files.wordpress.com/2006/01/sudoku.pdf
0
to co dales w linku nie dziala ;]
0
to poszukaj sobie takie które działa - chociaż to dziwne żeby nie działało. A co nie działa?
0
po zeskanowaniu sudoku, nie rozwiązuje go, wynik jest taki sam jak wejście :)
0
Zrobiłem na szybko kod w Pythonie, mimo tego, że działa dość długo (z pół minuty), to dla sudoku ne0 zwraca 1917 rozwiązań, więc ja bym stawiał na tę metodę (potwierdza się ze stroną), a nie na kod moje_rozwiązanie. Zamieszczam kod, brzydki i bez komentarzy, ale z wypisywaniem niepotrzebnych danych. http://pastebin.com/cUP7qs0q
0
no cóż - ja się temu nie przyglądałem ale popatrz dobrze może coś tam przeoczyłeś.
moje rozwiązanie:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define rozmiarSudoku 9 // Rozmiar Sudoku 9 x 9 ; 9 liczba kwadrarow
#define rozmiarKwadratu 3 // rozmiar małego kwadratu sudoku
//Zmienne pomocnicze
static int an1 = 0;
static int bn1 = 0;
static bool go = false;
static int yn1 = 0;
static int xn1 = 0;
static bool go1 = 0;
int licznikRoz = 0 ;
//
typedef struct
{
int x;
int y;
int x1;
int y1;
} RamkaKwadratu; // Struktura opisuje grancie malego kwadratu 3x3
typedef struct
{
int wartosc;
bool jestUzywana;
}Numerki; //Struktura trzyma numerki od 1...9
typedef struct
{
RamkaKwadratu granica;
Numerki tablicaNumerkow[rozmiarSudoku];
}Kwadrat; // Ta struktura opisuje kwdrat sudoku 3x3
int tablicaSudoku[rozmiarSudoku][rozmiarSudoku]; // tu jest nasze rozwiazanie
Kwadrat sudokuKwadaty[rozmiarSudoku]; //tablica kwadratow(3x3) sudoku
void pokaszTabliceSudoku( int tablicaSudoku[rozmiarSudoku][rozmiarSudoku]);//pokasz sudoku
void czytajSudoku(char * nazwaPliku);
void rozwiazSudoku( int numerKwadratu,int y , int x );
bool sprawdzWierszeKolumny( int wiersz , int kolumna , int wartosc ); // czy danwa wartosc jest w kolumnie i w wierszy
void inicializuj(); // inicializuj sudoku
void zapiszTabliceSudoku( int tabSudoku[rozmiarSudoku][rozmiarSudoku] );
int main( int argc ,char * argv[])
{
printf("Autorem programu jest Pawel Lepko: [email protected] \n");
printf("\n");
char nazwaPliku[200];
nazwaPliku[0] = '\0';
printf("Podaj nazwe pliku \n");
scanf("%s", nazwaPliku);
czytajSudoku(nazwaPliku);
inicializuj();
licznikRoz = 0;
pokaszTabliceSudoku(tablicaSudoku);
rozwiazSudoku( 0,0,0);//znajdz rozwiazanie
printf("Liczba rozwiazan %d \n", licznikRoz );
system("pause");
}
void rozwiazSudoku( int numerKwadratu, int y , int x )
{
int n = 0;
//Pracujemy nad kwadratem numer : numerKwadratu
if ( tablicaSudoku[y][x] == 0 ) // czy pole jest zajetes
{
//pokaszTabliceSudoku(tablicaSudoku);
//pokaszTabliceSudoku(tablicaSudoku);
for( n = 0 ;n < rozmiarSudoku; n++)
{
//sprawdz czy wybrany numerek jest zajety
if ( ! sudokuKwadaty[numerKwadratu].tablicaNumerkow[n].jestUzywana )
{
// sprawdzamy czy wstawienie numerka nie popsuje nam zawartosci planszy
if ( ! sprawdzWierszeKolumny( y ,x , sudokuKwadaty[numerKwadratu].tablicaNumerkow[n].wartosc ) )
{
tablicaSudoku[y][x] = sudokuKwadaty[numerKwadratu].tablicaNumerkow[n].wartosc;
sudokuKwadaty[numerKwadratu].tablicaNumerkow[n].jestUzywana = true;
//Czy mamy rozwiazanie ???
if( (y==rozmiarSudoku-1) && (x==rozmiarSudoku-1) )
{
//printf("Rzowiazanie \n");
//pokaszTabliceSudoku(tablicaSudoku);
//zapiszTabliceSudoku(tablicaSudoku);
//getchar();
licznikRoz++;
return;
}
//Wywolania rekurencyjne
an1 = x;
bn1 = y;
go = false;
if ( (( x + 1 ) <= ( sudokuKwadaty[numerKwadratu].granica.x1)) && (( x + 1 ) < rozmiarSudoku) )
{
an1 = an1 + 1; go = true;
}
else if ( ((y + 1 ) <= (sudokuKwadaty[numerKwadratu].granica.y1)) &&((y + 1 ) < rozmiarSudoku) )
{
bn1 = bn1 + 1;
an1 = 0;
go = true;
}
if ( go )
rozwiazSudoku(numerKwadratu, bn1, an1); // szukaj rozwiązania w bierzacym kwadracie
else if (numerKwadratu + 1 != (rozmiarSudoku + 1)) // przejdz do nastepnego kwadratu
rozwiazSudoku(numerKwadratu + 1 , sudokuKwadaty[numerKwadratu + 1].granica.y,sudokuKwadaty[numerKwadratu + 1].granica.x);
//BackTracing ....cofanie
tablicaSudoku[y][x]=0;
sudokuKwadaty[numerKwadratu].tablicaNumerkow[n].jestUzywana = false;
}
}
}
}
else // jesli pole ma stała wartosc to go nie ustawiaj ; idz na inne pola
{
if( (y==rozmiarSudoku-1) && (x==rozmiarSudoku-1))
{
//printf("Rozwiazanie ... \n");
//pokaszTabliceSudoku(tablicaSudoku);
//getchar();
licznikRoz++;
return;
}
else
{
// idziemy kwadratami po rzędach
yn1 = y;
xn1 = x;
go1 =false;
if ( (( x + 1 ) <= ( sudokuKwadaty[numerKwadratu].granica.x1)) && (( x + 1 ) < rozmiarSudoku) )
{
xn1 = xn1 + 1; go1 = true;
}
else if ( ((y + 1 ) <= (sudokuKwadaty[numerKwadratu].granica.y1)) &&((y + 1 ) < rozmiarSudoku) )
{
yn1 = yn1 + 1;
xn1 = 0;
go1 = true;
}
if ( go1 )
rozwiazSudoku(numerKwadratu, yn1, xn1);
else if (numerKwadratu + 1 != (rozmiarSudoku - 1))
rozwiazSudoku(numerKwadratu + 1 , sudokuKwadaty[numerKwadratu + 1].granica.y,sudokuKwadaty[numerKwadratu + 1].granica.x);
}
}
}
bool sprawdzWierszeKolumny( int wiersz , int kolumna , int wartosc )
{
int i = 0;
// sprawdz row
for( i = 0; i < rozmiarSudoku ;i++ )
{
if (tablicaSudoku[wiersz][i] == wartosc )
return true;// wartosc exist in row
}
for( i = 0; i < rozmiarSudoku; i++)
{
if ( tablicaSudoku[i][kolumna] == wartosc)
return true;
}
return false;// not exist
}
void czytajSudoku(char * fileName)
{
FILE * f = fopen(fileName, "r");
if ( f== NULL )
{
puts("Podales zla nazwe pliku \n");
system("pause");
exit(0);
}
else
{
int i = 0;
char znak = 0;
int wiersz = 0;
char buff[rozmiarSudoku] = {0};
while( (znak = fgetc(f))!=EOF )
{
if ( znak!='\n' && znak!='\r') // znak '\r' jest potrzeby w Linuxie
{
tablicaSudoku[wiersz][i++] = atoi( &znak);
if ( i % rozmiarSudoku == 0 )
wiersz++;
if ( i >=rozmiarSudoku)
i = 0;
}
}
}
}
void zapiszTabliceSudoku( int tabSudoku[rozmiarSudoku][rozmiarSudoku] )
{
char nazwaPliku[200];
FILE * plik = NULL;
int i = 0;
int j = 0;
nazwaPliku[0] = '\0';
printf("Podaj nazwe pliku do zapisania rozwiazania \n");
scanf("%s", nazwaPliku);
plik = fopen(nazwaPliku,"w");
if ( plik == NULL )
{
printf("Nie mogę zapisac danych do pliku \n");
}
else
{
fprintf(plik,"</---------Sudoku-------------\n");
for ( i = 0 ; i < rozmiarSudoku ; i++ )
{
for ( j = 0 ; j < rozmiarSudoku ; j++ )
{
if ( j % 3 == 0 ) printf(" " );
fprintf(plik," %d" , tabSudoku[i][j] );
}
if ( i==2 || i == 5 || i ==8) printf("\n");
fprintf(plik,"\n");
}
fprintf(plik,"----------------------------/>\n");
fprintf(plik,"\n");
fflush(plik);
fclose(plik);
}
}
void pokaszTabliceSudoku( int tabSudoku[rozmiarSudoku][rozmiarSudoku])
{
int i = 0;
int j = 0;
printf("</---------Sudoku-------------\n");
for ( i = 0 ; i < rozmiarSudoku ; i++ )
{
for ( j = 0 ; j < rozmiarSudoku ; j++ )
{
if ( j % 3 == 0 ) printf(" " );
printf(" %d" , tabSudoku[i][j] );
}
if ( i==2 || i == 5 || i ==8) printf("\n");
printf("\n");
}
printf("----------------------------/>\n");
printf("\n");
}
void inicializuj()
{
//Set Sudoku Kwadrat granicas
//0
sudokuKwadaty[0].granica.x = 0;
sudokuKwadaty[0].granica.y = 0;
sudokuKwadaty[0].granica.x1 = 2;
sudokuKwadaty[0].granica.y1 = 2;
//1
sudokuKwadaty[1].granica.x = 3;
sudokuKwadaty[1].granica.y = 0;
sudokuKwadaty[1].granica.x1 = 5;
sudokuKwadaty[1].granica.y1 = 2;
//2
sudokuKwadaty[2].granica.x = 6;
sudokuKwadaty[2].granica.y = 0;
sudokuKwadaty[2].granica.x1 = 8;
sudokuKwadaty[2].granica.y1 = 2;
//3
sudokuKwadaty[3].granica.x = 0;
sudokuKwadaty[3].granica.y = 3;
sudokuKwadaty[3].granica.x1 = 2;
sudokuKwadaty[3].granica.y1 = 5;
//4
sudokuKwadaty[4].granica.x = 3;
sudokuKwadaty[4].granica.y = 3;
sudokuKwadaty[4].granica.x1 = 5;
sudokuKwadaty[4].granica.y1 = 5;
//5
sudokuKwadaty[5].granica.x = 6;
sudokuKwadaty[5].granica.y = 3;
sudokuKwadaty[5].granica.x1 = 8;
sudokuKwadaty[5].granica.y1 = 5;
//6
sudokuKwadaty[6].granica.x = 0;
sudokuKwadaty[6].granica.y = 6;
sudokuKwadaty[6].granica.x1 = 2;
sudokuKwadaty[6].granica.y1 = 8;
//7
sudokuKwadaty[7].granica.x = 3;
sudokuKwadaty[7].granica.y = 6;
sudokuKwadaty[7].granica.x1 = 5;
sudokuKwadaty[7].granica.y1 = 8;
//8
sudokuKwadaty[8].granica.x = 6;
sudokuKwadaty[8].granica.y = 6;
sudokuKwadaty[8].granica.x1 = 8;
sudokuKwadaty[8].granica.y1 = 8;
//inicializuj numerKwadratuerkis
int numerKwadratu = 0;
int N = 0;
int wiersz = 0;
int kolumna = 0;
for ( numerKwadratu = 0 ; numerKwadratu < rozmiarSudoku; numerKwadratu++ )
{
for ( N = 0 ; N < rozmiarSudoku ; N++ )
{
sudokuKwadaty[numerKwadratu].tablicaNumerkow[N].wartosc = N + 1;
sudokuKwadaty[numerKwadratu].tablicaNumerkow[N].jestUzywana = false;
}
//Kwadrat jest zainicjalizowany
for( wiersz = sudokuKwadaty[numerKwadratu].granica.y; wiersz <= sudokuKwadaty[numerKwadratu].granica.y1;wiersz++)
{
for( kolumna = sudokuKwadaty[numerKwadratu].granica.x; kolumna <= sudokuKwadaty[numerKwadratu].granica.x1; kolumna++)
{
if ( tablicaSudoku[wiersz][kolumna] > 0 )
{
sudokuKwadaty[numerKwadratu].tablicaNumerkow[ tablicaSudoku[wiersz][kolumna] - 1].jestUzywana = true;
}
}
}
//
}
}
Program działa ok - ale nie wiem czemu daje mi za mało rozwiązań. Jak ktoś zechcę to poprawić to bardzo proszę.
1
Widzę, że kolega, który założył wątek probuje dostac się do dużej firmy na A..
0
?
0
o co chodzi z tą firmą? Na A.... to tylko A-s-s-e-c-0? Dobrze myślę?
0
nie wiem o co mu chodzi :/
0
no to niech powie o co mu chodzi?
0
(: 2dǝʇs ˙lǝʌǝp-dɥd oƃoɹpǝllɐ