Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » pfp » Forendiskussionen » codezuraufgabe7   (Übersicht)

Dies ist eine alte Version des Dokuments!

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;
}

}