九宫数独的方程求解算法研究

Research of equation solution algorithm about Sudoku puzzle

首先从数独的要求出发建立方程组,该方程组的解与原数独的解完全等价。然后由该方程组推导出一系列数学性质,包括删除候选数性质、唯一确定法性质、矛盾性质和不变性性质。并说明数独的人工推理规则包含在这些性质之中。最后由这些性质提出求解该方程组的算法,算法中用一个三维矩阵来表示待求解九宫数独的候选数矩阵,根据上述性质对候选数矩阵进行删减,直到能够解出此九宫数独。此算法能够求解出许多数独软件无法进行推理计算的数独难题,并用两个数独难题进行验证,说明了该算法的有效性。

It began with the requirement of Sudoku to establish the system of equations. The solution of equation system was equivalent to the original Sudoku. And many mathematical properties were derived from equation system, including candidates elimination techniques, unique determination property, contradiction property and invariance property. It also illustrated that the artificial deductive rules included these properties. Finally this paper proposed a algorithm which calculated the solution of equation system from these properties. The algorithm used a three-dimensional matrix to express the candidate matrix of an unsolved Sudoku, and according to the above properties the candidate matrix could be deleted until Sudoku was solved. The algorithm can resolve many difficult Sudoku puzzles. Two difficult Sudoku puzzles were demonstrated and solved easily with the method in this paper, which shows the method is very effective.