/* Das Java-Praktikum, dpunkt Verlag 2008, ISBN 978-3-89864-513-3
 * Aufgabe: Permutationen
 * Entwickelt mit: Sun Java 6 SE Development Kit
 */
package permutation;

/**
 * Definiert ein quadratisches Sudoku (japanisches Zahlenrätsel).
 *
 * @author Klaus Köhler, koehler@hm.edu
 * @author Reinhard Schiedermeier, rs@cs.hm.edu
 * @version 25.05.2008
 */
public class Sudoku {
    /**
     * JOKER repräsentiert einen unbekannten Wert.
     */
    public final static int JOKER = 0;

    /**
     * CELL = Höhe = Breite eines Blocks (Untermatrix)
     */
    public final static int CELL = 3;

    /**
     * SIZE = Zeilenzahl = Spaltenzahl der Matrix
     */
    public final static int SIZE = CELL*CELL;

    /**
     * Sudoku-Matrix
     */
    private static int[][] matrix;

    /**
     * Bestimmt die erste Lösung des Sudokus und druckt sie.
     * @return true, wenn das Sudoku lösbar ist, sonst false
     */
    public static boolean solve() {
        for(int r = 0; r < SIZE; r++)
            for(int c = 0; c < SIZE; c++)
                if(matrix[r][c] == JOKER) {
                    for(int num = 1; num <= SIZE; num++) {
                        matrix[r][c] = num;
                        if(isValid()  &&  solve())
                            return true;
                    }
                    matrix[r][c] = JOKER;
                    return false;
                }
        print();
        return true;
    }

    /**
     * Prüft, ob matrix und ihre CELL*CELL Blöcke Permutationsmatrizen sind.
     * @return true, wenn Prüfung erfolgreich, sonst false
     */
    public static boolean isValid() {
        for(int r = 0; r < SIZE; r += CELL)
            for(int c = 0; c < SIZE; c += CELL)
                if(!Permutation.isPermutationBlock(matrix, r, r + CELL, c, c + CELL))
                    return false;
        return Permutation.isPermutation(matrix);
    }

    /**
     * Gibt die Matrix in lesbarer Form aus.
     */
    public static void print() {
        for(int r = 0; r < SIZE; r++) {
            for(int c = 0; c < SIZE; c++)
                System.out.printf("%d ", matrix[r][c]);
            System.out.println();
        }
    }

    /**
     * Testprogramm für ein Standard-9x9-Sudoku.
     * @param args wird ignoriert
     */
    public static void main(final String[] args) {
        matrix = new int[][] {
                {1, 0, 8, 0, 9, 0, 0, 4, 6},
                {0, 6, 5, 0, 0, 0, 0, 0, 2},
                {9, 0, 7, 1, 0, 0, 0, 3, 0},
                {0, 0, 0, 0, 0, 0, 4, 0, 0},
                {0, 0, 2, 0, 0, 6, 0, 0, 1},
                {0, 4, 0, 0, 0, 7, 0, 0, 0},
                {0, 0, 3, 0, 2, 5, 0, 1, 4},
                {5, 0, 4, 0, 0, 1, 0, 0, 0},
                {0, 0, 0, 0, 7, 9, 3, 6, 5}
        };
        solve();
    }
}