#### Magic Sequence

```/*
* @brief [Magic sequence](https://www.csplib.org/Problems/prob019/)
* implementation
*
* @details Solve the magic sequence problem with backtracking
*
* "A magic sequence of length \$n\$ is a sequence of integers \$x_0
* \ldots x_{n-1}\$ between \$0\$ and \$n-1\$, such that for all \$i\$
* in \$0\$ to \$n-1\$, the number \$i\$ occurs exactly \$x_i\$ times in
* the sequence. For instance, \$6,2,1,0,0,0,1,0,0,0\$ is a magic
* sequence since \$0\$ occurs \$6\$ times in it, \$1\$ occurs twice, etc."
* Quote taken from the [CSPLib](https://www.csplib.org/Problems/prob019/)
* website
*
* @author [Jxtopher](https://github.com/Jxtopher)
*/

#include <algorithm>  /// for std::count
#include <cassert>    /// for assert
#include <iostream>   /// for IO operations
#include <list>       /// for std::list
#include <numeric>    /// for std::accumulate
#include <vector>     /// for std::vector

/**
* @namespace backtracking
* @brief Backtracking algorithms
*/
namespace backtracking {
/**
* @namespace magic_sequence
* @brief Functions for the [Magic
* sequence](https://www.csplib.org/Problems/prob019/) implementation
*/
namespace magic_sequence {
using sequence_t =
std::vector<unsigned int>;  ///< Definition of the sequence type
/**
* @brief Print the magic sequence
* @param s working memory for the sequence
*/
void print(const sequence_t& s) {
for (const auto& item : s) std::cout << item << " ";
std::cout << std::endl;
}

/**
* @brief Check if the sequence is magic
* @param s working memory for the sequence
* @returns true if it's a magic sequence
* @returns false if it's NOT a magic sequence
*/
bool is_magic(const sequence_t& s) {
for (unsigned int i = 0; i < s.size(); i++) {
if (std::count(s.cbegin(), s.cend(), i) != s[i]) {
return false;
}
}
return true;
}

/**
* @brief Sub-solutions filtering
* @param s working memory for the sequence
* @param depth current depth in tree
* @returns true if the sub-solution is valid
* @returns false if the sub-solution is NOT valid
*/
bool filtering(const sequence_t& s, unsigned int depth) {
return std::accumulate(s.cbegin(), s.cbegin() + depth,
static_cast<unsigned int>(0)) <= s.size();
}

/**
* @brief Solve the Magic Sequence problem
* @param s working memory for the sequence
* @param ret list of the valid magic sequences
* @param depth current depth in the tree
*/
void solve(sequence_t* s, std::list<sequence_t>* ret, unsigned int depth = 0) {
if (depth == s->size()) {
if (is_magic(*s)) {
ret->push_back(*s);
}
} else {
for (unsigned int i = 0; i < s->size(); i++) {
(*s)[depth] = i;
if (filtering(*s, depth + 1)) {
solve(s, ret, depth + 1);
}
}
}
}

}  // namespace magic_sequence
}  // namespace backtracking

/**
* @brief Self-test implementations
* @returns void
*/
static void test() {
// test a valid magic sequence
backtracking::magic_sequence::sequence_t s_magic = {6, 2, 1, 0, 0,
0, 1, 0, 0, 0};
assert(backtracking::magic_sequence::is_magic(s_magic));

// test a non-valid magic sequence
backtracking::magic_sequence::sequence_t s_not_magic = {5, 2, 1, 0, 0,
0, 1, 0, 0, 0};
assert(!backtracking::magic_sequence::is_magic(s_not_magic));
}

/**
* @brief Main function
* @returns 0 on exit
*/
int main() {
test();  // run self-test implementations

// solve magic sequences of size 2 to 11 and print the solutions
for (unsigned int i = 2; i < 12; i++) {
std::cout << "Solution for n = " << i << std::endl;
// valid magic sequence list
std::list<backtracking::magic_sequence::sequence_t> list_of_solutions;
// initialization of a sequence
backtracking::magic_sequence::sequence_t s1(i, i);
// launch of solving the problem
backtracking::magic_sequence::solve(&s1, &list_of_solutions);
// print solutions
for (const auto& item : list_of_solutions) {
backtracking::magic_sequence::print(item);
}
}
return 0;
}
```