# A Hybridalldifferent-Tabu Search Algorithm for Solving Sudoku Puzzles

Authors: Ricardo Soto; Broderick Crawford; Cristian Galleguillos; Fernando Paredes; Enrique Norero
Journal: Computational Intelligence and Neuroscience
 (2015)

---

## Abstract

The Sudoku problem is a well-known logic-based puzzle of combinatorial number-placement. It consists in filling an2×n2 grid, composed of n columns, n rows, and n subgrids, each one containing distinct integers from 1 to n2. Such a puzzle belongs to the NP-complete collection of problems, to which there exist diverse exact and approximate methods able to solve it. In this paper, we propose a new hybrid algorithm that smartly combines a classic tabu search procedure with the alldifferent global constraint from the constraint programming world. The alldifferent constraint is known to be efficient for domain filtering in the presence of constraints that must be pairwise different, which are exactly the kind of constraints that Sudokus own. This ability clearly alleviates the work of the tabu search, resulting in a faster and more robust approach for solving Sudokus. We illustrate interesting experimental results where our proposed algorithm outperforms the best results previously reported by hybrids and approximate methods.


---

## Body

## 1. Introduction

The Sudoku puzzle is a combinatorial problem consisting of assigningn2 digits, from 1 to n2, in each cell matrix of size n2×n2. The matrix is composed of n2 rows, n2 columns, and n2 subgrids of size n×n, as shown in Figure 1.Figure 1
Sudoku puzzle instance: AI Escargot.The problem has a set of simple rules; in each region every digit must be assigned only one time, and hence all digits must be assigned in each cell of each region. Any digit will be repeatedn2 times scattered across the grid but not repeated in same rows, columns, and subgrids. The common size of Sudoku is n=3; thus the puzzle is defined as a 9×9 matrix with nine 3×3 subgrids. Each Sudoku instance starts with some values, called thegivens and the difficulty of the puzzle depends on the positioning of those givens along the matrix. An instance has a unique solution if it contains at least 17 givens [1].During the last years, Sudokus have appeared as interesting problems to test constraint satisfaction and optimization algorithms because of their NP-completeness and different modeling capabilities. In this context, several approaches from different domains have been proposed. For instance, exact methods such as constraint programming [2, 3] and SAT [4] are in general efficient techniques to solve Sudokus. On the approximate methods domain, metaheuristics have proven to be efficient as well [5, 6]. Some hybrids combining exact and approximate methods have also been reported [7, 8], as well as techniques such as Sinkhorn balancing [9], rewriting rules [10], and entropy minimization [11].In this work, we introduce a new hybrid that smartly integrates a global constraint, namely, thealldifferent constraint, in a classic tabu search procedure. Thealldifferent constraint comes from the constraint programming world and has specially been designed for the efficient domain reduction of variables involved in constraints that must be pairwise different. This global constraint works perfectly for Sudokus since all the puzzle constraints can be expressed as a pairwise comparison. We implement thealldifferent constraint following Puget’s approach [12], which identifies Hall intervals [13] and then filters the domains. This allows one to efficiently propagate the constraints, considerably reducing the search space and alleviating the work of the tabu search. As a consequence, the search process is accelerated, while the quality of solutions is maintained. We illustrate interesting experimental results where our proposed algorithm outperforms the best results reported in the literature.This paper is organized as follows. In Section2, we describe the previous work. Section 3 presents the classic tabu search. Thealldifferent constraint is presented in Section 4. The proposed algorithm is presented in Section 5, followed by the corresponding experimental results. Finally, we conclude and give some directions for future work.


## 2. Related Work

