title: fast heuristic algorithm for n queens (n > 1000)
body: <p>I write two program :</p>
  
  <ol>
  <li>put together n queens in chess board without any threatening by backtracking algorithm. but that is very heavy for big n . at last you can run that for 100 queens.</li>
  <li>put together n queens in chess board without any threatening by Hill climbing algorithm. this algorithm better than past solution but it take 2 min for 300 queens and this time increase exponentially!</li>
  </ol>
  
  <p>But I didn't have any idea for doing that fast! I want algorithm for doing that faster .</p>
  
  <p>I want faster manner to solve problem fast as possible for 1000 queens.</p>
  
  <p>This is my Hill climbing Code : </p>
  
  <pre><code>// N queen - Reset Repair Hill Climbing.cpp
  // open-mind.ir
  
  #include "stdafx.h"
  #include &lt;vector&gt;
  #include &lt;iostream&gt;
  #include &lt;fstream&gt;
  #include &lt;time.h&gt;
  #include &lt;iomanip&gt;
  
  
  using namespace std;
  
  //print solution in console
  void printBoardinTerminal(int *board, int len)
  {
      for (int i = 0; i &lt; len; i++)
      {
          for (int j = 0; j &lt; len; j++)
          {
              if (j == board[i])
              {
                  cout &lt;&lt; 1 &lt;&lt; " ";
              }
              else
              {
                  cout &lt;&lt; 0 &lt;&lt; " ";
              }
          }
          cout &lt;&lt; endl;
      }
  }
  
  //print solution in File
  void printBoardinFile(int *board, int len)
  {
      ofstream fp("output.txt", ios::out);
  
      fp &lt;&lt; "Answer for " &lt;&lt; len &lt;&lt; " queen: \n \n";
  
      for (int i = 0; i &lt; len; i++)
      {
          for (int j = 0; j &lt; len; j++)
          {
              fp &lt;&lt; "----";
          }
          fp &lt;&lt; "\n|";
  
          for (int j = 0; j &lt; len; j++)
          {
              if (j == board[i])
              {
                  fp &lt;&lt; setw(4) &lt;&lt; "* |" ;
              }
              else
              {
                  fp &lt;&lt; setw(4) &lt;&lt; "  |";
              }
          }
          fp &lt;&lt; "\n";
      }
  }
  
  //The number of queens couples who are threatened themself
  int evaluate(int *board, int len)
  {
      int score = 0;
      for (int i = 0; i &lt; len - 1; i++)
      {
          for (int j = i + 1; j &lt; len; j++)
          {
              if (board[i] == board[j])
              {
                  score++;
                  continue;
              }
              if (board[i] - board[j] == i - j)
              {
                  score++;
                  continue;
              }
              if (board[i] - board[j] ==  j - i)
              {
                  score++;
                  continue;
              }
          }
      }
      return score;
  }
  
  //generate new state from current state 
  int* generateBoard(int *board,int len)
  {
      vector &lt;int&gt; choice;
  
      int temp;
      int score;
      int eval = evaluate(board, len);
      int k;
  
      int *boardOut;
      boardOut = new int [len];
  
  
      for (int i = 0; i &lt; len; i++)
      {
              boardOut[i] = board[i];
      }
  
      for (int i = 0; i &lt; len; i++)
      {
          choice.clear();
  
          choice.push_back(boardOut[i]);
          temp = boardOut[i];
  
          for (int j = 0; j &lt; len; j++)
          {
              boardOut[i] = j;
  
              k = evaluate(boardOut, len);
  
              if (k == eval)
              {
                  choice.push_back(j);
              }
  
              if (k &lt; eval)
              {
                  choice.clear();
                  choice.push_back(j);
                  eval = k;
              }
          }
          boardOut[i] = choice[rand() % choice.size()];
      }
  
      return boardOut;
  }
  
  //in this function , genarate new state by pervious function and if it has better value then replaces that by current state
  bool findNextState(int *board, int len)
  {
      int maineval = evaluate(board, len);
  
      int *tempBoard;
  
      tempBoard = generateBoard(board, len);
  
      if (evaluate(tempBoard, len) &lt; maineval)
      {
          for (int p = 0; p &lt; len; p++)
          {
              board[p] = tempBoard[p];
          }
  
          return  true;
      }
  
      return false;
  }
  
  // make random initial state , put one queen in each row
  void initialRandomBoard(int * board, int len)
  {
      bool access;
      int col;
  
      for (int i = 0; i &lt; len; i++)
      {
          board[i] = rand() % len;
      }
  }
  
  //this function include a loop that call findNextState function , and do that until reach solution
  //if findNextState function return NULL then we reset current state
  void SolveNQueen(int len)
  {
      cout &lt;&lt; "The program is under process! wait!" &lt;&lt; endl;
  
      int *board;
      board = new int[len];
  
  
      initialRandomBoard(board, len);
  
      while (evaluate(board, len) != 0)
      {
          if (!findNextState(board, len))
          {
              initialRandomBoard(board, len);
          }
      }
  
  
      //
      cout &lt;&lt; endl &lt;&lt; "Anwser for " &lt;&lt; len &lt;&lt; " queens: "&lt;&lt; endl &lt;&lt; endl;
      printBoardinTerminal(board, len);
      printBoardinFile(board, len);
      //
  }
  
  
  int main()
  {
      int n;
      srand(time(NULL));
  
      cout &lt;&lt; "Enter  number \'N\', \'N\' indicate numbers of queens in \"N * N\" chess board: " &lt;&lt; endl;
      cin &gt;&gt; n;
  
      if (n &lt; 4)
      {
          cout &lt;&lt; "\'n\' must be uper than 3!" &lt;&lt; endl;
          exit(1);
      }
  
      SolveNQueen(n);
  
      cout &lt;&lt; endl &lt;&lt; "As well , you can see result in \"output.txt\"." &lt;&lt; endl &lt;&lt; endl;
  
      return 0;
  }
  </code></pre>