알고리즘 - 기초

N-Queens Problem C++ Code BackTracking

치킨먹고싶어요 2022. 6. 17. 13:06
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int n, anscount;    //n for input of chessboard's size, anscount for answers count
vector<int> col;    //chessboard, drawed in 1st dimension(since it's square)
string sol;     //storage of largest solution
 
bool promising(int i) {
    int k = 1;
    bool flag = true;
    while (k < i && flag) {        //for (int k = 0; k < i && flag; k++)
        if ((col[i] == col[k]) || abs(col[i] - col[k]) == abs(i - k)) flag = false;
        //if new queen's in the same column or row || diagonal, stop
        k++;
    }
    return flag;    //return true if while() is okay, false if any of condition fails
}
 
void queens(int i) {
    int j;
    if (promising(i)) {        //if it meets conditions in promising
        if (i == n) {        //if queens == n
            anscount++;        //the solution is appropriate, thus adding 1 to count
            string temp;    //makes temp for string concatnation
            for (j = 1; j <= n; j++) temp += to_string(col[j]);    //make combinations string
            if (sol < temp) sol = temp;    //compare former largest solution to temp
 
        }
        else {
            for (j = 1; j <= n; j++) {    
                col[i + 1= j;        //mark col[i+1] as j(trial)
                queens(i + 1);        //see if it's possible
            }
        }
    }
 
}
 
int main(void) {
    cin >> n;        //input of n * n chessboard
    col = vector<int>(n + 1);    //make chessboard with (n * n) tiles, but it starts from 1
    queens(0);        //driver code starts with queens = 0
    cout << anscount << endl << sol;
    return 0;
}
 
 
cs