14. 判定数独矩阵

1. 描述

Sudoku is a number-placement puzzle. The objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 sub-grids that compose the grid contains all of the digits from 1 to 9.

This algorithm should check if the given grid of numbers represents a correct solution to Sudoku.

程序不复杂，就是来判定一个 9 × 9 的行、列、3 × 3 子矩阵是否是 1 ~ 9 不同数字组成。

2. 例子

• For

grid = [[1, 3, 2, 5, 4, 6, 9, 8, 7],
        [4, 6, 5, 8, 7, 9, 3, 2, 1],
        [7, 9, 8, 2, 1, 3, 6, 5, 4],
        [9, 2, 1, 4, 3, 5, 8, 7, 6],
        [3, 5, 4, 7, 6, 8, 2, 1, 9],
        [6, 8, 7, 1, 9, 2, 5, 4, 3],
        [5, 7, 6, 9, 8, 1, 4, 3, 2],
        [2, 4, 3, 6, 5, 7, 1, 9, 8],
        [8, 1, 9, 3, 2, 4, 7, 6, 5]]

the output should be
solution(grid) = true;

• For

grid = [[8, 3, 6, 5, 3, 6, 7, 2, 9],
        [4, 2, 5, 8, 7, 9, 3, 8, 1],
        [7, 9, 1, 2, 1, 4, 6, 5, 4],
        [9, 2, 1, 4, 3, 5, 8, 7, 6],
        [3, 5, 4, 7, 6, 8, 2, 1, 9],
        [6, 8, 7, 1, 9, 2, 5, 4, 3],
        [5, 7, 6, 9, 8, 1, 4, 3, 2],
        [2, 4, 3, 6, 5, 7, 1, 9, 8],
        [8, 1, 9, 3, 2, 4, 7, 6, 5]]

the output should be
solution(grid) = false.

通过这个程序也可以判断出，如果一个数独有解，必定这三个条件符合，这三个条件符合，也就说明横向相加必定是 15，而纵向相加也是 15，3 ×3 的子矩阵所有数字之和也肯定是 15。

3. 思路

还是用集合来实现，集合在判定是否有重复元素方面有着先天的优势，如果一个集合的元素个数不是 9，那就判定为不合格，否则即合格。

那么最主要的问题就是如何取得行、列、及子矩阵。

4. 代码

1. 取得每一列的元素：

all([len(set([r[x] for r in grid])) == 9 for x in range(9)])
 
更确切的代码是这样的：
[[r[x] for r in grid] for x in range(9)]

r 代表着行，r[0]代着第 1 列，x 代表所有的行。

2. 取得每一行的元素：

all([len(set([r[x] for x in range(9)])) == 9 for r in grid])
 
也就是说r代表行，r[0]代表第1列，r[1]代表第2列..
[[r[x] for x in range(9)]for r in grid]

用 all ()函数进行判断，如果里面全是 True，则返回 True，如果里面有个 False，则返回 False。

3. 判断子矩阵：

result = True  
  
for i in range(0, 9, 3):  
	for j in range(0, 9, 3):  
		if len(set(chain.from_iterable([r[j:j + 3] for r in grid[i:i + 3]]))) != 9:  
		result = False  
		break  
  
print(result)

主要是用 chain.form_iterable 函数把 3×3 的二维数组变成一维，方便用 set 来统计元素个数。对了，i 代表着行，而 j 代表着列，每个都是 3 的步距。

4. 最后强调一点，只有上面三个条件都为 True 的情况下，才能算这个数独通过。