在next_permutation中对n-queen的比较函数。

Question

我试图使用c++ STL中内置的next_permutation函数来解决n-queen的问题，在n queen中，有效的permutation是指前一个queen不应该与当前的queen相邻，即abs(current_queen_index - prev_queen_index) !=1我试图创建一个相同的比较函数，但它没有返回任何东西。

bool isValid(int cur_pos, int prev_pos) {
    return ( abs(cur_pos - prev_pos) != 1 );
}

int main() {
    vector<int> v = { 0, 1, 2, 3 };
    do {
        cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<" "<<v[3]<<"\n";
    } while( next_permutation(v.begin(), v.end(), isValid));

}

Answer 1

最后一个参数是一个比较函数，而不是一个 isValid.

如果您使用 std::next_permutation您可以查看完整的排列组合。

bool isNotValid(int cur_pos, int prev_pos) {
    return std::abs(cur_pos - prev_pos) == 1;
}

int main() {
    std::vector<int> v = { 0, 1, 2, 3 };
    do {
        if (std::adjacent_find(v.begin(), v.end(), &isNotValid) == v.end()) {
            std::cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<" "<<v[3]<<"\n";
        }
    } while (std::next_permutation(v.begin(), v.end()));
}

演示

请注意，对有效组合的检查对大小4有效，但在一般情况下是错误的。