[C][C++] rozwiązywanie sudoku

[przelacz]

Witam,
Na wstępie zaznaczę, że jestem w programowaniu zielony, znam minimalne podstawy.
"dziś na zajęciach w szkole otrzymaliśmy zadanie : stworzyć program, który rozwiązywałby sudoku na planszy 9x9. Najlepiej z użyciem rekurencji.
Czy ktoś mógłby mi podpowiedzieć/pomóc w napisaniu/wytłumaczyć jak to zrobić, lub chociaż na podstawie istniejącego programu wytłumaczyć mi mniej więcej na czym to polega." takie pytanie zadałem na jakimś forum.
W odpowiedzi otrzymałem, że :

Metoda siłowa:
1. Sprawdź ile liczb może być w danej komórce, jeśli tylko jedna, to będzie ta poprawna. Szukasz w danym kwadracie, w pionie i poziomie.
2. Dla każdego wiersza, kolumny i kwadratu wyznaczasz jakich liczb brakuje. Jeśli dana brakująca liczba może wystąpić tylko na jednym polu w danym wierszu/kolumnie/kwadracie, wpisujesz ją. Rekurencja jest potrzebna, gdy trzeba zgadywać, bo żadna z wyżej wymienionych metod nie znalazła żadnego rozwiązania. Ogólny szablon rozwiązania:

rozwiąż:
dopóki nierozwiązana:
zrobiono=nie
dla każdej komórki:
sporządź listę możliwych liczb do wstawienia
jeśli ta lista ma tylko jedną liczbę - wstaw ją, zrobiono=tak
dla każdego wiersza/kolumny/kwadratu:
sprawdź brakujące liczby i na jakich komórkach mogą wystąpić
jeśli dana brakująca liczba może wystąpić tylko na jednym polu w danym wierszu/kolumnie/kwadracie, wypełnij, zrobiono=tak
jeśli zrobiono=nie:
skopiuj planszę i uzupełnij jedno pole jakimś możliwym rozwiązaniem
rozwiąż skopiowaną planszę
rozwiązana poprawnie? zakończ
rozwiązana niepoprawnie? skopiuj planszę jeszcze raz i uzupełnij innym możliwym rozwiązaniem
rozwiązana poprawnie?
wypisz planszę, zakończ z komunikatem "poprawny"
rozwiązanie niepoprawne?
zakończ z komunikatem "błędny"

Tak więc wziąłem się do roboty. I... nie wiem jak obejść conio.h. Ktoś mi może pomóc ? I przy okazji, nie za bardzo wiem jak użyć rekurencji w podanym wyżej szablonie. Na końcu gdy wszystkie 'pojedyncze' liczby zostaną wstawione program miałby odwołać się do tych liczb i co dalej ?

Z góry dzięki za pomoc,
Pozdrawiam serdecznie.

[JSokol]

A w czym miałoby Ci conio.h być niezbędnym?
Najlepiej jakbyś pokazał kod który już wyczarowałeś i odnośnie niego zadał pytania - życie pokazuje, że nikt nikomu tutaj od zera niczego nie pisze, zresztą nie tylko tutaj, bo nie o to chodzi w pomaganiu.

[przelacz]

Wyczarować nie wyczarowałem, próbowałem ogarnąć wg. powyższego schematu, ale wyszło raczej nic wartego rzucenia okiem i multum błędów.
Znalazłem gdzieś przypadkiem, szukając jakiś wskazówek jak to ma wyglądać mniej czy więcej, takie coś :

Kod: Zaznacz cały

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct _ciag {
   int len;
   int cyfry[9];
   } ciag;

int wiersz_brakujace_liczby(int w);
int kolumna_brakujace_liczby(int k);
int kwadrat_brakujace_liczby(int x, int y);

int wybierz_liczbe(int a);

int i,x,y;
int tablica[9][9];
int wiersze[9];
int kolumny[9];
int kwadraty[3][3];
int czy_wpisal;

