1. Assignment2 Sudoku Explanation

数独规则简述：每行、每列、每个九宫格都由1-9构成，不能有数字重复。
解法思路简述：根据不重复的规则找到forced cell solution，再标记每个cell的possible solution，然后根据preemptive set来进一步确认剩余cell的解法。通常无法准确判断每一个cell的确定解，有一些cell必须要guess，这个时候要mark好当前的status，如果猜测不对，则要回到当前的status。

1.1 preassess()

初筛输入grid是否符合要求，检查：
（1）是否是9*9的table；
（2）所有元素是否是0-9的integer；
（3）每行、每列、每个九宫格没有digit repetition

1.2 bare_tex_output()

根据latex语法输出可供简洁查看的数独代码。包括不需要调整的主体代码部分：

\documentclass[10pt]{article}
\usepackage[left=0pt,right=0pt]{geometry}
\usepackage{tikz}
\usetikzlibrary{positioning}
\usepackage{cancel}
\pagestyle{empty}

\newcommand{\N}[5]{\tikz{\node[label=above left:{\tiny #1},
                               label=above right:{\tiny #2},
                               label=below left:{\tiny #3},
                               label=below right:{\tiny #4}]{#5};}}

\begin{document}

\tikzset{every node/.style={minimum size=.5cm}}

\begin{center}
\begin{tabular}{||@{}c@{}|@{}c@{}|@{}c@{}||@{}c@{}|@{}c@{}|@{}c@{}||@{}c@{}|@{}c@{}|@{}c@{}||}\hline\hline

\end{tabular}
\end{center}

\end{document}

需要调整的代码含义如下：

\N{}{}{}{}{} & \N{}{}{}{}{} & \N{}{}{}{}{1} &
\N{}{}{}{}{9} & \N{}{}{}{}{} & \N{}{}{}{}{} &
\N{}{}{}{}{} & \N{}{}{}{}{} & \N{}{}{}{}{8} \\ \hline
#每条line的代码需要调整，调整部分是{}中的内容。
#\N{}{}{}{}{9}为例，第1个{}代表cell左上的mark内容，第2个{}代表cell右上的mark内容，第3个{}代表cell左下的mark内容，第4个{}代表cell右下的mark内容，第5个{}代表cell正确的数字（这里是9）

mark删除value的写法如下：

{\cancel{7} \cancel{8}}
#前述第N个{}的输出写法，含义是删除7和8

1.3 forced_tex_output()

根据规则和latex代码含义输出所有能确定数字的cell值，使用latex格式输出。

1.4 marked_tex_output()

除了所有确定值cell的输出外，不能确定数值的cell有显示所有的possible values。
第1个{}存储1，2；
第2个{}存储3，4；
第3个{}存储5，6；
第4个{}存储7，8，9；

1.5 worked_tex_output()

使用preemptive set方法输出sudo的解。

2. Preemptive Set

假设在一行中有3个cell的数字不能确定，他们的possible values分别是{1,2,3}, {1,2}, {1,3}。
这说明这3个cell必须填充1，2，3这三个数字，他们组成了一个preemptive set。
用法是，如果在同一行另一个cell是{1, 5, 6}那么可以在这个cell中划去1，剩下{5, 6}。
该方法可以在每行、每列、每个九宫格中都使用，从而缩小possible values以最大程度接近最终解。

2.1 Combination判断Preemptive Set

找到包含所有元素的cell，根据这个cell可以列举所有的组合可能，再判断后续cell是否与之形成preemptive set。

from itertools import combinations
list(combinations([2, 3, 4], 2))
>>>
[(2, 3), (2, 4), (3, 4)]

2.2 二进制判断Preemptive Set

combination的方式效率不高，可以用二进制的思路提高效率。本质问题是判断两个集合是否有子集关系，假设：
x = {1, 3}
y = {1, 3, 5}
假设一个10位的二进制数，每一位都代表对应位置的数字，例如10代表1，100代表2，1000代表3。这样可以用一个二进制来表示一个上述的集合，x表示为1010，y表示为101010。
接下来判断子集关系是否成立，方法是这样的二进制的每一位上x | y == y，如果为True则x是y的子集，反之。
（1）集合转换为二进制表达的十进制操作方法：

s = {1, 4, 6} 
x = 0
for e in s:
   x |= 1 << (e - 1) 
f'{x:09b}'
>>>
'000101001'

（2）二进制表达的十进制数转换为集合的方法：

def convert_number_to_set(x):
    S = set()
    n = 1
    while x:
        if x & 1:
            S.add(n)
        x >>= 1
        n += 1
    return S

convert_number_to_set(41)

上述代码实现过程解释如下：

41的二进制表达是x = 101001
assign n = 1
进入while循环，x为True
进入if判断x & 1，x最后一位是1，x&1为True
s = {1}
接下来右移1位，二进制表达是x = 10100
n = 2
x = 1010
n = 3
x = 101
n = 4
x & 1 True
s = {1, 4}
x = 10
n = 5
x = 1
n = 6
x & 1 True
s = {1, 4, 6}