fast heuristic algorithm for n queens (n > 1000)

Question

I write two program :

1. 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.
2. 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!

But I didn't have any idea for doing that fast! I want algorithm for doing that faster .

I want faster manner to solve problem fast as possible for 1000 queens.

This is my Hill climbing Code :

// N queen - Reset Repair Hill Climbing.cpp
// open-mind.ir

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <fstream>
#include <time.h>
#include <iomanip>


using namespace std;

//print solution in console
void printBoardinTerminal(int *board, int len)
{
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < len; j++)
        {
            if (j == board[i])
            {
                cout << 1 << " ";
            }
            else
            {
                cout << 0 << " ";
            }
        }
        cout << endl;
    }
}

//print solution in File
void printBoardinFile(int *board, int len)
{
    ofstream fp("output.txt", ios::out);

    fp << "Answer for " << len << " queen: \n \n";

    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < len; j++)
        {
            fp << "----";
        }
        fp << "\n|";

        for (int j = 0; j < len; j++)
        {
            if (j == board[i])
            {
                fp << setw(4) << "* |" ;
            }
            else
            {
                fp << setw(4) << "  |";
            }
        }
        fp << "\n";
    }
}

//The number of queens couples who are threatened themself
int evaluate(int *board, int len)
{
    int score = 0;
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = i + 1; j < 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 <int> choice;

    int temp;
    int score;
    int eval = evaluate(board, len);
    int k;

    int *boardOut;
    boardOut = new int [len];


    for (int i = 0; i < len; i++)
    {
            boardOut[i] = board[i];
    }

    for (int i = 0; i < len; i++)
    {
        choice.clear();

        choice.push_back(boardOut[i]);
        temp = boardOut[i];

        for (int j = 0; j < len; j++)
        {
            boardOut[i] = j;

            k = evaluate(boardOut, len);

            if (k == eval)
            {
                choice.push_back(j);
            }

            if (k < 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) < maineval)
    {
        for (int p = 0; p < 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 < 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 << "The program is under process! wait!" << endl;

    int *board;
    board = new int[len];


    initialRandomBoard(board, len);

    while (evaluate(board, len) != 0)
    {
        if (!findNextState(board, len))
        {
            initialRandomBoard(board, len);
        }
    }


    //
    cout << endl << "Anwser for " << len << " queens: "<< endl << endl;
    printBoardinTerminal(board, len);
    printBoardinFile(board, len);
    //
}


int main()
{
    int n;
    srand(time(NULL));

    cout << "Enter  number \'N\', \'N\' indicate numbers of queens in \"N * N\" chess board: " << endl;
    cin >> n;

    if (n < 4)
    {
        cout << "\'n\' must be uper than 3!" << endl;
        exit(1);
    }

    SolveNQueen(n);

    cout << endl << "As well , you can see result in \"output.txt\"." << endl << endl;

    return 0;
}

Answer 1

Note: This answer assumes you're interested in finding one valid solution. If you need to find all solutions, this won't help you.

Artificial Intelligence: A Modern Approach, Second Edition by Russell & Norvig has a table in Chapter 5: Constraint Satisfaction Problems on page 143 comparing various constraint satisfaction problem algorithms for various tasks. (The latest edition is the Third Edition, and it looks like Constraint Satisfaction Problems is now Chapter 6.)

According to their results, the minimum conflicts local search heuristic scored best out of the algorithms tested on the n-Queens problem, requiring an average of 4K checks compared with >40,000K checks for backtracking and forward-checking.

The algorithm is quite simple:

• select an initial (random or preselected) assignment of queens
• while there are threatened queens (or until you get tired of trying... it's worthwhile to put this in a for loop to limit the number of tries):
  • select a random threatened queen
  • move the selected queen to the square that minimizes conflicts

In that last step, I'm assuming that each queen is constrained to her column, so she can only change rows within the column. If there are several rows that minimize conflicts for the current queen, you can choose randomly among them.

That's it. It's completely random and it works beautifully.

Edit:

I had a note here about not remembering how high I got n when I implemented this algorithm, saying I knew I had got it over 100. I didn't find my old code, but I decided to throw something together anyway. It turns out that this approach is far more effective than I remembered. Here are the results for 10 queens:

Starting Configuration:
14  0  2  13  12  17  10  14  14  2  9  8  11  10  6  16  0  7  10  8  
Solution found
Ending Configuration:
17  2  6  12  19  5  0  14  16  7  9  3  1  15  11  18  4  13  8  10  
Elapsed time (sec): 0.00167
Number of moves: 227

With no attempts at optimizing the code, here are the approximate timings I'm getting for different problem sizes:

Queens      ~Time(sec)
======      ==========
  100           0.03
  200           0.12
  500           1.42
 1000           9.76
 2000          72.32
 5000        1062.39

I only ran the last one for 5000 queens once, but to find a solution in under 18 minutes is quicker than I had expected.