{"id":612,"date":"2012-05-03T13:16:23","date_gmt":"2012-05-03T17:16:23","guid":{"rendered":"http:\/\/www.jlao.net\/?p=612"},"modified":"2015-07-23T06:19:21","modified_gmt":"2015-07-23T13:19:21","slug":"sodoku-solution-project-euler-96","status":"publish","type":"post","link":"https:\/\/www.jlao.net\/en\/technology\/612\/","title":{"rendered":"Sudoku Solution &#8211; Project Euler #96"},"content":{"rendered":"This is a Python solution for <a title=\"Project Euler #96\" href=\"https:\/\/projecteuler.net\/problem=96\" target=\"_blank\">Project Euler #96<\/a>, to find the solution for sudokus.<\/p>\n<p>The speed is modest (0.750s with pypy on Windows 7 @ i5 2.60GHz), but the code is relatively short and hopefully the idea is clear. Enjoy.<br \/>\n1. Find candidates for all items. If only one exists for a blank, fill it in.<br \/>\n2. Note down the blank with least but more than one candidates.<br \/>\n3. Copy the matrix and trial the candidates recursively until all blanks are filled.<br \/>\n<!--more--><\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">def solve(mat):\r\n    tcan = []  # list of candidates\r\n    i = 0\r\n    mincand = cand_i = cand_j = 10  # item with least > 1 candidates\r\n    while (i < 9):\r\n        j = 0\r\n        while (j < 9):\r\n            if mat[i][j] == 0:\r\n                t = list(set(range(1, 10)) -\r\n                         set([mat[x][y]\r\n                              for x in range(i \/\/ 3 * 3, i \/\/ 3 * 3 + 3)\r\n                              for y in range(j \/\/ 3 * 3, j \/\/ 3 * 3 + 3)] +\r\n                             mat[i] + [mat[a][j] for a in range(9)]))\r\n                if not t:  # can't find a candidate\r\n                    return False\r\n                if len(t) == 1:\r\n                    if cand_i == i and cand_j == j:  # replacing current least\r\n                        mincand = cand_i = cand_j = 10\r\n                    mat[i][j] = t[0]\r\n                    i = -1\r\n                    continue\r\n                if len(t) < mincand:  # saving shortest candidate list\r\n                    tcan, mincand, cand_i, cand_j = t, len(t), i, j\r\n            j += 1\r\n        i += 1\r\n    if mincand == 10:\r\n        return mat\r\n    else:\r\n        for test in tcan:\r\n            mtest = [r for r in mat]  # copy without reference\r\n            mtest[cand_i][cand_j] = test\r\n            mtry = solve(mtest)\r\n            if mtry:\r\n                return mtry\r\n    return False\r\n\r\ndef main():\r\n    a = open('96.txt', 'r').readlines()\r\n    mt = []\r\n    count = 0\r\n    for x in a:\r\n        if x[0] == 'G':\r\n            mt = []\r\n            print(x)\r\n        else:\r\n            mt.append(list(map(int, list(x)[0:9])))\r\n            if len(mt) == 9:\r\n                m = solve(mt)\r\n                for r in m:\r\n                    print(r)\r\n                i = int(''.join(list(map(str, m[0][0:3]))))\r\n                count += i\r\n    print(count)\r\n\r\nif __name__ == '__main__':\r\n    main()\r\n<\/pre>","protected":false},"excerpt":{"rendered":"<p>Sorry, this entry is only available in \u4e2d\u6587.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[5],"tags":[23,24,25],"class_list":["post-612","post","type-post","status-publish","format-standard","hentry","category-technology","tag-project-euler","tag-sudoku","tag-python"],"_links":{"self":[{"href":"https:\/\/www.jlao.net\/en\/wp-json\/wp\/v2\/posts\/612","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.jlao.net\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.jlao.net\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.jlao.net\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.jlao.net\/en\/wp-json\/wp\/v2\/comments?post=612"}],"version-history":[{"count":0,"href":"https:\/\/www.jlao.net\/en\/wp-json\/wp\/v2\/posts\/612\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.jlao.net\/en\/wp-json\/wp\/v2\/media?parent=612"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.jlao.net\/en\/wp-json\/wp\/v2\/categories?post=612"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.jlao.net\/en\/wp-json\/wp\/v2\/tags?post=612"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}