{"id":168,"date":"2009-02-22T15:56:33","date_gmt":"2009-02-22T14:56:33","guid":{"rendered":"http:\/\/www.fiveoclock.de\/?page_id=168"},"modified":"2009-02-22T21:01:01","modified_gmt":"2009-02-22T20:01:01","slug":"8-damen-problem","status":"publish","type":"page","link":"http:\/\/www.fiveoclock.de\/?page_id=168","title":{"rendered":"8-Damen-Problem"},"content":{"rendered":"<p>Dieses Problem wurde zum ersten Mal vom bayrischen Schachmeister Max Bezzel (1824-1871) 1848 in der &#8220;Berliner Schachzeitung&#8221; ver\u00f6ffentlich. Auf <a  class=\"world\" href=\"http:\/\/de.wikipedia.org\/wiki\/Acht-Damen-Problem\" target=\"_blank\">Wikipedia<\/a> gibt es hierzu einen ausf\u00fchrlicher Artikel.<\/p>\n<p>Das Problem eignet sich hervorragend, um daran das Verfahren des <a  href=\"http:\/\/de.wikipedia.org\/wiki\/Backtracking\">Backtrackings<\/a> zu erkl\u00e4ren.<\/p>\n<p>Das folgende C Programm sucht alle 92 L\u00f6sungen inklusive der sich durch Drehungen und Spiegelungen ergebenden und gibt diese als ASCII-Graphik aus.<\/p>\n<pre>\/* Copyright (c) 2007 by Bernd Breitenbach.  All Rights Reserved\r\n\r\nThis is free software; you can redistribute it and\/or modify\r\nit under the terms of the GNU General Public License as published by\r\nthe Free Software Foundation; either version 3 of the License, or\r\n(at your option) any later version.\r\n\r\nThis code is distributed in the hope that it will be useful,\r\nbut WITHOUT ANY WARRANTY; without even the implied warranty of\r\nMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r\nGNU General Public License for more details.\r\n\r\n*\/\r\n\r\n#include &lt;stdio.h&gt;\r\n\r\nsigned char columns[8];\r\n\r\nvoid search(int colno)\r\n{\r\n  const char hline[]=\"\\n+-+-+-+-+-+-+-+-+\\n\";\r\n  int i,j,ok;\r\n  for(i=0;i&lt;8;i++) {\r\n    ok=1;\r\n    for (j=0;j&lt;colno;j++) {\r\n      if (i==columns[j] || abs(i-columns[j])==abs(colno-j)) {\r\n        ok=0;\r\n        break;\r\n      }\r\n    }\r\n    if (ok) {\r\n      columns[colno]=i;\r\n      if (colno==7) {\r\n        printf(hline);\r\n        for(i=0;i&lt;8;i++) {\r\n          for (j=0;j&lt;8;j++) {\r\n            if (j==columns[i]) {\r\n              printf(\"|D\");\r\n            } else {\r\n              printf(\"| \");\r\n            }\r\n          }\r\n          printf(\"|%s\",hline);\r\n        }\r\n      } else {\r\n        search(colno+1);\r\n      }\r\n    }\r\n  }\r\n}\r\n\r\nint main()\r\n{\r\n  search(0);\r\n  return 0;\r\n}<\/pre>\n<p>Um nur die eindeutigen L\u00f6sungen zu ermitteln kann man z.B. die Informationen zu bereits gefundenen L\u00f6sungen und deren rotations- und spiegelsymmetrischen Varianten speichern und nur neue, nicht bereits gefundenen L\u00f6sungen symmetrische auszugeben bzw. zu z\u00e4hlen.<\/p>\n<p>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\u00e4lfte gesetzt, da sich alle L\u00f6sungen mit der Dame in der oberen H\u00e4lfte durch eine Spiegelung an der mitteleren Horizontalen ergeben. Die so gefunden L\u00f6sungen werden daher doppelt gez\u00e4hlt. Bei Brettern mit ungeraden Kangenl\u00e4ngen findet noch eine Sonderbehandlung f\u00fcr die mittelere Reihe statt. <\/p>\n<p>Mit dem Programm kann man auch die L\u00f6sungen auf kleineren oder gr\u00f6\u00dferen Brettern bis hin zu einem 16&#215;16-Brett berechnen lassen. Man ben\u00f6tigt zum \u00dcbersetzen einen GNU-C++-Compiler und zum laufen lassen f\u00fcr gro\u00dfe Bretter viel Speicher \ud83d\ude42<\/p>\n<pre>\r\n\/* Copyright (c) 2007 by Bernd Breitenbach.  All Rights Reserved\r\n\r\nThis is free software; you can redistribute it and\/or modify\r\nit under the terms of the GNU General Public License as published by\r\nthe Free Software Foundation; either version 3 of the License, or\r\n(at your option) any later version.\r\n\r\nThis code is distributed in the hope that it will be useful,\r\nbut WITHOUT ANY WARRANTY; without even the implied warranty of\r\nMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r\nGNU General Public License for more details.\r\n\r\n*\/\r\n#include &lt;stdio.h&gt;\r\n#include &lt;stdlib.h&gt;\r\n#include &lt;unistd.h&gt;\r\n\r\n#include &lt;vector&gt;\r\n#include &lt;ext\/hash_set&gt;\r\n\r\n\r\nclass Solution : public std::vector&lt;char&gt; {\r\npublic:\r\n  Solution(int size,int trfno=0):trfno(trfno){resize(size);}\r\n  Solution Transform();\r\n  int Size() {return size();}\r\n  long Id();\r\nprivate:\r\n  int trfno;\r\n};\r\n\r\nSolution Solution::Transform()\r\n{\r\n  int s=Size();\r\n  Solution ret(s,(trfno+1)%8);\r\n\r\n  if ((trfno&amp;3)==3) {\r\n    for (int i=0;i&lt;s;i++) {\r\n      ret[s-1-i]=(*this)[i];\r\n    }\r\n  } else {\r\n    for (int i=0;i&lt;s;i++) {\r\n      ret[s-1-(*this)[i]]=i;\r\n    }\r\n  }\r\n  return ret;\r\n}\r\n\r\n\r\nlong Solution::Id()\r\n{\r\n  long ret=0;\r\n  for (int i=0;i&lt;Size();i++) {\r\n    ret|=(*this)[i];\r\n    ret<<=4;\r\n  }\r\n  return ret;\r\n}\r\n\r\nclass NQueens : public Solution\r\n{\r\npublic:\r\n\r\n  NQueens(int size,bool print):Solution(size),colno(0),total(0),unique(0),print(print){}\r\n  void Run();\r\n  void Print();\r\n  int Solutions() const {return unique;}\r\n  int TotalSolutions() const {return total;}\r\n  int Size() const {return size();}\r\n  void Found();\r\nprivate:\r\n  void Search();\r\n  void Hline();\r\n  int colno;\r\n  int total;\r\n  int unique;\r\n  bool print;\r\n  int add;\r\n  __gnu_cxx::hash_set<long> solutions;\r\n};\r\n\r\n\r\nvoid NQueens::Found() \r\n{\r\n  total+=add;\r\n  if (solutions.find(Id())==solutions.end()) {\r\n    unique++;\r\n    Solution ret=Transform();\r\n    for(int i=0;i&lt;8;i++) {\r\n      if (ret[0]&lt;=(ret.Size()+1)\/2) {\r\n        solutions.insert(ret.Id());\r\n      }\r\n      ret=ret.Transform();\r\n    }\r\n    if (print) Print();\r\n  }\r\n}\r\n\r\nvoid NQueens::Search()\r\n{\r\n  bool ok;\r\n  for(int i=0;i&lt;Size();i++) {\r\n    ok=true;\r\n    for (int j=0;j&lt;colno;j++) {\r\n      if (i==(*this)[j] || abs(i-(*this)[j])==abs(colno-j)) {\r\n        ok=false;\r\n        break;\r\n      }\r\n    }\r\n    if (ok) {\r\n      (*this)[colno]=i;\r\n      if (colno==Size()-1) {\r\n        Found();\r\n      } else {\r\n        colno++;\r\n        Search();\r\n        colno--;\r\n      }\r\n    }\r\n  }\r\n}\r\n\r\nvoid NQueens::Run() \r\n{\r\n  bool ok;\r\n  int s=Size()\/2;\r\n  add=2;\r\n  colno=1;\r\n  for(int i=0;i&lt;s;i++) {\r\n    (*this)[0]=i;\r\n    Search();\r\n  }\r\n  add=1;\r\n  for(int i=s;i&lt;(Size()+1)\/2;i++) {\r\n    (*this)[0]=i;\r\n    Search();\r\n  }\r\n}\r\n\r\nvoid NQueens::Hline()\r\n{\r\n  int i;\r\n  printf(\"\\n\");\r\n  for(i=0;i&lt;Size();i++) {\r\n    printf(\"+-\");\r\n  }\r\n  printf(\"+\\n\");\r\n}\r\n\r\n\r\nvoid NQueens::Print()\r\n{\r\n  int i,j;\r\n  Hline();\r\n  for(i=0;i&lt;Size();i++) {\r\n    for (j=0;j&lt;Size();j++) {\r\n      if (j==(*this)[i]) {\r\n        printf(\"|D\");\r\n      } else {\r\n        printf(\"| \");\r\n      }\r\n    }\r\n    printf(\"|\");\r\n    Hline();\r\n  } \r\n}\r\n\r\nint main(int argc,char **argv)\r\n{\r\n  int size=8;\r\n  bool print=false;\r\n  int c;\r\n  if (sizeof(long)&lt;8) {\r\n    fprintf(stderr,\"error: size of type 'long' to short (min. 8 byte)\\n\");\r\n    exit(-1);\r\n  }\r\n  while(1) {\r\n    c=getopt(argc,argv,\"s:p\");\r\n    if (c&lt;0) break;\r\n    switch(c) {\r\n    case 's':\r\n      size=strtol(optarg,NULL,0);\r\n      if (size&lt;=0) size=8;\r\n      if (size&gt;16) {\r\n        fprintf(stderr,\"error: size to large (max. 16)\\n\");\r\n        exit(-1);\r\n      }\r\n      break;\r\n    case 'p':\r\n      print=true;\r\n      break;\r\n    }\r\n  }\r\n  NQueens p(size,print);\r\n  p.Run();\r\n  printf(\"Solutions (%dx%d): %d (total %d)\\n\",size,size,p.Solutions(),p.TotalSolutions());\r\n  return 0;\r\n}\r\n\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Dieses Problem wurde zum ersten Mal vom bayrischen Schachmeister Max Bezzel (1824-1871) 1848 in der &#8220;Berliner Schachzeitung&#8221; ver\u00f6ffentlich. Auf Wikipedia gibt es hierzu einen ausf\u00fchrlicher Artikel. Das Problem eignet sich hervorragend, um daran das Verfahren des Backtrackings zu erkl\u00e4ren. Das<span class=\"ellipsis\">&hellip;<\/span><\/p>\n<div class=\"read-more\"><a  href=\"http:\/\/www.fiveoclock.de\/?page_id=168\">Read more <span class=\"screen-reader-text\">8-Damen-Problem<\/span><span class=\"meta-nav\"> &#8250;<\/span><\/a><\/div>\n<p><!-- end of .read-more --><\/p>\n","protected":false},"author":2,"featured_media":0,"parent":185,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/www.fiveoclock.de\/index.php?rest_route=\/wp\/v2\/pages\/168"}],"collection":[{"href":"http:\/\/www.fiveoclock.de\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/www.fiveoclock.de\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/www.fiveoclock.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.fiveoclock.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=168"}],"version-history":[{"count":0,"href":"http:\/\/www.fiveoclock.de\/index.php?rest_route=\/wp\/v2\/pages\/168\/revisions"}],"up":[{"embeddable":true,"href":"http:\/\/www.fiveoclock.de\/index.php?rest_route=\/wp\/v2\/pages\/185"}],"wp:attachment":[{"href":"http:\/\/www.fiveoclock.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=168"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}