In this paper, we concentrate on incomplete search methods, specially on solving hard instances of the puzzle. Within this scenario, different approaches have been suggested, mainly based on metaheuristics. For instance, in [14], the Sudoku puzzles are modeled as a combinatorial optimization problem where the objective function is the minimization of the incorrectly placed numbers on the board. The previous model is solved by using simulated annealing, but the approach is mostly focused on producing valid Sudokus than on the performance of the resolution. In [15], where a particle swarm optimizer (PSO) for solving Sudokus is presented, the goal of authors was to validate the use of geometric operators for PSO for complex combinatorial spaces. In [5], a classic genetic algorithm is tuned with similar geometric operators, particularly Hamming space crossovers and swap space crossovers, reporting good solutions for a hard Sudoku instance. In [16], another GA is presented improving the selection, crossover, and mutation operators. They achieve a better convergence rate and stability with respect to the classic GA. In [8], a hybrid combining AC3 and tabu search is reported, where the idea is to apply AC3 at each iteration of the metaheuristic in order to systematically attempt to reduce the variable domains. A similar approach using cuckoo search is presented in [7], but the AC3 is only employed as a preprocessing phase.In [17], thealldifferent constraint is used to reduce variable domains by overlapping the 27 Sudoku constraints. The approach succeeds for easy instances and some other ones, but in more complex instances the solution is reached with a complete search solver. In Section 6, a comparison of the proposed algorithm with respect to the best results reached by hybrids and approximate methods is given.


## 3. Tabu Search

Tabu search (TS), introduced by Glover [18, 19], is a metaheuristic mainly concerned with combinatorial optimization problems. TS has successfully been employed for working on different kind of real-life problems as well as problems from operation research and computer science, such as the traveling salesman problem, the knapsack problem, and the timetabling problem.TS is based on local search over single solutions, employing a given solutionS as a start point. Then, this starting solution will be improved across small changes, being those solutions called “neighbors” of S, iteratively until some stopping criterion has been reached. The local search moves from neighbor to neighbor as long as possible according to a minimization/maximization of a defined objective function. Normally there exist problems with some moves so that S may be trapped in local optimum where the local search cannot find any further neighborhood solution.To tackle the previous problem, TS makes use of a memory structure named tabu list, which is a feature that distinguishes it from other incomplete methods. The aim of the tabu list is(i)
to evade poor-scoring areas;(ii)
to dodge unpromising areas and return to previously reached ones.Hence, in the tabu list some data is kept of the recently visited solutions, with the aim of avoiding them if these are bad solutions, and so improving the efficiency of the search process. The tabu list is considered the most important feature of TS.Algorithm1 describes the classic procedure of TS. As input, the algorithm receives a primary solution that includes the givens values and an empty cell in the other positions, and as output it returns the best solution scored. At line 3, awhile statement manages the iterations of the process until the defined stop criteria is reached. For instance, the stop condition is a maximum iteration limit or a threshold on the evaluation function. In this implementation, we use as evaluation function the minimization of remaining values to complete the puzzle. At line 7, new potential solutions are created by a neighboring procedure, these solutions are added to the candidate list exclusively if they do not include new solution elements on the tabu list. Then, a promising best candidate is selected on condition which is the best quality solution according to the evaluation by the cost function. At line 11, the cost evaluation of the chosen candidate is compared. If it improves the best solution (Sbest) cost, the differences of those are added to the tabu list and the Scandidate becomes the new Sbest.Algorithm 1:Tabu Search.
Input: S0
Output: Sbest
(1)Sbest←S0
(2)TabuList←∅
(3)While  ¬  Stop  Condition  do
(4)CandidateList←∅
(5)For (Scandidate∈Sbestneighboorhood) do
(6)If  ¬  ContainsAnyFeatures(Scandidate, TabuList)
(7)push(CandidateList, Scandidate)
(8)End If
(9)End For
(10)Scandidate ← LocateBestCandidate(CandidateList)
(11)If  cost(Scandidate) ≤ cost(Sbest)
(12)TabuList ← FeatureDifferences(Scandidate, Sbest)
(13)Sbest←Scandidate
(14)While  TabuList > TabuListsizedo
(15)ExpireFeature(TabuList)
(16)End While
(17)End If
(18)End While
(19)Return  SbestFinally, some features are expired in the tabu list, and generally in the same order they were included, permitting in next iterations to add solutions to the candidate list which contains the expired features.


