1. Runtime Distribution

2. Submission Details

3. Description

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

4. Example

There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]

6. Code

char ** board;
int* row;
int* col;
int** diagonal;

void Marking(int i, int j, int n, int mark) {
    row[i] += mark;
    col[j] += mark;

    for (int x = i, y = j; x >= 0 && y < n; x--, y++)
    {
        diagonal[x][y] += mark;
    }

    for (int x = i + 1, y = j - 1; x < n && y >= 0; x++, y--)
    {
        diagonal[x][y] += mark;
    }

    for (int x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--)
    {
        diagonal[x][y] += mark;
    }

    for (int x = i + 1, y = j + 1; x < n && y < n; x++, y++)
    {
        diagonal[x][y] += mark;
    }
}

void findNextOne(char*** ret, int* returnSize, int i, int j, int n)
{
    if (i == n)
    {
        ret[*returnSize] = (char **)malloc(sizeof(void *) * n);

        for (int a = 0; a < n; a++)
        {
            ret[*returnSize][a] = (char *)malloc(sizeof(char) * (n + 1));
        }

        for (int a = 0; a < n; a++)
        {
            for (int b = 0; b < n; b++)
            {
                ret[*returnSize][a][b] = board[a][b];
            }
            ret[*returnSize][a][n] = '\0';
        }

        (*returnSize)++;

        return;
    }

    for (int y = j; y < n; y++)
    {
        if (row[i] == 0 && col[y] == 0 && diagonal[i][y] == 0)
        {
            board[i][y] = 'Q';
            Marking(i, y, n, 1);
            findNextOne(ret, returnSize, i + 1, 0, n);
            Marking(i, y, n, -1);
            board[i][y] = '.';
        }
    }
}

char*** solveNQueens(int n, int* returnSize) {

    *returnSize = 0;
    char*** ret = (char***)malloc(sizeof(char **) * 512);

    board = (char **)malloc(sizeof(char*) * n);
    for (int i = 0; i< n; i++)
    {
        board[i] = (char *)malloc(sizeof(char) * n);
    }

    row = (int *)malloc(sizeof(int) * n);
    col = (int *)malloc(sizeof(int) * n);
    diagonal = (int **)malloc(sizeof(int *) * n);

    for (int i = 0; i< n; i++)
    {
        diagonal[i] = (int *)malloc(sizeof(int) * n);
    }

    for (int i = 0; i < n; i++)
    {
        row[i] = 0; col[i] = 0;
        for (int j = 0; j< n; j++)
        {
            board[i][j] = '.';
            diagonal[i][j] = 0;
        }
    }

    findNextOne(ret, returnSize, 0, 0, n);
    return ret;
}

vector<vector<string>> solveNQueens(int n) {

    vector<int> row(n);
    vector<int> col(n);

    vector<vector<int> > diagonal(n);

    vector<vector<char> > board(n);
    for (auto i = 0; i < n; i++)
    {
        diagonal[i].resize(n);
        board[i].resize(n);
    }

    for(auto i = 0; i< n; i++)
    {
        for(auto j = 0; j < n; j++)
        {
            board[i][j] = '.';
        }
    }

    vector<vector<string> > res;

    findNextOne(res, board, row, col, diagonal, 0, 0, n);

    return res;

}

static void findNextOne(vector<vector<string> > &res, vector<vector<char> > &board,
    vector<int> row, vector<int> col, vector<vector<int> > diagonal, int i, int j, int n)
{
    if (i == n)
    {
        vector<string> solution;
        for (auto a = 0; a < n; a++)
        {
            string line(board[a].begin(), board[a].end());
            solution.push_back(line);
        }

        res.push_back(solution);

        return;
    }

    for (int y = j; y < n; y++)
    {
        if (row[i] == 0 && col[y] == 0 && diagonal[i][y] == 0)
        {
            board[i][y] = 'Q';
            Marking(row, col, diagonal, i, y, n, 1);
            findNextOne(res, board, row, col, diagonal, i + 1, 0, n);
            Marking(row, col, diagonal, i, y, n, -1);
            board[i][y] = '.';
        }
    }
}

static void Marking(vector<int> &row, vector<int> &col, vector<vector<int> > &diagonal, int i, int j, int n, int mark) {

    row[i] += mark;
    col[j] += mark;

    for (int x = i, y = j; x >= 0 && y < n; x--, y++)
    {
        diagonal[x][y] += mark;
    }

    for (int x = i + 1, y = j - 1; x < n && y >= 0; x++, y--)
    {
        diagonal[x][y] += mark;
    }

    for (int x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--)
    {
        diagonal[x][y] += mark;
    }

    for (int x = i + 1, y = j + 1; x < n && y < n; x++, y++)
    {
        diagonal[x][y] += mark;
    }
}

7.Test

#include <stdio.h>
#include <stdlib.h>

char ** board;
int* row;
int* col;
int** diagonal;

void Marking(int i, int j, int n, int mark) {
    row[i] += mark;
    col[j] += mark;

    for (int x = i, y = j; x >= 0 && y < n; x--, y++)
    {
        diagonal[x][y] += mark;
    }

    for (int x = i + 1, y = j - 1; x < n && y >= 0; x++, y--)
    {
        diagonal[x][y] += mark;
    }

    for (int x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--)
    {
        diagonal[x][y] += mark;
    }

    for (int x = i + 1, y = j + 1; x < n && y < n; x++, y++)
    {
        diagonal[x][y] += mark;
    }
}

