Solving N-Queen problem using random picked queens

[longdoan1511]

My idea is to store the position of the queens in an 1D array with queen[i]=row and i = column, which is randomly generated in a way that no queen is on the same row or column. This will only leave threatened queens on diagonal lines

I scan the lines for threatened queens and store them on another array. The queens in this array will then be selected randomly to swap with another randomly selected queen on the board(swap the row index).


I changed few things and it got better but still can't reach 1000 queens

Each time it successfully perform a swap that can reduce conflict, loop count +1. And after n*90 counts (I noticed that if the board is solved, for example 100 queens, it would take around 8000-10000 loop and so on. So I came up with this), the program will generate another board and start again

The problem is, it can't run efficiently pass 500 queens and each loop takes much longer as the number of queen goes up

Anyone knows how can I improve my code to reach 1000 queens and more ?

Here's my code

#include <iostream>
#include <random>
#include <algorithm>
#include <chrono>
using namespace std;
int queen[1000];
int threat[1000];
int conflict;
long int loop;
int a;


void Out(int arr1[]){
    for(int i =1;i<=a;i++)
        cout << arr1[i] << "\t";
}
// check for conflict on diagonal lines
int Search(int arr1[]){
    conflict =0;
    for(int i=1;i<=a;i++){
        for(int j=i+1;j<=a;j++) {
            if (arr1[i] + i == arr1[j] + j || arr1[i]-i == arr1[j]-j) {
                threat[i] = i; // register position of threatened queen
                threat[j] = j;
                conflict++;
            }
        }
    }
    return conflict;
}
// generate a board with no queen on the same row or column
void Init(){
    for(int i=1;i<=a;i++){
        queen[i]=i;
    }
    shuffle(queen+1,queen+a, std::mt19937(std::random_device()()));
    while(Search(queen)>=a*0.8)
        Init();
}

// check if it's ok to swap
bool isOK(int arr1[],int arr2[]){
    if(Search(arr1)>=Search(arr2))
        return true;
    else
        return false;
}
// move the queen to reduce conflict
void MoveQueen(int arr1[]){
    loop=0;

    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_int_distribution<> dist(1, a);
    int temp[1000];
    int g[10];
    for(int i=1;i<=a;i++) {
        temp[i] = arr1[i]; // create a temporary array to store current position of the queens
    }
    while(Search(arr1)!=0){
        int k = dist(mt); // pick a random threatened queen
        if(threat[k]!=0) {
            int j = dist(mt);
            swap(temp[j], temp[threat[k]]); //swap it with a random queen on the board
            if (isOK(temp,arr1)) { // check if the swap reduces conflict
                for (int i = 1; i <= a; i++) {//revert the position if not
                    temp[i] = arr1[i];
                }
            } else {
                for (int i = 1; i <= a; i++) {//update if it does
                    arr1[i] = temp[i];
                }
            }
        }
        loop ++;
        // if the loop count passes a certain amount, try again
        if(loop>a*90){
            for(int i =1;i<=a;i++){
                queen[i]=0;
                temp[i]=0;
            }
            Init();
            Out(queen); // print out new board
            cout << endl;
            MoveQueen(queen);
        }
    }
}
int main(){
    cin >> a;
    auto start = std::chrono::high_resolution_clock::now();
    Init();
    Out(queen);
    cout << endl;
    MoveQueen(queen);
    Out(queen);
    cout << endl << loop << endl;
    auto stop = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop-start);
    cout << duration.count();
}

[salem c]

If you want to get to 1000, you need a better algorithm than "try random positions".

[longdoan1511]

Do you have any suggestion? I can't think of any
I tried hill climbing but doesn't pass 200, I saw someone mentioned this random method on stack overflow in a post from 2012, maybe I didn't implement it right

[TomCPP]

See
https://academyera.com/n-queen-problem
https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/

[dutch]

@TonyCPP, I doubt the OP was looking for help using google. The naive solution will not be fast enough for 1000 queens.

[salem c]

> Do you have any suggestion?
I find reading about a subject before starting to write code is quite useful.
https://en.wikipedia.org/wiki/Eight_queens_puzzle#Existence_of_solutions

Since you're only interested (or so it seems) in generating any workable solution (as opposed to say counting all the solutions, or printing all the solutions - which would be functionally unachievable for 1000x1000 sized boards anyway).

[longdoan1511]

