AI算法与系统（1）：八皇后问题

实验背景

逻辑编程是一种编程典范，它设置答案须匹配的规则来解决问题，而非设置步骤来解决问题。过程是“事实+規则=结果”。人工智能的发展与逻辑编程的发展是一个相辅相成的过程，早期的人工智能以规则和逻辑推理作为主要研究方向，这在逻辑编程的发展中发挥了重要的影响，另外更好更快的逻辑编程也推动了人工智能的发展，例如专家系统、知识图谱和自动定理证明。Python是一种解释型、面向对象、动态数据类型的高级程序设计语言。在数据驱动学习时代，Python的崛起已经是一个不争的事实，并且成为人工智能算法的第一语言。在本次实验中，我们学习将Python应用于逻辑编程，并尝试自主撰写逻辑規则解决八皇后问题。

实验内容

如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

实验要求

1. 基本掌握逻辑编程的思想，了解逻辑编程与命令式编程的区别
2. 能够依据给定的事实以及规则编写代码，解决逻辑约束问题（CLP）

LeetCode 51. N皇后

Python题解

class Solution:
    def __init__(self):
        self.res = []

    def isValid(self, row, col, board, n):
        # Check current column
        for i in range(row):
            if board[i][col] == 'Q':
                return False

        # Check diag (init_row = row - 1; downward)
        for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
            if board[i][j] == 'Q':
                return False

        # Check counter-diag (init_row = row - 1; upward)
        for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
            if board[i][j] == 'Q':
                return False

        return True

    def dfs(self, board, n, row):
        if row == n:
            self.res.append([''.join(row) for row in board])
            return

        for i in range(n):
            if self.isValid(row, i, board, n):
                board[row][i] = 'Q'
                self.dfs(board, n, row + 1)
                board[row][i] = '.'

    def solveNQueens(self, n):
        board = [['.' for _ in range(n)] for _ in range(n)]
        self.dfs(board, n, 0)
        return self.res

def main():
    n = 8
    solution = Solution()
    boards = solution.solveNQueens(n)

    for board in boards:
        for line in board:
            print(line)
        print()

if __name__ == "__main__":
    main()

C++题解

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string>> res;

    bool isValid(int row, int col, vector<string> &board, int n) {
        // Check current column
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }

        // Check diag (init_row = row - 1; downward)
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }

        // Check counter-diag (init_row = row - 1; upward)
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }

        return true;
    }

    void dfs(vector<string> &board, int n, int row) {
        if (row == n) {
            res.push_back(board);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (isValid(row, i, board, n)) {
                board[row][i] = 'Q';
                dfs(board, n, row + 1);
                board[row][i] = '.';
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        dfs(board, n, 0);
        return res;
    }
};

int main() {
    int n = 8;

    Solution solution;
    vector<vector<string>> boards = solution.solveNQueens(n);

    for (auto &board : boards) {
        for (auto &line : board) {
            printf("%s\n", line.c_str());
        }
    }

    return 0;
}