void findNextOne(char*** ret, int* returnSize, int i, int j, int n)
{
    if (i == n)
    {
        ret[*returnSize] = (char **)malloc(sizeof(void *) * n);

        for (int a = 0; a < n; a++)
        {
            ret[*returnSize][a] = (char *)malloc(sizeof(char) * (n + 1));
        }

        for (int a = 0; a < n; a++)
        {
            for (int b = 0; b < n; b++)
            {
                ret[*returnSize][a][b] = board[a][b];
            }
            ret[*returnSize][a][n] = '\0';
        }

        (*returnSize)++;

        return;
    }

    for (int y = j; y < n; y++)
    {
        if (row[i] == 0 && col[y] == 0 && diagonal[i][y] == 0)
        {
            board[i][y] = 'Q';
            Marking(i, y, n, 1);
            findNextOne(ret, returnSize, i + 1, 0, n);
            Marking(i, y, n, -1);
            board[i][y] = '.';
        }
    }
}

char*** solveNQueens(int n, int* returnSize) {

    *returnSize = 0;
    char*** ret = (char***)malloc(sizeof(char **) * 512);

    board = (char **)malloc(sizeof(char*) * n);
    for (int i = 0; i< n; i++)
    {
        board[i] = (char *)malloc(sizeof(char) * n);
    }

    row = (int *)malloc(sizeof(int) * n);
    col = (int *)malloc(sizeof(int) * n);
    diagonal = (int **)malloc(sizeof(int *) * n);

    for (int i = 0; i< n; i++)
    {
        diagonal[i] = (int *)malloc(sizeof(int) * n);
    }

    for (int i = 0; i < n; i++)
    {
        row[i] = 0; col[i] = 0;
        for (int j = 0; j< n; j++)
        {
            board[i][j] = '.';
            diagonal[i][j] = 0;
        }
    }

    findNextOne(ret, returnSize, 0, 0, n);
    return ret;
}

int main()
{
    int n = 8;
    int returnSize = 0;
    char*** res = solveNQueens(n, &returnSize);
    printf("size = %d\n", returnSize);

    for (int i = 0; i < returnSize; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                printf("%c ", res[i][j][k]);
            }
            printf("\n");
            free(res[i][j]);
        }
        printf("\n");
        free(res[i]);
    }

    free(res);
    system("pause");
    return 0;
}

#include <string>
#include <vector>
#include <iostream>

using namespace std;

class LeetCode0051 {
public:
    vector<vector<string>> solveNQueens(int n) {

        vector<int> row(n);
        vector<int> col(n);

        vector<vector<int> > diagonal(n);

        vector<vector<char> > board(n);
        for (auto i = 0; i < n; i++)
        {
            diagonal[i].resize(n);
            board[i].resize(n);
        }

        for(auto i = 0; i< n; i++)
        {
            for(auto j = 0; j < n; j++)
            {
                board[i][j] = '.';
            }
        }

        vector<vector<string> > res;

        findNextOne(res, board, row, col, diagonal, 0, 0, n);

        return res;

    }

    static void findNextOne(vector<vector<string> > &res, vector<vector<char> > &board,
        vector<int> row, vector<int> col, vector<vector<int> > diagonal, int i, int j, int n)
    {
        if (i == n)
        {
            vector<string> solution;
            for (auto a = 0; a < n; a++)
            {
                string line(board[a].begin(), board[a].end());
                solution.push_back(line);
            }

            res.push_back(solution);

            return;
        }

        for (int y = j; y < n; y++)
        {
            if (row[i] == 0 && col[y] == 0 && diagonal[i][y] == 0)
            {
                board[i][y] = 'Q';
                Marking(row, col, diagonal, i, y, n, 1);
                findNextOne(res, board, row, col, diagonal, i + 1, 0, n);
                Marking(row, col, diagonal, i, y, n, -1);
                board[i][y] = '.';
            }
        }
    }

    static void Marking(vector<int> &row, vector<int> &col, vector<vector<int> > &diagonal, int i, int j, int n, int mark) {

        row[i] += mark;
        col[j] += mark;

        for (int x = i, y = j; x >= 0 && y < n; x--, y++)
        {
            diagonal[x][y] += mark;
        }

        for (int x = i + 1, y = j - 1; x < n && y >= 0; x++, y--)
        {
            diagonal[x][y] += mark;
        }

        for (int x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--)
        {
            diagonal[x][y] += mark;
        }

        for (int x = i + 1, y = j + 1; x < n && y < n; x++, y++)
        {
            diagonal[x][y] += mark;
        }
    }

};

int main() {
    LeetCode0051 leetCode0051;
    vector<vector<string> > ret = leetCode0051.solveNQueens(4);

    for (int i = 0; i < ret.size(); i++) {
        for (int j = 0; j < ret[0].size(); j++) {
            cout << ret[i][j] << endl;
        }
        cout << "----" << endl;
    }
    return 0;
}

7、Appendix

Belowing is the num of queens of different n

  1                1  <br>
  2                0  <br>
  3                0  <br>
  4                2  <br>
  5                10  <br>
  6                4  <br>
  7                40  <br>
  8                92  <br>
  9                352  <br>
  10               724  <br>
  11               2680  <br>
  12               14200  <br>
  13               73712  <br>
  14               365596  <br>
  15               2279184  <br>
  16               14772512  <br>
  17               95815104  <br>
  18               666090624  <br>
  19               4968057848  <br>
  20               39029188884  <br>
  21               314666222712  <br>
  22               2691008701644  <br>
  23               24233937684440  <br>
  24               227514171973736  <br>
  25               2207893435808352  <br>