Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
A Sublinear Sudoku Solution in cP Systems and its Formal Verification
Authors: Yezhou Liu, Radu Nicolescu, Jing Sun, Alec Henderson
Keywords: cP~systems, P~systems, Sudoku problem, NP-complete problem, Formal verification.
– 0.30 Mb
Keywords: cP~systems, P~systems, Sudoku problem, NP-complete problem, Formal verification.
Abstract
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.Institution: The University of Auckland
Address: SCIENCE CENTRE 303S - Bldg 303S, Level 5, Room 596, 38 PRINCES
ST, AUCKLAND, New Zealand 1010
E-mail: , , ,
Address: SCIENCE CENTRE 303S - Bldg 303S, Level 5, Room 596, 38 PRINCES
ST, AUCKLAND, New Zealand 1010
E-mail: , , ,
Fulltext
– 0.30 Mb
Contents
- A Sublinear Sudoku Solution in cP Systems and its Formal Verification
- On a modified M/M/m/n queueing model
- Properties of Finitely Supported Self - Mappings on the Finite Powerset of Atoms
- On the bondage, strong and weak bondage numbers in Complementary Prism Graphs
- Some properties of maximum deficiency energy of a graph
- Connected Domination Number and a New Invariant in Graphs with Independence Number Three
- Total energy of signed digraphs
- Backtracking algorithm for lexicon generation
