# include<iostream>
# include<string>
class SudokuFeld{
	public:
		SudokuFeld(){
			ziffer = 0;
			h = -1;
			v = -1;
		};
		SudokuFeld(int z){
			ziffer = z;
		};
		void printZiffer(){
			std::cout << ziffer;
		};	
		void setZiffer(int z){
			ziffer = z;
		};
		void setH(int x){
			h = x;
		}
		void setV(int x){
			v = x;
		}
		int getH(){
			return h;
		}
		int getV(){
			return v;
		}
		const int getZiffer(){
			return ziffer;
		};
	private:
		int ziffer;
		int h;
		int v;
};
class Sudoku{
	public:
		SudokuFeld *ziffern;
		Sudoku(int z[]){
			ziffern = new SudokuFeld[81];
			for(int i = 0; i < 81;i++){
				ziffern[i].setZiffer(z[i]);
				ziffern[i].setH(i%9);
				ziffern[i].setV(i/9);
			}
		};
		void printSudoku(){
			for(int i = 0;i < 9;i++){
				for(int j = 0;j < 9;j++){
					std::cout << getZiffer((i*9)+j);
				}
				std::cout << std::endl;
			}
		};
		void test(){
			int *t = getHLine(0);
			int *r = getVLine(0);
			int *s = getQuadrat(0, 0);
			std::cout << std::endl;
			for(int i = 0; i < 9; i++){
				std::cout << std::endl << t[i] ;
			}
			std::cout << std::endl;
			for(int i = 0; i < 9; i++){
				std::cout << std::endl << r[i] ;
			}
			std::cout << std::endl;
			for(int i = 0; i < 9; i++){
				std::cout << std::endl << s[i] ;
			}
			std::cout << std::endl;
		
			for(int i = 0; i < 81; i++){
				if(ziffern[i].getZiffer()==0){
					int *p = getPossible(ziffern[i]);
					std::cout << ziffern[i].getH() << ":" << ziffern[i].getV() << " = ";
					for(int i = 0; i < 9; i++){
						if(p[i]==0) break;
						std::cout << p[i] ;
					}
					std::cout << std::endl;
				}
			}
			


			
		};
		~Sudoku(){
			delete[] ziffern;		
		};
	private:
		int *getPossible(SudokuFeld& feld){
			int *re = new int[10];
			for(int s = 0; s < 10; s++){
				re[s]=0;
			}
			int pos = 0;
			int *pr = getHVQArray(feld);
			for(int i = 1; i < 10; i++){
				bool find = false;
				for(int j = 0; j < 27; j++){
					if(pr[j]==i){
						find = true;
					}
				}
				if(!find){
					re[pos++]=i;
				}
			}
			return re;
		};
		const int getZiffer(int z){
			return ziffern[z].getZiffer();
		};
		int *getHVQArray(SudokuFeld feld){
			int *re = new int[27];
			int *hl = getHLine(feld.getV());
			int *vl = getVLine(feld.getH());
			int *qu = getQuadrat(feld.getH(), feld.getV());
			int u = 0;
			int i;
			for(i = 0; i < 9 ; i++){
				re[u] = hl[i];
				u++;
			}
			for(i = 0; i < 9 ; i++){
				re[u] = vl[i];
				u++;
			}
			for(i = 0; i < 9 ; i++){
				re[u] = qu[i];
				u++;
			}

			return re;
		}
		int *getHLine(int z){
			int *re = new int[9];
			for(int i = 0; i < 9 ; i++){
				re[i] = getZiffer((z*9)+i);
			}
			return re;
		}
		int *getVLine(int z){
			int *re = new int[9];
			for(int i = 0; i < 9 ; i++){
				re[i] = getZiffer((i*9)+z);
			}
			return re;
		}
		int *getQuadrat(int h, int v){
			int *re = new int[9];
			int a = 0;
			h = (h/3)*3;
		       	v = (v/3)*27;
			for(int i = 0; i < 3; i++){
				for(int j = 0;j < 3;j++){
					re[a] = getZiffer(h + v + (i*9) + j);
					a++;
				}
			}
			return re;
		}
};