Das Damenproblem (Teil II)

3 Lösungen

#77

Fortgeschrittener - Python von ElPapito - 07.05.2015 um 11:45 Uhr

Das verallgemeinerte Damenproblem besteht aus einem nxn Schachfeld und n Damen.
Die Aufgabe besteht darin die n 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 für n = 1, ..., 13 ausgibt wie viele Lösungen existieren.

Fragen einsehen (2)

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 eulerscheZhl (5230 Punkte) - 01.01.2016 um 09:16 Uhr

Python-Code

import sys

def placeQueenInLine(pos, line):
	if line == len(pos):
		return 1
	result = 0;
	for i in range(len(pos)):
		blocked = False;
		for j in range(line):
			if pos[j] == i or pos [j] - (line-j) == i or pos [j] + (line-j) == i:
				blocked = True
				break
		pos [line] = i
		if not blocked: result += placeQueenInLine (pos, line + 1);
	return result;

def placeQueens(n):
	pos = [0] * n
	result = 0;
	for i in range(n//2): #Ausnutzen der Symmetrie
		pos [0] = i
		result += 2 * placeQueenInLine (pos, 1)
	if n % 2 == 1:
		pos [0] = n // 2;
		result += placeQueenInLine (pos, 1)
	return result

for i in range(14):
	print "n = " + str(i) + ": " + str(placeQueens(i)) + " Möglichkeiten"