| 摘要: |
| 为了更好地求解数独问题，提出了一种新的求解方法，利用一个具有抑制催化和膜溶解规则以及进化规则的优先级的膜系统来进行求解；结果表明，对于一个数独问题，只要其所有部分解都至少包含一个具有唯一解的单元格，方法都是有效的；如果数独问题可以利用此策略求解，则膜系统在计算的最后一步将问题的解编码并返回物质YES，否则，膜系统可以检测出数独问题不符合上述特征，返回物质NO，计算停止；方法求解策略与人类求解数独问题的思考过程非常类似，并且给出的是数独问题的统一解，即与数独问题的维度和提示数无关。 |
| 关键词: 膜计算 数独游戏 细胞膜系统 |
| DOI： |
| 分类号: |
| 基金项目: |
|
| Basic Solution to Sudoku Based on Membrane Computing Model |
|
JIANG Yun
|
| Abstract: |
| Sudoku problem has been proved to be an NP complete problem. In order to solve the Sudoku more efficiently, a novel approach was proposed.We designed a family of P systems using enzymatic rules, dissolution rules and priorities among sets of rules to solve a large amount of Sudokus. Results show that the strategy is effective as long as Sudokus satisfy the property that in its all partial solutions there exists at least one square with a unique candidate. If the solution can be solved by using this strategy, the P system encodes the solution and returns Yes in the last step of computation. Otherwise, the P system detects that the property is not satisfied and the computation halts by returning No. The solution is searched by using a human style method based on looking for squares where only one candidate can be placed.Meanwhile, the solution is a uniform solution to Sudoku problem, in other words, it is irrelevant to the order of the problem and the hint numbers. |
| Key words: membrane computing Sudoku cell like P system |
