app.ipynb · Yogurt_cry/local-excel_sudoku-decoder_20210402

6月21日 Gitee Talk | 模力方舟 AI 应用沙龙 · 青岛站开放报名，来聊聊 AI+ 应用的多场景落地实践~

加入 Gitee

与超过 1200万开发者一起发现、参与优秀开源项目，私有仓库也完全免费：）

文件

该仓库未声明开源许可证文件（LICENSE），使用请关注具体项目描述及其代码上游依赖。

克隆/下载

app.ipynb 15.48 KB

{
 "metadata": {
  "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.8.3"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python383jvsc74a57bd0b3ba2566441a7c06988d0923437866b63cedc61552a5af99d1f4fb67d367b25f",
   "display_name": "Python 3.8.3 64-bit ('base': conda)"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "解题开始\n65 解题成功\n0:00:00.105684\n[[1 2 3 4 5 6 7 8 9]\n [4 5 6 7 8 9 1 2 3]\n [7 8 9 1 2 3 4 5 6]\n [2 3 1 6 7 4 8 9 5]\n [8 7 5 9 1 2 3 6 4]\n [6 9 4 5 3 8 2 1 7]\n [3 1 7 2 6 5 9 4 8]\n [5 4 2 8 9 7 6 3 1]\n [9 6 8 3 4 1 5 7 2]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from datetime import datetime\n",
    "from collections import Counter\n",
    "\n",
    "class Soduku:\n",
    "    # 初始化\n",
    "    def Initialize(self, data: list):\n",
    "        # 初始数据\n",
    "        dataArray = np.array(data)\n",
    "        return dataArray\n",
    "    \n",
    "    # 备选数字\n",
    "    def BackupNumber(self, dataArray):\n",
    "        # 初始备选数据\n",
    "        backupItem = ''.join([str(x) for x in range(1, 10)])\n",
    "        backupRow = [backupItem for x in range(9)]\n",
    "        backupShape = [backupRow for x in range(9)]\n",
    "        backupArray = np.array(backupShape)\n",
    "\n",
    "        # 去除已填写数字的备选\n",
    "        backupArray = np.where(dataArray == 0, backupArray, '')\n",
    "        \n",
    "        # 计算备选数字\n",
    "        # 行备选\n",
    "        for rowIndex in range(9):\n",
    "            dataItem = dataArray[rowIndex]\n",
    "            dataItem = dataItem.astype(np.str)\n",
    "            usedDataList = list(''.join(list(dataItem)).replace('0', ''))\n",
    "\n",
    "            for item in usedDataList:\n",
    "                for colIndex in range(9):\n",
    "                    backupItem = backupArray[rowIndex, colIndex]\n",
    "                    backupArray[rowIndex, colIndex] = backupItem.replace(item, '')\n",
    "        \n",
    "        # 列备选\n",
    "        for colIndex in range(9):\n",
    "            dataItem = dataArray[:,colIndex]\n",
    "            dataItem = dataItem.astype(np.str)\n",
    "            usedDataList = list(''.join(list(dataItem)).replace('0', ''))\n",
    "\n",
    "            for item in usedDataList:\n",
    "                for rowIndex in range(9):\n",
    "                    backupItem = backupArray[rowIndex, colIndex]\n",
    "                    backupArray[rowIndex, colIndex] = backupItem.replace(item, '')\n",
    "\n",
    "        # 九宫格备选\n",
    "        for rowIndex in range(0, 9, 3):\n",
    "            for colIndex in range(0, 9, 3):\n",
    "                dataItem = dataArray[rowIndex : rowIndex + 3, colIndex : colIndex + 3]\n",
    "                dataItem = dataItem.astype(np.str)\n",
    "                usedDataList = list(''.join(list([*dataItem.flat])).replace('0', ''))\n",
    "                \n",
    "                for item in usedDataList:\n",
    "                    for bkRowIndex in range(rowIndex, rowIndex + 3):\n",
    "                        for bkColIndex in range(colIndex, colIndex + 3):\n",
    "                            backupItem = backupArray[bkRowIndex, bkColIndex]\n",
    "                            backupArray[bkRowIndex, bkColIndex] = backupItem.replace(item, '')\n",
    "    \n",
    "        # 选出备选数字中唯一结果\n",
    "        # 行\n",
    "        for rowIndex in range(9):\n",
    "            bkItem = backupArray[rowIndex]\n",
    "            bkData = ''.join(list(bkItem))\n",
    "\n",
    "            numberFrequency = sorted(dict(Counter(bkData)).items(), key = lambda x:x[1])\n",
    "            onlyNumberList = []\n",
    "            for item in numberFrequency:\n",
    "                number, counts = item\n",
    "                if counts == 1:\n",
    "                    onlyNumberList.append(number)\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            for item in onlyNumberList:\n",
    "                for colIndex in range(9):\n",
    "                    backupItem = backupArray[rowIndex, colIndex]\n",
    "                    if len(backupItem) > 1:\n",
    "                        if item in backupItem:\n",
    "                            backupArray[rowIndex, colIndex] = item\n",
    "        \n",
    "        # 列\n",
    "        for colIndex in range(9):\n",
    "            bkItem = backupArray[:,colIndex]\n",
    "            bkData = ''.join(list(bkItem))\n",
    "\n",
    "            numberFrequency = sorted(dict(Counter(bkData)).items(), key = lambda x:x[1])\n",
    "            onlyNumberList = []\n",
    "            for item in numberFrequency:\n",
    "                number, counts = item\n",
    "                if counts == 1:\n",
    "                    onlyNumberList.append(number)\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            for item in onlyNumberList:\n",
    "                for rowIndex in range(9):\n",
    "                    backupItem = backupArray[rowIndex, colIndex]\n",
    "                    if len(backupItem) > 1:\n",
    "                        if item in backupItem:\n",
    "                            backupArray[rowIndex, colIndex] = item\n",
    "\n",
    "        # 九宫格\n",
    "        for rowIndex in range(0, 9, 3):\n",
    "            for colIndex in range(0, 9, 3):\n",
    "                bkItem = backupArray[rowIndex : rowIndex + 3, colIndex : colIndex + 3]\n",
    "                bkData = ''.join(list([*bkItem.flat]))\n",
    "\n",
    "                numberFrequency = sorted(dict(Counter(bkData)).items(), key = lambda x:x[1])\n",
    "                onlyNumberList = []\n",
    "                for item in numberFrequency:\n",
    "                    number, counts = item\n",
    "                    if counts == 1:\n",
    "                        onlyNumberList.append(number)\n",
    "                    else:\n",
    "                        break\n",
    "                \n",
    "                for item in onlyNumberList:\n",
    "                    for bkRowIndex in range(rowIndex, rowIndex + 3):\n",
    "                        for bkColIndex in range(colIndex, colIndex + 3):\n",
    "                            backupItem = backupArray[bkRowIndex, bkColIndex]\n",
    "                            if len(backupItem) > 1:\n",
    "                                if item in backupItem:\n",
    "                                    backupArray[bkRowIndex, bkColIndex] = item\n",
    "\n",
    "        # 挑出第一个备选最少的结果\n",
    "        backupLeast = {}\n",
    "        for rowIndex in range(9):\n",
    "            for colIndex in range(9):\n",
    "                item = backupArray[rowIndex, colIndex]\n",
    "                if backupLeast == {}:\n",
    "                    backupLeast = {\n",
    "                        'rowIndex': rowIndex,\n",
    "                        'colIndex': colIndex,\n",
    "                        'value': item\n",
    "                    }\n",
    "                else:\n",
    "                    if item != '':\n",
    "                        if backupLeast['value'] == '':\n",
    "                            backupLeast = {\n",
    "                                'rowIndex': rowIndex,\n",
    "                                'colIndex': colIndex,\n",
    "                                'value': item\n",
    "                            }\n",
    "                        if len(backupLeast['value']) > len(item):\n",
    "                            backupLeast = {\n",
    "                                'rowIndex': rowIndex,\n",
    "                                'colIndex': colIndex,\n",
    "                                'value': item\n",
    "                            }\n",
    "\n",
    "        return backupLeast, backupArray\n",
    "    \n",
    "    # 检验结果是否正确, 主要检验指定区域内是否存在重复数据\n",
    "    def NumberCheck(self, dataArray):\n",
    "        # 行检验\n",
    "        for rowIndex in range(9):\n",
    "            dataItem = dataArray[rowIndex]\n",
    "            dataItem = dataItem.astype(np.str)\n",
    "            usedDataList = list(''.join(list(dataItem)).replace('0', ''))\n",
    "\n",
    "            if len(usedDataList) > 0:\n",
    "                if Counter(usedDataList).most_common()[0][1] > 1:\n",
    "                    return False\n",
    "        \n",
    "        # 列检验\n",
    "        for colIndex in range(9):\n",
    "            dataItem = dataArray[:,colIndex]\n",
    "            dataItem = dataItem.astype(np.str)\n",
    "            usedDataList = list(''.join(list(dataItem)).replace('0', ''))\n",
    "\n",
    "            if len(usedDataList) > 0:\n",
    "                if Counter(usedDataList).most_common()[0][1] > 1:\n",
    "                    return False\n",
    "        \n",
    "        # 九宫格检验\n",
    "        for rowIndex in range(0, 9, 3):\n",
    "            for colIndex in range(0, 9, 3):\n",
    "                dataItem = dataArray[rowIndex : rowIndex + 3, colIndex : colIndex + 3]\n",
    "                dataItem = dataItem.astype(np.str)\n",
    "                usedDataList = list(''.join(list([*dataItem.flat])).replace('0', ''))\n",
    "\n",
    "                if len(usedDataList) > 0:\n",
    "                    if Counter(usedDataList).most_common()[0][1] > 1:\n",
    "                        return False\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    # 根据唯一备选结果填写数字\n",
    "    def WriteNumber(self, dataArray, backupArray):\n",
    "        onlyBackupArray = backupArray.copy()\n",
    "        onlyBackupArray = np.where(onlyBackupArray == '', 0, onlyBackupArray)\n",
    "        onlyBackupArray = onlyBackupArray.astype(np.int)\n",
    "        onlyBackupArray = np.where(onlyBackupArray <= 9, onlyBackupArray, 0)\n",
    "        dataArray = np.where(dataArray == 0, onlyBackupArray, dataArray)\n",
    "\n",
    "        dataCode = dataArray.astype(np.str)\n",
    "        dataCode = ''.join([*dataCode.flat])\n",
    "\n",
    "        return dataCode, dataArray\n",
    "    \n",
    "    # 填入测试数字\n",
    "    def TestWriteNumber(self, dataArray, backupLeast, parseHistoryDict, parseLocationList):\n",
    "        rowIndex = backupLeast['rowIndex']\n",
    "        colIndex = backupLeast['colIndex']\n",
    "        value = backupLeast['value']\n",
    "\n",
    "        numberLocation = '{}{}'.format(str(rowIndex), str(colIndex))\n",
    "\n",
    "        if numberLocation not in parseLocationList:\n",
    "            parseLocationList.append(numberLocation)\n",
    "            parseHistoryDict[numberLocation] = {\n",
    "                'rowIndex': rowIndex,\n",
    "                'colIndex': colIndex,\n",
    "                'value': value,\n",
    "                'dataArray': dataArray\n",
    "            }\n",
    "        \n",
    "        if len(parseLocationList) > 0:\n",
    "            numberLocation = parseLocationList[-1]\n",
    "            testObj = parseHistoryDict[numberLocation]\n",
    "            testRowIndex = testObj['rowIndex']\n",
    "            testColIndex = testObj['colIndex']\n",
    "            testValue = testObj['value']\n",
    "            testDataArray = testObj['dataArray']\n",
    "\n",
    "            if testObj['value'] == '':\n",
    "                parseLocationList = parseLocationList[:-1]\n",
    "                parseHistoryDict.pop(numberLocation)\n",
    "            else:\n",
    "                testNumber = testValue[0]\n",
    "                testObj['value'] = testValue.replace(testNumber, '')\n",
    "\n",
    "                dataArray = testDataArray.copy()\n",
    "                dataArray[testRowIndex, testColIndex] = testNumber\n",
    "\n",
    "                if testObj['value'] == '':\n",
    "                    parseLocationList = parseLocationList[:-1]\n",
    "                    parseHistoryDict.pop(numberLocation)\n",
    "\n",
    "        return dataArray, parseHistoryDict, parseLocationList\n",
    "\n",
    "    # 还原执行历史\n",
    "    def ResetDataArray(self, dataArray, parseHistoryDict, parseLocationList):\n",
    "        if len(parseLocationList) > 0:\n",
    "            numberLocation = parseLocationList[-1]\n",
    "            testObj = parseHistoryDict[numberLocation]\n",
    "            testDataArray = testObj['dataArray']\n",
    "\n",
    "            dataArray = testDataArray.copy()\n",
    "        \n",
    "            return dataArray, parseHistoryDict, parseLocationList\n",
    "\n",
    "# 执行代码\n",
    "# 世界上最难的数独\n",
    "# data = [\n",
    "#     [ 8, 0, 0, 0, 0, 0, 0, 0, 0 ],\n",
    "#     [ 0, 0, 3, 6, 0, 0, 0, 0, 0 ],\n",
    "#     [ 0, 7, 0, 0, 9, 0, 2, 0, 0 ],\n",
    "#     [ 0, 5, 0, 0, 0, 7, 0, 0, 0 ],\n",
    "#     [ 0, 0, 0, 0, 4, 5, 7, 0, 0 ],\n",
    "#     [ 0, 0, 0, 1, 0, 0, 0, 3, 0 ],\n",
    "#     [ 0, 0, 1, 0, 0, 0, 0, 6, 8 ],\n",
    "#     [ 0, 0, 8, 5, 0, 0, 0, 1, 0 ],\n",
    "#     [ 0, 9, 0, 0, 0, 0, 4, 0, 0 ],\n",
    "# ]\n",
    "\n",
    "data = [\n",
    "    [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n",
    "    [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n",
    "    [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n",
    "    [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n",
    "    [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n",
    "    [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n",
    "    [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n",
    "    [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n",
    "    [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n",
    "]\n",
    "\n",
    "sodukuObj = Soduku()\n",
    "\n",
    "print('解题开始')\n",
    "startTime = datetime.now()\n",
    "\n",
    "# 初始化\n",
    "dataArray = sodukuObj.Initialize(data)\n",
    "parseHistoryDict = {}\n",
    "parseLocationList = []\n",
    "\n",
    "stepIndex = 0\n",
    "while stepIndex < 1000:\n",
    "    # 计算备选\n",
    "    backupLeast, backupArray = sodukuObj.BackupNumber(dataArray)\n",
    "    # 根据唯一结果填写数字\n",
    "    dataCode, dataArray = sodukuObj.WriteNumber(dataArray, backupArray)\n",
    "\n",
    "    if sodukuObj.NumberCheck(dataArray) == False:\n",
    "        # print(stepIndex, '解题失败')\n",
    "        dataArray, parseHistoryDict, parseLocationList = sodukuObj.ResetDataArray(\n",
    "            dataArray = dataArray,\n",
    "            parseHistoryDict = parseHistoryDict,\n",
    "            parseLocationList = parseLocationList\n",
    "        )\n",
    "    else:\n",
    "        if len(dataCode.replace('0', '')) == 81:\n",
    "            print(stepIndex, '解题成功')\n",
    "            break\n",
    "        else:\n",
    "            dataArray, parseHistoryDict, parseLocationList = sodukuObj.TestWriteNumber(\n",
    "                dataArray = dataArray,\n",
    "                backupLeast = backupLeast,\n",
    "                parseHistoryDict = parseHistoryDict,\n",
    "                parseLocationList = parseLocationList\n",
    "            )\n",
    "\n",
    "    stepIndex += 1\n",
    "\n",
    "endTime = datetime.now()\n",
    "\n",
    "print(endTime - startTime)\n",
    "print(dataArray)"
   ]
  }
 ]
}

一键复制编辑原始数据按行查看历史

提交于 2021-04-25 13:54 +08:00 . 2021-04-25 13:54 完成所有代码开发

马建仓 AI 助手

尝试更多

代码解读

代码找茬

代码优化

https://gitee.com/Yogurt_cry/local-excel_sudoku-decoder_20210402.git

git@gitee.com:Yogurt_cry/local-excel_sudoku-decoder_20210402.git

Yogurt_cry

local-excel_sudoku-decoder_20210402

develop

Yogurt_cry/local-excel_sudoku-decoder_20210402

简介

发行版

贡献者

语言

近期动态

Yogurt_cry/local-excel_sudoku-decoder_20210402 .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

语言

近期动态

搜索帮助

Yogurt_cry/local-excel_sudoku-decoder_20210402