文章基本信息

标题：A Sublinear Sudoku Solution in cP Systems and its Formal Verification
本地全文：下载
作者：Yezhou Liu ; Radu Nicolescu ; Jing Sun 等
期刊名称：Computer Science Journal of Moldova
印刷版ISSN：1561-4042
出版年度：2021
卷号：29
期号：1
页码：3-28
出版社：Institute of Mathematics and Computer Science
摘要：Sudoku is known as a NP-complete combinatorial number-placement puzzle. In this study, we propose the first cP~system solution to generalised Sudoku puzzles with $m imes m$ cells grouped in $m$ blocks. By using a fixed constant number of rules, our cP~system can solve all Sudoku puzzles in sublinear steps. We evaluate the cP~system and discuss its formal verification.
关键词：cP~systems; P~systems; Sudoku problem; NP-complete problem; Formal verification.