int main() {
   printf("Podaj liczby (0 oznacza puste pole)\n");
   printf("Dziewięć lini po dziewięć liczb)\n");
   for(i=0;i<9;i++)
      scanf("%i %i %i %i %i %i %i %i %i",
         &tablica[i][0],
         &tablica[i][1],
         &tablica[i][2],
         &tablica[i][3],
         &tablica[i][4],
         &tablica[i][5],
         &tablica[i][6],
         &tablica[i][7],
         &tablica[i][8]);


   /* glowny algorytm */
   do {
      /* brakujace liczby w poszczegolnych kolumnach i wierszach*/
      for(i=0;i<9;i++) {
         kolumny[i]=kolumna_brakujace_liczby(i);
         wiersze[i]=wiersz_brakujace_liczby(i);
         }

      /* brakujace liczby w poszczegolnych kwadratach */
      for(x=0;x<3;x++) for(y=0;y<3;y++) kwadraty[x][y]=kwadrat_brakujace_liczby(x,y);


      czy_wpisal = 0;
      for(x=0;x<9;x++) for(y=0;y<9;y++) if(tablica[x][y]==0) {
            i = wiersze[x] & kolumny[y] & kwadraty[x/3][y/3];
            i = wybierz_liczbe(i);
            if(i!=0) { tablica[x][y]=i; czy_wpisal=1; }
            }
      } while(czy_wpisal!=0);

   printf("\n----------------------------\n");
   for(x=0;x<9;x++) {
      for(y=0;y<9;y++) printf("%i ", tablica[x][y]);
      printf("\n");
      }

   system("PAUSE");
   return 0;
   }

int wiersz_brakujace_liczby(int w) {
   int wiersz,i;
   wiersz=0;
   for(i=0;i<9;i++)
      if(tablica[w][i]) {
         wiersz|=(1 << (tablica[w][i]-1));
         }

   wiersz=~wiersz;
   wiersz&=511;
   return wiersz;
   }

int kolumna_brakujace_liczby(int k) {
   int kolumna,i;
   kolumna=0;
   for(i=0;i<9;i++)
      if(tablica[i][k])
         kolumna|=(1 << (tablica[i][k]-1));
   kolumna=~kolumna;
   kolumna&=511;
   return kolumna;
   }

int kwadrat_brakujace_liczby(int x, int y) {
   int kwadrat,i,j;
   kwadrat=0;
   for(i=x*3;i<x*3+3;i++)
      for(j=y*3;j<y*3+3;j++)

         if(tablica[i][j])
            kwadrat|=(1 << (tablica[i][j]-1));

   kwadrat=~kwadrat;
   kwadrat&=511;
   return kwadrat;
   }

int wybierz_liczbe(int a) {
   int i, ret = -1;
   for(i=0;i<10;i++)
      if(a & (1<<i))
         if(ret==-1) ret=i; else
            return 0;

   return ret+1;
   }

Czytałem, zagłębiałem się, bo jest jakiś tam opis kodu, resztę można się domyślić i wydedukować. Wrzuciłem do kompilatora i wyrzuca właśnie wspomniane przeze mnie conio.h, stąd też pytanie jak je zastąpić...

[ethanak]

To powiedz mi w której linijce kodu wsiadasz na tego konia.
Typowy kod dosianego debila co przepisuje jeden od drugiego nawet nie próbując zrozumieć co jaka linijka w kodzie znaczy...
BTW. system("PAUSE") to też raczej mało prawdopodobne żeby poszło (chyba że sobie PAUSE sam zrobisz).

[przelacz]

Na wstępie zaznaczę, że jestem w programowaniu zielony, znam minimalne podstawy.

Dla Ciebie mogę być i debilem, jakoś się nie przejmuję, w 1. poście m.in. jest zawarte :

