Solving Sudoku with Membrane Computing

Solving Sudoku with Membrane Computing Daniel Diaz-Pernil1, Carlos M. Fernandez-Marquez 2, Manuel Garcfa-Quisrnondo 3, Miguel A. Gutierrez-Naranjo 4, Miguel A. Martinez-del-Arnor 5 Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla. Avda. Reina Mercedes sin, 41012, Sevilla, Spain [email protected] [email protected] [email protected] 4[email protected] [email protected] Abstract-Sudoku is a very popular puzzle which consists on placing several numbers in a squared grid according to some simple rules. In this paper we present an efficient family of P systems which solve sudokus of any order verifying a specific property. The solution is searched by using a simple human-style method. If the sudoku cannot be solved by using this strategy, the P system detects this drawback and then the computations stops and returns No. Otherwise, the P system encodes the solution and returns Yes in the last computation step. I. INTRODUCTION Sudoku is currently one of the most famous puzzles in the world. The most popular version consists on a 9 x 9 grid made up of 3 x 3 subgrids, but the general case, an n2 x n2 grid with n x n subgrids is considered. Some cells contain numbers, which can be considered as input data. The goal is to fill in the empty cells, one number in each, so that each column, row, and subgrid contains the numbers 1 through 9 exactly once (numbers 1 to n2 in the general case). If the input data are correct, the sudoku has one and only one solution. The creator is believed to be Howard Garns [6]. He is likely to be the inventor of a puzzle called "Number Place" that appeared in New York in 1979. The puzzle was introduced in Japan by the publishing company Nikoli in the paper Monthly Nikolist in April 1984 as Suji wa dokushin ni kagiru [7], which can be translated as the numbers must occur only once or the numbers must be single. Later, the name was abbreviated as sudoku, where su stands for number and doku stands for alone. Later Wayne Gould from New Zealand discovered the puzzle on a trip to Japan and wrote a program to generate new puzzles. He convinced The Times of London to publish Sudoku puzzles in 2004. In addition to its undoubted success in entertainment, su doku has important properties from a mathematical point of view. The first natural question is to wonder about is the number of all possible sudoku grids. The answer to this question is not an easy matter. A valid sudoku solution is also a Latin square. A Latin square is an n x n table filled by using numbers from 1 to n in such a way that each symbol occurs exactly once in each row and exactly once in each column. The number of 9 x 9 Latin squares is about 5.525 x 1027. Sudoku imposes the additional constraint on subgrids, so from the previous number we need to remove the Latin squares which do not satisfy the condition. The number of valid sudoku solution grids for the standard 9 x 9 grid is 6,670,903,752,021,072,936,960. This number is equal to 9! x 722 x 27 x 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. The details can be found at [1]. Other important property is that it has been proved that the general problem of solving sudoku puzzles on n2 x n2 grids of n x n boxes is known to be NP-complete [5]. Nonetheless, the number of possible solution grids is not the object of study of this paper nor the complexity of finding the solution. In this paper we study the problem of solving sudoku by using Membrane Computing techniques. In the first part of the paper, we develop a theoretical study about the use of brute force algorithms to solve it, based on a well-known solution for the SAT problem. As we will see below, the number of elementary membranes for a usual 9 x 9 sudoku exceeds the number of atoms of the observable universe, so we have a good reason for looking for a different strategy. In the second part of the paper, we present a family of P systems {II(n)}nEN such that II(n) is a P system with input. Such an input is, of course, the input for one sudoku puzzle encoded as a multiset. The solution is searched by using a human-style method based on looking for squares where only one candidate can be placed. This method is good enough to find the solution for a large amount of sudokus, but not all the sudokus can be solved by using this method. An original control method in the design of the algorithm is that the P system stops if the sudoku cannot be solved, i.e., instead of going into a non-ending search, the P system detects the drawback and halts. If the solution can be reached, the P systems stops, sends out an object Yes to the environment and provides the solution encoded on the skin. Otherwise, if the P system detects that the solution cannot be reached then it halts and sends No to the environment in the last step of computation. The paper is organized as follows: first we explore a theo retical brute force algorithm based on a Membrane Computing solution for the SAT problem. After showing the practical drawback of such a solution, we present our efficient family of P systems for solving a large amount of sudokus. We illustrate the behavior of this family with an overview of the computation and, finally, some final remarks are presented. II. A BRUTE FORCE ALGORITHM A sudoku square of order n consists of n4 constants (usually n2 copies of the numbers 1,2, ... , n2), arranged into an n2 x n2 grid which comprises n2 subgrids of size n x n (also called boxes). Such a grid verifies that the entries in each row, each column and each box are all different. A sudoku problem consists on a partial assignment of the variables in a Sudoku square. The target is to find a completion of the assignment which extends the partial assignment and satisfies the constraints. The first idea for solving a sudoku problem is to consider it as a constraint problem. In fact, we are looking for one assignment of numbers to squares which satisfies a finite amount of restrictions. The set of constraints of a sudoku problem can be expressed as a logic formula in conjunctive normal form. Following [3], a sudoku square of order n can be represented as an instance of the SAT problem with n6 propositional variables. For each entry in the n2 x n2 grid, we will consider n2 variables. Let us use the notation Sxyz to refer to variables. Variable Sxyz is assigned true if and only if the entry in the row x and column y is number z. This way, if the variable S753 takes the value true, then it means that the number 3 is placed at position (7,5) of the grid. According to this notation, the different constraints for the sudoku problem can be represented as the following formulae: • There is at least one number in each entry: n2 n2 n2 'l/J1 = /\ /\ V Sxyz x=ly=lz=l • Each number appears at most once in each row: n2 n2 n2_1 n2 'l/J2 = /\ /\ /\ /\ (---'Sxyz V ---'SiYZ) y=l z=l x=l i=x+1 • Each number appears at most once in each column: n2 n2 n2-1 n2 'l/J3 = /\ /\ /\ /\ (---'Sxyz V ---'Sxiz) x=l z=l y=l i=y+1 • Each number appears at most one in each box: n2 n-1n-1 n n n 'l/J4 /\ /\ /\ /\ /\ /\ (---'S(nHx)(nHy)z V z=l i=O j=O x=l y=l k=y+1 ---'S(nHx)(nHk)z) n2 n-1 n-1 n n n n 'l/J5 = /\ /\ /\ /\ /\ /\ /\ (---'S(nHx)(nHy)z V z=l i=O j=O x=l y=l k=x+11=1 ---'S(nHk)(nHI)z) The conjunction of these five formulae IP 'l/J1 /\ 'l/J2 /\ 'l/J3 /\ 'l/J4 /\ 'l/J5 is a formula in conjunctive normal form and each truth assignment which makes it true represents a right arrangement of n2 copies of 1,2, ... , n2 according to the sudoku constraints. Once expressed the sudoku as such a formula, finding a solution to the puzzle can be considered as the problem of finding a truth assignment which satisfies the formula. This is exactly the satisfiability (SAT) problem. Any truth assignment which makes it true represents a right arrangement of n2 copies of 1,2, ... , n2 according to the sudoku constraints over an empty sudoku grid of order n, but we are not interested in finding such solutions. In fact, a sudoku puzzle should have a certain amount of numbers placed in the right position as input in such way that there exists a unique possible assignment which represents the solution to the problem. Given a sudoku puzzle, we will call Input to the set Input = { (x, y, z) : z is placed on the square } (x, y) of the grid In order to deal with the input, it is enough to add the corresponding values to the formula IP as follows: lPin = IP /\ /\ Sxyz (x,y,z) )Elnput Given a sudoku problem and its associated formula lPin, finding the solution to the problem is equivalent to finding a truth assignment which satisfies the formula. In [2], a family of P systems with active membranes to solve the SAT problem was presented. It was based on the solution presented in [4]. The main difference was that the solution from [4] only provides Yes or No as answers to the problem. The solution in [2] found and stored all the truth assignments which satisfy the formula, if there exists. By considering the encoding of a sudoku problem as a CNF formula on one side and the family of P systems which provides solutions for SAT on the other side, we have a Membrane Computing solution for all sudoku problems. This nice theoretical solution has an insurmountable obsta cle from a practical point of view: the number of elementary membranes in one configuration of one P system from the family reaches 2N, where N is the number of variables of the CNF formula. For a sudoku of order n, the number of variables is n6, and so the number of elementary membranes is 2n6. For a usual sudoku of order 3, 2729 elementary membranes are simultaneously handled. Estimates of the matter content of the observable universe indicate that it contains on the order of 1080 atoms 1, so the brute force algorithm is only a fine calculus for Membrane Computing theory. III. A NEW SOLUTION In this section we present a family of P systems P = {II(n) : n E N} such that II(n) solves sudokus of order n. The P system II (n) receives as input the initial data placed in a sudoku puzzle. It is designed to solve sudokus which satisfy a property which will be described below. If the sudoku satisfies the property, the P system computes the solution, it sends an object Yes to the environment in the last step of computation and encodes the solution to the sudoku as a multiset in the skin of the halting configuration. Otherwise, the P system detects that the property is not satisfied and halts by sending an object No to the environment in the last step of computation. 1 http://en.wikipedia.orglwikilObservable_universe The property is the following: In all partial solutions of the sudoku, there exists at least one square (i, j) with a unique candidate. We will call partial solution of a sudoku to a sudoku grid where some new numbers have been placed and all of them are in the right position. A number p is a unique candidate for the square (i,j) if for all q E {1, ... ,n2}, p =f. q, q has been previously placed in the same row, the same column or the same box of (i, j). For example, if we consider the sudoku of order 2 of Figure 1, number 4 is a unique candidate for the square (1,2), since 1 is in the same row, 2 is in the same column and 3 is in the same box. 4[ 42 43 44 1 2 3[ 32 33 34 3 2[ 22 23 24 1 [[ [2 13 [4 Fig. 1. A sudoku problem of order 2 Many sudokus satisfy this property. It is in the base of many human strategies for solving sudokus. Nonetheless, sometimes it is not enough to solve the sudoku and more sophisticated methods are necessary. A. A Family of P Systems Next, we present a family II = {II(n)}nEN for solving any sudoku of order n verifying the property stated above. Each P system II(n) only depends on the order n of the sudoku and it does not increase the number of membranes along the computation. The used rules are of the following types: • Enzymatic rules: [,in u ----+ vle• The multiset u evolves cat to the multiset v in the membrane with label e. The rule is applied if in the same membrane the objects from the set cat are present (catalysts) and none of the objects from the set in are present (inhibitors). The catalysts and the inhibitor are not modified by the application of the rules and cat, in and v can be empty. • Dissolution rules: [u le ----+ o. The multiset u causes membrane e to dissolve and produces the object o. • Send-out rules: [a le ----+ [le a. The object a is sent out of the membrane with label e. As usual, all the rules are applied in parallel and in a maximal manner. In one step, one object of a membrane can be used by only one rule (chosen in a non deterministic way), but any object which can evolve by one rule of any form, should evolve. If a membrane is dissolved, its content is left free in the surrounding region. If there are objects in this membrane which evolve by means of enzymatic rules and a membrane h is dissolved at the same time, then we suppose that first the enzymatic rules are used and then the dissolution is produced. Of course, this process takes only one step. We will also use priorities among sets of rules. The input will be provided as a set of objects Zijn by denoting that the number n is placed at the square with row i and column j. The initial configuration will also contain information about the box corresponding to each square. In such a way, objects bOXijk with i,j E {I, ... , n2} are place in the initial configuration and k is the box corresponding to the square (i, j), i.e., if i = em + /3 and j = "(n + 5 with a,"( E {O, ... ,n -I} and /3,5 E {l, ... ,n} then k=an+"(+1. The initial configuration also contains the objects fix, Cjx, bkx, Sqij with i,j, k, x E {I, ... , n2}. The occurrence of fix in the configuration denotes that the number x is not placed in any square of the row i yet and then, the number x can be eventually placed in such a row in the future. Analogously, Cjx denotes that x is not placed in the column j and bkx that the object is not placed in any square of the box k. The objects sqij are witnesses of the existence of the corresponding square. Finally, n2 copies of each object rij with i, j E {l, ... , n2} are also placed in the initial configuration. The idea of the design is to develop a sequence of two stages: The checking stage and the reset stage. In the checking stage, the P system looks for squares with a unique candidate. If such squares are found, the candidates are placed in them. After the stage all the auxiliary objects are recalculated in the reset stage and then we start again the checking stage. This checking-reset cycle ends when all the squares are filled and the sudoku is solved or if in a checking stage no new squares with unique candidates are found. Formally, the P system of order n with input that solves the sudokus with the property claimed above is a construct II(n) = (r, H, /1, We, ws, io, R1, R2, R�, Hr, R�, R4, ... ,R11,R}2,RI2) with the priorities Rl > R2 > Rj > R4 > ... Rll > Ri'2 with q E {a, r, m} and x E {I, 2} where • The alphabet r = {Sijx, Zijx, bOXijk, sqij, fix, Cjx, bkx, aij,rij : i,j,k,XE{1, ... ,n2}}U {ko,k1,w} • The set of labels H = {e, s} • The membrane structure /1 = [[ 1 e 1 s • The initial multisets We = {k1}U{boXijk,sqij,Jix,Cjx, bkX,ri'/ : i,j,k,x E {l, ... ,n2}} and Ws = 0. The initial configuration of a P system which solves a concrete sudoku problem also includes the input (encoded with Zijn objects) in the membrane e. • io = e, i.e., the input membrane is e. We also consider the following sets of rules2 Each input object Zijx produces an object Sijx and one object p. In any configuration we will have as many objects p as numbers are correctly placed on the sudoku. After 2We write -, before the object a if a acts as an inhibitor. applying these rules, we have as many objects p as numbers are placed as input. { [fix ---+ Ale } Sijx R2 [Cjx ---+ Ale for i,j,k,x E Sijx [bkx Sijx bOXijk ) Ale {I, ... ,n2}. The object Sijx represents that the number x is placed in the square (i,j). When such an object is generated the objects fix, Cjx and bkx must disappear. Before starting with the checking stage, we ensure that the markers (mijx) and counters (aij and rij) are reset. First, we remove all the copies of aij, mij and rij' In the next step we add n2 copies of each object rij to membrane e. The reset stage ends when object kl (used as catalyst in the previous sets of rules) evolves to ko. i,j,X E{1, ... ,n2}. The checking stage starts with the set R6• We know that if objects fix Cjx bkx are present in membrane e in one configuration, then the number x is a candidate to be placed in the square (i, j), since x has not been placed yet in the row i, the column j or the box k. The question is to know if x is the unique candidate. This is checked by rules from set R6• Before applying these rules, we have checked that for all square (i, j) we have n 2 copies of r ij in membrane e and zero copies of aij' If fix Cjx bkx are present in the membrane (they act as catalyst), then the corresponding rule is applied. The application of the rule removes one copy of rij and produces one copy of aij' The occurrence of mijx ensures that the rule is applied once. If there exists only one aij and n2 - 1 copies of rij (and the square (i,j) is empty) then the square (i,j) has a unique candidate. These rules delete the objects fix Cjx bkx and introduce the objects Sijx, P and w. The object Sijx corresponds to a number and a square in the solution of the sudoku, p denotes that a new number has been placed in the solution (when preaches n2 copies, the cycle reset-checking stops) and w is a witness to the application of the rule. Rs [w ko -+ k2le { [w -+ Ale [kole -+ No If an object w has been produced, it means that at least one of the rules from the set R7 has been applied. In other words, a new number has been placed on the solution of the sudoku and the reset-checking cycle must go on. In this case, objects wand ko are consumed by the rule from Rs and a new object ko is produced. If ko has not been consumed by the rule from Rs, then no new number has been placed on the sudoku. This means that it does not make sense going on with the reset-checking cycle, since the next checking stage will have the same configuration that this one. In order to prevent an infinite sequence of cycles, object ko dissolves membrane e and the remaining objects w (if any) are removed. The copies of p denote the number of squares correctly filled. When it reach n6 copies, the membrane e is dissolved. _ { [d -+ Ale Rll = [k2 -+ klle This set of rules marks the end of the checking stage. The inhibitor d is removed and the catalyst kl is produced so rules from R3 can be triggered and the reset stage starts again. Notice that membrane e is dissolved anyway. If the sudoku is not completed, but no more numbers can be placed, then the rule [kole -+ No is applied and the object No appears in membrane s. Otherwise, if the sudoku is completed, [pn6le -+ Yes is applied and Yes appears in membrane s. In the last step of computation, the corresponding object Yes or No is sent out to the environment. Rl = { [Yesls -+ [ls Yes 12 -[Nols -+ [ls No Also in the last step, the auxiliary objects are removed from membrane S = {[p -+ Als [mijx -+ Als [aij -+ Als Rr2[fix -+ Als [d -+ Als hj -+ Als [Cjx -+ Als [bOXijk -+ Als [k2 -+ Als [bkx -+ Als [sqij -+ Als IV. AN OVERVIEW OF THE COMPUTATION We will give some hints on the computation by following the computation of the example of order two showed in Figure 1. We start with a sudoku problem with 4 numbers placed. Such an input is encoded in the multi set Input = Z311 Z322 Z213 Z141. The initial configuration Co has two mem branes [[le Js. Membrane S is empty and membrane e contains the input plus the objects kl and fix Cjx bkx 8qij bOXijk, T'0 for i,j,k,XE{1, ... ,4}. From this configuration Co, rules from sets R1, R!3 ' R5 and R6 can be applied. Due to priority, rules from Rl are applied and we obtain configuration C1. The objects Zijx are removed and replaced by the corresponding 8ijx. Four copies of object p also appear. This means that four numbers are correctly placed in the sudoku. Rules from Rl will not be applied any more, since no rule produces objects Zijx' From C1 rules of set R2 are applied and IDe objects 131 C11 b31 132 C22 b32 iz3 C13 b13 i11 C41 b21 are removed from membrane e and we obtain configuration C2• Next, rules from R!3 are applied (obtaining C3) and then we apply rules from R4 (obtaining C4). This is the first time that we reset the system, so C4 is identical to C2, but with new objects d. Since membrane e contains objects d, none of the rules from sets R'3 nor from R4 are applicable. The next application of the rule corresponds to R5• The object kl evolves to ko and the checking stage begins. The new configuration C5 contains ko. Since no object mijx has been created yet, for each triplet (i, j, x) such that the number x can be placed in the square (i,j), one of the rules from R6 is triggered, reaching configuration C6• The application of one of these rules removes one copy of the corresponding Tij and produces one copy of aij' Each rule only can be triggered once due to object mijx' After the application of these rules, the number of objects aij denotes the number of possible candidates to be placed in the square (i,j). In the next step, two rules from R7 are triggered and the objects 8124 and 8414 are produced and configuration C7 is reached. After the application of rules from R6, IDe number of objects aij for squares (1,2) and (4,1) is exactly one. This means that for these squares, the candidate is unique. The current partial solution for the sudoku is shown in Figure 2. 4 4[ 42 43 44 1 2 3[ 32 33 34 3 2[ 22 23 24 4 1 [[ [2 13 [4 Fig. 2. Partial solution at configuration C7 The application of rules from R7 has produced two copies of the object w in the configuration C8. One of these copies, along with ko produces kl (Configuration Cg). In the next step IDe remaining w is deleted (Configuration CIO). The checking stage finishes with the application of the rule from RIO. Object d is removed and the configuration C11 is reached. The object d is a strong inhibitor. Since it has disappeared, rules from R3 can be applied and the reset stage starts again. We go on with this new reset stage and the application of three rules from R7 produces the objects 8221. 8423 and 8112. This means that three new numbers can be placed on the sudoku (see Figure 3). 4 3 4[ 42 43 44 1 2 3[ 32 33 34 3 1 2[ 22 23 24 2 4 1 [[ [2 13 [4 Fig. 3. Partial solution at configuration C16 The checking-reset cycle goes on and in C24, the objects 8133 and 8442 are added. In C32, 8431, 8334 and 8244 are added, and finally in C40, IDe objects 8232 and 8343 are generated. Figure 4 shows the solution of IDe sudoku according to the objects 8ijx in membrane e. 4 3 1 2 4[ 42 43 44 1 2 4 3 3[ 32 33 34 3 1 2 4 2[ 22 23 24 2 4 3 1 [[ [2 13 [4 Fig. 4. Solution at configuration C40 The P system follows with the computation and in C42 there are 16 copies of objects p in membrane e. The rule from RIO is triggered, the membrane e is dissolved and all the objects go to membrane 8. In the next step, one objects Yes is sent out and the remaining objects (but 8ijx) are deleted, so the final configuration has an object Yes in IDe environment and one membrane where the solution is encoded. As pointed above, it is possible that for some sudokus there no exist squares with unique candidates. In such cases, when the checking stage is reached, no rule from R7 is applied and no object w is produced. Since we do not have objects w, the rule from R8 is not applied, and according to priority, the dissolution rule from Rg is applied. When an object No is sent to membrane 8, IDe reset-checking cycle is stopped. In the next step an object No is sent out and the computation ends. Notice that we have chosen an example of order 2 for illustrating the process, but the computation is similar for a sudoku problem of any order. V. FINAL REMARKS P systems have showed many times to be versatile enough to represent many different situations, from real life or from more abstract scenarios. In parallel with a very expressive representation system, Membrane Computing also provides a friendly set of tools for dealing with the information. Besides the computational power of the expressiveness, the research in a new computational model also needs to face a problem of efficiency. In this paper we provide a first theoretical solution for the problem of finding a solution to a sudoku problem. It is based on an appropriate representation of the problem as a formula and a well-established solution of the SAT problem. The solution works from a theoretical point of view, but it does not make sense form a practical one. In the second part of the paper, we have designed a solution for solving sudoku problems in an effective way. It solves all the sudokus which verify a very common property, by following a strategy close to human-style solutions. One of the main original contributions of the design is the checking to avoid infinite loops. The implemented strategy is enough to find the solution to many sudoku problems, but it is not enough to solve all of them. The next step is to go on with the research and tackle these hard sudoku problems. Beyond these efforts it is the horizon of a better understanding of the cellular processes and making more and more efficient cellular designs. Acknowledgements The authors acknowledge the support of the projects TIN2008-04487-E and TIN-2009-13192 of the Ministerio de Ciencia e Innovaci6n of Spain and the support of the Project of Excellence with Investigador de Reconocida Valfa of the Junta de Andalucfa, grant P08-TIC-04200. REFERENCES [I] B. Felhenhauer, F. Jarvis, Enumerating possible sudoku grids. Univ. Sheffield and Univ. Dresden, 2005. http://www.shef.ac.uk/ pmlafj/sudoku/sudoku.pdf [2] M.A. Gutierrez-Naranjo, M.A. Martinez-del-Amor, I. Perez-Hurtado, MJ. Perez-Jimenez. Solving the N -Queens Puzzle with P systems. In Seventh Brainstorming Week on Membrane Computing, Vol. I, R. Gutierrez-Escudero, M.A. Gutierrez-Naranjo, Gh. Pliun, Ignacio Perez Hurtado, A. Riscos Nunez, (eds.) Fenix Editora (2009) 199-210. [3] I. Lynce, J.Ouaknine. Sudoku as a SAT Problem. Proceedings of the 9 th International Symposium on Artificial Intelligence and Mathematics, AIMATH 2006, Fort Lauderdale (2006). http://anytime.cs.umass.edu/aimath06/proceedings/ P34.pdf [4] M.J. Perez-Jimenez, A. Romero-Jimenez, F. Sancho-Caparrinini. A polynomial complexity class in P systems using membrane division. In E. Csuhaj-Vruju, C. Kintala, D. Wotschke, G. Vaszil (Eds.). Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, DCFS 2003, Computer and Automaton Research Institute of the Hun garian Academy of Sciences (2003) 284-294. [5] T. Yato and T. Seta. Complexity and Completeness of Finding Another Solution and Its Application to Puzzles. IEICE Trans. Fundamentals, E86-A (5) (2003) 1052-1060. [6] http://www.dellmagazines.com [7] http://www.nikoli.co.jp/puzzles/