Item
背景:数独是一个在9x9格子上玩的游戏。这个游戏的目标是用1到9的数字填充网格的所有单元格,这样每一列、每一行以及9个3x3子网格(也称为块)中的每一个都包含1到9的所有数字。 目标:编写一个函数,检查该数独是否正确,正确的数独返回True,错误的则返回False。
题目来源:Codewars(4kyu)
题目原文:Sudoku is a game played on a 9x9 grid. The goal of the game is to fill all cells of the grid with digits from 1 to 9, so that each column, each row, and each of the nine 3x3 sub-grids (also known as blocks) contain all of the digits from 1 to 9. (More info at: http://en.wikipedia.org/wiki/Sudoku) Write a function validSolution/ValidateSolution/valid_solution() that accepts a 2D array representing a Sudoku board, and returns true if it is a valid solution, or false otherwise. The cells of the sudoku board may also contain 0’s, which will represent empty cells. Boards containing one or more zeroes are considered to be invalid solutions.
Example
[[5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8], [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 4, 5, 2, 8, 6, 1, 7, 9]] => True
[[5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 0, 3, 4, 8], [1, 0, 0, 3, 4, 2, 5, 6, 0], [8, 5, 9, 7, 6, 1, 0, 2, 0], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 0, 1, 5, 3, 7, 2, 1, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 0, 0, 4, 8, 1, 1, 7, 9]] => False
Knowledge
- 数据类型:整数(int)
- 运算符:赋值运算符、比较运算符、逻辑运算符
- 容器:列表、矩阵
- 其他:For循环体、list.count()方法、numpy库、sum函数、矩阵分离
Parsing
- 近期学习了numpy库中处理矩阵的一些方法,看到此题,心中的小九九油然而生;
- 引入numpy库;
- 分析数独游戏胜利的规则:99的大矩阵平均分割为9个小矩阵,分别是33的小矩阵,每个小矩阵包含1-9,大矩阵每行每列包含1-9。特点一目了然,第一就是每个小矩阵的元素和为45,第二则是每行每列的元素和也为45;
- 大概思路:分割>求和>返回依据(搭建2个辅助函数,1个主函数)
- 分割小矩阵并求和,一个大矩阵则有9个45,全存入列表;
- 分割每行并求和,一个大矩阵则有9个45,存入另一个列表;
- 对于每一列,同上操作;
- 判断依据则是利用之前日记中的老熟人“list.count()方法”,是否等于9,逻辑运算符使用and。
Code
import numpy as np
def sumList(list):
x = sum(j for i in list for j in i)
return x
def separation(board):
seAll = [sumList(s) for hs in np.hsplit(np.array(board), 3) for s in np.vsplit(hs, 3)]
seH = [sumList(hs) for hs in np.hsplit(np.array(board), 9)]
seV = [sumList(hs) for hs in np.vsplit(np.array(board), 9)]
return seAll, seH, seV
def valid_solution(board):
if separation(board)[0].count(45) == 9 and separation(board)[1].count(45) == 9 and separation(board)[2].count(45) == 9:
return True
else:
return False
|