N 皇后问题 - 回溯算法求解

\u003c!-- 这是 N 皇后问题的解决方案，采用回溯算法实现 --\u003e\n\u003c!-- 首先定义棋盘大小和皇后位置数组 --\u003e\n#include \u003ciostream\u003e\nusing namespace std;\n\nconst int MAXN = 10;\n\nint n;\nint a[MAXN]; // 存放皇后的列号\n\n\u003c!-- 定义 check 函数，用于判断当前位置是否可以放置皇后 --\u003e\nbool check(int row, int col) {\n for (int i = 0; i \u003c row; i++) {\n // 检查是否和之前的皇后在同一列或者在同一对角线\n if (a[i] == col || abs(row - i) == abs(col - a[i])) {\n return false;\n }\n }\n return true;\n}\n\u003c!-- 定义 dfs 函数，使用回溯算法搜索所有可能的方案 --\u003e\nvoid dfs(int row) {\n if (row == n) {\n // 找到一个解\n for (int i = 0; i \u003c n; i++) {\n cout \u003c setw(5) \u003c a[i];\n }\n cout \u003c endl;\n return;\n }\n for (int col = 0; col \u003c n; col++) {\n if (check(row, col)) {\n a[row] = col; // 在第 row 行的 col 列放置皇后\n dfs(row + 1);\n }\n }\n}\n\u003c!-- 主函数，输入棋盘大小并调用 dfs 函数进行搜索 --\u003e\nint main() {\n cin >> n;\n dfs(0);\n return 0;\n}\n