A Sublinear Sudoku Solution in cP Systems and its Formal Verification
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
203 5
Ultima descărcare din IBN:
2021-06-26 01:16
Căutarea după subiecte
similare conform CZU
004+510+519.1 (1)
Știința și tehnologia calculatoarelor. Calculatoare. Procesarea datelor (2900)
Considerații fundamentale și generale ale matematicii (31)
Analiză combinatorică. Teoria grafurilor (99)
SM ISO690:2012
LIU, Yezhou; NICOLESCU, Radu; SUN, Jing; HENDERSON, Alec. A Sublinear Sudoku Solution in cP Systems and its Formal Verification. In: Computer Science Journal of Moldova. 2021, nr. 1(85), pp. 3-28. ISSN 1561-4042.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Computer Science Journal of Moldova
Numărul 1(85) / 2021 / ISSN 1561-4042

A Sublinear Sudoku Solution in cP Systems and its Formal Verification

CZU: 004+510+519.1
MSC 2010: 68Q07, 68N30.

Pag. 3-28

Liu Yezhou, Nicolescu Radu, Sun Jing, Henderson Alec
 
University of Auckland
 
Disponibil în IBN: 24 aprilie 2021


Rezumat

Sudoku is known as a NP-complete combinatorial numberplacement puzzle. In this study, we propose the first cP system solution to generalised Sudoku puzzles with m×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.

Cuvinte-cheie
cP systems, P systems, Sudoku problem, NPcomplete problem, Formal verification