// ======================
// === Précis de Sudoku
// = (c) 2006 Narendra Jussien
// code java complet de résolution d'une grille de sudoku (nxn)
// le code proposé ici est (presque) générique (n peut varier)
// et suppose que le solveur choco est installé 
// (cf. http://choco-solver.net)


import choco.Problem;         // pour manipuler les problèmes
import choco.integer.IntVar;  // pour manipuler les variables

public class sudokuchoco {
    public static void main(String[] args) {
        int n = 9; // la taille de la grille
        Problem pb = new Problem(); // une nouvelle instance de la classe Problem

        // déclaration des lignes (rows) et colonnes (cols)
        IntVar[][] rows = new IntVar[n][]; // les n lignes
        IntVar[][] cols = new IntVar[n][]; // les n colonnes

        // déclaration des variables
        for (int i = 0; i < n; i++) {
           rows[i] = new IntVar[n];
           for (int j = 0; j < n; j++) {
               // on crée une nouvelle IntVar énumérée
               // en utilisant l'usine à variables de Problem
               rows[i][j] = pb.makeEnumIntVar("(" + i + "," + j + ")", 1, n);
           }
        }

        // correspondance ligne-colonne
        for (int i = 0; i < n; i++) {
           cols[i] = new IntVar[n];
           for (int j = 0; j < n; j++) {
               cols[i][j] = rows[j][i];
           }
        }

        // pose des contraintes définissant le sudoku
        for (int i = 0; i < n; i++) {
           pb.post(pb.allDifferent(cols[i]));
           pb.post(pb.allDifferent(rows[i]));
        }

        // définition des blocs
        IntVar[][] blocks = new IntVar[n][];
        for (int i = 0; i < n; i++) {
           blocks[i] = new IntVar[n];
        }

        // un peu de réflexion
        for (int i = 0; i < 3; i++) {
           for (int j = 0; j < 3; j++) {
               for (int k = 0; k < 3; k++) {
                   blocks[j + k * 3][i] = rows[0 + k * 3][i + j * 3];
                   blocks[j + k * 3][i + 3] = rows[1 + k * 3][i + j * 3];
                   blocks[j + k * 3][i + 6] = rows[2 + k * 3][i + j * 3];
               }
           }
        }

        // pose des contraintes par bloc
        for (int i = 0; i < n; i++) {
           pb.post(pb.allDifferent(blocks[i]));
        }


	// on résout ici la grille à 17 dévoilés de la figure 6.1 page 74

        // prise en compte des dévoilés (on se souviendra que les tableaux
        // démarrent à 0 en java
        pb.post( pb.eq(rows[0][7], 1)); pb.post( pb.eq(rows[1][0], 4));
        pb.post( pb.eq(rows[2][1], 2)); pb.post( pb.eq(rows[3][4], 5));
        pb.post( pb.eq(rows[3][6], 4)); pb.post( pb.eq(rows[3][8], 7));
        pb.post( pb.eq(rows[4][2], 8)); pb.post( pb.eq(rows[4][6], 3));
        pb.post( pb.eq(rows[5][2], 1)); pb.post( pb.eq(rows[5][4], 9));
        pb.post( pb.eq(rows[6][0], 3)); pb.post( pb.eq(rows[6][3], 4));
        pb.post( pb.eq(rows[6][6], 2)); pb.post( pb.eq(rows[7][1], 5));
        pb.post( pb.eq(rows[7][3], 1)); pb.post( pb.eq(rows[8][3], 8));
        pb.post( pb.eq(rows[8][5], 6));

        // demande de résolution du problème au solveur
        pb.solve();

        // affichage du résultat
        System.out.println("----- Solution ----");
        for (int i = 0; i < n; i++) {
           for (int j = 0; j < n; j++) {
              // the getVal method gives the actual value of the variable
              System.out.print(rows[i][j] + " ");
           }
           System.out.println();
        }
    }
}