八皇后问题_0.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "\"\"\" 我的错误代码 \"\"\"\n",
    "class Solution:\n",
    "    def backtrack(self, depth, board: List[str]):\n",
    "        if depth == self.size:\n",
    "            self.ret.append(board)\n",
    "            return\n",
    "\n",
    "        if depth == 0:\n",
    "            first_line = \"\"\n",
    "            for i in range(self.size):\n",
    "                for j in range(self.size):\n",
    "                    if i != j:\n",
    "                        first_line += '.'\n",
    "                    else:\n",
    "                        first_line += 'Q'\n",
    "                depth += 1\n",
    "                board.append(first_line)\n",
    "                self.backtrack(depth, board)\n",
    "                board = board[:-1]\n",
    "                depth -= 1\n",
    "        else:\n",
    "            opt = [True] * self.size\n",
    "            for i in range(depth):\n",
    "                line = board[i]\n",
    "                #for j in range(len(line)):\n",
    "                for j in range(self.size):\n",
    "                    if line[j] == 'Q':\n",
    "                        opt[j] = False\n",
    "                        opt[(j + (depth - i)) % self.size] = False\n",
    "                        opt[(j - (depth - i) + self.size) % self.size] = False\n",
    "            \n",
    "            for i in range(len(opt)):\n",
    "                if opt[i]:\n",
    "                    new_line = ''.join(['Q' if i == j else '.' for j in range(self.size)])\n",
    "                    \n",
    "                    depth += 1\n",
    "                    board.append(new_line)\n",
    "                    self.backtrack(depth, board)\n",
    "                    board = board[:-1]\n",
    "                    depth -= 1\n",
    "\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        self.ret = []\n",
    "        self.size = n\n",
    "        \n",
    "        self.backtrack(0, [])\n",
    "\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" GPT基于我的代码所给出的正确代码 \"\"\"\n",
    "class Solution:\n",
    "    def backtrack(self, depth, board):\n",
    "        if depth == self.size:  # 如果已经放置完所有行的皇后，记录解法\n",
    "            self.ret.append(board[:])\n",
    "            return\n",
    "\n",
    "        # 构建可放置皇后的位置的选项集\n",
    "        opt = [True] * self.size  # 标记这一行所有列的可用性\n",
    "        for i in range(depth):\n",
    "            line = board[i]\n",
    "            # 找到之前行中的皇后，更新当前行的列和对角线的可用性\n",
    "            for j in range(self.size):\n",
    "                if line[j] == 'Q':\n",
    "                    opt[j] = False  # 列冲突\n",
    "                    if j + (depth - i) < self.size:\n",
    "                        opt[j + (depth - i)] = False  # 主对角线冲突\n",
    "                    if j - (depth - i) >= 0:\n",
    "                        opt[j - (depth - i)] = False  # 次对角线冲突\n",
    "\n",
    "        # 遍历每个可行的列位置\n",
    "        for i in range(len(opt)):\n",
    "            if opt[i]:\n",
    "                new_line = ''.join(['Q' if i == j else '.' for j in range(self.size)])  # 构建新行\n",
    "\n",
    "                depth += 1\n",
    "                board.append(new_line)  # 将新行添加到棋盘\n",
    "                self.backtrack(depth, board)  # 继续递归处理下一行\n",
    "                board.pop()  # 回溯，移除当前行\n",
    "                depth -= 1\n",
    "\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        self.ret = []\n",
    "        self.size = n\n",
    "\n",
    "        # 开始回溯\n",
    "        self.backtrack(0, [])\n",
    "\n",
    "        return self.ret"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}