A Cellular Sudoku Solver

A Cellular Sudoku Solver Daniel D´ıaz-Pernil, Carlos M. Fern´andez-M´arquez, Manuel Garc´ıa-Quismondo, Miguel A. Guti´errez-Naranjo, Miguel A. Mart´ınez-del-Amor Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012, Sevilla, Spain [email protected], [email protected], [email protected], [email protected], [email protected] Summary. 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 sudoku puzzles 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. 1 Introduction Sudoku is currently one of the most famous puzzles in the world. The most popular version consists on a 9 ×9 grid made up of 3×3 subgrids, but the general case, an n2×n2grid with n×nsubgrids 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 n2in 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, sudoku has important properties from a mathematical point of view. The first natural question is to won- 78 D. D´ıaz-Pernil et al. der 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×ntable filled by using numbers from 1 to nin such way that each symbol occurs exactly once in each row and exactly once in each column. The number of 9×9 Latin squares is about 5.525 ×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 ×9 grid is 6,670,903,752,021,072,936,960. This number is equal to 9! ×722×27× 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×n2grids of n×nboxes 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 ×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 {Π(n)}n∈N such that Π(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 theoretical 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. A Cellular Sudoku Solver 79 2 A Brute Force Algorithm Asudoku square of order nconsists of n4constants (usually n2copies of the numbers 1,2, . . . , n2), arranged into an n2×n2grid which comprises n2subgrids of size n×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 ncan be represented as an instance of the SAT problem with n6propositional variables. For each entry in the n2×n2grid, we will consider n2variables. Let us use the notation sxyz to refer to variables. Variable sxyz is assigned true if and only if the entry in the row xand column yis number z. In 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: ψ1≡ n2 ^ x=1 n2 ^ y=1 n2 _ z=1 sxyz •Each number appears at most once in each row: ψ2≡ n2 ^ y=1 n2 ^ z=1 n2−1 ^ x=1 n2 ^ i=x+1 (¬sxyz ∨ ¬siyz) •Each number appears at most once in each column: ψ3≡ n2 ^ x=1 n2 ^ z=1 n2−1 ^ y=1 n2 ^ i=y+1 (¬sxyz ∨ ¬sxiz) •Each number appears at most one in each box: ψ4≡ n2 ^ z=1 n−1 ^ i=0 n−1 ^ j=0 n ^ x=1 n ^ y=1 n ^ k=y+1 (¬s(ni+x)(nj+y)z∨ ¬s(ni+x)(nj+k)z) ψ5≡ n2 ^ z=1 n−1 ^ i=0 n−1 ^ j=0 n ^ x=1 n ^ y=1 n ^ k=x+1 n ^ l=1 (¬s(ni+x)(nj+y)z∨ ¬s(ni+k)(nj+l)z) The conjunction of these five formulae Φ≡ψ1Vψ2Vψ3Vψ4Vψ5is a formula in conjunctive normal form and each truth assignment which makes it true represents a right arrangement of n2copies of 1,2, . . . , n2according to the sudoku constraints. 80 D. D´ıaz-Pernil et al. 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 n2copies of 1,2, . . . , n2according 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 ={hx, y, zi:zis 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 Φas follows: Φin ≡Φ∧^ hx,y,zi)∈Input sxyz Given a sudoku problem and its associated formula Φin, 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 obstacle from a practical point of view: The number of elementary membranes in one configuration of one P system from the family reaches 2N, where Nis 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 atoms1, so the brute force algorithm is only a fine calculus for Membrane Computing theory. 3 A New Solution In this section we present a family of P systems P={Π(n) : n∈N}such that Π(n) solves sudokus of order n. The P system Π(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 1http://en.wikipedia.org/wiki/Observable universe A Cellular Sudoku Solver 81 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. 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 pis a unique candidate for the square (i, j) if for all q∈ {1, . . . , n2},p6=q,qhas 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. 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44 1 3 1 2 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. 3.1 A Family of P Systems Next, we present a family Π={Π(n)}n∈Nfor solving any sudoku of order n verifying the property stated above. Each P system Π(n) only depends only on the order nof 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 −−→ cat v]e. The multiset uevolves to the multiset vin 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 vcan be empty. •Dissolution rules: [u]e→o. The multiset ucauses membrane eto dissolve and produces the object o. 82 D. D´ıaz-Pernil et al. •Send-out rules: [a]e→[ ]ea. The object ais 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 his 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 nis placed at the square with row iand 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 ∈ {1, . . . , n2}are place in the initial configuration and kis the box corresponding to the square (i, j), i.e., if i=αn +βand j=γn +δ with α, γ ∈ {0, . . . , n −1}and β, δ ∈ {1, . . . , n}then k=αn +γ+ 1. The initial configuration also contains the objects fix,cjx,bkx,sqij with i, j, k, x ∈ {1, . . . , n2}. The occurrence of fix in the configuration denotes that the number xis not placed in any square of the row iyet and then, the number x can be eventually placed in such a row in the future. Analogously, cjx denotes that xis not placed in the column jand 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, n2copies of each object rij with i, j ∈ {1, . . . , 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 nwith input that solves the sudokus with the property claimed above is a construct Π(n) = hΓ, H, µ, we, ws, i0, R1, R2, Ra 3, Rm 3, Rd 3, R4, . . . , R11, R1 12, R2 12i with the priorities R1> R2> Rq 3> R4> . . . R11 > Rx 12 with q∈ {a, r, m}and x∈ {1,2}where •The alphabet Γ={sijx, zijx, boxijk, sqij, fix, cjx, bkx, aij , rij :i, j, k, x ∈ {1, . . . , n2} } ∪ {k0, k1, w} •The set of labels H={e, s} •The membrane structure µ= [ [ ]e]s •The initial multisets we={k1}∪{boxijk, sqij , fix, cjx, bkx, rn2 ij :i, j, k, x ∈ {1, . . . , n2} } and ws=∅. A Cellular Sudoku Solver 83 •i0=e, i.e., the input membrane is e. We also consider the following sets of rules2 R1≡[zijx →sijx p]efor i, j, x ∈ {1, . . . , n2}. Each input object zijx produces an object sijx and one object p. In any configuration we will have as many objects pas numbers are correctly placed on the sudoku. After applying these rules, we have as many objects pas numbers are placed as input. R2≡       [fix −−→ sijx λ]e [cjx −−→ sijx λ]e [bkx −−−−−−−→ sijx boxijk λ]e        for i, j, k, x ∈ {1, . . . , n2}. The object sijx represents that the number xis placed in the square (i, j). When such an object is generated the objects fix,cjx and bkx must disappear. Rm 3≡[¬d mijx −→ k1 λ]e Ra 3≡[¬d aij −→ k1 λ]e Rr 3≡[¬d rij −→ k1 λ]e        for i, j, x ∈ {1, . . . , n2}. R4≡[¬d¬rijsqij −→ k1 sqij rn2 ij d]efor i, j ∈ {1, . . . , n2}. 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 n2copies of each object rij to membrane e. R5≡[k1→k0]e The reset stage ends when object k1(used as catalyst in the previous sets of rules) evolves to k0. R6≡[¬mijx rij −−−−−−−−−−−→ fix cjx bkx boxijk mijx aij]efor i, j, x ∈ {1, . . . , n2}. The checking stage starts with the set R6. We know that if objects fix cjx bkx are present in membrane ein one configuration, then the number xis a candidate to be placed in the square (i, j), since xhas not been placed yet in the row i, the column jor the box k. The question is to know if xis 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 n2copies of rij in membrane eand zero copies of aij. If fix cjx bkx are present in the membrane (they act as catalyst), then the 2We write ¬before the object aif aacts as an inhibitor. 84 D. D´ıaz-Pernil et al. 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. R7≡[¬sijq rn2−1 ij aijfix cjx bkx −−−−−→ d boxijk sijx p w]ei, j, x, q ∈ {1, . . . , n2}. 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. The rules delete the objects fix cjx bkx and introduce the objects sijx,pand w. The object sijx corresponds to a number and a square in the solution of the sudoku, pdenotes that a new number has been placed in the solution (when preaches n2copies, the cycle reset-checking stops) and wis a witness of the application of the rule. R8≡[w k0→k2]e R9≡½[w→λ]e [k0]e→No If an object whas been produced, it means that at least one of the rules from the set R7has 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 k0are consumed by the rule from R8and a new object k0is produced. If k0has not been consumed by the rule from R8, 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 k0dissolves membrane eand the remaining objects w(if any) are removed. R10 ≡[pn6]e→Yes The copies of pdenote the number of squares correctly filled. When it reach n6copies, the membrane eis dissolved. R11 ≡½[d→λ]e [k2→k1]e This set of rules marks the end of the checking stage. The inhibitor dis removed and the catalyst k1is produced so rules from R3can be triggered and the reset stage starts again. Notice that membrane eis dissolved anyway. If the sudoku is not completed, but no more numbers can be placed, then the rule [k0]e→No is applied and the object No appears in membrane s. Otherwise, if the sudoku is completed, [pn6]e→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. A Cellular Sudoku Solver 85 R1 12 ≡½[Yes]s→[ ]sYes [No]s→[ ]sNo Also in the last step, the auxiliary objects are removed from membrane s R2 12 ≡       [p→λ]s[mijx →λ]s[aij →λ]s [fix →λ]s[d→λ]s[rij →λ]s [cjx →λ]s[boxijk →λ]s[k2→λ]s [bkx →λ]s[sqij →λ]s 4 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 multiset Input = z311 z322 z213 z141. The initial configuration C0has two membranes [ [ ]e]s. Membrane sis empty and membrane econtains the input plus the objects k1and fix cjx bkx sqij boxijk, r4 ij for i, j, k, x ∈ {1,...,4}. From this configuration C0, rules from sets R1,Rr 3,R5and R6can be applied. Due to priority, rules from R1are applied and we obtain configuration C1. The objects zijx are removed and replaced by the corresponding sijx. Four copies of object palso appear. This means that four numbers are correctly placed in the sudoku. Rules from R1will nor be applied any more, since no rule produces objects zijx. From C1rules of set R2are applied and the objects f31 c11 b31 f32 c22 b32 f23 c13 b13 f11 c41 b21 are removed from membrane eand we obtain configuration C2. Next, rules from Rr 3are applied (obtaining C3) and then we apply rules from R4(obtaining C4). This is the first time that we reset the system, so C4is identical to C2, but with new objects d. Since membrane econtains objects d, none of the rules from sets R∗ 3nor from R4are applicable. The next application of the rule corresponds to R5. The object k1evolves to k0and the checking stage begins. The new configuration C5contains k0. Since no object mijx has been created yet, for each triplet (i, j, x) such that the number xcan be placed in the square (i, j), one of the rules from R6is triggered, reaching configuration C6. The application of one of these rules removes one copy of the corresponding rij 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 R7are triggered and the objects s124 and s414 are produced and configuration C7is reached. After the application of rules from R6, the number of objects aij for squares (1,2) and (4,1) was exactly one. This means that for these squares, the candidate is unique. The current partial solution for the sudoku is shown in Figure 2.