import java.util.*;
import java.io.*;

/**
 * Generates all solutions to any sudoku.
 * 
 * @author jpoial
 * @version 1.2
 */
public class Sudokugen {

   /** sqrt(rowlength) */
   static int s = 3;

   /** board */
   static int[][] board = new int[s * s][s * s];

   /** number of solutions */
   static long numsol = 0L;

   /** Main method where the program starts. */
   public static void main (String[] p) {
      // init(); // use this to define the initial state
      readFrom ("lahend.txt"); // use this to read the initial state from the file
      System.out.println ("Initial state:");
      display ();
      System.out.println ("=================================");
      solve ();
   }

   /** first row can be fixed - permutations generate the rest */
   public static void init () {
      int k = 0;
      for (int j = 0; j < s * s; j++) {
         board[0][j] = ++k;
      }
      for (int i = 1; i < s * s; i++) {
         for (int j = 0; j < s * s; j++) {
            board[i][j] = 0;
         }
      }
   }

   /** display the board */
   public static void display () {
      for (int m = 0; m < s; m++) {
         System.out.println ();
         for (int n = 0; n < s; n++) {
            int i = m * s + n;
            for (int b = 0; b < s; b++) {
               for (int c = 0; c < s; c++) {
                  int j = b * s + c;
                  System.out.printf ("%3d", board[i][j]);
               }
               System.out.print ("  ");
            }
            System.out.println ();
         }
      }
   }

   /** read the board data from the file */
   public static void readFrom (String fname) {
      String row = null;
      try {
         int i = 0;
         BufferedReader inp = new BufferedReader (new FileReader (fname));
         while (((row = inp.readLine ()) != null) && (i < s * s)) {
            StringTokenizer st = new StringTokenizer (row);
            if (st.countTokens () == 0)
               continue; // skip empty lines
            int j = 0;
            while ((st.hasMoreTokens ()) && (j < s * s)) {
               int elem = 0;
               try {
                  elem = Integer.parseInt (st.nextToken ().trim ());
               } catch (NumberFormatException e) {
               }
               if (!check (i, j, elem)) {
                  inp.close ();
                  display ();
                  throw new IllegalArgumentException (" Illegal number " + elem
                        + " in position " + i + "," + j + " in file " + fname);
               }
               board[i][j] = elem;
               j++;
            }
            i++;
         }
         inp.close ();
      } catch (IOException e) {
         e.printStackTrace ();
      }
   }

   /** write the board data to the file */
   public static void writeTo (String fname) {
      try {
         PrintWriter pw = new PrintWriter (new FileWriter (fname), true);
         for (int m = 0; m < s; m++) {
            pw.println ();
            for (int n = 0; n < s; n++) {
               int i = m * s + n;
               for (int b = 0; b < s; b++) {
                  for (int c = 0; c < s; c++) {
                     int j = b * s + c;
                     pw.printf ("%3d", board[i][j]);
                  }
                  pw.print ("  ");
               }
               pw.println ();
            }
         }
         pw.close ();
      } catch (IOException e) {
         e.printStackTrace ();
      }
   }

   /** what to do when solution is found */
   public static void solution () {
      // writeTo ("lahend.txt");
      if (numsol < 3) {
         display ();
         // System.exit(0);
         System.out.println ();
         System.out.println ("======================================================");
      }
   }

   /** true, if k is good in position i,j */
   public static boolean check (int i, int j, int k) {
      TreeSet<Integer> block = new TreeSet<Integer> ();
      for (int p = 0; p < s * s; p++) {
         if ((board[i][p] != 0) && (p != j))
            block.add (board[i][p]);
      }
      if (block.contains (k))
         return false;
      block.clear ();
      for (int p = 0; p < s * s; p++) {
         if ((board[p][j] != 0) && (p != i))
            block.add (board[p][j]);
      }
      if (block.contains (k))
         return false;
      block.clear ();
      int q = (i / s) * s;
      int r = (j / s) * s;
      for (int t = 0; t < s; t++) {
         for (int u = 0; u < s; u++) {
            int elem = board[q + t][r + u];
            if ((elem != 0) && (!(q + t == i && r + u == j)))
               block.add (elem);
         }
      }
      if (block.contains (k))
         return false;
      return true;
   }

   /** main solver uses pure backtracking */
   public static void solve () {
      ArrayList<Integer> emptyCells = new ArrayList<Integer> ();
      int p = 0;
      for (int i = 0; i < s * s; i++) {
         for (int j = 0; j < s * s; j++) {
            if (board[i][j] == 0)
               emptyCells.add (p);
            p++;
         }
      }
      numsol = 0L;
      if (emptyCells.isEmpty ()) {
         display ();
         return;
      }
      int n = 0;
      do {
         int pos = emptyCells.get (n);
         int u = pos / (s * s);
         int v = pos % (s * s);
         if (board[u][v] < s * s) {
            board[u][v]++;
            if (!check (u, v, board[u][v]))
               continue;
            if (n < emptyCells.size () - 1) {
               n++;
               continue;
            } else {
               numsol++;
               solution ();
            }
         } else {
            board[u][v] = 0;
            n--;
         }
      } while (n >= 0);
      System.out.println ("Number of solutions: " + numsol);
   }
}