Czy ktoś mógłby mi podpowiedzieć/pomóc w napisaniu/wytłumaczyć jak to zrobić, lub chociaż na podstawie istniejącego programu wytłumaczyć mi mniej więcej na czym to polega.

Powyższy kod, znaleziony jest na jakimś forum, gdzie niby wszystko wszystkim działało, stąd też skupiłem się na bibliotece którą w kompilatorze wyrzucało mi jako error.

[ethanak]

Gwoli ścisłości: za debila dotychczas uważałem autora owego arcydzieła. Jeśli Ty uważasz że jesteś debilem, to ja się nie będę kłócić.
Zadam ponownie pytanie: gdzie masz w tym kodzie użycie biblioteko conio? Jeśli tego pytania nie zrozumiałeś - nadajesz się idealnie na polityka, sprzedawcę marchewki czy hydraulika, ale od programowania to się trzymaj z daleka.
Poza tym chciałeś pomocy... a odrzucasz pomoc kogoś kto jest zawodowym programistą w C? Ciekawe, ciekawe... czy przypadkiem nie uczysz się w szkole Marketingu i Zarządzania?

[przelacz]

nie, nie odrzucam, odebrałem to jako niechęć do mojej niewiedzy, przepraszam, za niezrozumienie intencji. I nie, nie uważam się za debila.
Ok, mój błąd, ślepo zaufałem twórcy, nie zwracając uwagi na brak funkcji korzystających z ów biblioteki.
I nie, nie uczę się w takiej szkole.

-- 8 paź 2012, o 22:26 --

ok, a czy ktoś mógłby mi wytłumaczyć, czemu powyższy kod rozwiązuje różne diagramy, ale przy takich danych wejściowych :

{1,0,0, 7,8,9, 4,0,0},
{2,0,0, 0,0,0, 5,0,0},
{3,0,0, 0,0,0, 6,0,0},

{0,4,0, 0,0,0, 0,7,0},
{0,5,0, 1,2,3, 0,8,0},
{0,6,0, 0,0,0, 0,9,0},

{0,0,7, 0,0,0, 0,0,1},
{0,0,8, 0,0,0, 0,0,2},
{0,0,9, 4,5,6, 0,0,3}

dane wyjściowe są takie same, diagram pozostaje nie ruszony ?

[linuxozaurus]

{1,0,0, 7,8,9, 4,0,0},
{2,0,0, 0,0,0, 5,0,0},
{3,0,0, 0,0,0, 6,0,0},

{0,4,0, 0,0,0, 0,7,0},
{0,5,0, 1,2,3, 0,8,0},
{0,6,0, 0,0,0, 0,9,0},

{0,0,7, 0,0,0, 0,0,1},
{0,0,8, 0,0,0, 0,0,2},
{0,0,9, 4,5,6, 0,0,3}

bo brałeś przykład który nie ma rozwiązania.

z innej beczki ja sama rozwiązuję sudoku na papierze

[adammaj1]

Zapisz jako c.c

Kompilacja :
gcc c.c -Wall

wynik :
c.c: In function ‘wybierz_liczbe’:
c.c:110:13: warning: suggest explicit braces to avoid ambiguous ‘else’

Kod po drobnych zmianach poniżej.

Uruchomienie :
./a.out

Trochę męczące jest ręczne wprowadznie kodu
więc zmieniłem to.

Znajdz w google : sudoku rozwiązywanie
jak jest tu użyta metoda.

Czy zapomocą czy_wpisal można sprawdzić czy coś zostało zmienione ?

HTH

Adam

