/**
 * A brute-force Sudoku solver.
 * 
 * @author (Stefan Edelkamp) 
 * @version (2013)
 */
public class Sudoku 
{
    public char s[] = {'0','0','0','0','0','0','0','0','0',
                       '0','0','0','0','0','3','0','8','5',
                       '0','0','1','0','2','0','0','0','0',
                       '0','0','0','5','0','7','0','0','0',
                       '0','0','4','0','0','0','1','0','0',
                       '0','9','0','0','0','0','0','0','0',
                       '5','0','0','0','0','0','0','7','3',
                       '0','0','2','0','1','0','0','0','0',
                       '0','0','0','0','4','0','0','0','9'};

    /**
     *  calling the solver 
     */
    public void solve() { 
      show(); search(0); show(); 
    } 
    private void show() {
      for (int i=0;i<9;i++) {
        for(int j=0;j<9;j++)  
         System.out.print(s[i*9+j] == '0' ? "." : s[i*9+j]); 
        System.out.println(); 
      }
      System.out.println(); 
    }
    public boolean test(char d, int r, int c) {
      for(int i=0;i<9;i++) 
         if (s[9*r+i] == d || s[9*i+c] == d || s[9*(r/3*3+i/3)+(c/3*3+i%3)] == d) 
           return false;
      return true; 
    }
    /**
     * backtrack search for a Sudoku solution
     * 
     * @param  p   current position in string
     * @return     true, if solution found, or false, if not 
     */
    public boolean search(int pos) {
      if (pos == 81) return true;
      if (s[pos] > '0') { 
        if (search(pos+1)) return true; 
      }
      else      
        for (int i=0;i<9;i++) 
          if (test((char) ('1'+i),pos/9,pos%9)) { 
            s[pos] = (char) ('1'+i); 
            if (search(pos+1)) return true; 
            s[pos] = 0; 
          } 
      return false; 
    }

}