8-Damen-Problem

Ein Klassiker. Auf einem Schachbrett (8 x 8 Felder) sind 8 Damen so zu platzieren, dass sich diese gegenseitig nicht
schlagen können.

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 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) 2006 by Bernd Breitenbach.  All Rights Reserved 
 * \file 8queens.c
 * \author Bernd Breitenbach
 * \remarks
 *      bb - Mar 24, 2006: Created.
 */

#include 
#include 

signed char columns[8];
const char hline[]="\n+-+-+-+-+-+-+-+-+\n";

void search(int colno) 
{
  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 zu
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.

/** Copyright (c) 2006 by Bernd Breitenbach.  All Rights Reserved 
 * \file Nqueens.cc
 * \author Bernd Breitenbach
 * \remarks
 *      bb - Mar 26, 2006: Created.
 */

#include 
#include 
#include 

#include 
#include 


class Solution : public std::vector {
public:
  Solution(int size,int trfno=0):trfno(trfno){resize(size);}
  Solution Transform();
  int Size() {return size();}
  long 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 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;i16) {
	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;
}