{"id":792,"date":"2010-08-23T03:38:26","date_gmt":"2010-08-22T18:38:26","guid":{"rendered":"http:\/\/peta.okechan.net\/blog\/?p=792"},"modified":"2010-08-23T04:30:07","modified_gmt":"2010-08-22T19:30:07","slug":"python%e3%81%a7%e6%95%b0%e7%8b%ac%e3%82%bd%e3%83%ab%e3%83%90%e3%83%bc%e3%82%92%e5%ae%9f%e8%a3%85%e3%81%97%e3%81%9f","status":"publish","type":"post","link":"https:\/\/peta.okechan.net\/blog\/archives\/792","title":{"rendered":"Python\u3067\u6570\u72ec\u30bd\u30eb\u30d0\u30fc\u3092\u5b9f\u88c5\u3057\u305f"},"content":{"rendered":"<p><a href=\"http:\/\/gigazine.net\/index.php?\/news\/comments\/20100822_hardest_sudoku\/\" target=\"_blank\">\u6570\u5b66\u306e\u30a8\u30ad\u30b9\u30d1\u30fc\u30c8\u304c3\u30f6\u6708\u304b\u3051\u3066\u4f5c\u6210\u3057\u305f\u300c\u4e16\u754c\u4e00\u96e3\u3057\u3044\u6570\u72ec\u300d\uff08GIGAZINE\uff09<\/a>\u3068\u3044\u3046\u8a18\u4e8b\u3092\u8aad\u307f\u307e\u3057\u3066\u3001\u4e16\u754c\u4e00\u96e3\u3057\u3044\u3068\u805e\u3044\u3066\u653e\u3063\u3066\u306f\u304a\u3051\u306a\u3044\u306a\u3001\u3068\u3044\u3046\u3053\u3068\u3067\u30c1\u30e3\u30ec\u30f3\u30b8\u3057\u3066\u307f\u307e\u3057\u305f\u3002Python\u3067w<\/p>\n<p>\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068\u3057\u3066\u306f\u6df1\u3055\u512a\u5148\u63a2\u7d22\uff08\u518d\u5e30\u5229\u7528\uff09\u3067\u3059\u306a\u3002<br \/>\n\u66f8\u304f\u306e\u306b1\u6642\u9593\u307b\u3069\u304b\u304b\u308a\u307e\u3057\u305f\u3002<\/p>\n<p>\u6700\u521d\u8003\u3048\u305f\u901a\u308a\u306b\u5b9f\u88c5\u3057\u305f\u3042\u3068\u306b\u9811\u5f35\u3063\u3066\u9ad8\u901f\u5316\u3057\u3066\u3044\u3053\u3046\u3068\u601d\u3063\u3066\u307e\u3057\u305f\u304c\uff08\u5927\u62b5\u30d1\u30ba\u30eb\u3082\u306e\u306e\u7b54\u3048\u306e\u63a2\u7d22\u306f\u679d\u5207\u308a\u306a\u3093\u304b\u3092\u3057\u306a\u3044\u3068\u30e1\u30c3\u30c1\u30e3\u6642\u9593\u304c\u639b\u304b\u308b\uff09\u3001\u81ea\u5206\u306e\u305d\u3093\u306a\u306b\u65e9\u304f\u306a\u3044\u30de\u30b7\u30f3\u30671\u79d2\u304f\u3089\u3044\u3067\u89e3\u3051\u305f\u306e\u3067\u305d\u306e\u307e\u307e\u3067\u3059\u3002<\/p>\n<p>\u3068\u3044\u3046\u3053\u3068\u3067\u30bd\u30fc\u30b9\u516c\u958b\u3002<br \/>\n\uff08\u3057\u304b\u3057\u3053\u306e\u96e3\u6613\u5ea6\u3060\u3063\u305f\u3089\u5b9f\u88c5\u3057\u305f\u4eba\u3044\u3063\u3071\u3044\u3044\u305d\u3046\u2026\uff09<\/p>\n<p>stage_base\u306b\u8a2d\u5b9a\u3055\u308c\u3066\u308b\u306e\u306f\u3001\uff08\u4eba\u9593\u306b\u3068\u3063\u3066\uff09\u4e16\u754c\u4e00\u96e3\u3057\u3044\u3068\u3055\u308c\u3066\u3044\u308b\u6570\u72ec\u306e\u554f\u984c\u3067\u3059\u3002<\/p>\n<pre class=\"brush: python; title: ; notranslate\" title=\"\">\r\n#!\/usr\/bin\/python\r\n# -*- coding: utf-8 -*-\r\n\r\nstage_base = &#x5B;\r\n\t&#x5B;0, 0, 5,  3, 0, 0,  0, 0, 0],\r\n\t&#x5B;8, 0, 0,  0, 0, 0,  0, 2, 0],\r\n\t&#x5B;0, 7, 0,  0, 1, 0,  5, 0, 0],\r\n\t\r\n\t&#x5B;4, 0, 0,  0, 0, 5,  3, 0, 0],\r\n\t&#x5B;0, 1, 0,  0, 7, 0,  0, 0, 6],\r\n\t&#x5B;0, 0, 3,  2, 0, 0,  0, 8, 0],\r\n\t\r\n\t&#x5B;0, 6, 0,  5, 0, 0,  0, 0, 9],\r\n\t&#x5B;0, 0, 4,  0, 0, 0,  0, 3, 0],\r\n\t&#x5B;0, 0, 0,  0, 0, 9,  7, 0, 0],\r\n]\r\n\r\ndef main():\r\n\tif solve(0, 0, stage_base):\r\n\t\tprint u'\u89e3\u3051\u305f\uff01'\r\n\t\tprintStage(stage_base)\r\n\telse:\r\n\t\tprint u'\u89e3\u3051\u306a\u304b\u3063\u305forz'\r\n\r\ndef solve(x, y, stage):\r\n\tif x == 0 and y == 9:\r\n\t\treturn True\r\n\t\r\n\tif stage&#x5B;y]&#x5B;x] == 0:\r\n\t\tfor t in xrange(1, 10):\r\n\t\t\tstage&#x5B;y]&#x5B;x] = t\r\n\t\t\tif isValid(x, y, stage):\r\n\t\t\t\t(nx, ny) = next(x, y)\r\n\t\t\t\tif solve(nx, ny, stage):\r\n\t\t\t\t\treturn True\r\n\t\tstage&#x5B;y]&#x5B;x] = 0\r\n\t\treturn False\r\n\telse:\r\n\t\t(nx, ny) = next(x, y)\r\n\t\tif solve(nx, ny, stage):\r\n\t\t\treturn True\r\n\r\ndef next(x, y):\r\n\tx += 1\r\n\tif x &gt; 8:\r\n\t\tx = 0\r\n\t\ty += 1\r\n\treturn (x, y)\r\n\r\ndef isValid(x, y, stage):\r\n\treturn isValidYoko(x, y, stage) and isValidTate(x, y, stage) and isValid3x3(x, y, stage)\r\n\r\ndef isValidTate(x, y, stage):\r\n\tfor yt in xrange(9):\r\n\t\tif yt != y:\r\n\t\t\tif stage&#x5B;y]&#x5B;x] == stage&#x5B;yt]&#x5B;x]:\r\n\t\t\t\treturn False\r\n\treturn True\r\n\r\ndef isValidYoko(x, y, stage):\r\n\tfor xt in xrange(9):\r\n\t\tif xt != x:\r\n\t\t\tif stage&#x5B;y]&#x5B;x] == stage&#x5B;y]&#x5B;xt]:\r\n\t\t\t\treturn False\r\n\treturn True\r\n\r\ndef isValid3x3(x, y, stage):\r\n\txbase = (x \/\/ 3) * 3\r\n\tybase = (y \/\/ 3) * 3\r\n\tfor yt in xrange(ybase, ybase + 3):\r\n\t\tfor xt in xrange(xbase, xbase + 3):\r\n\t\t\tif xt != x and yt != y:\r\n\t\t\t\tif stage&#x5B;y]&#x5B;x] == stage&#x5B;yt]&#x5B;xt]:\r\n\t\t\t\t\treturn False\r\n\treturn True\r\n\r\ndef printStage(stage):\r\n\tfor y in xrange(9):\r\n\t\tfor x in xrange(9):\r\n\t\t\tprint stage&#x5B;y]&#x5B;x],\r\n\t\tprint &quot;&quot;\r\n\r\nif __name__ == &quot;__main__&quot;:\r\n\tmain()\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p><a href=\"http:\/\/gigazine.net\/index.php?\/news\/comments\/20100822_hardest_sudoku\/\" target=\"_blank\">\u6570\u5b66\u306e\u30a8\u30ad\u30b9\u30d1\u30fc\u30c8\u304c3\u30f6\u6708\u304b\u3051\u3066\u4f5c\u6210\u3057\u305f\u300c\u4e16\u754c\u4e00\u96e3\u3057\u3044\u6570\u72ec\u300d\uff08GIGAZINE\uff09<\/a>\u3068\u3044\u3046\u8a18\u4e8b\u3092\u8aad\u307f\u307e\u3057\u3066\u3001\u4e16\u754c\u4e00\u96e3\u3057\u3044\u3068\u805e\u3044\u3066\u653e\u3063\u3066\u306f\u304a\u3051\u306a\u3044\u306a\u3001\u3068\u3044\u3046\u3053\u3068\u3067\u30c1\u30e3\u30ec\u30f3\u30b8\u3057\u3066\u307f\u307e\u3057\u305f\u3002Python\u3067w<\/p>\n<p>\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068\u3057\u3066\u306f\u6df1\u3055\u512a\u5148\u63a2\u7d22\uff08\u518d\u5e30\u5229\u7528\uff09\u3067\u3059\u306a\u3002<br \/>\n\u66f8\u304f\u306e\u306b1\u6642\u9593\u307b\u3069\u304b\u304b\u308a\u307e\u3057\u305f\u3002<\/p>\n<p>\u6700\u521d\u8003\u3048\u305f\u901a\u308a\u306b\u5b9f\u88c5\u3057\u305f\u3042\u3068\u306b\u9811\u5f35\u3063\u3066\u9ad8\u901f\u5316\u3057\u3066\u3044\u3053\u3046\u3068\u601d\u3063\u3066\u307e\u3057\u305f\u304c\uff08\u5927\u62b5\u30d1\u30ba\u30eb\u3082\u306e\u306e\u7b54\u3048\u306e\u63a2\u7d22\u306f\u679d\u5207\u308a\u306a\u3093\u304b\u3092\u3057\u306a\u3044\u3068\u30e1\u30c3\u30c1\u30e3\u6642\u9593\u304c\u639b\u304b\u308b\uff09\u3001\u81ea\u5206\u306e\u305d\u3093\u306a\u306b\u65e9\u304f\u306a\u3044\u30de\u30b7\u30f3\u30671\u79d2\u304f\u3089\u3044\u3067\u89e3\u3051\u305f\u306e\u3067\u305d\u306e\u307e\u307e\u3067\u3059\u3002<\/p>\n<p>\u3068\u3044\u3046\u3053\u3068\u3067\u30bd\u30fc\u30b9\u516c\u958b\u3002<br \/>\n\uff08\u3057\u304b\u3057\u3053\u306e\u96e3\u6613\u5ea6\u3060\u3063\u305f\u3089\u5b9f\u88c5\u3057\u305f\u4eba\u3044\u3063\u3071\u3044\u3044\u305d\u3046\u2026\uff09<\/p>\n<p>stage_base\u306b\u8a2d\u5b9a\u3055\u308c\u3066\u308b\u306e\u306f\u3001\uff08\u4eba\u9593\u306b\u3068\u3063\u3066\uff09\u4e16\u754c\u4e00\u96e3\u3057\u3044\u3068\u3055\u308c\u3066\u3044\u308b\u6570\u72ec\u306e\u554f\u984c\u3067\u3059\u3002<\/p>\n<pre class=\"brush: python; title: ; notranslate\" title=\"\">\r\n#!\/usr\/bin\/python\r\n# -*- coding: utf-8 -*-\r\n\r\nstage_base = &#x5B;\r\n\t&#x5B;0, 0, 5,  3, 0, 0,  0, 0, 0],\r\n\t&#x5B;8, 0, 0,  0, 0, 0,  0, 2, 0],\r\n\t&#x5B;0, 7, 0,  0, 1, 0,  5, 0, 0],\r\n\t\r\n\t&#x5B;4, 0, 0,  0, 0, 5,  3, 0, 0],\r\n\t&#x5B;0, 1, 0,  0, 7, 0,  0, 0, 6],\r\n\t&#x5B;0, 0, 3,  2, 0, 0,  0, 8, 0],\r\n\t\r\n\t&#x5B;0, 6, 0,  5, 0, 0,  0, 0, 9],\r\n\t&#x5B;0, 0, 4,  0, 0, 0,  0, 3, 0],\r\n\t&#x5B;0, 0, 0,  0, 0, 9,  7, 0, 0],\r\n]\r\n\r\ndef main():\r\n\tif solve(0, 0, stage_base):\r\n\t\tprint u'\u89e3\u3051\u305f\uff01'\r\n\t\tprintStage(stage_base)\r\n\telse:\r\n\t\tprint u'\u89e3\u3051\u306a\u304b\u3063\u305forz'\r\n\r\ndef solve(x, y, stage):\r\n\tif x == 0 and y == 9:\r\n\t\treturn True\r\n\t\r\n\tif stage&#x5B;y]&#x5B;x] == 0:\r\n\t\tfor t in xrange(1, 10):\r\n\t\t\tstage&#x5B;y]&#x5B;x] = t\r\n\t\t\tif isValid(x, y, stage):\r\n\t\t\t\t(nx, ny) = next(x, y)\r\n\t\t\t\tif solve(nx, ny, stage):\r\n\t\t\t\t\treturn True\r\n\t\tstage&#x5B;y]&#x5B;x] = 0\r\n\t\treturn False\r\n\telse:\r\n\t\t(nx, ny) = next(x, y)\r\n\t\tif solve(nx, ny, stage):\r\n\t\t\treturn True\r\n\r\ndef next(x, y):\r\n\tx += 1\r\n\tif x &gt; 8:\r\n\t\tx = 0\r\n\t\ty += 1\r\n\treturn (x, y)\r\n\r\ndef isValid(x, y, stage):\r\n\treturn isValidYoko(x, y, stage) and isValidTate(x, y, stage) and isValid3x3(x, y, stage)\r\n\r\ndef isValidTate(x, y, stage):\r\n\tfor yt in xrange(9):\r\n\t\tif yt != y:\r\n\t\t\tif stage&#x5B;y]&#x5B;x] == stage&#x5B;yt]&#x5B;x]:\r\n\t\t\t\treturn False\r\n\treturn True\r\n\r\ndef isValidYoko(x, y, stage):\r\n\tfor xt in xrange(9):\r\n\t\tif xt != x:\r\n\t\t\tif stage&#x5B;y]&#x5B;x] == stage&#x5B;y]&#x5B;xt]:\r\n\t\t\t\treturn False\r\n\treturn True\r\n\r\ndef isValid3x3(x, y, stage):\r\n\txbase = (x \/\/ 3) * 3\r\n\tybase = (y \/\/ 3) * 3\r\n\tfor yt in xrange(ybase, ybase + 3):\r\n\t\tfor xt in xrange(xbase, xbase + 3):\r\n\t\t\tif xt != x and yt != y:\r\n\t\t\t\tif stage&#x5B;y]&#x5B;x] == stage&#x5B;yt]&#x5B;xt]:\r\n\t\t\t\t\treturn False\r\n\treturn True\r\n\r\ndef printStage(stage):\r\n\tfor y in xrange(9):\r\n\t\tfor x in xrange(9):\r\n\t\t\tprint stage&#x5B;y]&#x5B;x],\r\n\t\tprint &quot;&quot;\r\n\r\nif __name__ == &quot;__main__&quot;:\r\n\tmain()\r\n<\/pre>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[32],"tags":[60,350,349],"class_list":["post-792","post","type-post","status-publish","format-standard","hentry","category-tech","tag-python","tag-350","tag-349"],"_links":{"self":[{"href":"https:\/\/peta.okechan.net\/blog\/wp-json\/wp\/v2\/posts\/792","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/peta.okechan.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/peta.okechan.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/peta.okechan.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/peta.okechan.net\/blog\/wp-json\/wp\/v2\/comments?post=792"}],"version-history":[{"count":0,"href":"https:\/\/peta.okechan.net\/blog\/wp-json\/wp\/v2\/posts\/792\/revisions"}],"wp:attachment":[{"href":"https:\/\/peta.okechan.net\/blog\/wp-json\/wp\/v2\/media?parent=792"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/peta.okechan.net\/blog\/wp-json\/wp\/v2\/categories?post=792"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/peta.okechan.net\/blog\/wp-json\/wp\/v2\/tags?post=792"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}