[c++] sudoku

0

witam

Napisałem program, który rozwiązuje sudoku (czyt. powinien rozwiązywać), lecz coś nie wypaliło i nie mogę doszukać się błędu.
Dodam, że po włączeniu użycie procesora rośnie do 100%.
Widziałem, że na necie są opisane jakieś algorytmy do sudoku, ale chciałem to zrobić w ten sposób, czyli jakby "ręcznie".
Może ktoś dostrzeże błąd, którego ja nie widzę.
oto kod:

#include <stdio.h>

#define N 9

using namespace std;

//==========================  deklaracje funkcji  ==============================

bool czyWczesniej(int **macierz, int kolumna, int wiersz, int wartosc);
void wczytajDane (int **macierz, int ileDanych);
void wstawLiczbe (int **macierz, int wie, int kol, int wartosc);
void generuj (int **macierz);
void wyswietl(int **macierz);

//==============================================================================

int main(void)
{
    int **macierz, ile; 

        macierz = new int* [N];

        for(int i=0; i<N; ++i)
        {
            macierz[i] = new int [N];
        }

        //=========  wyzerowanie macierzy ========
        for(int i=0; i<N; ++i)
        {
            for(int j=0; j<N; ++j)  
            {
                *( *(macierz + i) + j ) = 0;            
            }
        }

        printf("ilosc znanych cyfr: ");
        scanf("%d",&ile);

        wczytajDane(macierz,ile);
        generuj (macierz);
        wyswietl(macierz);

    return 0;
}

//============ sprawdzenie, czy wartosc wystapila juz w kolumnie,wierszu lub 'kwadracie' ===========

bool czyWczesniej(int **macierz, int kolumna, int wiersz, int wartosc)
{   

        //============ przeszukanie kolumny ==============

        for(int i=0; i<wiersz; ++i)
        {
            if( (* (* (macierz + i) + kolumna)) == (* (* (macierz + wiersz) + kolumna)) )
                return true;
        }

        //============ przeszukanie wiersza ==============

        for(int i=0; i<kolumna; ++i)
        {
            if( (* (* (macierz + wiersz) + i)) == (* (* (macierz + wiersz) + kolumna)) )
                return true;
        }

        //=========== wyznaczenie polozenia poczatkowego elementu danego kwadratu =============

        int     wie_pocz = (wiersz/3)*3,
            kol_pocz = (kolumna/3)*3;

        //============ przeszukanie 'kwadratu' =============

        for(int i=wie_pocz; i<(wie_pocz+3); ++i)
        {
            for(int j=kol_pocz; j<(kol_pocz+3); ++j)
            {
                if( (* (* (macierz + i) +j)) == (* (* (macierz + wiersz) + kolumna)) )
                    return true;
            }
        }

    return false;
}

//============================== wczytanie znanych liczb =================================

void wczytajDane(int **macierz, int ile_danych)
{
        int wie, kol;

                for(int i=0; i < ile_danych; ++i)
                {
                        printf("\npodaj wiersz oraz kolumne (oddziel spacja) ");
                        scanf("%d %d",&wie, &kol);

                        printf("\npodaj liczbe: ");
            scanf("%d",((macierz + wie) + kol));
                }
}

//=========================== wstawienie liczby do macierzy =============================

void wstawLiczbe(int **macierz, int wie, int kol, int wartosc)
{
    (* (* (macierz + wie) + kol)) = wartosc;
}

//=============== wypelnienie macierzy liczbami zgodnymi z zalozeniami sudoku =============

void generuj(int **macierz)
{
    int wartosc = 1;

    for(int i=0; i < N; ++i)
    {
        for(int j=0; j < N; ++j)
        {
            while( czyWczesniej(macierz, j, i, wartosc))
            {
                ++wartosc;
            }

            wstawLiczbe(macierz, i, j, wartosc);
            wartosc = 1;
        }
    }
}

//========================== wyswietlenie wypelnionej macierzy =========================

void wyswietl(int **macierz)
{
    for(int i=0; i < N; ++i)
    {
        for(int j=0; j < N; ++j)
        {
            printf("%d ", *( *( macierz + i ) + j));
        }

        printf("\n");
    }
}

z góry dziękuję
pzdr.

0

jestes pewien ze funkcja 'generuj' rzeczywiscie jest az tak prosta? pare sudokow rozwiazalem i wydaje mi sie ze problem jest bardziej skomplikowany, ale moze sie myle..

ps. zamiast ( (macierz + i) + j ) szybciej i czytelniej jest pisac macierz[i][j]
ps2. opisz moze dokaldniej co programowi nie wypalilo..

0

quetzalcoatl:
masz rację, przypuszczając, że funkcja 'generuj' jest za prosta. W takiej postaci rozwiąże tylko pewne klasy sudoku - mój kolega rok temu pisał na zalkę z ćwiczeń rozwiązywanie sudoku w C - tą samą metodą. Wzięliśmy jakieś czasopismo z Sudoku i okazało się, że rozwiązywał te oznaczone jako "łatwe", bardziej zaawansowane rozwiązywał tylko częściowo - tzn. pisał dotąd, dopóki był pewien, później zwracał sudoku nie wypełnione do końca.

Źródło sobie zachowałem, przeformatowując na swój styl, z zamiarem poprawienia. Ale znalazło się 1000 innych rzeczy... tak czy inaczej, skoro mam gotowy kod, to mogę go rzucić, może w czymś pomoże.

#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;
   }
0

dziekuję za pomoc :)
biorę się za lekturę kodu.

pzdr.

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