A generic membrane computing-based Sudoku solver

Sudoku is a logic-based, combinatorial number placement puzzle, with the objective of filling an n²×n² grid of cells with digits so that each column, row and n×n sub-grid (box) that compose the grid contain all the digits from 1 to n². In this paper we study the problem of implementing the Sudoku solving algorithm through the membrane computing paradigm. The devices of this paradigm are called P systems. The solution is obtained by first finding a unique candidate in rows, columns and boxes using the constraints, and then applying various Sudoku solving strategies. Finally, if every strategy fails, the solution is searched through a brute force method. If the solution is obtainable, the P system returns the object YES to the environment. If the Sudoku is unsolvable, the P system returns the object NO to the environment and the system eventually halts. The main contribution of this paper is that the basic P System model defined in [1] has been extended further with additional powerful strategies based on the deductive logic popular with human solvers. The objectives of this effort are twofold (0 to study the very expressive, compact & elegant representation system membrane computing offers (ii) to study the resilience & flexibility offered by the representation to permit addition of new strategies; this being an important requirement in real life applications. The results are presented and discussed for some of the most difficult Sudoku problems available in open source literature. The model will find a solution if it exists. In this sense the model is a generic Sudoku solver.