首页 > itarticle > n-queen-problem

n-queen-problem

admin 11月 12, 2020 0

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
queens will attack each other when they are in the same row or same column or diagonal.

Solution 1

用一个大小为N的一维数组表示每一行的皇后所放置的列，只要列数不重复且不在对角线上就可以保证皇后不会互相攻击。
采用递归实现，伪代码如下：

void (void row) {
    if row == N:
        printResult()
    else:
        for k from 0 to N:
            if can place in (row, k):
                place in (row, k)
                eightQueen(row + 1)
}

这是纯C代码实现，在递归得出结果后会把结果打印出来

result 92:
0 —- 7
1 —- 3
2 —- 0
3 —- 2
4 —- 5
5 —- 1
6 —- 6
7 —- 4
0 1 2 3 4 5 6 7
0 . . . . . . . @
1 . . . @ . . . .
2 @ . . . . . . .
3 . . @ . . . . .
4 . . . . . @ . .
5 . @ . . . . . .
6 . . . . . . @ .
7 . . . . @ . . .

#include <stdlib.h>
#define ASSERT
typedef enum {FALSE, TRUE} Bool;
void (int curRow);
Bool canPlace(int curRow, int k);
void placeQueen(int curRow, int k);
void printResult(void);
int N = 8;
int *board;
int main(int argc, char* argv[])
{
    if (argc >= 2)
        sscanf(argv[1], "%d", &N);
    if ((board = malloc(N * sizeof(int))) == NULL)
    {
         fprintf(stderr, "No available memory!n");
         exit(EXIT_FAILURE);
    }
    for (int i = 0; i < N; i++)
        board[i] = 2 * N + 1;
    eightQueen(0);
    return 0;
}
Bool canPlace(int curRow, int k)
{
    for (int i = 0; i < curRow; i++)
    {
        if (board[i] == k || abs(i - curRow) == abs(k - board[i]))
            return FALSE;
    }
    return TRUE;
}
void placeQueen(int curRow, int k)
{
    board[curRow] = k;
}
void (int curRow)
{
    if (curRow == N)
        printResult();
    else
        for (int k = 0; k < N; k++)
            if (canPlace(curRow, k))
            {
                 placeQueen(curRow, k);
                 eightQueen(curRow + 1);
            }
}
void printResult(void)
{
    static int resultNum = 1;
    printf("nnnresult %d:n", resultNum);
#ifdef ASSERT
    for (int i = 0; i < N; i++)
        printf("%d ---  %dn", i, board[i]);
#endif
    printf("   ");
    for (int i = 0; i < N; i++)
        printf("%2d ", i);
    printf("n");
    for (int i = 0; i < N; i++)
    {
         printf("%2d ", i);
         for (int j = 0; j < N; j++)
         {
             if (j == board[i])
                 printf(" @ ");
             else
                 printf(" . ");
         }
         printf("n");
    }
    resultNum++;
}

Solution 2

A pythonic short implementation

from itertools import *
cols = range(8)
for vec in permutations(cols):
    if (8 == len(set(vec[i] + i for i in cols))
          == len(set(vec[i] - i for i in cols))):
        print(vec)