XSudoku

Aufgabenstellung: Schreiben Sie ein Programm welches ein XSudoku mit 9×9 Feldern loest. Die zu verwendeten Methoden und Parameter waren vorgegeben.

package gdp.aufgabe22;

import java.util.Arrays;

import javax.management.RuntimeErrorException;

public class XSudoku {

	public static boolean isPermutation(int[] a) {
		// TODO Ueberprüft unsere Permutationsbedingung fuer das Array a
		int[] numbersToCheck = a;
		for (int j = 0; j < numbersToCheck.length; j++) {
			for (int k = j + 1; k < numbersToCheck.length; k++) {
				if (numbersToCheck[j] == 0) {
					continue;
				}

				if (numbersToCheck[j] == numbersToCheck[k]) {
					return false;
				}
			}
		}
		return true;
	}

	public static boolean isPermutationRow(int[][] a, int row) {
		int[] numbersToCheck = new int[a[0].length];

		// schreibt alle Zahlen in das Array checkNumber
		for (int i = 0; i < a[0].length; i++) {
			// schreibt an stelle i des Arrays checkNumber den Wert des
			// Arrays a
			numbersToCheck[i] = a[row][i];
		}
		// Schaut ob das Array numbersToCheck keine Doppelten Zahlen mit
		// Ausnahme der 0 enthaelt.
		return isPermutation(numbersToCheck);
	}

	// TODO Ueberprueft, ob Reihe row im zweidimensionalen Array a eine
	// Permutationsmenge ist
	public static boolean isPermutationCol(int[][] a, int col) {

		int[] numbersToCheck = new int[a.length];

		// schreibt alle Zahlen in das Array checkNumber
		for (int i = 0; i < a.length; i++) {
			// schreibt an stelle i des Arrays checkNumber den Wert des
			// Arrays a
			numbersToCheck[i] = a[i][col];
		}
		// Schaut ob das Array numbersToCheck keine Doppelten Zahlen mit
		// Ausnahme der 0 enthaelt.
		return isPermutation(numbersToCheck);
	}

	public static boolean isPermutationDiagonalLeftRight(int[][] a) {
		// TODO Ueberprueft, ob die beiden Diagonalen im zweidimensionalen Array
		// a Permutationsmengen sind
		int[] numbersToCheck = new int[a.length];

		// schreibt alle Zahlen fuer die Diagonale links oben nach rechts unten
		// in das Array checkNumber
		for (int i = 0; i < a.length; i++) {
			// schreibt an stelle i des Arrays checkNumber den Wert des
			// Arrays a
			numbersToCheck[i] = a[i][i];
		}
		// Schaut ob das Array numbersToCheck keine Doppelten Zahlen mit
		// Ausnahme der 0 enthaelt.
		return isPermutation(numbersToCheck);
	}

	public static boolean isPermutationDiagonalRightLeft(int[][] a) {
		// TODO Ueberprueft, ob die beiden Diagonalen im zweidimensionalen Array
		// a Permutationsmengen sind
		int[] numbersToCheck = new int[a.length];

		// schreibt alle Zahlen fuer die Diagonale rechts oben nach links unten
		// in das Array checkNumber
		for (int i = 0; i < a.length; i++) {
			// schreibt an stelle i des Arrays checkNumber den Wert des
			// Arrays a
			numbersToCheck[i] = a[i][a.length - 1 - i];
		}
		// Schaut ob das Array numbersToCheck keine Doppelten Zahlen mit
		// Ausnahme der 0 enthaelt.
		return isPermutation(numbersToCheck);
	}

	public static boolean isPermutationDiagonal(int[][] a) {
		// TODO Ueberprueft, ob die beiden Diagonalen im zweidimensionalen Array
		// a Permutationsmengen sind
		return (isPermutationDiagonalLeftRight(a) && isPermutationDiagonalRightLeft(a));
	}

	public static boolean isPermutationBlock(int[][] a, int minRow, int maxRow, int minCol, int maxCol) {
		// TODO Ueberprueft, ob die Menge aller Zahlen im zweidimensionalen
		// Block zwischen den Reihen minRow (inklusive) und maxRow (exklusive)
		// und den Spalten minCol (inklusive) und maxCol (exklusive) eine
		// Permutationsmenge (nicht nur eine Permutationsmatrix) darstellt.
		// if (maxRow - minRow > 3 || maxRow < minRow) {
		// return false;
		// }
		// if (maxCol - minCol > 3 || maxCol < minCol) {
		// return false;
		// }
		//
		int[] numbersToCheck = new int[(maxRow - minRow) * (maxCol - minCol)];
		int col = minCol;
		int row = minRow;
		int i = 0;
		// schreibt alle Zahlen fuer die Diagonale rechts oben nach links unten
		// in das Array checkNumber
		while (row < maxRow) {
			col = minCol;
			while (col < maxCol) {
				try {
					numbersToCheck[i] = a[row][col];
				} catch (Throwable e) {
					throw new RuntimeException("Problem: i=" + i + ", row=" + row + ", col=" + col + ", minrow="
							+ minRow + ", mincol=" + minCol + ", maxrow=" + maxRow + ", maxcol=" + maxCol, e);
				}
				i++;
				col++;
			}
			row++;
		}
		// Schaut ob das Array numbersToCheck keine Doppelten Zahlen mit
		// Ausnahme der 0 enthaelt.
		return isPermutation(numbersToCheck);
	}
	//Checkt ob Zeile und Spalte eine Permutation ist.
	public static boolean isPermutationMatrix(int[][] a) {
		for (int i = 0; i < a.length; i++) {
			if (!isPermutationRow(a, i)) {
				return false;
			}
			if (!isPermutationCol(a, i)) {
				return false;
			}
		}
		return true;
	}
	// Ueberprueft alle Permutationen
	public static boolean checkAllPermutations(int[][] a) {
		if(!isPermutationMatrix(a)){
			return false;
		}
		// int minRow, int maxRow, int minCol, int maxCol
		int kantenlaenge = a.length / 3;
		for (int row = 0; row < a.length; row += kantenlaenge) {
			for (int col = 0; col < a[0].length; col += kantenlaenge) {
				if (!isPermutationBlock(a, row, row + kantenlaenge, col, col + kantenlaenge)) {
					return false;
					// throw new RuntimeException("kantenlaenge: " +
					// kantenlaenge + ", row: " + row + ", col: " + col
					// + ", a.length: " + a.length);
				}
			}
		}

		return isPermutationDiagonal(a);
	}

