{"id":5307,"date":"2025-09-15T10:41:37","date_gmt":"2025-09-15T02:41:37","guid":{"rendered":"\/math\/?post_type=tkuisotope&p=5307"},"modified":"2025-09-26T09:34:52","modified_gmt":"2025-09-26T01:34:52","slug":"114-09-30-%e9%83%ad%e5%90%9b%e9%80%b8-%e5%8d%9a%e5%a3%ab%e4%b8%bb%e8%ac%9b%e5%9c%8b%e7%ab%8b%e8%87%ba%e7%81%a3%e5%b8%ab%e7%af%84%e5%a4%a7%e5%ad%b8%e6%95%b8%e5%ad%b8%e7%b3%bb-%e6%95%99%e6%8e%88","status":"publish","type":"tkuisotope","link":"\/math\/?tkuisotope=114-09-30-%e9%83%ad%e5%90%9b%e9%80%b8-%e5%8d%9a%e5%a3%ab%e4%b8%bb%e8%ac%9b%e5%9c%8b%e7%ab%8b%e8%87%ba%e7%81%a3%e5%b8%ab%e7%af%84%e5%a4%a7%e5%ad%b8%e6%95%b8%e5%ad%b8%e7%b3%bb-%e6%95%99%e6%8e%88","title":{"rendered":"114\/10\/14 \u90ed\u541b\u9038 \u00a0\u535a\u58eb\u4e3b\u8b1b(\u570b\u7acb\u81fa\u7063\u5e2b\u7bc4\u5927\u5b78\u6578\u5b78\u7cfb \u6559\u6388)"},"content":{"rendered":"\n

<\/p>\n\n\n\n

\u4e3b\u8b1b\u4eba\uff1a\u90ed\u541b\u9038 \u535a\u58eb(\u570b\u7acb\u81fa\u7063\u5e2b\u7bc4\u5927\u5b78\u6578\u5b78\u7cfb)<\/strong><\/p>\n\n\n\n

\u984c  \u76ee\uff1a\u795e\u9b54\u4e4b\u5854\u597d\u96e3Tower of Saviors is (Computationally) Hard<\/strong><\/p>\n\n\n\n

\u65e5\u00a0 \u671f\uff1a114\u5e7410\u670814\u65e5\uff08\u661f\u671f\u4e8c\uff09<\/p>\n\n\n\n

\u6642  \u9593\uff1a\u4e0b\u534814:00 ~ 15:00<\/strong><\/p>\n\n\n\n

\u5730  \u9ede\uff1a\u79d1\u5b78\u9928S433<\/strong><\/p>\n\n\n\n

\u6458\u8981<\/strong>Abstract:<\/strong><\/p>\n\n\n\n

Candy Crush Saga\u662f\u4e00\u6b3e\u975e\u5e38\u53d7\u6b61\u8fce\u7684\u904a\u6232\uff0c\u57282012\u5e74\u767c\u4f48\u5f8c\uff0c\u9694\u4e86\u4e09\u5e74\uff0c\u57282014\u5e74\u88ab\u8b49\u660e\u5c6c\u65bcNP-\u5b8c\u5099\u300215-\u62fc\u5716(\u6216\u7a31\u83ef\u5bb9\u9053)\u4e5f\u662f\u7d93\u5178\u7684\u6ed1\u584a\u904a\u6232\uff0c\u4e5f\u540c\u6a23\u88ab\u8b49\u660e\u70baNP-\u5b8c\u5099\u3002\u5c07\u9019\u5169\u6b3e\u904a\u6232\u7d50\u5408\uff0c\u5373\u8a95\u751f\u4e86\u9f8d\u65cf\u62fc\u5716\u9019\u6b3e\u57282014\u767c\u4f48\u7684\u904a\u6232\u3002\u5f8c\u4f86\u795e\u9b54\u4e4b\u5854\u7684\u8a95\u751f\uff0c\u628a\u6b64\u985e\u904a\u6232\u767c\u63da\u5149\u5927\u3002\u5728\u795e\u9b54\u4e4b\u5854\u4e2d\uff0c\u73a9\u5bb6\u6ed1\u52d5\u67d0\u4e00\u9846\u73e0\u5b50(\u6ed1\u584a)\uff0c\u6ed1\u52d5\u7684\u8ecc\u8de1\u6703\u5c07\u73e0\u5b50\u91cd\u65b0\u6392\u5217\uff0c\u96e2\u624b\u6642\uff0c\u6709\u5927\u65bc\u7b49\u65bc\u4e09\u500b\u73e0\u5b50\u76f8\u9023\u6210\u4e00\u7dda\u5c31\u6703\u50cfCandy Crush Saga\u4e00\u6a23\u6d88\u9664\uff0c\u5269\u4e0b\u7684\u73e0\u5b50\u6703\u4f9d\u91cd\u529b\u843d\u4e0b\u3002\u6b64\u8ad6\u6587\u4e2d\uff0c\u6539\u5584\u4e86\u904e\u53bb\u75282\/2\/4-SAT\u8b49\u660e\u83ef\u5bb9\u9053\u70baNP-\u56f0\u96e3\u7684\u65b9\u6cd5\uff0c\u4e26\u5229\u75281-in-3-positive SAT\u8b49\u660e\u4e86\u795e\u9b54\u4e4b\u5854\u70baNP-\u5b8c\u5099\u3002<\/p>\n\n\n\n

Candy Crush Saga is a popular game, released in 2012, and three years later, in 2014, it was proven to be NP-complete. The 15-puzzle is another classic sliding block game, which has also been shown to be NP-complete. By combining these two games, Puzzle & Dragons was released in 2014. Subsequently, the emergence of Tower of Saviors further popularized this genre. In Tower of Saviors, the player slides a particular orb (or block), and the trajectory of the slide rearranges the orbs. When the player releases the orb, if three or more orbs are aligned in a straight line, they disappear just like in Candy Crush Saga, and the remaining orbs fall. In this paper, we improve previous methods that used 2\/2\/4-SAT to prove the NP-hardness of the sliding puzzle, and instead utilize 1-in-3-positive SAT to prove that Tower of Saviors is NP-complete.<\/p>\n\n\n\n

\u5099  \u8a3b\uff1a\u672c\u696d\u52d9\u8207\u806f\u5408\u570b\u6c38\u7e8c\u767c\u5c55\u76ee\u6a19SDG4\u512a\u8cea\u6559\u80b2\u9023\u7d50<\/strong><\/p>\n\n\n\n

ESG+AI=\u221e  AI+SDGs=\u221e<\/strong>
<\/p>\n","protected":false},"template":"","meta":[],"categories":[9],"tags":[],"featured_image_urls":{"full":"","thumbnail":"","medium":"","medium_large":"","large":"","1536x1536":"","2048x2048":""},"post_excerpt_stackable":"

\u4e3b\u8b1b\u4eba\uff1a\u90ed\u541b\u9038 \u535a\u58eb(\u570b\u7acb\u81fa\u7063\u5e2b\u7bc4\u5927\u5b78\u6578\u5b78\u7cfb) \u984c  \u76ee\uff1a\u795e\u9b54\u4e4b\u5854\u597d\u96e3Tower of Saviors is (Computationally) Hard \u65e5\u00a0 \u671f\uff1a114\u5e7410\u670814\u65e5\uff08\u661f\u671f\u4e8c\uff09 \u6642  \u9593\uff1a\u4e0b\u534814:00 ~ 15:00 \u5730  \u9ede\uff1a\u79d1\u5b78\u9928S433 \u6458\u8981Abstract: Candy Crush Saga\u662f\u4e00\u6b3e\u975e\u5e38\u53d7\u6b61\u8fce\u7684\u904a\u6232\uff0c\u57282012\u5e74\u767c\u4f48\u5f8c\uff0c\u9694\u4e86\u4e09\u5e74\uff0c\u57282014\u5e74\u88ab\u8b49\u660e\u5c6c\u65bcNP-\u5b8c\u5099\u300215-\u62fc\u5716(\u6216\u7a31\u83ef\u5bb9\u9053)\u4e5f\u662f\u7d93\u5178\u7684\u6ed1\u584a\u904a\u6232\uff0c\u4e5f\u540c\u6a23\u88ab\u8b49\u660e\u70baNP-\u5b8c\u5099\u3002\u5c07\u9019\u5169\u6b3e\u904a\u6232\u7d50\u5408\uff0c\u5373\u8a95\u751f\u4e86\u9f8d\u65cf\u62fc\u5716\u9019\u6b3e\u57282014\u767c\u4f48\u7684\u904a\u6232\u3002\u5f8c\u4f86\u795e\u9b54\u4e4b\u5854\u7684\u8a95\u751f\uff0c\u628a\u6b64\u985e\u904a\u6232\u767c\u63da\u5149\u5927\u3002\u5728\u795e\u9b54\u4e4b\u5854\u4e2d\uff0c\u73a9\u5bb6\u6ed1\u52d5\u67d0\u4e00\u9846\u73e0\u5b50(\u6ed1\u584a)\uff0c\u6ed1\u52d5\u7684\u8ecc\u8de1\u6703\u5c07\u73e0\u5b50\u91cd\u65b0\u6392\u5217\uff0c\u96e2\u624b\u6642\uff0c\u6709\u5927\u65bc\u7b49\u65bc\u4e09\u500b\u73e0\u5b50\u76f8\u9023\u6210\u4e00\u7dda\u5c31\u6703\u50cfCandy Crush Saga\u4e00\u6a23\u6d88\u9664\uff0c\u5269\u4e0b\u7684\u73e0\u5b50\u6703\u4f9d\u91cd\u529b\u843d\u4e0b\u3002\u6b64\u8ad6\u6587\u4e2d\uff0c\u6539\u5584\u4e86\u904e\u53bb\u75282\/2\/4-SAT\u8b49\u660e\u83ef\u5bb9\u9053\u70baNP-\u56f0\u96e3\u7684\u65b9\u6cd5\uff0c\u4e26\u5229\u75281-in-3-positive SAT\u8b49\u660e\u4e86\u795e\u9b54\u4e4b\u5854\u70baNP-\u5b8c\u5099\u3002 Candy Crush Saga is a popular game, released in 2012, and three years later, in 2014, it was proven to be NP-complete. The 15-puzzle is another classic sliding block game, which has also been shown to be NP-complete. By combining these two games, Puzzle & Dragons was released in 2014. Subsequently, the emergence of Tower of Saviors further popularized this genre. In Tower of Saviors, the player slides a particular orb (or block), and the trajectory…<\/p>\n","category_list":"News<\/a>","author_info":{"name":"","url":""},"comments_num":"0 comments","acf":[],"_links":{"self":[{"href":"\/math\/index.php?rest_route=\/wp\/v2\/tkuisotope\/5307"}],"collection":[{"href":"\/math\/index.php?rest_route=\/wp\/v2\/tkuisotope"}],"about":[{"href":"\/math\/index.php?rest_route=\/wp\/v2\/types\/tkuisotope"}],"wp:attachment":[{"href":"\/math\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5307"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"\/math\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5307"},{"taxonomy":"post_tag","embeddable":true,"href":"\/math\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5307"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}