数独一
* * * *
拉格朗日计划
* * * *
数独一

数独是一种常见的益智游戏,给定一个$9\times 9$的网格,其中一些格子已经填入了1到9之间的数字,要求在每一个空格中也填入1到9之间的数字,使得每一行、每一列,和指定的$3\times 3$的子区域中这9个数字都只出现正好一次。

输入数据是9个字符串,依次表示网格中从上到下的9行。每个字符串的长度为9,表示每行从左到右的9列,其中数字表示已填入的数字,下划线表示空格。

解出该数独,并按如下格式输出:

注:因边框为非标准Unicode字符,其宽度在不同的环境中会有变化,而原题页面中用于正确排版的特定字体本站并未安装,因此以下用截图代替。边框所用的具体字符可以参见下文的源代码,或原题页面



本题难度:



解答

数独是典型的需要使用回溯算法的问题,常规写法很长,不容易缩写。

以下r方法改写自Shortest Sudoku Solver,p、q两个方法处理输出时的不同边框和空格。

最终代码有七行。

代码长度:565字节 vs. 全站第一:301字节。

import sys
b,y,z=' 0\n'
t=''.join
q=lambda x:x[0]+x[1].join([x[3:]]*3)+x[2]+z
def p(a):print(q('┏┳┓━━━┯━━━┯━━━')+t('┃ '*(i%9<1)+a[i]+b+'┃│'[i%3<2]+b+(z+([q('┠╂┨───┼───┼───'),q('┣╋┫━━━┿━━━┿━━━')][i%27>25])*(i<80))*(i%9>7)for i in range(81))+q('┗┻┛━━━┷━━━┷━━━'))
def r(a):i=a.find(y);~i or p(a);[m in[(i-j)%9*(i//9^j//9)*(i//27^j//27|i%9//3^j%9//3)or a[j]for j in range(81)]or r(a[:i]+m+a[i+1:])for m in'123456789']
r(t(sys.argv[1:]).replace('_',y))