Solving N-Queen problem using random picked queens

longdoan1511 (6)

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
#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();
}
Last edited on
salem c (3700)
If you want to get to 1000, you need a better algorithm than "try random positions".



longdoan1511 (6)
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
Last edited on
dutch (2548)
@TonyCPP, I doubt the OP was looking for help using google. The naive solution will not be fast enough for 1000 queens.
salem c (3700)
> 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 (6)
@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 (32)
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
#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 (6)
@TomCPP
Thank you, I'll have a look
Topic archived. No new replies allowed.