牛子 Solution

link

结论：一个方案合法当且仅当，每行数种类为 \(2\)，或者每列数种类为 \(2\)。

证明：我们试图证明，如果一个方案存在一行的数种类 \(\ge3\)，则这个方案的每列数种类为 \(2\)。

对于有 \(\ge3\) 种数的这一行，必然存在某连续的三个数两两不同，即形如 abc 的形式。

这个可以反证：否则任意三个数都是 aba 的形式，则这一行形如 abababababababa，只有两种数，矛盾。

那么对于这一个 abc，b 上下两个数必然都是剩下的一个数 d，最终 abc 上下两行加起来 \(9\) 个数必定形如

cda
abc
cda

这时候再在中间这行左右任意添加字符，都满足上下行的对应位置数被确定。例如

ada-cda-badc
cbc-abc-dcba
ada-cda-badc

恰好是填 a 确定 c，填 c 确定 a，填 b 确定 d，填 d 确定 b。

可以继续向上一行、下一行拓展，结论仍然适用。容易发现，这说明此时每列数种类只有 \(2\)。

至此，证明了要么每行数种类为 \(2\)，要么每列数种类为 \(2\)。求解方案直接根据本行或本列已有数字构造即可。