Das Damenproblem (Teil I)

2 Lösungen

#95

Fortgeschrittener - C# 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

5 Kommentare

von eulerscheZhl (5230 Punkte) - 08.05.2015 um 16:10 Uhr

C#-Code

using System;

namespace trainYourProgrammer
{
	class MainClass
	{
		static long PlaceQueens(int n, bool[,] blocked, int line) {
			if (line == n)
				return 1;
			long result = 0;
			for (int i = 0; i < n; i++) {
				if (blocked [i, line])
					continue;
				result += PlaceQueens (n, PlaceQueenAt (i, line, n, blocked), line + 1);
			}
			return result;
		}

		static long PlaceQueens(int n) {
			bool[,] blocked = new bool[n, n];
			long result = 0;
			for (int i = 0; i < n/2; i++) { //Ausnutzen der Symmetrie
				result += 2 * PlaceQueens (n, PlaceQueenAt (i, 0, n, blocked), 1);
			}
			if (n % 2 == 1)
				result += PlaceQueens (n, PlaceQueenAt (n / 2, 0, n, blocked), 1);
			return result;
		}

		static bool[,] PlaceQueenAt(int x, int y, int n, bool[,] blocked) {
			int[,] offset = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
			bool[,] result = (bool[,]) blocked.Clone();
			for(int dir = 0; dir < 8; dir++) {
				int x_ = x + offset[dir, 0];
				int y_ = y + offset[dir, 1];
				while (x_ >= 0 && x_ < n && y_ >= 0 && y_ < n) {
					result[x_, y_] = true;
					x_ += offset[dir, 0];
					y_ += offset[dir, 1];
				}
			}
			return result;
		}

		static void Main(string[] args) {
			for (int i = 8; i < 9; i++) {
				Console.WriteLine ("n = " + i.ToString().PadLeft(2) + ": " + PlaceQueens(i).ToString().PadLeft(6) + " Möglichkeiten");
			}
		}
	}
}

Kommentare:

Robi

Punkte: 390

10 Lösungen
6 Kommentare

15.01.2016 um 10:30 Uhr

Könntest du mir deine Lösung irgendwie mal verständlich machen, wenn es nicht den Rahmen sprengt^^? Scheint mal wieder mehr als genial zu sein.
Bin schon beim "Ausnutzen der Symmetrie ausgestiegen, aber dein "PlaceQueenAt" hat mich vollkommen verwirrt.

eulerscheZhl

Punkte: 5230

110 Aufgaben
76 Lösungen
64 Kommentare

15.01.2016 um 14:09 Uhr

Vorab: es geht besser. Im python Bereich habe ich noch eine Variante eingestellt, die ohne das Kopieren von Arrays auskommt: http://trainyourprogrammer.de/python-77-das-damenproblem-teil-ii.html

PlaceQueens(int n) füllt nur die erste Zeile, platziert dort also eine Dame.
Da es aber bei der ersten Dame keinen Unterschied macht, ob die Dame ganz nach rechts oder ganz nach links kommt (Symmetrie zu einer senkrechten Achse), platziere ich sie nur links und verdopple dann das Ergebnis. (Zeile 22-24). Das geht natürlich nur, wenn die Feldbreite Vielfaches von 2 ist. Sonst wir zusatzlich noch eine Dame in der Mitte der ersten Reihe platziert, ohne das Ergebnis zu verdoppeln (Zeile 25-27).

PlaceQueenAt bekommt ein zweidimensionales Array, das angibt, welches Feld schon bedroht wird und die Koordinaten einer weiteren Dame. Das Ergebnis ist ein anderes 2D Array, das zusätzlich zum eingegebenen noch die Felder als bedroht markiert, die die neue Dame erreichen kann. (Das nach oben gehen könnte ich mir sparen, weil ich das Feld von oben nach unten fülle, ich oben also sowieso keine Dame mehr platzieren will.)

PlaceQueens(int n, bool[,] blocked, int line) prüft zunähst, ob die nächste zu füllende Zeile (line) noch im Feld liegt (Zeile 8-9). Wenn nicht, ist das Brett bereits vollständig gefüllt, es wird 1 zurückgegeben, da eine Belegung gefunden wurde.
Andernfalls wid für jedes Feld in der Reihe geprüft, ob es bedroht wird. Wenn ja, wird einfach beim nächsten Feld weitergemacht (continue in Zeile 13). Wenn nein (Zeile 14) wird dort eine Dame platziert (PlaceQueenAt, zur Erinnerung: dadurch wird ein neues Brett bedrohter Felder erstellt). Die Zeile wird um eins erhöht, weil die aktuelle Zeile fertig ist (es kann nur eine Dame pro Zeile geben). Es wird rekursiv ausgerechnet, wie viele Damen in den folgenden Zeilen sein können und der Wert zum bisherigen Ergebnis addiert.

Die Main ist recht langweilig. Die Schleife steht da nur wegen Teil 2 der Aufgabe.

Robi

Punkte: 390

10 Lösungen
6 Kommentare

15.01.2016 um 14:19 Uhr

Vielen, vielen Dank! Die Funktion zum "blocken" der Felder im Array ist echt cool. Wäre ich nicht drauf gekommen.

eulerscheZhl

Punkte: 5230

110 Aufgaben
76 Lösungen
64 Kommentare

15.01.2016 um 14:25 Uhr

Naja. Sie kopiert jedes mal ein komplettes Array und berechnet Werte die ich sowieso nie wieder brauche. Ist eigentlich ziemlicher Mist :)

Robi

Punkte: 390

10 Lösungen
6 Kommentare

15.01.2016 um 14:37 Uhr

Jetzt fühl ich mich noch dümmer als vorher xD

Bitte melden Sie sich an um eine Kommentar zu schreiben.

Kommentar schreiben

Seite 1 von 1 1