第九章代码.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第九章代码\n",
    "\n",
    "## 算法 9.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def queen_puzzle_bruteforce(A, r):\n",
    "    if r == 8:\n",
    "        col = [0 for i in range(8)]\n",
    "        vis1 = [0 for i in range(15)]\n",
    "        vis2 = [0 for i in range(15)]\n",
    "        flg = True\n",
    "        for i in range(8):\n",
    "            if col[A[i]] or vis1[i + A[i]] or vis2[i - A[i] + 7]:\n",
    "                flg = False\n",
    "                break\n",
    "            col[A[i]] = vis1[i + A[i]] = vis2[i - A[i] + 7] = True\n",
    "        if flg:\n",
    "            print(A)\n",
    "        return\n",
    "    \n",
    "    for c in range(8):\n",
    "        A[r] = c\n",
    "        queen_puzzle_bruteforce(A, r + 1)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    A = [0 for i in range(8)]\n",
    "    queen_puzzle_bruteforce(A, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法 9.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "col = [0 for i in range(8)]\n",
    "vis1 = [0 for i in range(15)]\n",
    "vis2 = [0 for i in range(15)]\n",
    "def queen_puzzle_backtracking(A, r):\n",
    "    if r == 8:\n",
    "        print(A)\n",
    "        return\n",
    "    \n",
    "    for c in range(8):\n",
    "        if not (col[c] or vis1[r + c] or vis2[r - c + 7]):\n",
    "            col[c] = vis1[r + c] = vis2[r - c + 7] = True\n",
    "            A[r] = c\n",
    "            queen_puzzle_backtracking(A, r + 1)\n",
    "            col[c] = vis1[r + c] = vis2[r - c + 7] = False\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    A = [0 for i in range(8)]\n",
    "    queen_puzzle_backtracking(A, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法 9.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def xy2id(x : int, y : int):\n",
    "    return x * 8 + y\n",
    "\n",
    "def id2xy(id : int):\n",
    "    return [id // 8, id % 8]\n",
    "\n",
    "def valid(x : int, y : int):\n",
    "    return x > -1 and x < 9 and y > -1 and y < 9\n",
    "\n",
    "dx = [1, 1, -1, -1, 2, 2, -2, -2]\n",
    "dy = [2, -2, 2, -2, 1, -1, 1, -1]\n",
    "def neighbor(id : int):\n",
    "    x, y = id2xy(id)\n",
    "    ret = []\n",
    "    for i in range(8):\n",
    "        if(valid(x + dx[i], y + dy[i])):\n",
    "            ret.append(xy2id(x + dx[i], y + dy[i]))\n",
    "    return ret\n",
    "\n",
    "def knight_tour_bruteforce(A, r):\n",
    "    if r == 64:\n",
    "        flg = True\n",
    "        for i in range(2, 64):\n",
    "            if not A[i] in neighbor(A[i - 1]):\n",
    "                flg = False\n",
    "                break\n",
    "        return 1 if flg else 0\n",
    "    \n",
    "    ans = 0\n",
    "    for id in range(64):\n",
    "        flg = True\n",
    "        for i in range(r):\n",
    "            if A[i] == id:\n",
    "                flg = False\n",
    "                break\n",
    "        if flg:\n",
    "            A[r] = id\n",
    "            ans += knight_tour_bruteforce(A, r + 1)\n",
    "            A[r] = -1\n",
    "    return ans\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    x, y = map(int, input().strip().split())\n",
    "    A = [-1 for i in range(64)]\n",
    "    A[0] = xy2id(x, y)\n",
    "    ans = knight_tour_bruteforce(A, 1)\n",
    "    print(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法 9.4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valid(x : int, y : int):\n",
    "    return x >= 0 and x <= 8 and y >= 0 and y <= 8\n",
    "\n",
    "dx = [1, 1, -1, -1, 2, 2, -2, -2]\n",
    "dy = [2, -2, 2, -2, 1, -1, 1, -1]\n",
    "def neighbor(x : int, y : int):\n",
    "    ret = []\n",
    "    for i in range(8):\n",
    "        if(valid(x + dx[i], y + dy[i])):\n",
    "            ret.append((x + dx[i], y + dy[i]))\n",
    "    return ret\n",
    "\n",
    "vis = [[False for i in range(65)] for j in range(65)]\n",
    "def knight_tour_backtracking(A):\n",
    "    if len(A) == 64:\n",
    "        return 1\n",
    "    ans = 0\n",
    "    for nxtx, nxty in neighbor(A[-1][0], A[-1][1]):\n",
    "        if not vis[nxtx][nxty]:\n",
    "            vis[nxtx][nxty] = True\n",
    "            A.append((nxtx, nxty))\n",
    "            ans += knight_tour_backtracking(A)\n",
    "            A.pop()\n",
    "            vis[nxtx][nxty] = False\n",
    "    return ans\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    x, y = map(int, input().strip().split())\n",
    "    A = [(x, y)]\n",
    "    ans = knight_tour_backtracking(A)\n",
    "    print(ans)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}