Kod: Zaznacz cały

     #include <stdio.h>
   //#include <conio.h>
    #include <stdlib.h>

    typedef struct _ciag {
       int len;
       int cyfry[9];
       } ciag;

    int wiersz_brakujace_liczby(int w);
    int kolumna_brakujace_liczby(int k);
    int kwadrat_brakujace_liczby(int x, int y);

    int wybierz_liczbe(int a);

    int i,x,y;
    int tablica[9][9] = {{1,0,0, 7,8,9, 4,0,0},
{2,0,0, 0,0,0, 5,0,0},
{3,0,0, 0,0,0, 6,0,0},

{0,4,0, 0,0,0, 0,7,0},
{0,5,0, 1,2,3, 0,8,0},
{0,6,0, 0,0,0, 0,9,0},

{0,0,7, 0,0,0, 0,0,1},
{0,0,8, 0,0,0, 0,0,2},
{0,0,9, 4,5,6, 0,0,3}};
    int wiersze[9];
    int kolumny[9];
    int kwadraty[3][3];
    int czy_wpisal;

 
    int wiersz_brakujace_liczby(int w) {
       int wiersz,i;
       wiersz=0;
       for(i=0;i<9;i++)
          if(tablica[w][i]) {
             wiersz|=(1 << (tablica[w][i]-1));
             }

       wiersz=~wiersz;
       wiersz&=511;
       return wiersz;
       }

    int kolumna_brakujace_liczby(int k) {
       int kolumna,i;
       kolumna=0;
       for(i=0;i<9;i++)
          if(tablica[i][k])
             kolumna|=(1 << (tablica[i][k]-1));
       kolumna=~kolumna;
       kolumna&=511;
       return kolumna;
       }

    int kwadrat_brakujace_liczby(int x, int y) {
       int kwadrat,i,j;
       kwadrat=0;
       for(i=x*3;i<x*3+3;i++)
          for(j=y*3;j<y*3+3;j++)

             if(tablica[i][j])
                kwadrat|=(1 << (tablica[i][j]-1));

       kwadrat=~kwadrat;
       kwadrat&=511;
       return kwadrat;
       }

    int wybierz_liczbe(int a) {
       int i, ret = -1;
       for(i=0;i<10;i++)
          if(a & (1<<i))
             if(ret==-1) ret=i; 
             else return 0;

       return ret+1;
       }



   int main() {

       printf(" ----  wejście  ----------------------------\n");
       for(x=0;x<9;x++) {
          for(y=0;y<9;y++) printf("%i ", tablica[x][y]);
          printf("\n");
          }
       printf(" ------------- obliczenia ----------------\n ");
       do {
          /* brakujace liczby w poszczegolnych kolumnach i wierszach*/
          for(i=0;i<9;i++) {
             kolumny[i]=kolumna_brakujace_liczby(i);
             wiersze[i]=wiersz_brakujace_liczby(i);
             }

          /* brakujace liczby w poszczegolnych kwadratach */
          for(x=0;x<3;x++) for(y=0;y<3;y++) kwadraty[x][y]=kwadrat_brakujace_liczby(x,y);


          czy_wpisal = 0;
          for(x=0;x<9;x++) for(y=0;y<9;y++) if(tablica[x][y]==0) {
                i = wiersze[x] & kolumny[y] & kwadraty[x/3][y/3];
                i = wybierz_liczbe(i);
                if(i!=0) { tablica[x][y]=i; czy_wpisal=1; }
                }
          } while(czy_wpisal!=0);

       printf(" ----  wynik ----------------------------\n");
       for(x=0;x<9;x++) {
          for(y=0;y<9;y++) printf("%i ", tablica[x][y]);
          printf("\n");
          }

       
       return 0;
       }

[ethanak]

Zapisz jako c.c

Kompilacja :
gcc c.c -Wall

wynik :
c.c: In function ‘wybierz_liczbe’:
c.c:110:13: warning: suggest explicit braces to avoid ambiguous ‘else’

No i co z tego? Równie dobrze można kompilować z -Eall. A programowanie w C nie polega na pozbywaniu się sugestii kompilatora.

[adammaj1]

-Wall tells the compiler to implement 'all' Warning options.
Gdzie jest pozbywanie się sugestii kompilatora ?

[ethanak]

A, sorry, zasugerowałem się czort wie czemu że koniecznie usiłujesz to poprawić. Zwracam honor.