8 queens

在8×8的国际象棋棋盘上放置8个皇后，要求任意两个皇后不能在同一行、同一列或同一条对角线上。

#include <cstdio>
#include <cstdlib>

void print(int cols[], int N);

inline bool is_safe(int cols[], int y)
{
        for (int i = 0; i < y; ++i)
                if (cols[i] == cols[y] || abs(cols[i] - cols[y]) == y - i)
                        return false;
        return true;
}

void queens(int cols[], int n, int N)
{
        if (n == N)
                return print(cols, N);
        for (int i = 0; i < N; ++i)
        {
                cols[n] = i;
                if (is_safe(cols, n))
                        queens(cols, n+1, N);
        }
}

int main()
{
        int cols[8] = { 0 };
        queens(cols, 0, sizeof(cols) / sizeof(int));
}

inline void prtn(const char* s, int n, const char* t = "")
{
        for (int i = 0; i < n; ++i)
                printf(s);
        printf(t);
}

void print(int cols[], int N)
{
        for (int y = 0; y < N; ++y)
                prtn("+---", N, "+\n"),
                prtn("|   ", cols[y], "| Q "), prtn("|   ", N-cols[y]-1, "|\n");
        prtn("+---", N, "+\n\n");
}

+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | Q |
+---+---+---+---+---+---+---+---+
|   |   |   | Q |   |   |   |   |
+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   | Q |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | Q |   |   |
+---+---+---+---+---+---+---+---+
|   | Q |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | Q |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | Q |   |   |   |
+---+---+---+---+---+---+---+---+