/**
 *
 * @author : Ahmed Aboelsaoud Ahmed 
 * E-mail  : ahmedsaoud31@gmail.com
 */
public class Sudoku {
    private static byte sudokuArr[][];
	
    public static void main(String[] args) {
        setSudoku();
        solveSudoku();
        for(byte i=0;i<9;i++){
           for(byte j=0;j<9;j++)
                System.out.print(" "+sudokuArr[i][j]+" ");
           System.out.print("\n");
        }
    }
    // هذة الدالة لملئ خريطة السودوكو فقط ضع الخريطة المراد حلها فى المتغير النصى معوضاً الخانات الفارغة بصفر
    public static void setSudoku(){
        String a="902100040000460100500007000600000035401000602820000001000900007006073000040006208";
       sudokuArr = new byte[9][9] ;
       int count=0;
       for(byte i=0;i<9;i++)
           for(byte j=0;j<9;j++)
               sudokuArr[i][j]=(byte)(a.charAt(count++)-48);
    }
    
    // دالة حل الخريطة
    public static void solveSudoku(){
    // عداد حساب الخانات الفارغة فى الخريطة
    byte count=0;
    for(byte i=0;i<9;i++)
            for(byte j=0;j<9;j++)
                    if(sudokuArr[i][j]==0) count++;
    // لكل خانة فارغة يتم عمل دورة كاملة على الخريطة لإختبار الخانات الفارغة هل تقبل رقم واحد فقط فى الخانة أم لا
    for(byte k=0;k<count+10;k++)
            for(byte i=0;i<9;i++)
                    for(byte j=0;j<9;j++)
                            if(sudokuArr[i][j]==0) reTimes(i,j);

    }


    // حساب عدد الأعداد التى يمكن أن توضع فى الخلية
    public static void reTimes(byte row,byte col){
    byte reT=0;
    for(byte val=1;val<10;val++)
            if(check(row,col,val)) reT++;
    // فى حالة كون الخلية لا تسمح إلا برقم واحد فقط أى هو الحل الوحيد لهذة الخلية يتم وضعه
    if(reT==1)
            for(byte val=1;val<10;val++)
                    if(check(row,col,val)) sudokuArr[row][col]=val;
    }

   
   
   // هذة دالة إختبار القيمة أهى موجودة فى الصف والعمود والمربع الصغير أم لا
   public static boolean check( byte row,byte col, byte val )
   {
      for( int i = 0; i < 9; i++ )
		if( sudokuArr[row][i] == val ) return false ;
      for( int i = 0; i < 9; i++ )
		if( sudokuArr[i][col] == val ) return false ;
      row = (byte)((row / 3) * 3 );
      col = (byte)((col / 3) * 3 );
      for( byte i = 0; i < 3; i++ )
         for( byte j = 0; j < 3; j++ )
			if( sudokuArr[row+i][col+j] == val ) return false ;
      return true ;
   }

   
}