@TomCPP
I have tried backtrack and hill climbing. Both got me no further than 200 queens which I have already achieved 300 with this random method in at best few seconds and at worst around a minute and half, maybe I did it wrong
@salem c
https://stackoverflow.com/questions/27697929/fast-heuristic-algorithm-for-n-queens-n-1000/27699543
I did do some google and found this post and was following it but apparently I did something wrong at the heuristic and it seems my runtime will multiply by 10 on average when the number of queens is doubled, I also found the genetic algorithm but I don't quite understand it so I can't implement it

[TomCPP]

You can read some intresting solution from https://www.researchgate.net/publication/258651417_An_Unique_Solution_for_N_queen_Problem

If case if you must stay in your primary solution with random swap of conflicted queen, you can use following ( more modern C++) code. Note that, the main computation is performing in separate thread, but it still requires a lot of time, for larger cases, to find out solution or not if maximum number of tries will be exceeded.

#include <iostream>
#include <array>
#include <random>
#include <algorithm>
#include <chrono>
#include <vector>
#include <thread>
#include <future>

using namespace std;

template< int N >
class NQueenSolver
{
public:

    NQueenSolver(){ init(); }

    bool solve()
    {
       int tries {0};

       while( !trySolveRandom() && tries<maxTries )
       {
           ++tries;
           init();
       }

       return  tries<maxTries ? true : false ;
    }

    void print()
    {
        if( N>30 )
        {
            cout << "Solution found!";
            return;
        }

        for( int i {0} ; i<N ; ++i )
        {
            for( int j {0} ; j<N ; ++j ) cout << (board[i]==j ? "1" : "0") << " ";
            cout << endl;
        }
    }

private:

    void init()
    {
        iota( board.begin() , board.end() , 0 );
        auto seed = chrono::system_clock::now().time_since_epoch().count();
        shuffle( board.begin() , board.end() , default_random_engine(seed) );
        findQueensInConflict();
    }

    void findQueensInConflict()
    {
        queensInConflict.clear();
        for( int i {0} ; i<N ; ++i )
        {
            if( findQueensInConflict(i)>0 ) queensInConflict.push_back(i);
        }
    }

    int getNumberOfQueensInConflict( int i , int j )
    {
        return i!=j ? findQueensInConflict(i) + findQueensInConflict(j) : 0;
    }

    int findQueensInConflict( int i )
    {
        int conflicts {0};
        for( int a {1} ; a<N ; ++a )
        {
             if( (i-a) >= 0 )
             {
                 if( abs(board[i] - board[i-a]) == a ) ++conflicts;
             }

             if( (i+a) < N )
             {
                 if( abs(board[i] - board[i+a]) == a ) ++conflicts;
             }
        }
        return conflicts;
    }

    bool trySolveRandom()
    {
        size_t tries {0};

        while( queensInConflict.size()>0 && tries<10*queensInConflict.size() )
        {
            int ri = getRandom(0,queensInConflict.size()-1);
            int rj = getRandom(0,queensInConflict.size()-1);
            if( ri == rj ) continue;

            auto beforeSwap { getNumberOfQueensInConflict(queensInConflict[ri],queensInConflict[rj]) };
            swap( board[queensInConflict[ri]] , board[queensInConflict[rj]] );
            auto afterSwap { getNumberOfQueensInConflict(queensInConflict[ri],queensInConflict[rj]) };

            if( afterSwap >= beforeSwap )
            {
                swap( board[queensInConflict[ri]] , board[queensInConflict[rj]] );
                tries++;
            }
            else
            {
                tries = 0;
                findQueensInConflict();
            }
        }

        cout << "=" << queensInConflict.size() << "\n";

        return queensInConflict.size() == 0 ? true : false ;
    }

    int getRandom( int min , int max )
    {
         mt19937 mt {random_device{}()};
         uniform_int_distribution<int> dist {min,max};
         return dist(mt);
    }

    array<int,N>  board;
    vector<int> queensInConflict;
    const int maxTries {1000};
};

using NQueenSolverM = NQueenSolver<30>;

int main()
{
    NQueenSolverM solver;

    auto start {chrono::steady_clock::now()};
    auto future = async(launch::async,&NQueenSolverM::solve,&solver);
    auto result = future.get();
    cout << "\nProceed in " << chrono::duration<double>(chrono::steady_clock::now()-start).count() << " seconds" << endl;

    if( result ) solver.print();
    else cout << "Solution not found." << endl;

    return 0;
}

https://wandbox.org/permlink/mV9ptZD9XTU69BcY

[longdoan1511]

@TomCPP
Thank you, I'll have a look