C# :: Aufgabe #95
2 Lösungen
Das Damenproblem (Teil I)
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.
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.
Lösungen:
C#-Codeusing 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");
}
}
}
}
Sicherlich nicht der "cleanste" Code, aber er funktioniert.
C#-Code
C#-Code
C#-Code
C#-Code
Ausgabe:
C#-Codeusing System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Damenproblem
{
class Program
{
/// <summary>
/// Programmablauf
/// </summary>
static void Main(string[] args)
{
//Setup
SchachbrettClass schachbrett = new SchachbrettClass();
Loesung loesung = new Loesung();
Dame[] damen = new Dame[8];
for (int i = 0; i < 8; i++)
{
damen[i] = new Dame(schachbrett);
}
//Möglichkeiten durchgehen
Check(damen, 0, schachbrett, loesung);
Console.WriteLine("Es gibt {0} Lösungen.", loesung.Moeglichkeiten);
Console.ReadLine();
}
private static void Check(Dame[] damen, int spalte, SchachbrettClass schachbrett, Loesung loesung)
{
int zaehler = 0;
do
{
if (damen[spalte].Spalte < 7)
{
Check(damen, (spalte + 1), schachbrett, loesung);
}
if (damen[spalte].Reihe < 7)
{
damen[spalte].Bewegen(schachbrett, damen[spalte].Reihe + 1, spalte);
loesung.Ueberpruefe(schachbrett);
}
zaehler++;
} while (zaehler < 8);
damen[spalte].Bewegen(schachbrett, 0, spalte);
}
}
} C#-Codeusing System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Damenproblem
{
public class SchachbrettClass
{
private int[,] schachbrett = new int[8,8];
public SchachbrettClass()
{
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
schachbrett[i, j] = 0;
}
}
}
public int[,] Schachbrett
{
get
{
return schachbrett;
}
set
{
schachbrett = value;
}
}
public void SetzeDameBei(int reihe, int spalte)
{
if (IstEineDameBei(reihe, spalte))
{
throw new Exception("Feld bereits besetzt!");
}
else
{
schachbrett[reihe, spalte] = 1;
}
}
public void EntferneDameBei(int reihe, int spalte)
{
if (IstEineDameBei(reihe, spalte))
{
schachbrett[reihe, spalte] = 0;
}
else
{
throw new Exception("Keine Dame auf Feld!");
}
}
public bool IstEineDameBei(int reihe, int spalte)
{
if (schachbrett[reihe, spalte] == 1)
{
return true;
}
else
{
return false;
}
}
}
}
C#-Codeusing System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Damenproblem
{
public class Loesung
{
private int moeglichkeiten = 0;
public int Moeglichkeiten
{
get
{
return moeglichkeiten;
}
set
{
moeglichkeiten = value;
}
}
/// <summary>
/// Überprüfe ob das übergebene Schachbrett Lösungskonform ist.
/// </summary>
public void Ueberpruefe(SchachbrettClass schachbrett)
{
bool checkr = true;
bool checks = true;
bool checkd = true;
int checksGesamt = 0;
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
if (schachbrett.IstEineDameBei(i, j))
{
checkr = CheckReihe(schachbrett, i);
if (!checkr)
{
checks = CheckSpalte(schachbrett, j);
if (!checks)
{
checkd = CheckDiagonale(schachbrett, i, j);
}
}
if (!checkd && !checkr && !checks)
{
checksGesamt++;
}
}
}
}
if (checksGesamt == 8)
{
this.moeglichkeiten++;
}
}
public bool CheckReihe(SchachbrettClass schachbrett, int reihe)
{
int zaehler = 0;
for (int j = 0; j < 8; j++)
{
if (schachbrett.IstEineDameBei(reihe, j))
{
zaehler++;
if (zaehler > 1)
{
return true;
}
}
}
return false;
}
public bool CheckSpalte(SchachbrettClass schachbrett, int spalte)
{
int zaehler = 0;
for (int i = 0; i < 8; i++)
{
if (schachbrett.IstEineDameBei(i, spalte))
{
zaehler++;
if (zaehler > 1)
{
return true;
}
}
}
return false;
}
public bool CheckDiagonale(SchachbrettClass schachbrett, int reihe, int spalte)
{
int i = reihe;
int j = spalte;
while (i > 0 && j > 0)
{
i--;
j--;
if (schachbrett.IstEineDameBei(i, j))
{
return true;
}
}
i = reihe;
j = spalte;
while (i < 7 && j > 0)
{
i++;
j--;
if (schachbrett.IstEineDameBei(i, j))
{
return true;
}
}
i = reihe;
j = spalte;
while (i < 7 && j < 7)
{
i++;
j++;
if (schachbrett.IstEineDameBei(i, j))
{
return true;
}
}
i = reihe;
j = spalte;
while (i > 0 && j < 7)
{
i--;
j++;
if (schachbrett.IstEineDameBei(i, j))
{
return true;
}
}
return false;
}
}
}
C#-Codeusing System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Damenproblem
{
public class Dame
{
private int reihe = -1;
private int spalte = -1;
/// <summary>
/// Setze neue Dame auf das Schachbrett. Wenn die Standardposition schon belegt ist wird nach einer neuen Position gesucht.
/// </summary>
public Dame(SchachbrettClass schachbrett)
{
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
if (!schachbrett.IstEineDameBei(i, j))
{
reihe = i;
spalte = j;
schachbrett.SetzeDameBei(i, j);
return;
}
}
}
}
public int Reihe
{
get
{
return reihe;
}
set
{
reihe = value;
}
}
public int Spalte
{
get
{
return spalte;
}
set
{
spalte = value;
}
}
public bool Bewegen(SchachbrettClass schachbrett, int reihe, int spalte)
{
if (schachbrett.IstEineDameBei(reihe, spalte))
{
return false;
}
else
{
schachbrett.SetzeDameBei(reihe, spalte);
schachbrett.EntferneDameBei(this.reihe, this.spalte);
this.reihe = reihe;
this.spalte = spalte;
return true;
}
}
}
}
Ausgabe:
Konsolenausgabe:
Es gibt 92 Lösungen.