Dieses Problem wurde zum ersten Mal vom bayrischen Schachmeister Max Bezzel (1824-1871) 1848 in der “Berliner Schachzeitung” veröffentlich. Auf Wikipedia gibt es hierzu einen ausführlicher Artikel.
Das Problem eignet sich hervorragend, um daran das Verfahren des Backtrackings zu erklären.
Das folgende C Programm sucht alle 92 Lösungen inklusive der sich durch Drehungen und Spiegelungen ergebenden und gibt diese als ASCII-Graphik aus.
/* Copyright (c) 2007 by Bernd Breitenbach. All Rights Reserved
This is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
This code is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
*/
#include <stdio.h>
signed char columns[8];
void search(int colno)
{
const char hline[]="\n+-+-+-+-+-+-+-+-+\n";
int i,j,ok;
for(i=0;i<8;i++) {
ok=1;
for (j=0;j<colno;j++) {
if (i==columns[j] || abs(i-columns[j])==abs(colno-j)) {
ok=0;
break;
}
}
if (ok) {
columns[colno]=i;
if (colno==7) {
printf(hline);
for(i=0;i<8;i++) {
for (j=0;j<8;j++) {
if (j==columns[i]) {
printf("|D");
} else {
printf("| ");
}
}
printf("|%s",hline);
}
} else {
search(colno+1);
}
}
}
}
int main()
{
search(0);
return 0;
}
Um nur die eindeutigen Lösungen zu ermitteln kann man z.B. die Informationen zu bereits gefundenen Lösungen und deren rotations- und spiegelsymmetrischen Varianten speichern und nur neue, nicht bereits gefundenen Lösungen symmetrische auszugeben bzw. zu zählen.
Das folgende C++-Programm leistet dieses und benutzt dabei verschiedene Optimierungen: zum einen wird in der ersten Spalte die Dame nur in die untere Hälfte gesetzt, da sich alle Lösungen mit der Dame in der oberen Hälfte durch eine Spiegelung an der mitteleren Horizontalen ergeben. Die so gefunden Lösungen werden daher doppelt gezählt. Bei Brettern mit ungeraden Kangenlängen findet noch eine Sonderbehandlung für die mittelere Reihe statt.
Mit dem Programm kann man auch die Lösungen auf kleineren oder größeren Brettern bis hin zu einem 16×16-Brett berechnen lassen. Man benötigt zum Übersetzen einen GNU-C++-Compiler und zum laufen lassen für große Bretter viel Speicher 🙂
/* Copyright (c) 2007 by Bernd Breitenbach. All Rights Reserved
This is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
This code is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
*/
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <vector>
#include <ext/hash_set>
class Solution : public std::vector<char> {
public:
Solution(int size,int trfno=0):trfno(trfno){resize(size);}
Solution Transform();
int Size() {return size();}
long Id();
private:
int trfno;
};
Solution Solution::Transform()
{
int s=Size();
Solution ret(s,(trfno+1)%8);
if ((trfno&3)==3) {
for (int i=0;i<s;i++) {
ret[s-1-i]=(*this)[i];
}
} else {
for (int i=0;i<s;i++) {
ret[s-1-(*this)[i]]=i;
}
}
return ret;
}
long Solution::Id()
{
long ret=0;
for (int i=0;i<Size();i++) {
ret|=(*this)[i];
ret<<=4;
}
return ret;
}
class NQueens : public Solution
{
public:
NQueens(int size,bool print):Solution(size),colno(0),total(0),unique(0),print(print){}
void Run();
void Print();
int Solutions() const {return unique;}
int TotalSolutions() const {return total;}
int Size() const {return size();}
void Found();
private:
void Search();
void Hline();
int colno;
int total;
int unique;
bool print;
int add;
__gnu_cxx::hash_set solutions;
};
void NQueens::Found()
{
total+=add;
if (solutions.find(Id())==solutions.end()) {
unique++;
Solution ret=Transform();
for(int i=0;i<8;i++) {
if (ret[0]<=(ret.Size()+1)/2) {
solutions.insert(ret.Id());
}
ret=ret.Transform();
}
if (print) Print();
}
}
void NQueens::Search()
{
bool ok;
for(int i=0;i<Size();i++) {
ok=true;
for (int j=0;j<colno;j++) {
if (i==(*this)[j] || abs(i-(*this)[j])==abs(colno-j)) {
ok=false;
break;
}
}
if (ok) {
(*this)[colno]=i;
if (colno==Size()-1) {
Found();
} else {
colno++;
Search();
colno--;
}
}
}
}
void NQueens::Run()
{
bool ok;
int s=Size()/2;
add=2;
colno=1;
for(int i=0;i<s;i++) {
(*this)[0]=i;
Search();
}
add=1;
for(int i=s;i<(Size()+1)/2;i++) {
(*this)[0]=i;
Search();
}
}
void NQueens::Hline()
{
int i;
printf("\n");
for(i=0;i<Size();i++) {
printf("+-");
}
printf("+\n");
}
void NQueens::Print()
{
int i,j;
Hline();
for(i=0;i<Size();i++) {
for (j=0;j<Size();j++) {
if (j==(*this)[i]) {
printf("|D");
} else {
printf("| ");
}
}
printf("|");
Hline();
}
}
int main(int argc,char **argv)
{
int size=8;
bool print=false;
int c;
if (sizeof(long)<8) {
fprintf(stderr,"error: size of type 'long' to short (min. 8 byte)\n");
exit(-1);
}
while(1) {
c=getopt(argc,argv,"s:p");
if (c<0) break;
switch(c) {
case 's':
size=strtol(optarg,NULL,0);
if (size<=0) size=8;
if (size>16) {
fprintf(stderr,"error: size to large (max. 16)\n");
exit(-1);
}
break;
case 'p':
print=true;
break;
}
}
NQueens p(size,print);
p.Run();
printf("Solutions (%dx%d): %d (total %d)\n",size,size,p.Solutions(),p.TotalSolutions());
return 0;
}