N皇后问题（python，C实现）

N皇后是在N×N棋盘上放置N个棋后的问题，这样没有两个皇后在横、竖、对角线上相互攻击。
例如，以下是4皇后问题的解决方案。

{ 0, 1, 0, 0}
{ 0, 0, 0, 1}
{ 1, 0, 0, 0}
{ 0, 0, 1, 0}

1的位置表示皇后所在位置

while 还有没有试过的放置位置
{
	产生新的放置方案
	if 皇后们没有相安无事
	{
		打印皇后们的位置方案
	}
}

回溯算法是将皇后从最左边的列开始一一放置在不同的列中，当我们将皇后放在一列中时，我们会检查与已放置的皇后是否有冲突。在当前位置中，如果没有冲突，我们将此位置暂时先放置一个皇后。如果由于冲突，那么我们回溯并返回false。

从最左边的列开始如果所有皇后都被放置返回真尝试当前列中的所有行，对每个尝试的行执行以下操作。
3.1 如果皇后可以安全地放在这一位置则将此[row, column]标记此位置为本宫所有。
3.2 如果将皇后放在[row, column]中没有冲突在返回true。
3.3 如果放置皇后有冲突，那么打回冷宫取消[row, column]标记（即回溯）并转到步骤3.1尝试其他行。如果所有行都已尝试都有冲突，返回false回溯尝试其它行。

#python

import numpy as np;
import os,time

def print_board(board):
    for i in range(board.shape[0]):
        for j in range(board.shape[1]):
            if board[i][j]:
                print(f'33[1;41m{board[i][j]} 33[0m  ', end='')
            else:
                print(f'{board[i][j]}   ', end='')
        print()
        print()

def trace_board(board):
    os.system('cls')
    print_board(board)
    time.sleep(1)

def is_safe(board, row, col):
    for i in range(col):
        if board[row][i]:
            return False

    for i, j in zip(reversed(range(row+1)), reversed(range(col+1))):
        if (board[i][j]):
            return False

    for i, j in zip(range(row, board.shape[0]), reversed(range(col+1))):
        if (board[i][j]):
            return False

    return True

def solve_nq(board, col):
    if col >= board.shape[1]:
        return True

    for i in range(board.shape[0]):
        if is_safe(board, i, col):
            board[i][col] = 1

            trace_board(board)

            if solve_nq(board, col + 1):
                return True
            board[i][col] = 0

    return False

if __name__ == "__main__":
    N = 6

    board = np.zeros((N, N), dtype=np.uint8)

    if solve_nq(board, 0):
        #print_board(board)
        print("Solution NQ problem")
        pass
    else:
        print("Solution does not exist")

// C
#include 
#include 
#include 
#include 

//#define false 0
//#define true 1

#define N 5

void print(int board[][N])
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			printf(" %d ", board[i][j]);
		printf("n");
	}
}

bool is_safe(int board[][N], int row, int col)
{
	int i, j;

	for (i = 0; i < col; i++)
		if (board[row][i])
			return false;

	for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
		if (board[i][j])
			return false;

	for (i = row, j = col; j >= 0 && i < N; i++, j--)
		if (board[i][j])
			return false;

	return true;
}

bool solve_nq(int board[][N], int col)
{
	if (col >= N) return true;

	for (int i = 0; i < N; i++) {
		if (is_safe(board, i, col)) {
			board[i][col] = 1;

			if (solve_nq(board, col + 1))
				return true;

			board[i][col] = 0;
		}
	}

	return false;
}

int main()
{
	int board[N][N];

	memset(board, 0, sizeof(board));

	if (solve_nq(board, 0)) {
		print(board);
	} else {
		printf("Solution does not exist");
	}

	return 0;
}