## 4. CP Overview and thealldifferent Constraint

Constraint programming (CP) is a paradigm for solving combinatorial search and optimization problems mainly from domains such as scheduling, planning, and vehicle routing. In CP, a problem is modeled by relating all involved variables of the problem in constraints terms, and a constraint solver is employed to solve it.CP consists in two identifiable stages:(i)
Modeling: stating constraints involving the problem variables;(ii)
Solving: finding a solution satisfying all the constraints.Hence, all problems are represented in terms of decision variables and constraints, and the aim of the constraint solver is to find an assignment to all the variables that satisfies all the constraints.


### 4.1. Basic Concepts

A Constraint Satisfaction Problem (CSP) is defined by:(i)
A finite set of variables,X=x1,x2,…,xn.(ii)
A domain for each variable,D(X)=D(x1),D(x2),…,D(xn), also noted as d1,d2,…,dn, where di is the domain of xi.(iii)
A finite set of constraintsC(X), where c(x1,…,xn) denotes a constraint involving variables x1,…,xn.A CSP is denoted by the tupleP〈X,D,C〉. A CSP has solution only if every constraint in C is satisfied, and it is called a consistent CSP; further if no solution exists, it is an inconsistent CSP. Algorithms based on backtracking such as the forward checking are in general employed to solve CSPs. [20].


### 4.2.alldifferent Constraint

