4. Queen's puzzle

Queen's puzzle

  • E

    Das 8-Dame-Problem ist schon alt. Bisher konnte man die Lösungen berechnen für ein quadratisches Schachbrett bis N=27.
    https://de.wikipedia.org/wiki/Damenproblem#Anzahl_der_L.C3.B6sungen_bis_zur_Brettgr.C3.B6.C3.9Fe_27.C2.A0.C3.97.C2.A027

    Nachdem man für N=27 schon ca. 1000 Prozessorjahre benötigt, wird nun eine verbesserte Vorgehensweise gesucht, die dem exponentiellen Wachstum der zu berechnenden Varianten mit steigendem N eine geniale Lösung entgegen setzt:
    https://www.welt.de/kmpkt/article168402274/Eine-Million-Dollar-fuer-denjenigen-der-dieses-Schachraetsel-loesen-kann.html

    Mit normalem Brute Force kommt man schnell an ein zeitbedingtes Ende. Man muss da schon etwas zartfühlender ran gehen. Man hört immer von rekursivem backtracking, was nix anderes ist als die Tiefensuche.

    Hier ein kleines C-Progrämmchen zum Testen:

    #include <stdio.h>
#include <time.h>
typedef enum { false, true } bool;

clock_t begin, end;
float tps = 0.0f;  // time per solution
int N = 1;         // number of fields (normal chess board: 8)
int x[27];         // column of chess queen, row i.
int solutions = 0; // number of solutions

void printHorizontalBorder()
{
  printf ("+");
  for (int i=0; i<N; ++i)
    printf("--");
  printf("+\n");
}

void showBoard()
{
  printHorizontalBorder();
  for (int i=0; i<N; ++i)
  {
    printf ("|");
    for (int j=0; j<N; j++)
    {
      if (j==x[i])
        printf ("x ");
      else
        printf ("  ");
    }
    printf ("|\n");
  }
  printHorizontalBorder();
  printf ("\n");
}

bool check(int a, int b)
{
  for (int i=0; i<b; ++i)
    if ((x[i]==a) || (abs(x[i]-a)==abs(i-b)))
        return false;
  return true;
}

void test(int n)
{
  if (n==N)
  {
     ++solutions;
     if (N<7)
       showBoard();
  }
  else
  {
    for (int i=0; i<N; ++i)
    {
      if (check(i,n))
      {
        x[n]=i;
        test(n+1);
      }
    }
  }
}

int main()
{
  int M = 15;
  while (N<=M)
  {
    solutions = 0;
    begin = clock();
    test(0);
    end = clock();
    float timespan = (float)(end - begin)/(float)CLOCKS_PER_SEC;
    float tps = 1000.0 * timespan/(float)solutions;
    printf("N = %i \ttime = %f s \tsolutions = %i", N, timespan, solutions);
    if (N>10)
        printf("\ttps = %f ms\n", tps);
    printf("\n");
    N += 1;
  }
  return 0;
}

    Resultat:

    +--+
|x |
+--+

N = 1   time = 0.001000 s       solutions = 1
N = 2   time = 0.000000 s       solutions = 0
N = 3   time = 0.000000 s       solutions = 0
+--------+
|  x     |
|      x |
|x       |
|    x   |
+--------+

+--------+
|    x   |
|x       |
|      x |
|  x     |
+--------+

N = 4   time = 0.002000 s       solutions = 2
+----------+
|x         |
|    x     |
|        x |
|  x       |
|      x   |
+----------+

+----------+
|x         |
|      x   |
|  x       |
|        x |
|    x     |
+----------+

+----------+
|  x       |
|      x   |
|x         |
|    x     |
|        x |
+----------+

+----------+
|  x       |
|        x |
|    x     |
|x         |
|      x   |
+----------+

+----------+
|    x     |
|x         |
|      x   |
|  x       |
|        x |
+----------+

+----------+
|    x     |
|        x |
|  x       |
|      x   |
|x         |
+----------+

+----------+
|      x   |
|x         |
|    x     |
|        x |
|  x       |
+----------+

+----------+
|      x   |
|  x       |
|        x |
|    x     |
|x         |
+----------+

+----------+
|        x |
|  x       |
|      x   |
|x         |
|    x     |
+----------+

+----------+
|        x |
|    x     |
|x         |
|      x   |
|  x       |
+----------+

N = 5   time = 0.009000 s       solutions = 10
+------------+
|  x         |
|      x     |
|          x |
|x           |
|    x       |
|        x   |
+------------+

+------------+
|    x       |
|          x |
|  x         |
|        x   |
|x           |
|      x     |
+------------+

+------------+
|      x     |
|x           |
|        x   |
|  x         |
|          x |
|    x       |
+------------+

+------------+
|        x   |
|    x       |
|x           |
|          x |
|      x     |
|  x         |
+------------+

N = 6   time = 0.000000 s       solutions = 4
N = 7   time = 0.000000 s       solutions = 40
N = 8   time = 0.015000 s       solutions = 92
N = 9   time = 0.000000 s       solutions = 352
N = 10  time = 0.000000 s       solutions = 724
N = 11  time = 0.016000 s       solutions = 2680        tps = 0.005970 ms
N = 12  time = 0.109000 s       solutions = 14200       tps = 0.007676 ms
N = 13  time = 0.640000 s       solutions = 73712       tps = 0.008682 ms
N = 14  time = 4.118000 s       solutions = 365596      tps = 0.011264 ms
N = 15  time = 27.238000 s      solutions = 2279184     tps = 0.011951 ms

    Lässt man etwas länger laufen, dann erreicht man noch N = 18. Ab dann benötigt es mehrere Tage/Wochen/Monate:

    ...
N = 12  time = 0.109000 s       solutions = 14200       tps = 0.007676 ms
N = 13  time = 0.640000 s       solutions = 73712       tps = 0.008682 ms
N = 14  time = 4.118000 s       solutions = 365596      tps = 0.011264 ms
N = 15  time = 26.927000 s      solutions = 2279184     tps = 0.011814 ms
N = 16  time = 190.570000 s     solutions = 14772512    tps = 0.012900 ms
N = 17  time = 1441.657000 s    solutions = 95815104    tps = 0.015046 ms
N = 18  time = 12273.083000 s   solutions = 666090624   tps = 0.018426 ms

    Siehe auch:
    https://tu-dresden.de/tu-dresden/newsportal/news/neuer-weltrekord-fuer-queens-tud-team (N=27)
    https://www.heise.de/newsticker/meldung/26-Damen-Problem-geloest-6855.html (N=26)

    Macht aber alles keinen Sinn. Etwas völlig Neues muss her. 😉

    Code in C++: https://www.c-plusplus.net/forum/p2540093#2540093

    0
Anmelden zum Antworten