	public static boolean isValid(int[][] a) {
		if (a.length != 9) {
			return false;
		}
		if (a[0].length != 9) {
			return false;
		}
		return checkAllPermutations(a);
	}

	public static int[][] solve(int[][] a) {
		int[][] sudoku = a;

		if (!isValid(sudoku)) {
			return null;
		}

		for (int row = 0; row < a.length; row++) {
			for (int col = 0; col < a[0].length; col++) {
				if (sudoku[row][col] == 0) {
					for (int k = 1; k <= a.length; k++) {
						sudoku[row][col] = k;
						if (checkAllPermutations(sudoku)) {
							int[][] solvedSudoku = solve(sudoku);
							if (solvedSudoku != null) {
								return sudoku;
							}
						}
					}
					sudoku[row][col] = 0; // nicht sicher
					return null; // nicht sicher
				}
			}
		}
		return sudoku; // nicht sicher
		// throw new RuntimeException("this should never happen");
	}

	// int[][] solvedSudoku = new int[9][9];
	// // int tmp;
	// // int row = 0;
	// // int col = 0;
	//
	// if (!isPermutationMatrix(sudoku)) {
	// solve(sudoku);
	// } else {
	// solvedSudoku = sudoku;
	// return solvedSudoku;
	// }
	// return null;
	// // TODO Berechnet eine Loesung fuer das X-Sudokufeld a. Liefert diese
	// // zurueck, falls sie existiert. Liefert sonst null zurueck.
	// }

	public static void main(String[] args) {
		// testing solver
		int[][] falschesSudoku = new int[][] { { 0, 0, 0, 0, 0, 0, 6, 8, 0 }, { 0, 0, 0, 0, 7, 3, 0, 0, 9 },
				{ 3, 0, 9, 0, 0, 0, 0, 4, 5 }, { 4, 9, 0, 0, 0, 0, 0, 0, 0 }, { 8, 0, 3, 0, 5, 0, 9, 0, 2 },
				{ 0, 8, 0, 0, 0, 0, 0, 3, 6 }, { 9, 6, 0, 0, 0, 0, 3, 0, 8 }, { 7, 0, 0, 6, 8, 0, 0, 0, 0 },
				{ 0, 2, 8, 0, 0, 0, 0, 0, 0 } };
		System.out.println("----Test falsches Sudoku----");
		int[][] solvedSudoku = solve(falschesSudoku);
		if (solvedSudoku == null) {
			System.out.println("Sudoku kann nicht geloest werden.");
		}
		int[][] sudoku2 = new int[][] { { 0, 0, 6, 1, 3, 0, 0, 0, 7 }, { 0, 0, 0, 0, 0, 0, 1, 0, 0 },
				{ 0, 0, 0, 0, 7, 0, 6, 8, 3 }, { 0, 2, 7, 3, 1, 0, 0, 0, 0 }, { 1, 0, 0, 4, 0, 0, 0, 7, 2 },
				{ 0, 0, 0, 0, 5, 0, 3, 0, 0 }, { 0, 6, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 8, 0, 6, 0, 7, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 1, 6 } };
		System.out.println("----Test Sudoku2----");
		solvedSudoku = solve(sudoku2);
		if (solvedSudoku == null) {
			System.out.println("Sudoku2 kann nicht geloest werden.");
		} else {
			for (int row = 0; row < 9; row++) {
				for (int col = 0; col < 9; col++) {
					System.out.print(" " + solvedSudoku[row][col]);
				}
				System.out.println("");
			}
		}
		int[][] sudoku3 = new int[][] { { 0, 8, 7, 0, 0, 0, 0, 0, 0 }, { 5, 0, 4, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 1, 0, 7, 0, 2, 0, 0 },

				{ 0, 0, 9, 0, 0, 0, 1, 3, 0 }, { 2, 0, 0, 0, 0, 1, 0, 9, 0 }, { 1, 0, 0, 0, 0, 0, 0, 0, 4 },

				{ 0, 0, 0, 0, 1, 9, 0, 0, 0 }, { 0, 0, 2, 7, 0, 0, 0, 6, 0 }, { 8, 9, 0, 0, 0, 3, 0, 0, 0 } };
		System.out.println("----Test Sudoku3----");
		solvedSudoku = solve(sudoku3);
		if (solvedSudoku == null) {
			System.out.println("Sudoku3 kann nicht geloest werden.");
		} else {
			for (int row = 0; row < 9; row++) {
				for (int col = 0; col < 9; col++) {
					System.out.print(" " + solvedSudoku[row][col]);
				}
				System.out.println("");
			}
		}
	}

}