Thealldifferent constraint commonly appears in problems which are based on permutations or when disjoint paths need to cover a directed graph [21–23], among other problems that involve constraints of pairwise difference. The main ability of this constraint is that it exploits the global information of the problem constraint, instead of handling each pairwise constraint independently. Exploiting the whole information leads to a more efficient domain filtering as explained in [24]. In the following, we provide some necessary definitions.Definition 1.
Ak-ary constraint connecting variables in X with domains D(X) is defined as a subset of the cartesian product ∀d∈D(X) and it is intended as the set of allowed k-tuples for these k variables.A constraint that involves one variable (e.g., 1-ary:x1=8) is called unary constraint and a binary one (e.g., 2-ary: x1≠x2) involves 2 variables, and so on. In general, a k-ary constraint has a scope of size k. A conjunction of several simpler constraints is called a global constraint providing a more simple model for a problem; one of these constraints is the well-knownalldifferent constraint.Thealldifferent constraint is a constraint of difference between all variables involved in the variable relation and specified that the value assigned to the variables must be pairwise different.Definition 2.
Letx1,x2,…,xn be variables with respective finite domains Dx1,Dx2,…,D(xn), then(1)alldifferentx1,…,xn=d1,…,dn∣∀idi∈Dxi,∀i≠jdi≠dj.
Since the introduction of thealldifferent constraint [25], several filtering algorithms have been developed [24], depending on the desired degree of local consistency from “weaker” local consistency with low degree of filtering but short-time to “stronger” with an efficient filtering in a longer runtime. In this work, we employ thealldifferent constraint based on bounds consistency [12] and Hall’s marriage theorem [13]. This implementation provides stronger propagation behavior, checking for exhaustion of all subranges of possible values [24].Definition 3 (bounds consistency).
Letc be a constraint c(x1,x2,…,xn) with n>1; a CSP is bounds consistent if for all variables and each value di from its domain, di∈{minD(xi),maxD(xi)}, there exist values dj∈[minD(xj),maxD(xj)] for all j∈{1,…,n}-i such that (d1,d2,…,dn)∈C. minD and maxD represent the minimum and maximum value, respectively, from the domain D.Definition 4 (Hall’s theorem).
LetX be a set of variables and D the corresponding finite variable domains. Suppose G is a bipartite graph with bipartition (X,D). There exists a matching that covers X if and only if for every subset I⊆D, DI≤I is fulfilled. Then I is called a Hall interval if I=KI with KI={xi∣Di⊆I}.Theorem 5.
The constraintalldifferent(x1,…,xn) is bounds consistent if and only if {di≥1∣∀di∈D} and(i)
for each intervalI: |I|≥|KI|,(ii)
for each Hall intervalI:{minDi,maxDi}∩I=∅;∀xi∉KI.Proof.
We proceed by induction, observing that the caseI=1 obviously holds, because all domains are greater than 1. Let I be a Hall interval and xi∉KI. Ifalldifferent(x1,x2,…,xn) is bounds consistent, it has a solution when xi=minDi, by Definition 3.Example 6.
Consider the following CSP which is represented in Figure2: (2)x1∈1,2,x2∈1,2,x3∈1,2,3,x4∈1,2,4alldifferentx1,x2,x3,x4.
In order to make bounds consistency of the CSP, the inconsistent values must be removed. The algorithm founds Hall intervals, in this case when the interval is set to{1,2}. Since |I|=2 and to satisfy the theorem, I:{minDi,maxDi}∩I=∅, the interval must be removed from x3 and x4 domains.
The new domains for all variables will be(3)x1∈1,2,x2∈1,2,x3∈3,x4∈4.Figure 2
Example ofalldifferent constraint through Hall’s theorem approach.In summary, there exists a solution to analldifferent constraint if and only if for each subset of variables, the union of their domains holds the adequate values to match every one of them with a distinct value. In the previous example, when the Hall interval is set to I={1,2}, being represented by green and red lines, we note that the values from x1 and x2 domains cannot be assigned to any other variable. Hence, the values of the interval I are removed from x3 and x4 variables. The reduced domains are only sets with feasible values with respect to all constraints.Example 7.
We illustrate with another example applying thealldifferent constraint on the most difficult Sudoku instance, and it is called AI Escargot ([28]). Each Sudoku instance is composed of three types of constraints: row, columns, and subgrid. We begin by enforcing thealldifferent constraint on the rows of the Sudoku puzzle. We have used just 3 constraints corresponding to the first three Sudoku rows (enclosed with dashed lines in Figure 3) instead of the nine ones in order to simplify the illustration, but the filtering technique is applied to all constraints.
After applying thealldifferent constraint from the first to third rows, the domains are only reduced but no value is discovered due the difficulty of the instance. The values deleted from the reduced domains did not satisfy the constraint; they have been already taken for another cell on the same row.
In Figure4, thealldifferent constraint is applied to columns of the puzzle. Only the first three columns are shown.
In Figure5, thealldifferent constraint is applied to the subgrids of the puzzle; the reduced domains by the previous domain filterings are used. At this point, the overall domain size of the subgrid has been reduced from 57 elements to 20, being more than 64% of domain reduction, significantly decreasing the amount of possible assignments.Figure 3
alldifferent constraint applied to the rows of AI Escargot instance. Only the first three rows are shown.Figure 4
alldifferent constraint applied to the columns of the AI Escargot instance, using the reduced domains of variables in common with the previous reduced ones. Only the first three columns are shown.Figure 5
alldifferent constraint applied to the subgrids of AI Escargot instance, using the reduced domains of variables in common with the previous reduced ones. Only the first subgrid is shown.


## 4.1. Basic Concepts

A Constraint Satisfaction Problem (CSP) is defined by:(i)
A finite set of variables,X=x1,x2,…,xn.(ii)
A domain for each variable,D(X)=D(x1),D(x2),…,D(xn), also noted as d1,d2,…,dn, where di is the domain of xi.(iii)
A finite set of constraintsC(X), where c(x1,…,xn) denotes a constraint involving variables x1,…,xn.A CSP is denoted by the tupleP〈X,D,C〉. A CSP has solution only if every constraint in C is satisfied, and it is called a consistent CSP; further if no solution exists, it is an inconsistent CSP. Algorithms based on backtracking such as the forward checking are in general employed to solve CSPs. [20].


