#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("Dziewiec lini po dziewiec 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;
   }