Queen's puzzle



  • s. https://www.c-plusplus.net/forum/p2539980

    Hier der entsprechende Code in C++:

    #include <chrono>
    #include <ctime>
    #include <ratio>
    #include <iostream>
    
    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()
    {
      std::cout << "+";
      for (int i=0; i<N; ++i)
      {
        std::cout << "--";
      }
      std::cout << "+" << std::endl;
    }
    
    void showBoard()
    {
      printHorizontalBorder();
      for (int i=0; i<N; ++i)
      {
        std::cout << "|";
        for (int j=0; j<N; j++)
        {
          if (j==x[i])
            std::cout << "x ";
          else
            std::cout << "  ";
        }
        std::cout << "|\n";
      }
      printHorizontalBorder();
      std::cout << std::endl;
    }
    
    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 = 27;
      while (N<=M)
      {
        solutions = 0;
        auto t1 = std::chrono::system_clock::now();
        test(0);
        auto t2 = std::chrono::system_clock::now();
        float timespan = std::chrono::duration<float>(t2-t1).count();
        float tps = 0.0f;
        if (solutions)
        {
            tps = 1000 * timespan/(float)solutions;
        }
        std::cout << "N = " << N << "\ttime = " << timespan << " s \tsolutions = " << solutions;
        if (N>10)
            std::cout << "\ttps = " << tps << " ms\n";
        std::cout << std::endl;
        N += 1;
      }
      return 0;
    }
    

Log in to reply