## 4.2.alldifferent Constraint

Thealldifferent constraint commonly appears in problems which are based on permutations or when disjoint paths need to cover a directed graph [21–23], among other problems that involve constraints of pairwise difference. The main ability of this constraint is that it exploits the global information of the problem constraint, instead of handling each pairwise constraint independently. Exploiting the whole information leads to a more efficient domain filtering as explained in [24]. In the following, we provide some necessary definitions.Definition 1.
Ak-ary constraint connecting variables in X with domains D(X) is defined as a subset of the cartesian product ∀d∈D(X) and it is intended as the set of allowed k-tuples for these k variables.A constraint that involves one variable (e.g., 1-ary:x1=8) is called unary constraint and a binary one (e.g., 2-ary: x1≠x2) involves 2 variables, and so on. In general, a k-ary constraint has a scope of size k. A conjunction of several simpler constraints is called a global constraint providing a more simple model for a problem; one of these constraints is the well-knownalldifferent constraint.Thealldifferent constraint is a constraint of difference between all variables involved in the variable relation and specified that the value assigned to the variables must be pairwise different.Definition 2.
Letx1,x2,…,xn be variables with respective finite domains Dx1,Dx2,…,D(xn), then(1)alldifferentx1,…,xn=d1,…,dn∣∀idi∈Dxi,∀i≠jdi≠dj.
Since the introduction of thealldifferent constraint [25], several filtering algorithms have been developed [24], depending on the desired degree of local consistency from “weaker” local consistency with low degree of filtering but short-time to “stronger” with an efficient filtering in a longer runtime. In this work, we employ thealldifferent constraint based on bounds consistency [12] and Hall’s marriage theorem [13]. This implementation provides stronger propagation behavior, checking for exhaustion of all subranges of possible values [24].Definition 3 (bounds consistency).
Letc be a constraint c(x1,x2,…,xn) with n>1; a CSP is bounds consistent if for all variables and each value di from its domain, di∈{minD(xi),maxD(xi)}, there exist values dj∈[minD(xj),maxD(xj)] for all j∈{1,…,n}-i such that (d1,d2,…,dn)∈C. minD and maxD represent the minimum and maximum value, respectively, from the domain D.Definition 4 (Hall’s theorem).
LetX be a set of variables and D the corresponding finite variable domains. Suppose G is a bipartite graph with bipartition (X,D). There exists a matching that covers X if and only if for every subset I⊆D, DI≤I is fulfilled. Then I is called a Hall interval if I=KI with KI={xi∣Di⊆I}.Theorem 5.
The constraintalldifferent(x1,…,xn) is bounds consistent if and only if {di≥1∣∀di∈D} and(i)
for each intervalI: |I|≥|KI|,(ii)
for each Hall intervalI:{minDi,maxDi}∩I=∅;∀xi∉KI.Proof.
We proceed by induction, observing that the caseI=1 obviously holds, because all domains are greater than 1. Let I be a Hall interval and xi∉KI. Ifalldifferent(x1,x2,…,xn) is bounds consistent, it has a solution when xi=minDi, by Definition 3.Example 6.
Consider the following CSP which is represented in Figure2: (2)x1∈1,2,x2∈1,2,x3∈1,2,3,x4∈1,2,4alldifferentx1,x2,x3,x4.
In order to make bounds consistency of the CSP, the inconsistent values must be removed. The algorithm founds Hall intervals, in this case when the interval is set to{1,2}. Since |I|=2 and to satisfy the theorem, I:{minDi,maxDi}∩I=∅, the interval must be removed from x3 and x4 domains.
The new domains for all variables will be(3)x1∈1,2,x2∈1,2,x3∈3,x4∈4.Figure 2
Example ofalldifferent constraint through Hall’s theorem approach.In summary, there exists a solution to analldifferent constraint if and only if for each subset of variables, the union of their domains holds the adequate values to match every one of them with a distinct value. In the previous example, when the Hall interval is set to I={1,2}, being represented by green and red lines, we note that the values from x1 and x2 domains cannot be assigned to any other variable. Hence, the values of the interval I are removed from x3 and x4 variables. The reduced domains are only sets with feasible values with respect to all constraints.Example 7.
We illustrate with another example applying thealldifferent constraint on the most difficult Sudoku instance, and it is called AI Escargot ([28]). Each Sudoku instance is composed of three types of constraints: row, columns, and subgrid. We begin by enforcing thealldifferent constraint on the rows of the Sudoku puzzle. We have used just 3 constraints corresponding to the first three Sudoku rows (enclosed with dashed lines in Figure 3) instead of the nine ones in order to simplify the illustration, but the filtering technique is applied to all constraints.
After applying thealldifferent constraint from the first to third rows, the domains are only reduced but no value is discovered due the difficulty of the instance. The values deleted from the reduced domains did not satisfy the constraint; they have been already taken for another cell on the same row.
In Figure4, thealldifferent constraint is applied to columns of the puzzle. Only the first three columns are shown.
In Figure5, thealldifferent constraint is applied to the subgrids of the puzzle; the reduced domains by the previous domain filterings are used. At this point, the overall domain size of the subgrid has been reduced from 57 elements to 20, being more than 64% of domain reduction, significantly decreasing the amount of possible assignments.Figure 3
alldifferent constraint applied to the rows of AI Escargot instance. Only the first three rows are shown.Figure 4
alldifferent constraint applied to the columns of the AI Escargot instance, using the reduced domains of variables in common with the previous reduced ones. Only the first three columns are shown.Figure 5
alldifferent constraint applied to the subgrids of AI Escargot instance, using the reduced domains of variables in common with the previous reduced ones. Only the first subgrid is shown.


