Computer Science Journal of Moldova (Apr 2021)

A Sublinear Sudoku Solution in cP Systems and its Formal Verification

  • Yezhou Liu,
  • Radu Nicolescu,
  • Jing Sun,
  • Alec Henderson

Journal volume & issue
Vol. 29, no. 1(85)
pp. 3 – 28


Read online

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 \times 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.