Puzzles/Alphabetoku.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Alphabetoku(字母独)\n",
    "\n",
    "> 规则：\n",
    "\n",
    "- 标准数独规则的推广：每行、每列、每个宫内的字母不重复。\n",
    "- 字母序号从A编号到Y，一共25个字母。\n",
    "\n",
    "----\n",
    "\n",
    "English Version:\n",
    "\n",
    "- Standard Sudoku Rules Applied (Extension, of course).\n",
    "- Size 25 * 25 (digits from $A$ to $Y$ )\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24 7 25 2 4 21 10 14 3 8 1 12 9 23 19 5 20 17 11 22 6 18 15 16 13 \n",
      "10 21 5 16 19 7 25 17 6 11 15 8 20 24 14 13 1 2 18 23 3 4 9 22 12 \n",
      "17 11 14 9 22 24 23 20 1 19 7 10 3 13 18 6 12 15 16 4 8 25 21 5 2 \n",
      "18 23 15 3 20 12 9 16 13 5 2 4 11 22 6 24 8 21 10 25 1 7 14 19 17 \n",
      "13 1 6 8 12 18 2 22 4 15 5 25 17 21 16 9 19 3 7 14 10 11 23 24 20 \n",
      "20 19 4 7 3 16 12 15 17 10 11 2 14 6 22 1 23 18 13 24 5 21 8 9 25 \n",
      "5 13 1 21 17 3 7 24 23 14 25 16 8 18 9 10 15 6 2 19 4 20 12 11 22 \n",
      "16 2 23 14 6 19 8 4 22 13 12 17 10 7 21 11 25 20 5 9 24 15 18 3 1 \n",
      "22 9 12 25 18 11 21 1 5 2 13 20 15 4 24 14 16 8 3 17 7 19 6 10 23 \n",
      "11 8 24 15 10 9 20 18 25 6 19 3 23 1 5 7 22 12 4 21 2 14 17 13 16 \n",
      "19 22 18 20 16 14 17 6 7 3 10 11 12 8 15 23 24 5 25 2 9 13 1 4 21 \n",
      "4 3 7 1 9 13 15 23 20 16 21 24 19 14 25 12 10 11 8 6 17 22 5 2 18 \n",
      "21 5 10 12 2 8 22 9 19 24 18 13 16 3 20 4 17 7 1 15 11 23 25 6 14 \n",
      "23 17 13 24 25 1 4 11 10 21 9 6 2 5 7 20 18 14 22 16 15 12 19 8 3 \n",
      "15 14 11 6 8 25 5 2 18 12 22 23 1 17 4 19 21 13 9 3 16 24 20 7 10 \n",
      "8 20 9 13 7 22 11 3 16 23 17 14 24 19 1 21 4 25 6 12 18 10 2 15 5 \n",
      "2 4 19 23 24 5 18 10 12 25 8 21 13 11 3 17 7 9 15 1 14 16 22 20 6 \n",
      "12 18 21 10 1 6 24 8 15 4 20 9 5 25 2 22 11 16 14 13 19 17 3 23 7 \n",
      "14 6 3 17 11 20 13 7 21 9 16 18 22 15 23 2 5 10 19 8 12 1 24 25 4 \n",
      "25 16 22 5 15 17 14 19 2 1 4 7 6 10 12 18 3 24 23 20 13 9 11 21 8 \n",
      "6 15 16 11 21 2 19 25 14 18 24 1 4 12 8 3 13 23 20 7 22 5 10 17 9 \n",
      "9 25 17 18 5 23 1 13 8 22 6 15 7 20 11 16 2 19 12 10 21 3 4 14 24 \n",
      "1 24 2 19 13 15 6 21 9 20 3 22 18 16 10 25 14 4 17 5 23 8 7 12 11 \n",
      "7 10 8 22 23 4 3 12 24 17 14 5 25 2 13 15 9 1 21 11 20 6 16 18 19 \n",
      "3 12 20 4 14 10 16 5 11 7 23 19 21 9 17 8 6 22 24 18 25 2 13 1 15 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.032988\n"
     ]
    }
   ],
   "source": [
    "from __future__ import print_function\n",
    "from ortools.sat.python import cp_model as cp\n",
    "\n",
    "str2Int = {\n",
    "    \"A\" : 1,\n",
    "    \"B\" : 2,\n",
    "    \"C\" : 3,\n",
    "    \"D\" : 4,\n",
    "    \"E\" : 5,\n",
    "    \"F\" : 6,\n",
    "    \"G\" : 7,\n",
    "    \"H\" : 8,\n",
    "    \"I\" : 9,\n",
    "    \"J\": 10,\n",
    "    \"K\": 11,\n",
    "    \"L\": 12,\n",
    "    \"M\": 13,\n",
    "    \"N\": 14,\n",
    "    \"O\": 15,\n",
    "    \"P\": 16,\n",
    "    \"Q\": 17,\n",
    "    \"R\": 18,\n",
    "    \"S\": 19,\n",
    "    \"T\": 20,\n",
    "    \"U\": 21,\n",
    "    \"V\": 22,\n",
    "    \"W\": 23,\n",
    "    \"X\": 24,\n",
    "    \"Y\": 25,\n",
    "}\n",
    "\n",
    "def main_25by25(grid, grid_size):\n",
    "\n",
    "    model = cp.CpModel()\n",
    "    n = grid_size\n",
    "    x = {}\n",
    "    for i in range(grid_size):\n",
    "        for j in range(grid_size):\n",
    "            if grid[i * grid_size  + j] != \"0\":\n",
    "                x[i, j] = str2Int[grid[i * grid_size + j]]\n",
    "                # 这里规定：初始已经给了的数字不变\n",
    "            else:\n",
    "                x[i, j] = model.NewIntVar(1, grid_size, 'x[{},{}]'.format(i,j) ) \n",
    "                # 这里规定：余下的数字从1到9\n",
    "    \n",
    "    # ======= 下面是约束 ==========\n",
    "    # 行和列必须不重复\n",
    "    for i in range(n):\n",
    "        row = [x[i, j] for j in range(n)]\n",
    "        model.AddAllDifferent(row)\n",
    "        col = [x[j, i] for j in range(n)]\n",
    "        model.AddAllDifferent(col)\n",
    "\n",
    "    # 25 * 25 的宫内数字不能重复\n",
    "    for i in range(5):\n",
    "        for j in range(5):\n",
    "            cell = [\n",
    "                x[r, c]\n",
    "                for r in range(i * 5, i * 5 + 5)\n",
    "                for c in range(j * 5, j * 5 + 5)\n",
    "            ]\n",
    "            model.AddAllDifferent(cell)\n",
    "\n",
    "    solver = cp.CpSolver() \n",
    "    status = solver.Solve(model)\n",
    "\n",
    "    if status == cp.OPTIMAL:\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                print(solver.Value(x[i, j]), end=\" \")\n",
    "            print()\n",
    "        print()\n",
    "\n",
    "        print(\"NumConflicts:\", solver.NumConflicts())\n",
    "        print(\"NumBranches:\", solver.NumBranches())\n",
    "        print(\"WallTime:\", solver.WallTime())\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    grid = \"0G0B0UJ00H00000E00KVFR0PM0UEPSG0Q00O00000000W00I000000VXWTA00JCMR000PD0Y00B0WO00000ME0DK00X00J0AGNSQ0AFHL0B0DOEY00PI0CGN00000T000CP0OQ00000V0WRM0E0HI0E00UQ0GXWNY000000FB00T0K0000N000D00LQJ0UK0T0I0OR00VI00R00AEBMTOD0N000Q0S0J0K0XO0I0R0FS0000GV00UBN0MPS00TPNQ000J0LHOWX0Y0000D0DCG0000W0000SN000K0FQVE0000JLBH0000R0P0T0000OKWY0000MXYA0K000FB0000N0000SHC0N0000E0RLVWA0D000ICPX00JHT0MGV00PW0000AU0Y0L0JB0E0D0W0E000Y0UMKCQGI00N00TF00UJ0F0H0DT0EYB00P000Q0000F0Q00MG000000WBEJS0LA00D0PV0O0NSB0D00000CX0TM000H00000BSY0RX00LHCM0T0VEJQ0IYQRE0A00V00GT0PB00000DN0A00S0OF000CVRP00NDQEW000000H00D00000000M00A0KTFPR0CL0DNJP00G00000H00XR0B0A0\"\n",
    "    main_25by25(grid, 25)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Alphabetic Sudoku](../assets/figures/Board.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "py310",
   "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}