## 5. Proposed Algorithm

The main idea of the proposed algorithm (Algorithm2) is to employ thealldifferent constraint so as to filter the concerned variable domains as a preprocessing phase (line 1) and at every iteration of the Tabu search (line 9). Thealldifferent constraint is applied iteratively over all structures of the grid (rows, columns, and subgrids). In the preprocessing phase and within each iteration some values are deleted from unfeasible regions, easing the work of the search process of the metaheuristic.Algorithm 2:Hybrid alldifferent-Tabu search.
Input: D,C
Output: Sbest
(1)Sbest,D ← alldifferent(D,C)
(2)tabuList ← ∅
(3)While  ¬  Stop Condition  do
(4)CandidateList ← ∅
(5)While Len(CandidateList) ≤ LengthCandidateListdo
(6)push(CandidateList, CandidateGenerator(Sbest, D))
(7)End While
(8)Scandidate ← LocateBestCandidate(CandidateList)
(9)Scandidate,D ← alldifferent(DScandidate,C)
(10)If  cost(Scandidate) ≤ cost(Sbest)
(11)TabuList ← FeatureDifferences(Scandidate,Sbest)
(12)Sbest←Scandidate
(13)While  TabuList>TabuListsize  do
(14) ExpireFeature(TabuList)
(15)End While
(16)End If
(17)End While
(18)Return  SbestAt line 6, we have limited the search neighboring procedure to assignments from the filtered domain. The randomization is still used, but just for randomizing the value selection of filtered values.As stop condition (line 3), we use the full coverage of the grid, and it means that solution is found and a maximum of iterations which has been fixed to 10,000.As output, the procedure returnsSbest, which is the outstanding solution achieved by the algorithm.


## 6. Experimental Results

