#include <cstdio>
#include <vector>
#include <algorithm>
template <typename F> void solve(int n, std::vector<int> &st, F f) {
int size = int(st.size());
if (n == size) {
f(&st[0], size);
return;
}
for (int x = 1; x <= size; ++x) {
bool safe = true;
for (int i = 0; i < n && safe; ++i)
if (st[i] == x || std::abs(st[i] - x) == n - i)
safe = false;
if (safe) {
st[n] = x;
solve(n + 1, st, f);
}
}
}
template <typename F> void queens(int size, F f)
{
std::vector<int> state(size);
solve(0, state, f);
}
void print(const int *p, size_t size)
{
for (size_t i = 0; i < size; ++i)
std::printf("(%d %d)", p[i], i + 1);
std::putchar('\n');
}
int main()
{
queens(8, print);
}
/*
struct collect {
std::vector<std::vector<int> > result;
void operator ()(const int *p, size_t size) {
result.push_back(std::vector<int>(p, p + size));
}
};
#include <windows.h>
int main()
{
DWORD now = GetTickCount();
for (int i = 0; i < 100; ++i)
queens(8, collect());
std::printf("%d\n", GetTickCount() - now);
}
*/