Sie befinden sich hier: Treffen » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » pfp » Forendiskussionen » codezuraufgabe7   (Übersicht)

import java.util.Arrays;
 
public class Maerz14_Backtrack {
	public static void main(String[] args) {
		int[][] sq={
						{2 ,7, 6},
						{9, 5 ,1}, 
						{4 ,3 ,8}
						};
 
		System.out.println(isSolved(sq));
 
		MagicSquare(3);
 
	}
 
	static void MagicSquare(int n) {
		int[][] sq = new int[n][n];
		if (solve(sq, 0, new boolean[n * n]))
			print(sq);
	}
 
	private static void print(int[][] sq) {
		for (int[] s : sq) {
			System.out.println(Arrays.toString(s));
		}
	}
	static boolean isSolved(int[][] sq) {
		int n = sq.length;
		int checkSum = ((n * n * n) + n) / 2;
		int rowSum = 0, colSum = 0, diag1Sum = 0, diag2Sum = 0;
 
		for(int y= 0 ; y< n; y++){
 
			diag1Sum += sq[y][y];
			diag2Sum += sq[n-1-y][n-1-y];
 
			for(int x=0; x < n ; x++){
				rowSum += sq[y][x];
				colSum += sq[x][y];
			}
 
			if(rowSum != checkSum || colSum != checkSum)
				return false;
 
			rowSum=colSum=0;
		}
 
		if(diag1Sum != checkSum || diag2Sum != checkSum)
			return false;
 
		return true;
	}
 
	static boolean solve(int[][] sq, int pos, boolean[] used) {
		int n = sq.length;
		int col = pos % n;
		int row = (pos - col) / n;
 
		// Basisfall
		if(isSolved(sq))
			return true;
 
		//Rekursion
		for(int i=0; i < n*n; i++){
			if(!used[i]){
				used[i]=true;
				int c=i+1;
				sq[col][row]=c;
 
				if(solve(sq,pos+1,used))
					return true;
 
				sq[col][row]=0;
				used[i]=false;
			}
		}
		return false;
	}
 
}