In this section, we present a performance evaluation of the proposed algorithm to solve Sudokus. The tested benchmarks are classified in diverse kinds of complexity, including the AI Escargot which is considered the most difficult instance [28]. A useful difficulty classification including easy, medium, and hard Sudoku instances has been proposed in [26]. Here, we extend this classification in order to incorporate additional instances reported in the literature [29, 30]. The reclassification is depicted in Table 1. All difficulty classification groups have 3 instances (a, b, and c) per subgroup, except for the AI Escargot which is a single instance. All instances have unique solution.Table 1
Difficulty of tested instances.
Authors
Difficulty groups
Easy
Medium
Difficult
Most difficult
[26]
1, 2
3, 4, 5
—
—
E
C, D
SD
—
[27]
Easy
Medium
Hard
—
[28]
—
—
—
AI EscargotFirstly, we have compared the filtering technique used in previous work [7, 8]. As mentioned before, this phase is very important and useful to reduce the search space, consequently facilitating the metaheuristic work. The filtering technique employed was arc consistency-3 (AC-3) [31]. AC-3 examines the arcs between pairs of variables and removes those values from the domains which are not consistent with the involved constraints. If a domain of a variable changes, the involved arcs of the variable, which its domain has been recently reduced, are examined again to check the arc consistency of the reduced domain.Table2 illustrates the percentage of domain reduction for each Sudoku instance. The results exhibit the fact that thealldifferent constraint outperforms the AC-3 algorithm in terms of filtering capabilities. This is produced due to the ability of thealldifferent constraint to employ the global information of the pairwise constraints instead of handling the constraints independently as the AC3 does. Let us note that the ability to infer a greater number of elements which do not belong to the domain of the problem solution depends only on the problem constraints. Thealldifferent constraint and the characteristics of the problem, X=n, enable the use of Hall’s theorem to infer the reduction of domains until each domain variable has one element (in the best case) by eliminating the elements of the domains in which they never be part of any (the only) solution.Table 2
Comparison of effectiveness by filtering techniques.
Difficulty group
Difficulty subgroup
% Domain reduction
% Domain reduction
a
lldifferent
AC-3
a
b
c
a
b
c
Easy
1
100%
100%
100%
100%
100%
100%
2
100%
100%
100%
79%
100%
100%
E
100%
100%
100%
100%
100%
100%
Easy
100%
100%
100%
100%
100%
100%
Medium
3
100%
100%
89%
92%
74%
82%
4
86%
100%
82%
75%
75%
76%
5
87%
100%
80%
73%
74%
79%
C
100%
100%
100%
88%
100%
100%
D
75%
100%
100%
68%
73%
77%
Medium
100%
100%
100%
81%
78%
76%
Difficult
SD
80%
80%
84%
69%
68%
68%
Hard
68%
87%
100%
66%
74%
68%
Most difficult
AI Escargot
71%
70%Table3 depicts the required runs to successfully solve 30 times each Sudoku instance considering 10,000 iterations as limit. The symbol ↑50 indicates that more than 50 runs are needed to successfully solve 30 times the instance. We contrast the proposed approach with the best performing algorithms reported in the literature (AC3-TS [8], AC3-CS [7], and GA [26, 29]). The results for easy instances show no relevant differences. However, for medium, SD, and hard instances, the performance of the proposedalldiff-TS is greatly better.Table 3
Solving Sudokus considering 10,000 iterations as maximum.
Difficulty group
Difficulty subgroup
Tries
Tries
Tries
Tries
a
lldiff-TS
AC3-TS
AC3-CS
GA
a
b
c
a
b
c
a
b
c
a
b
c
Easy
1
30
30
30
30
30
30
30
30
30
—
—
—
2
30
30
30
30
30
30
↑ 50
30
30
—
—
—
E
30
30
30
30
30
30
30
30
30
—
—
—
Easy
30
30
30
30
30
30
30
30
30
30
30
30
Medium
3
30
30
30
30
30
30
48
↑ 50
↑ 50
—
—
—
4
30
30
30
30
30
30
↑ 50
↑ 50
↑ 50
—
—
—
5
30
30
30
30
30
30
↑ 50
↑ 50
↑ 50
—
—
—
C
30
30
30
30
30
30
—
—
—
—
—
—
D
30
30
30
41
30
30
—
—
—
—
—
—
Medium
30
30
30
30
30
30
↑ 50
↑ 50
↑ 50
22
—
—
Difficult
SD
30
30
30
30
30
↑ 50
—
—
—
—
—
—
Hard
30
30
30
30
30
46
↑ 50
↑ 50
—
2
—
—
Most difficult
AI Escargot
30
30
—
—Table4 contrasts the proposed approach with AC3-TS, which is the best performing one from previously reported approaches. We compare the minimum, average, and maximum iterations needed to successfully solve each Sudoku instance. We consider 30 runs for each instance. The results exhibit the fact thatalldiff-TS achieves the constraint satisfaction of all tested instances requiring considerable less iterations than AC3-TS (A graphical comparison can be seen in Figures 6, 7, and 8). Let us remark that TS has a high participation in the search process and the work is not only done by the filtering technique.Table 4
Iterations needed (minimum, average, maximum, and standard deviation) considering 30 runs.
Difficulty group
Difficulty  subgroup
Iterations
a
lldiff-TS
AC3-TS
Minimum
Average
Maximum
σ
Minimum
Average
Maximum
σ
Easy
1
1
1
1
0
1
1
1
0
2
1
1
1
0
1
7.4
58
11.7
E
1
1
1
0
1
1
1
0
Easy
1
1
1
0
1
1
1
0
Medium
3
1
2.0
7
1.6
3
90.2
897
140.5
4
1
13.1
95
23.5
2
163.3
1,318
226.3
5
1
20
276
45.0
5
143.9
1,778
230.4
C
1
1
1
0
1
4.0
29
6.0
D
1
27.2
424
64.5
5
1,897.6
9,088
2,214.3
Medium
1
1
1
0
5
138.8
865
173.9
Difficult
SD
3
51.5
298
68.8
10
5,005.6
29,329
7,358.1
Hard
1
195.0
1881
397.0
4
1,872.4
7,590
2,217.6
Most difficult
AI Escargot
52
1,248.3
6,328
1,378.6
57
2,566.7
7,224
2,076.6Figure 6
Comparing minimum needed iterations for Sudoku solving.Figure 7
Comparing maximum needed iterations for Sudoku solving.Figure 8
Comparing average needed iterations for Sudoku solving and their standard deviations.


## 7. Conclusion and Future Work

In this paper, we have presented a new hybrid that integrates the powerfulalldifferent constraint into a classic tabu search algorithm. Thealldifferent constraint is employed to efficiently delete the values from domains that do not conduct to any feasible solution. The role of this filter is to act prior to the TS procedure but also in the search cycle, which permits progressive filtering of the best solutions. This allows us to relieve the work of the metaheuristic in order to achieve faster solving processes. We have carried out a set of experiments in order to contrast our approach with the best performing approximate methods and hybrids reported in the literature. We have considered different complexity instance Sudokus, including the AI Escargot which is considered the most difficult one. The result has exhibited encouraging results, where the proposed approach noticeably outperforms the previous algorithms reported in the literature.A clear direction for future work is to study the integration of thealldifferent constraint on additional metaheuristics and to contrast performance. Particularly, the addition of global constraints on a cuckoo search [32] algorithm would be a promising hybrid, given the fact that CS algorithm has exhibited great performance and has already been combined with filtering techniques. Another interesting research direction will be the study of variations of the classicalldifferent constraint working in conjunction with approximate methods. An example is thesymm  alldifferent constraint [24], which will be useful in the resolution of the well-known round-robin tournament.



---

*Source: 286354-2015-05-20.xml*