Trying to finalize recursive function for queen problem

I am trying to finish code in my void function, however I'm not sure what I am missing in my void function.

edit: thanks
Last edited on
A recursive function needs a recursive call!

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
#include <iostream>
using namespace std;

const int MAXSIZE = 20;
int placements[MAXSIZE];
int solutionsCount = 0;

void printSolution(int size) {
    for (int r = 0; r < size; ++r) {
        for (int c = 0; c < size; ++c)
            cout << (placements[r] == c ? 'Q' : '-') << ' ';
        cout << '\n';
    }
    cout << '\n';
}

bool canPlaceQueen(int row, int column)
{
    for (int r = row; r-- > 0; )
        if (placements[r] == column
            || abs(placements[r] - column) == abs(r - row))
            return false;
    return true;
}

void placeQueens(int size, int row) {
    if (row >= size) {
        ++solutionsCount;
        //printSolution(size);
    }
    else
        for (int column = 0; column < size; ++column)
            if (canPlaceQueen(row, column)) {
                placements[row] = column;
                placeQueens(size, row + 1);
            }
}

int main() {
    int size = 0;
    while (true) {
        cout << "Enter size: ";
        cin >> size;
        if (size > 0 && size <= MAXSIZE) break;
        cout << "Size must be > 0 and <= " << MAXSIZE << '\n';
    }
    
    placeQueens(size, 0);
    cout << "Number of solutions: " << solutionsCount << '\n';
}


Note that a size of 20 is a little ambitious with this program!

Size       Total Solutions       Unique Solutions 
--------------------------------------------------
1                        1                      1 
2                        0                      0 
3                        0                      0 
4                        2                      1 
5                       10                      2 
6                        4                      1 
7                       40                      6 
8                       92                     12 
9                      352                     46 
10                     724                     92 
11                   2,680                    341 
12                  14,200                  1,787 
13                  73,712                  9,233 
14                 365,596                 45,752 
15               2,279,184                285,053 
16              14,772,512              1,846,955 
17              95,815,104             11,977,939 
18             666,090,624             83,263,591 
19           4,968,057,848            621,012,754 
20          39,029,188,884          4,878,666,808 
21         314,666,222,712         39,333,324,973 
22       2,691,008,701,644        336,376,244,042 
23      24,233,937,684,440      3,029,242,658,210 
24     227,514,171,973,736     28,439,272,956,934 
25   2,207,893,435,808,352    275,986,683,743,434 
26  22,317,699,616,364,044  2,789,712,466,510,289 

("Unique solutions" means ignoring rotations and reflections.)
Last edited on
Topic archived. No new replies allowed.