Das Damenproblem (Teil I)

1 Lösung

#87

Fortgeschrittener - Java von ElPapito - 07.05.2015 um 11:42 Uhr

Das klassische Damenproblem besteht aus einem 8x8 Schachfeld und 8 Damen.
Die Aufgabe besteht darin die 8 Damen so zu positionieren, dass sie sich gegenseitig nicht bedrohen, d.h. es dürfen keine zwei Damen in der gleichen Zeile/Spalte/Diagonale stehen.

Schreibe ein kleines Programm, welches ausgibt wie viele Lösungen existieren.

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von ElPapito (2690 Punkte) - 07.05.2015 um 20:50 Uhr

Java-Code


/**
 * @author ElPapito
 * @date 07.05.2015
 */

public class DasDamenproblem {

	public static void main(String[] args) {
		boolean[][] queen = new boolean[8][8];
		int counter = solutions(queen, 0);
		System.out.println(counter);
	}

	private static int solutions(boolean[][] queen, int row) {
		if (row == queen.length) {
			return 1;
		}

		int counter = 0;
		for (int col = 0; col < queen.length; col++) {
			if (!isPositionSave(queen, row, col)) {
				continue;
			}

			queen[row][col] = true;
			counter += solutions(queen, row + 1);
			queen[row][col] = false;
		}

		return counter;
	}

	public static boolean isPositionSave(boolean[][] queen, int row, int col) {

		for (int i = 0; i < row; i++) {
			int dC = row - i;
			// Teste Spalte
			if (queen[i][col]) {
				return false;
			}
			// Teste linke Diagonale
			if (col - dC >= 0 && queen[i][col - dC]) {
				return false;
			}
			// Teste rechte Diagonale
			if (col + dC < queen.length && queen[i][col + dC]) {
				return false;
			}
		}

		return true;
	}

}