package backtracking;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Sudoku {

  private int[] grid; // 0..80 (9 * row + col)

  Sudoku() {
    this.grid = new int[81];
  }

  Sudoku(String s) {
    this.grid = new int[81];
    for (int i = 0; i < 81; i++)
      this.grid[i] = s.charAt(i) - '0';
  }

  int row(int c) { return c / 9; }
  int col(int c) { return c % 9; }
  int group(int c) { return 3 * (row(c) / 3) + col(c) / 3; }

  boolean sameZone(int c1, int c2) {
    return row(c1) == row(c2)
          || col(c1) == col(c2)
          || group(c1) == group(c2);
  }

  // vérifie que la valeur dans p est compatible avec les autres cases
  boolean check(int p) {
    for (int c = 0; c < 81; c++)
      if (c != p && sameZone(p, c) && this.grid[p] == this.grid[c])
        return false;
    return true;
  }

  // essaye de résoudre la grille courante et renvoie un booléen indiquant le succès
  boolean solve() {
    for (int c = 0; c < 81; c++)
      if (this.grid[c] == 0) {
        for (int v = 1; v < 10; v++) {
          this.grid[c] = v;
          if (check(c) && solve())
            return true;
        }
        this.grid[c] = 0;
        return false;
      }
    return true;
  }

  void print() {
    for (int i = 0; i < 9; i++) {
      if (i % 3 == 0) System.out.println("+---+---+---+");
      for (int j = 0; j < 9; j++) {
        if (j % 3 == 0) System.out.print("|");
        System.out.print(this.grid[9*i+j]);
      }
      System.out.println("|");
    }
    System.out.println("+---+---+---+");
  }

  public static void main(String[] args) throws FileNotFoundException {
    Scanner sc = new Scanner(new File("puzzles.sdk"));
    double start = System.currentTimeMillis();
    while (sc.hasNext()) {
      String s = sc.nextLine();
      System.out.println("s = " + s);
      Sudoku sk = new Sudoku(s);
      sk.print();
      System.out.println();
      if (sk.solve())
        sk.print();
      else
        System.out.println("pas de solution");
      System.out.println();
    }
    sc.close();
    System.out.println((System.currentTimeMillis() - start) / 1000);
  }
}

/* expérience : maintenir la liste des cases à remplir (par ex. dans une pile)
 * n'améliore en rien les performances */