# A Prefiltered Cuckoo Search Algorithm with Geometric Operators for Solving Sudoku Problems

Authors: Ricardo Soto; Broderick Crawford; Cristian Galleguillos; Eric Monfroy; Fernando Paredes
Journal: The Scientific World Journal
 (2014)

---

## Abstract

The Sudoku is a famous logic-placement game, originally popularized in Japan and today widely employed as pastime and as testbed for search algorithms. The classic Sudoku consists in filling a9
×
9 grid, divided into nine 3
×
3 regions, so that each column, row, and region contains different digits from 1 to 9. This game is known to be NP-complete, with existing various complete and incomplete search algorithms able to solve different instances of it. In this paper, we present a new cuckoo search algorithm for solving Sudoku puzzles combining prefiltering phases and geometric operations. The geometric operators allow one to correctly move toward promising regions of the combinatorial space, while the prefiltering phases are able to previously delete from domains the values that do not conduct to any feasible solution. This integration leads to a more efficient domain filtering and as a consequence to a faster solving process. We illustrate encouraging experimental results where our approach noticeably competes with the best approximate methods reported in the literature.


---

## Body

## 1. Introduction

The Sudoku is a logic-based placement puzzle, widely present as pastime game in newspapers and magazines. It was initially popularized in Japan during the eighties, but today it is a worldwide popular game and a useful benchmark for testing artificial intelligence solving techniques. A Sudoku puzzle consists in filling a board of9
×
9 subdivided into subgrids of size 3
×
3 so that each row, column, and subgrid contains different digits from 1 to 9. A Sudoku problem includes prefilled cells, namely, the “givens,” which cannot be changed or moved (see Figure 1). Certainly, the amount of givens has limited or no impact on the difficulty of the problem. The difficulty is mostly dependent on the positioning of the givens along the puzzle. A useful difficulty classification including easy, medium, and hard Sudokus has been proposed by Mantere and Koljonen [1].Figure 1
Sudoku puzzle instance.The literature reports various approaches to solve Sudoku puzzles. For instance, exact methods such as constraint programming [2–4] and boolean satisfiability [5] are well-known candidates for the efficient handling of such kind of puzzles. In the context of approximate methods, genetic programming [1] and metaheuristics in general [6–10] have illustrated promising results. Additional, but less traditional, Sudoku solving techniques have been proposed as well, such as Sinkhorn balancing [11], rewriting rules [12], and entropy minimization [13].In this paper, we focus on approximate methods. We propose a new algorithm for the efficient solving of Sudoku instances based on cuckoo search, geometric operators, and prefiltering phases. The cuckoo search is a relatively modern nature-inspired metaheuristic [14–18] to which we introduce geometric operators in order to correctly move to promising regions of a discrete space of solutions. This combination is additionally enhanced with a domain reducer component based on local consistencies. The idea is to previously delete from the search space the values that do not conduct to any feasible solution. This integration straightforwardly alleviates the work of the metaheuristic leading to a faster solving process. We illustrate encouraging experimental results where our approach noticeably competes with the best approximate methods reported in the literature.This paper is organized as follows. In Section2, we describe the previous work. Section 3 presents the classic cuckoo search algorithm. The geometric operators and the prefiltering phase employed are illustrated and exemplified in Sections 4 and 5, respectively. The resulting new cuckoo search algorithm is presented in Section 6, followed by the corresponding experimental results. Finally, in Section 8, we conclude and give some directions for future work.


## 2. Related Work

Sudoku puzzles have been solved with various techniques during the last decades. For instance, complete methods such as Boolean satisfiability and constraint satisfaction can clearly be used to solve Sudokus [3–5, 19]. In this paper, we focus on incomplete search methods, specially on solving hard instances of such a puzzle. Within this scenario, different solutions have been suggested, mainly based on metaheuristics. For instance, Lewis [7] models the puzzle as an optimization problem where the number of incorrectly placed digits on the board must be minimized. The 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 [10], an ant colony algorithm is proposed, where the problem is modeled in an opposite form: maximizing the number of correctly filled cells. The best result completes only 76 out of 81 cells of the puzzle. In [8], a particle swarm optimizer (PSO) for solving Sudokus is presented, but the goal of authors was rather to validate the use of geometric operators in PSO for complex combinatorial spaces.In [6], a hill-climbing algorithm for Sudokus is reported. The approach succeeds in solving easy Sudoku instances, failing for medium and hard ones. In the same work, a genetic algorithm (GA) outperforms the hill-climber previously presented. Such a GA is tuned with geometric operators, in particular Hamming space crossovers and swap space crossovers, reporting solutions for a hard Sudoku. In Mantere and Koljonen [1], another GA is proposed that succeeds for easy and medium instances, but it only reaches the optimum in 2 out of 30 tries for a hard Sudoku. A cultural algorithm is proposed by the same authors [9], but it is generally outperformed by the GA previously reported. In Soto et al. [20], a tabu search is tuned with a prefiltered phase, being capable of solving 30 out of 30 tries for a hard Sudoku.


## 3. Cuckoo Search

Cuckoo search is a nature-inspired metaheuristic, based on the principle of the brood parasitism of some cuckoo species. This kind of bird has an aggressive reproduction strategy, which is based on the use of foreign nests for incubation. Cuckoos proceed by laying their eggs in nests from other bird species, removing the other bird eggs to increase incubation probability. Eventually, cuckoo eggs may be discovered by the host bird, which might act in two ways: taking off the alien eggs or simply abandoning its nest and building a new one elsewhere. In practice, an egg represents a solution and cuckoo eggs represent potentially better solutions than the current ones in nests. In the simplest form each nest has only one egg.The cuckoo search procedure for minimization is described in Algorithm1. The process begins by randomly generating an initial population of host nests. Next, the algorithm iterates until a given stop criterion is reached, which is commonly a maximum number of iterations. At line 3, a new solution is created, normally by employing a random walk via Lévy flights. Equation (1) describes such a random walk, wherex
i
t
+
1 is the new solution,tcorresponds to the iteration number, and the product⊕means entrywise multiplications. Theαparameter is the step size, whereα
>
0, and determines how far the process can go for a fixed number of iterations. Then, at line 4, anE
g
g
jis randomly chosen to be then compared with the previous one in order to keep the egg exhibiting the best cost. Finally, the worse nests are abandoned depending on the probabilityp
aand new solutions are built:
(1)
x
i
t
+
1
=
x
i
t
+
α
⊕
L
e
´
vy
(
λ
)
,
L
e
´
vy
~
u
=
t
-
λ
,
(
1
<
λ
≤
3
)
.Algorithm 1:Cuckoo search.
Input: N
e
s
t
s
i
z
e
,
α
,
λ
Output: E
g
g
b
e
s
t
(1)N
e
s
t
s
←  G
enerateInitialPopulation
(
N
e
s
t
size
)
(2)While ¬ S
t
o
p
C
o
n
d
i
t
i
o
n  do
(3)E
g
g
i
←  GetCuckooByLevyFlight
(
N
e
s
t
s
,
α
,
λ
)
(4)E
g
g
j
←  ChooseRamdomlyFrom
(
N
e
s
t
s
)
(5)If cost
(
E
g
g
i
) ≤ cost
(
E
g
g
j
)
(6)E
g
g
j
←
E
g
g
i
(7)End If
(8)E
g
g
best
←  FindCurrentBest
(
N
e
s
t
s
)
(9)N
e
s
t
s
←  AbandonWorseNests
(
p
a
,
N
e
s
t
s
)
(10)N
e
s
t
s
←  BuildNewSolutions
(
E
g
g
b
e
s
t
)
(11)End While


## 4. Geometric Operators

The cuckoo search has been originally designed for continuous domains, while Sudokus own discrete values. Then, a discretization phase for the CS algorithm is mandatory to correctly explore the potential solutions. The discretization phase applied here has been inspired from the work reported in [8], where a particle swarm optimization algorithm is adapted to solve discrete domains. The idea relies on the use of geometric-based operators able to correctly move to promising regions of a discrete search space. In particular, for this work, we employ the partially matched crossover, the geometric crossover, and the feasible geometric mutation, which are described in the following.


### 4.1. Partially Matched Crossover

The partially matched crossover (PMX) basically works with two parents, creating two crossover points that are selected at random and then PMX proceeds by position swap. The PMX process is described in Algorithm2.Algorithm 2:PMX crossover.
Input: P
a
r
e
n
t
1
[
]
,
P
a
r
e
n
t
2
[
]
Output: C
h
i
l
d
[
]
(1)C
h
i
l
d
←  S
electRandomSegmentFrom
(
P
a
r
e
n
t
1
)
(2)L
i
s
t
v
a
l
←  SelectNotCopiedToChild
(
P
a
r
e
n
t
2
,
C
h
i
l
d
)
(3)For Each v
a
l
∈
L
i
s
t
v
a
l
(6)l
v
a
l
←
v
a
l
(4)V  ←
P
a
r
e
n
t
1
[
IndexOf
(
v
a
l
,
P
a
r
e
n
t
2
)
]
(5)If IndexOf
(
V
,
P
a
r
e
n
t
2
)
∈  SegmentOf
(
C
h
i
l
d
)
(6)v
a
l
←
V
(6)Go To (4)
(7)Else
(8)C
h
i
l
d[IndexOf
(
V
,
P
a
r
e
n
t
2
)] ←
l
v
a
l
(9)End If
(10)End For Each
(11)CopyRemaining
(
C
h
i
l
d
,
P
a
r
e
n
t
2
)At the beginning, a segment fromParent
1 is randomly selected and copied to the child. Then, looking in the same segment positions in Parent
2, each value not copied to the child is stored in a list. Then, for each value in this list, the V value is located in Parent
1 in the position given by the index ofv
a
lin Parent
2. Then, an if-else conditional operates as follows: if the index of V is present in the original segment, V becomes the newv
a
land the process goes to line 4; otherwise,l
v
a
lis inserted into the child in the position given by the index of V in Parent
2. Finally, the remaining positions from Parent
2 are copied to the child. The PMX operator applied to the Sudoku can be seen in Example 1.Example 1 (PMX crossover).
Let two rows located in the same position from different solutions of a Sudoku instance be the parents. The corresponding child produced by the PMX crossover is constructed as follows.(1)
A random segment of consecutive digits fromParent
1 is copied to the child. Assuming that 1 corresponds to the index of the first position, the segment has size 5, from index 4 to 8:
(2)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
-
-
-
3
6
2
5
1
3
4
5
6
7
3
6
2
5
1
9
8
-
(2)
“4” is the first value in the observed segment ofP
a
r
e
n
t
2that is not present in the child. Then,v
a
l
=
4, and the index ofv
a
lin Parent
2 is “5.” Hence, the V value corresponds to “6.” Next, the index of V in Parent
2 is “7.” This index exists in the observed segment, so the process comes back to line 4 using “6” asv
a
l:
(3)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
-
-
-
3
6
2
5
1
3
4
5
6
7
3
6
2
5
1
9
8
-
(3)
Now, using “6” asv
a
l, the new V is “5.” Then, the index of “5” in Parent
2 also appears within the segment. So, the process comes back again to line 4 using “5” asv
a
l:
(4)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
-
-
-
3
6
2
5
1
3
4
5
6
7
3
6
2
5
1
9
8
-
(4)
Then, theV value is “2,” and its index in Parent
2 does not appear within the segment. Hence, we obtain a position in the child for the value “4” from step 2:
(5)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
-
-
4
3
6
2
5
1
3
4
5
6
7
3
6
2
5
1
9
8
-
(5)
“7” is the next value fromParent
2 in the segment that is not already included in the child. Then, “1” is the V value, whose index does not appear within the segment as well. Hence, a position for the value “7” is obtained in the child:
(6)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
-
7
4
3
6
2
5
1
3
4
5
6
7
3
6
2
5
1
9
8
-
(6)
Now, everything else fromParent
2 is copied down to the child:
(7)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
9
7
4
3
6
2
5
1
3
4
5
6
7
3
6
2
6
1
9
8
8


### 4.2. Multiparental Sorting Crossover

This operator may employ multiple parents; our approach based on [8] uses three, where each one represents a row of a potential solution: one from the best solution of all generations, one from the best solution of the current generation, and one from the current solution. Each parent is associated with a weight (w) according to (8) in order to control the relevance of each solution in the generation of the new one. The influence of parents given by the weights is reflected in a mask used in the process.The multiparental crossover is described in Algorithm3. The three parents and the mask are the input of the procedure, and the child resulting from the crossover is the output. A for each loop is used to scan the mask, where every entry indicates which parent the other two parents need to be equal to for that specific position. The replacement depends on the value of the mask and it is performed by swapping the corresponding values as indicated in the conditionals stated at lines 2, 6, and 10. The swapping process is described in Algorithm 4:
(8)
w
1
+
w
2
+
w
3
=
1
,
such
that
w
i
>
0
∀
i
∈
{
1,2
,
3
}
.Algorithm 3:Multiparental sorting crossover.
Input: P
a
r
e
n
t
1
[
]
,
P
a
r
e
n
t
2
[
]
,
P
a
r
e
n
t
3
[
]
Output: C
h
i
l
d
[
]
(1)M
a
s
k
← I
nitializeMask()
(1)For Each i
∈
{
1
,
…
,
M
a
s
k
l
e
n
g
t
h
}
(2)If M
a
s
k
[
i
]
=
1
(3)C
h
i
l
d
[
i
]
←
P
a
r
e
n
t
1
[
i
]
(4)P
a
r
e
n
t
2
← Swap
(
P
a
r
e
n
t
1
[
i
]
,
P
a
r
e
n
t
2
,
i
)
(5)P
a
r
e
n
t
3
← Swap
(
P
a
r
e
n
t
1
[
i
]
,
P
a
r
e
n
t
3
,
i
)
(6)Else If M
a
s
k
[
i
]
=
2
(7)C
h
i
l
d[i] ←
P
a
r
e
n
t
2
[
i
]
(8)P
a
r
e
n
t
1
← Swap
(
P
a
r
e
n
t
2
[
i
]
,
P
a
r
e
n
t
1
,
i
)
(9)P
a
r
e
n
t
3
← Swap
(
P
a
r
e
n
t
2
[
i
]
,
P
a
r
e
n
t
3
,
i
)
(10)Else
(11)C
h
i
l
d[i] ←
P
a
r
e
n
t
3
[
i
]
(12)P
a
r
e
n
t
1
← Swap
(
P
a
r
e
n
t
3
[
i
]
,
P
a
r
e
n
t
1
,
i
)
(13)P
a
r
e
n
t
2
← Swap
(
P
a
r
e
n
t
3
[
i
]
,
P
a
r
e
n
t
2
,
i
)
(14)End If
(15)End For EachAlgorithm 4:Swap.
Input: v
a
l
u
e
,
P
a
r
e
n
t
[
]
,
p
o
s
Output:  P
a
r
e
n
t
[
]
(1)If P
a
r
e
n
t
[
p
o
s
]
≠
v
a
l
u
e
(2)For Each i
∈
{
1
,
…
,
P
a
r
e
n
t
l
e
n
g
t
h
}
(3)If P
a
r
e
n
t
[
i
]
=
v
a
l
u
e
(4)a
u
x
←
P
a
r
e
n
t
[
i
]
(5)P
a
r
e
n
t
[
i
]
←
P
a
r
e
n
t
[
p
o
s
]
(6)P
a
r
e
n
t
[
p
o
s
]
←
a
u
x
(7)End If
(8)For Each
(9)End IfExample 2 (multiparental sorting crossover).
LetParent
1 be a row from the best solution of all generations, Parent
2 a row from the best solution of the current generation, and Parent
3 a row from the current solution. We employ 0.55 as the weight for Parent
1, 0.33 for Parent
2, and 0.12 for Parent
3. Those weights represent the percentage of appearances of the given parent within the mask. For instance, P
a
r
e
n
t
1appears five times in the mask, Parent
2
three times, and Parent
3
once. The corresponding child produced by the multiparental sorting crossover is constructed as follows.(1)
A mask of parent length is randomly generated according to the parent weights:(9)
M
a
s
k


:
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
P
a
r
e
n
t
3


:
3
1
2
1
1
1
1
2
2
8
4
7
3
6
2
5
1
9
9
1
2
3
4
5
6
7
8
4
7
9
3
6
2
5
1
8
(2)
The first value of the mask corresponds to parent “3”, and then the first value ofP
a
r
e
n
t
1andP
a
r
e
n
t
2needs to be equal to the first value ofP
a
r
e
n
t
3, which is “4.” To this end, inP
a
r
e
n
t
1andP
a
r
e
n
t
2, the first cell is swapped with the cell that holds the value “4”:
(10)
M
a
s
k


:
3
1
2
1
1
1
2
2
3
P
a
r
e
n
t
1


:
4
_
8
_
7
3
6
2
5
1
9
P
a
r
e
n
t
2


:
4
_
1
2
3
9
_
5
6
7
8
P
a
r
e
n
t
3


:
4
7
9
3
6
2
5
1
8
C
h
i
l
d
4
(3)
Next, the second value from the mask is “1.” The swapping process is analogous:(11)
M
a
s
k


:
3
1
2
1
1
1
2
2
3
P
a
r
e
n
t
1


:
4
8
7
3
6
2
5
1
9
P
a
r
e
n
t
2


:
4
8
_
2
3
9
5
6
7
1
_
P
a
r
e
n
t
3


:
4
8
_
9
3
6
2
5
1
7
_
C
h
i
l
d
4
8
(4)
Following the same procedure, the last step is shown below obtaining 4 8 2 3 6 7 9 5 1 as the new child:(12)
M
a
s
k


:
3
1
2
1
1
1
2
2
3
P
a
r
e
n
t
1


:
4
8
2
3
6
7
9
5
1
P
a
r
e
n
t
2


:
4
8
2
3
6
7
9
5
1
P
a
r
e
n
t
3


:
4
8
2
3
6
7
9
5
1
C
h
i
l
d
4
8
2
3
6
7
9
5
1


### 4.3. Feasible Geometric Mutation

This is a simple operator used to maintain diversity in the solutions. It swaps two nonfixed elements in a row guaranteeing that mutation is applied only over the cells with no given value. The procedure is described in Algorithm5.Algorithm 5:Feasible geometric mutation.
Input: i
n
i
t
S
o
l
[
]
[
]
,
s
o
l
[
]
[
]
Output: s
o
l
[
]
[
]
(1)r
o
w
s
← C
hooseRowsRandomly
(
i
n
i
t
S
o
l
)
(2)For Each r
o
w
∈
r
o
w
s
(3)p
o
s
1
,
p
o
s
2
← ChooseTwoEmptyCells
(
r
o
w
)
(4)a
u
x
← sol[r
o
w][p
o
s
1]
(5)sol
[
r
o
w
]
[
p
o
s
1
]
← sol
[
r
o
w
]
[
p
o
s
2
]
(6)sol
[
r
o
w
]
[
p
o
s
2
]
←
a
u
x
(7)End For EachExample 3 (feasible geometric mutation).
Let us consider a given Sudoku row and a solution candidate row, as shown below:(13)
Sudoku
problem
row


:
-
-
-
3
-
-
-
-
-
Solution
candidate
row


:
9
7
4
3
6
2
5
1
8The mutation is allowed in any cell except for cell 4, which owns the value 3 as given for the Sudoku instance. Examples of allowed and forbidden mutations are depicted below:(14)
allowed
mutation


:
9
6
4
3
7
2
5
1
8
forbidden
mutation


:
9
7
4
4
6
2
5
1
8


## 4.1. Partially Matched Crossover

The partially matched crossover (PMX) basically works with two parents, creating two crossover points that are selected at random and then PMX proceeds by position swap. The PMX process is described in Algorithm2.Algorithm 2:PMX crossover.
Input: P
a
r
e
n
t
1
[
]
,
P
a
r
e
n
t
2
[
]
Output: C
h
i
l
d
[
]
(1)C
h
i
l
d
←  S
electRandomSegmentFrom
(
P
a
r
e
n
t
1
)
(2)L
i
s
t
v
a
l
←  SelectNotCopiedToChild
(
P
a
r
e
n
t
2
,
C
h
i
l
d
)
(3)For Each v
a
l
∈
L
i
s
t
v
a
l
(6)l
v
a
l
←
v
a
l
(4)V  ←
P
a
r
e
n
t
1
[
IndexOf
(
v
a
l
,
P
a
r
e
n
t
2
)
]
(5)If IndexOf
(
V
,
P
a
r
e
n
t
2
)
∈  SegmentOf
(
C
h
i
l
d
)
(6)v
a
l
←
V
(6)Go To (4)
(7)Else
(8)C
h
i
l
d[IndexOf
(
V
,
P
a
r
e
n
t
2
)] ←
l
v
a
l
(9)End If
(10)End For Each
(11)CopyRemaining
(
C
h
i
l
d
,
P
a
r
e
n
t
2
)At the beginning, a segment fromParent
1 is randomly selected and copied to the child. Then, looking in the same segment positions in Parent
2, each value not copied to the child is stored in a list. Then, for each value in this list, the V value is located in Parent
1 in the position given by the index ofv
a
lin Parent
2. Then, an if-else conditional operates as follows: if the index of V is present in the original segment, V becomes the newv
a
land the process goes to line 4; otherwise,l
v
a
lis inserted into the child in the position given by the index of V in Parent
2. Finally, the remaining positions from Parent
2 are copied to the child. The PMX operator applied to the Sudoku can be seen in Example 1.Example 1 (PMX crossover).
Let two rows located in the same position from different solutions of a Sudoku instance be the parents. The corresponding child produced by the PMX crossover is constructed as follows.(1)
A random segment of consecutive digits fromParent
1 is copied to the child. Assuming that 1 corresponds to the index of the first position, the segment has size 5, from index 4 to 8:
(2)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
-
-
-
3
6
2
5
1
3
4
5
6
7
3
6
2
5
1
9
8
-
(2)
“4” is the first value in the observed segment ofP
a
r
e
n
t
2that is not present in the child. Then,v
a
l
=
4, and the index ofv
a
lin Parent
2 is “5.” Hence, the V value corresponds to “6.” Next, the index of V in Parent
2 is “7.” This index exists in the observed segment, so the process comes back to line 4 using “6” asv
a
l:
(3)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
-
-
-
3
6
2
5
1
3
4
5
6
7
3
6
2
5
1
9
8
-
(3)
Now, using “6” asv
a
l, the new V is “5.” Then, the index of “5” in Parent
2 also appears within the segment. So, the process comes back again to line 4 using “5” asv
a
l:
(4)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
-
-
-
3
6
2
5
1
3
4
5
6
7
3
6
2
5
1
9
8
-
(4)
Then, theV value is “2,” and its index in Parent
2 does not appear within the segment. Hence, we obtain a position in the child for the value “4” from step 2:
(5)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
-
-
4
3
6
2
5
1
3
4
5
6
7
3
6
2
5
1
9
8
-
(5)
“7” is the next value fromParent
2 in the segment that is not already included in the child. Then, “1” is the V value, whose index does not appear within the segment as well. Hence, a position for the value “7” is obtained in the child:
(6)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
-
7
4
3
6
2
5
1
3
4
5
6
7
3
6
2
5
1
9
8
-
(6)
Now, everything else fromParent
2 is copied down to the child:
(7)
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
C
h
i
l
d


:
8
4
7
9
1
2
9
7
4
3
6
2
5
1
3
4
5
6
7
3
6
2
6
1
9
8
8


## 4.2. Multiparental Sorting Crossover

This operator may employ multiple parents; our approach based on [8] uses three, where each one represents a row of a potential solution: one from the best solution of all generations, one from the best solution of the current generation, and one from the current solution. Each parent is associated with a weight (w) according to (8) in order to control the relevance of each solution in the generation of the new one. The influence of parents given by the weights is reflected in a mask used in the process.The multiparental crossover is described in Algorithm3. The three parents and the mask are the input of the procedure, and the child resulting from the crossover is the output. A for each loop is used to scan the mask, where every entry indicates which parent the other two parents need to be equal to for that specific position. The replacement depends on the value of the mask and it is performed by swapping the corresponding values as indicated in the conditionals stated at lines 2, 6, and 10. The swapping process is described in Algorithm 4:
(8)
w
1
+
w
2
+
w
3
=
1
,
such
that
w
i
>
0
∀
i
∈
{
1,2
,
3
}
.Algorithm 3:Multiparental sorting crossover.
Input: P
a
r
e
n
t
1
[
]
,
P
a
r
e
n
t
2
[
]
,
P
a
r
e
n
t
3
[
]
Output: C
h
i
l
d
[
]
(1)M
a
s
k
← I
nitializeMask()
(1)For Each i
∈
{
1
,
…
,
M
a
s
k
l
e
n
g
t
h
}
(2)If M
a
s
k
[
i
]
=
1
(3)C
h
i
l
d
[
i
]
←
P
a
r
e
n
t
1
[
i
]
(4)P
a
r
e
n
t
2
← Swap
(
P
a
r
e
n
t
1
[
i
]
,
P
a
r
e
n
t
2
,
i
)
(5)P
a
r
e
n
t
3
← Swap
(
P
a
r
e
n
t
1
[
i
]
,
P
a
r
e
n
t
3
,
i
)
(6)Else If M
a
s
k
[
i
]
=
2
(7)C
h
i
l
d[i] ←
P
a
r
e
n
t
2
[
i
]
(8)P
a
r
e
n
t
1
← Swap
(
P
a
r
e
n
t
2
[
i
]
,
P
a
r
e
n
t
1
,
i
)
(9)P
a
r
e
n
t
3
← Swap
(
P
a
r
e
n
t
2
[
i
]
,
P
a
r
e
n
t
3
,
i
)
(10)Else
(11)C
h
i
l
d[i] ←
P
a
r
e
n
t
3
[
i
]
(12)P
a
r
e
n
t
1
← Swap
(
P
a
r
e
n
t
3
[
i
]
,
P
a
r
e
n
t
1
,
i
)
(13)P
a
r
e
n
t
2
← Swap
(
P
a
r
e
n
t
3
[
i
]
,
P
a
r
e
n
t
2
,
i
)
(14)End If
(15)End For EachAlgorithm 4:Swap.
Input: v
a
l
u
e
,
P
a
r
e
n
t
[
]
,
p
o
s
Output:  P
a
r
e
n
t
[
]
(1)If P
a
r
e
n
t
[
p
o
s
]
≠
v
a
l
u
e
(2)For Each i
∈
{
1
,
…
,
P
a
r
e
n
t
l
e
n
g
t
h
}
(3)If P
a
r
e
n
t
[
i
]
=
v
a
l
u
e
(4)a
u
x
←
P
a
r
e
n
t
[
i
]
(5)P
a
r
e
n
t
[
i
]
←
P
a
r
e
n
t
[
p
o
s
]
(6)P
a
r
e
n
t
[
p
o
s
]
←
a
u
x
(7)End If
(8)For Each
(9)End IfExample 2 (multiparental sorting crossover).
LetParent
1 be a row from the best solution of all generations, Parent
2 a row from the best solution of the current generation, and Parent
3 a row from the current solution. We employ 0.55 as the weight for Parent
1, 0.33 for Parent
2, and 0.12 for Parent
3. Those weights represent the percentage of appearances of the given parent within the mask. For instance, P
a
r
e
n
t
1appears five times in the mask, Parent
2
three times, and Parent
3
once. The corresponding child produced by the multiparental sorting crossover is constructed as follows.(1)
A mask of parent length is randomly generated according to the parent weights:(9)
M
a
s
k


:
P
a
r
e
n
t
1


:
P
a
r
e
n
t
2


:
P
a
r
e
n
t
3


:
3
1
2
1
1
1
1
2
2
8
4
7
3
6
2
5
1
9
9
1
2
3
4
5
6
7
8
4
7
9
3
6
2
5
1
8
(2)
The first value of the mask corresponds to parent “3”, and then the first value ofP
a
r
e
n
t
1andP
a
r
e
n
t
2needs to be equal to the first value ofP
a
r
e
n
t
3, which is “4.” To this end, inP
a
r
e
n
t
1andP
a
r
e
n
t
2, the first cell is swapped with the cell that holds the value “4”:
(10)
M
a
s
k


:
3
1
2
1
1
1
2
2
3
P
a
r
e
n
t
1


:
4
_
8
_
7
3
6
2
5
1
9
P
a
r
e
n
t
2


:
4
_
1
2
3
9
_
5
6
7
8
P
a
r
e
n
t
3


:
4
7
9
3
6
2
5
1
8
C
h
i
l
d
4
(3)
Next, the second value from the mask is “1.” The swapping process is analogous:(11)
M
a
s
k


:
3
1
2
1
1
1
2
2
3
P
a
r
e
n
t
1


:
4
8
7
3
6
2
5
1
9
P
a
r
e
n
t
2


:
4
8
_
2
3
9
5
6
7
1
_
P
a
r
e
n
t
3


:
4
8
_
9
3
6
2
5
1
7
_
C
h
i
l
d
4
8
(4)
Following the same procedure, the last step is shown below obtaining 4 8 2 3 6 7 9 5 1 as the new child:(12)
M
a
s
k


:
3
1
2
1
1
1
2
2
3
P
a
r
e
n
t
1


:
4
8
2
3
6
7
9
5
1
P
a
r
e
n
t
2


:
4
8
2
3
6
7
9
5
1
P
a
r
e
n
t
3


:
4
8
2
3
6
7
9
5
1
C
h
i
l
d
4
8
2
3
6
7
9
5
1


## 4.3. Feasible Geometric Mutation

This is a simple operator used to maintain diversity in the solutions. It swaps two nonfixed elements in a row guaranteeing that mutation is applied only over the cells with no given value. The procedure is described in Algorithm5.Algorithm 5:Feasible geometric mutation.
Input: i
n
i
t
S
o
l
[
]
[
]
,
s
o
l
[
]
[
]
Output: s
o
l
[
]
[
]
(1)r
o
w
s
← C
hooseRowsRandomly
(
i
n
i
t
S
o
l
)
(2)For Each r
o
w
∈
r
o
w
s
(3)p
o
s
1
,
p
o
s
2
← ChooseTwoEmptyCells
(
r
o
w
)
(4)a
u
x
← sol[r
o
w][p
o
s
1]
(5)sol
[
r
o
w
]
[
p
o
s
1
]
← sol
[
r
o
w
]
[
p
o
s
2
]
(6)sol
[
r
o
w
]
[
p
o
s
2
]
←
a
u
x
(7)End For EachExample 3 (feasible geometric mutation).
Let us consider a given Sudoku row and a solution candidate row, as shown below:(13)
Sudoku
problem
row


:
-
-
-
3
-
-
-
-
-
Solution
candidate
row


:
9
7
4
3
6
2
5
1
8The mutation is allowed in any cell except for cell 4, which owns the value 3 as given for the Sudoku instance. Examples of allowed and forbidden mutations are depicted below:(14)
allowed
mutation


:
9
6
4
3
7
2
5
1
8
forbidden
mutation


:
9
7
4
4
6
2
5
1
8


## 5. Prefiltering Phase

In the presence of unfeasible solutions, the cuckoo procedure is responsible for detecting and discarding them in order to conduct the search to feasible regions of the space of solutions. The goal of the prefiltering phase is to alleviate the work of the cuckoo algorithm by previously eliminating those unfeasible values. This is possible by representing the Sudoku as a constraint network [4] and then applying efficient filtering techniques from the constraint satisfaction domain. In this context, arc-consistency [2] is a widely employed local consistency for filtering algorithms. Arc-consistency was initially defined for binary constraint [21, 22]. We employ here the more general filtering for nonarbitrary constraints named generalized arc-consistency (GAC). The idea is to enforce a local consistency to the problem in a process called constraint propagation. Before detailing this process, let us introduce some necessary definitions [23].Definition 4 (constraint).
A constraintcis a relation defined on a sequence of variablesX
(
c
)
=
(
x
i
1
,
…
,
x
i
|
X
(
c
)
|
), called the scheme ofc
;
cis the subset ofℤ
|
X
(
c
)
|that contains the combinations of tuplesτ
∈
ℤ
|
X
(
c
)
|that satisfyc.|
X
(
c
)
|is called the arity ofc. A constraintcwith schemeX
(
c
)
=
(
x
1
,
…
,
x
k
)is also noted asc
(
x
1
,
…
,
x
k
).Definition 5 (constraint network).
A constraint network also known as constraint satisfaction problem (CSP) is defined by a tripleN
=
〈
X
,
D
,
C
〉, where (i)
Xis a finite sequence of integer variablesX
=
(
x
1
,
…
,
x
n
);
(ii)
Dis the corresponding set of domains forX; that is,D
=
D
(
x
1
)
×
⋯
×
D
(
x
n
), whereD
(
x
i
)
⊂
ℤis the finite set of values that variablex
ican take;
(iii)
Cis a set of constraintsC
=
{
c
1
,
…
,
c
e
}, where variables inX
(
c
j
)are inX.Example 6 (the Sudoku as a constraint network).
Let〈
X
,
D
,
C
〉be the constraint network, which is composed of the following. (i)
X
=
(
x
1,1
,
…
,
x
n
,
m
)is the sequence of variables, andx
i
,
j
∈
Xidentifies the cell placed in the ith row and jth column of the Sudoku matrix, fori
=
1
,
…
,
nandi
=
1
,
…
,
m.
(ii)
Dis the corresponding set of domains, whereD
(
x
i
j
)
∈
Dis the domain of the variablex
i
j.
(iii)
Cis the set of constraints defined as follows.
(a)
To ensure that values are different in rows and columns,x
k
,
i
≠
x
k
,
j
∧
x
i
,
k
≠
x
j
,
k, for all (
k
∈
[
1,9
]
,
i
∈
[
1,9
]
,
j
∈
[
i
+
1,9
]
).
(b)
To ensure that values are different in subgrid:x
(
k
1
-
1
)
*
3
+
k
2
,
(
j
1
-
1
)
*
3
+
j
2
≠
x
(
k
1
-
1
)
*
3
+
k
3
,
(
j
1
-
1
)
*
3
+
j
3, for all (
k
1
,
j
1
,
k
2
,
j
2
,
k
3
,
j
3
∈
[
1,3
]
∣
k
2
≠
k
3
∧
j
2
≠
j
3
).Definition 7 (projection).
A projection ofconYis denoted asπ
Y
(
c
), which defines the relation with schemeYthat contains the tuples that can be extended to a tuple onX
(
c
)satisfyingc.Definition 8 ((generalized) arc-consistency).
Given a networkN
=
〈
X
,
D
,
C
〉, a constraintc
∈
C, and a variablex
i
∈
X
(
c
),(i)
a valuev
i
∈
D
(
x
i
)is consistent withc
∈
Dif and only if there exists a valid tupletausatisfyingcsuch thatv
i
=
τ
[
{
x
i
}
]; such a tuple is called a support for(
x
i
,
v
i
)onc;
(ii)
the domainDis (generalized) arc-consistent oncforx
iif and only if all the values inD
(
x
i
)are consistent withcin D; that is, D
(
x
i
)
⊆
π
x
i
(
c
∩
π
X
(
c
)
(
D
)
);
(iii)
the networkNis (generalized) arc-consistent if and only ifDis (generalized) arc-consistent for all variables inXon all constraints inC.The filtering process is achieved by enforcing the arc-consistency on the problem. This can be carried out by using Algorithms6 and 7. The idea is to revise the arcs (the constraint relation between variables) by removing the values fromD
(
X
i
)that lead to inconsistencies with respect to a given constraint. Such a revision process is done by Algorithm 6, which takes each valuev
i
∈
D
(
x
i
)(line 2) and analyses the spaceτ
∈
c
∩
π
X
(
c
)
(
D
), searching for a support on constraintc(line 3). If support does not exist, the valuev
iis eliminated fromD
(
x
i
). Finally, the procedure informs if the domain has been modified by returning the corresponding Boolean value (line 8).Algorithm 6:Revise3.
Input: x
i
,
c
Output: C
H
A
N
G
E
(1)C
H
A
N
G
E
← false
(2)Foreach v
i
∈
D
(
x
i
) do
(3)If ∄
τ
∈
c
∩
π
X
(
c
)
(
D
)
with
τ
[
x
i
]
=
v
i do
(4)    removev
i from D
(
x
i
)
(5)C
H
A
N
G
E
← true
(6)End If
(7)End Foreach
(8)Return C
H
A
N
G
EAlgorithm 7:AC3/GAC3.
Input: X
,
D
,
C
Output: B
oolean
(1)Q
←
(
x
i
,
c
)
∣
c
∈
C
,
x
i
∈
X
(
c
)
(2)While Q
≠
∅ do
(3)   select and remove(
x
i
,
c
) from Q
(4)If Revise3
(
x
i
,
c
) then
(5)    IfD
(
x
i
)
=
∅ then
(6)Return false
(7)Else
(8)Q
←
Q
∪
{
(
x
j
,
c
′
)
∣
c
′
∈
C
∧
c
′
≠
c
∧
x
i
,
x
j
∈
X
(
c
′
)
∧
j
≠
i
}
(9)End If
(10)End If
(11)End While
(12)Return trueThe role of Algorithm7 is to guarantee that every domain is arc-consistent. This is done by iteratively revising the arcs by performing calls to Algorithm 6. At the beginning, a list calledQis filled with pairs (x
i
,
c) such thatx
i
∈
X
(
c
). Pairs for whichD
(
x
i
)is not ensured to be arc-consistent are kept in order to avoid useless calls to Algorithm 7. This is a main advantage of AC3 with respect to its predecessor Algorithms AC1 and AC2. Then, at line 2, a while statement controls the calls to Revise3. If a true value is received from Revise3,D
(
X
i
)is verified and if no value remains within the domain, the algorithm returns false. If there still exist values inD
(
X
i
), normally, a value for another variablex
jhas lost its support onc. Hence, the listQmust be refilled with all pairs (x
i; c). The process finishes and returns true when all remaining values within domains are arc-consistent with respect to all constraints.Example 9 (enforcing AC3 on a Sudoku puzzle).
Let us exemplify the work of the prefiltering phase by enforcing the AC3 on three constraints of a Sudoku instance. We begin by enforcing the AC3 on a given subgrid (enclosed with dashed lines in Figure2) of the Sudoku puzzle. The subgrid has three variables with no value assigned (x
4,9, x
5,8, andx
6,9). Then, enforcing AC3 via the GAC3 algorithm with respect to the subgrid constraint (second constraint from Example 6) leads to the elimination of six values fromD
(
x
4,9
), D
(
x
5,8
), andD
(
x
6,9
). Those values have no support on the verified constraint; that is, they have been already taken for another cell on the same subgrid. Thus, the original domains for the three variables are reduced to{
5,6
,
8
}.Figure 2
Enforcing AC3 to a subgrid constraint.In Figure3, the AC3 is enforced to a row of the puzzle. This row has four variables (x
5,2, x
5,4, x
5,6, andx
5,8) with no assigned value. The GAC3 algorithm filters from domains five values with no support fromD
(
x
5,2
), D
(
x
5,4
), andD
(
x
5,6
). The variablex
5,8has been refiltered, remaining only two possible values. Finally, in Figure 4, four values are filtered from four variables, remaining only one possible value for variablex
5,8.Figure 3
Enforcing AC3 to a row constraint.Figure 4
Enforcing AC3 to a column constraint.


## 6. The Prefiltered Cuckoo Search via Geometric Operators

The cuckoo search proposed here combines geometric operators with prefiltering phases. The goal is to enhance the performance of the cuckoo search as well as to allow it to correctly explore a discrete search space. Algorithm5 illustrates the new hybrid algorithm. Now the input set is quite larger. It considers the size of the nest, the constraint network〈
X
,
D
,
C
〉representing the Sudoku problem, and two parameters that define probabilities for regulating the usage of geometric operators. As output, the procedure returns the best egg reached by the algorithm. The prefiltering phase via the AC3 algorithm is triggered at the beginning. The AC3 algorithm receives as input the constraint network〈
X
,
D
,
C
〉of the Sudoku and reduces if possible the set of domainsDby deleting the unfeasible values. Then, an initial population of nests is generated but, unlike the classic cuckoo, the generation is bounded to the reduced set of domainsD. Between lines 3 and 13, a while loop manages the iteration process until the stop condition is reached, which for the current implementation corresponds to a maximum number of iterations. At line 4, an E
g
g
i is randomly chosen from nests to which the geometric operators are then applied. The usage of geometric operators is illustrated in Algorithm 9, where they apply only whether the evaluated egg is not the best one. The PMX and multiparent sorting crossovers act depending on a random value and on theP
p
m
x
-
m
u
l
t
iprobability. Analogously, the mutation operates using theP
m
u
t
a
t
eprobability, andDis used as input of the mutation to validate that only feasible mutations are carried out. At line 6, anE
g
g
jis randomly chosen to be then compared with the previous one in order to keep the one exhibiting the best cost. The cost of a solution corresponds to the sum of wrong values in subgrids, columns, and rows (see Figure 5). At line 11, the worse nests are abandoned depending on probabilityp
a. Finally, new solutions are built, but again, the set of filtered domainsDis considered in order to avoid unfeasible solutions. Algorithm 8 illustrates the prefiltered discrete cuckoo search.Algorithm 8:Prefiltered discrete cuckoo search.
Input: N
e
s
t
s
i
z
e
,
X
,
D
,
C
,
P
p
m
x
-
m
u
l
t
i
,
P
m
u
t
a
t
e
Output: E
g
g
b
e
s
t
(1)D
← A
C3(X
,
D
,
C)
(2)N
e
s
t
s
← G
enerateInitialPopulation
(
N
e
s
t
s
i
z
e
,
D
)
(3)While  ¬  S
t
o
p
C
o
n
d
i
t
i
o
n do
(4)E
g
g
i
← G
etRandomlyFrom
(
N
e
s
t
s
)
(5)E
g
g
i
← G
eometricOperators
(
P
p
m
x
-
m
u
l
t
i
,
P
m
u
t
a
t
e
)
(6)E
g
g
j
← C
hooseRamdomlyFrom
(
N
e
s
t
s
)
(7)If cost
(
E
g
g
i
) ≤ cost
(
E
g
g
j
)
(8)E
g
g
j
←
E
g
g
i
(9)End If
(10)
E
g
g
b
e
s
t
← FindCurrentBest
(
N
e
s
t
s
)
(11)
N
e
s
t
s
← AbandonWorseNests
(
p
a
,
N
e
s
t
s
)
(12)
N
e
s
t
s
← BuildNewSolutions
(
E
g
g
best
,
D
)
(13)End WhileAlgorithm 9:Geometric operators.
Input: E
g
g
,
E
g
g
b
e
s
t
,
E
g
g
l
a
s
t
b
e
s
t
,
P
p
m
x
-
m
u
l
t
i
,
P
m
u
t
a
t
e
Output: E
g
g
(1)Foreach E
g
g
∈
N
e
s
t
s
(2)If (E
g
g
〈
〉
E
g
g
b
e
s
t)
(3)If (r
and
(
)
<
P
p
m
x
-
m
u
l
t
i)
(4)E
g
g
← P
MXCrossover
(
E
g
g
,
E
g
g
b
e
s
t
)
(5)Else
(6)E
g
g = MultiParentalSortingCrossover
(
E
g
g
,
E
g
g
b
e
s
t
,
E
g
g
l
a
s
t
b
e
s
t
)
(7)End If
(8)If (rand
(
)
<
P
m
u
t
a
t
e)
(9)E
g
g
← FeasibleGeometricMutation
(
D
,
E
g
g
)
(10) End If
(11)End If
(12)End ForeachFigure 5
Solution cost of a Sudoku puzzle.


## 7. Experimental Results

Different experiments have been performed in order to validate our approach. The Sudoku benchmarks used have been taken from [24], which are organized in three difficulty levels: easy, medium, and hard. All tested Sudokus have a unique solution. The algorithms have been implemented in Octave 3.6.3, and the experiments have been performed on a 2.0 GHz Intel Core2 Duo T5870 with 1 Gb RAM running Fedora 17. The configuration of the proposed cuckoo search is the following, which corresponds to the best one achieved after a tuning phase:P
a
=
0.25, P
p
m
x
-
m
u
l
t
i
=
0.7, P
m
u
t
a
t
e
=
0.9, andN
e
s
t
s
i
z
e
=
10.Table1 illustrates the results of solving 9 problems, 3 from each difficulty level, by using the proposed cuckoo search algorithm considering 10000 iterations. From left to right, the table states the number of tries performed, the number of tries solved, the minimum solving time reached, the average solving time, the maximum solving time, and the standard deviation (SD). Regarding the easy Sudokus, the proposed cuckoo search is able to rapidly solve them reaching a 100% of success (50 out of 50 tries solved). Then, increasing one difficulty level, the percentage of success shortly diminishes, keeping the 100% of success for the “medium a” benchmark. Finally, for hard Sudokus, the runtime naturally gets bigger (see Figure 6); however, the performance is reasonable, reaching a 51% (50 out of 97 tries solved) of success for “hard a,” 80% (50 out of 62 tries solved) of success for “hard b,” and a 70% (50 out of 71 tries solved) of success for “hard c.”Table 1
Solving Sudokus with the prefiltered discrete cuckoo search considering 10000 iterations.
Tries
Solved
Min. solving  time (sec)
x
¯ solving  time (sec)
Max. solving  time (sec)
SD  time (sec)
Easy a
50
50
1.302
1.310
1.329
0.004
Easy b
50
50
1.005
1.007
1.029
0.003
Easy c
50
50
1.019
1.021
1.036
0.003
Medium a
50
50
2.501
384.341
1171.312
291.336
Medium b
84
50
38.32
729.673
1932.691
516.867
Medium c
67
50
26.807
800.471
1923.442
561.877
Hard a
97
50
385.652
2059.690
3777.340
984.921
Hard b
62
50
49.608
1484.692
6810.882
1473.731
Hard c
71
50
9.497
771.211
3561.042
825.516Figure 6
Comparing solving times for Sudoku.In Table2, the performance of the proposed cuckoo search is compared with the best-performing incomplete methods reported in the literature: a genetic algorithm (GA) [1] and a hybrid tabu search (hybrid TS) [20]. We contrast the number of problems solved from a total of 30 tries taking into account both unlimited iterations and 100000 iterations. The results depict that the three techniques are able to easily succeed for the first Sudoku level. In the presence of medium Sudokus, the GA begins to decrease its performance, being able to solve a medium Sudoku with a 33% of success (10 out of 30 tries solved). The cuckoo search and the hybrid TS keep their 100% of success. Finally, observing hard Sudokus, the performance of the cuckoo search and the hybrid TS is considerably better than GA, which solves only 2 out of 30 tries, while our proposal as well as the hybrid TS is able to reach a 100% of success.Table 2
Comparing the prefiltered discrete cuckoo search with the best-performing incomplete methods for Sudokus considering 100000 and unlimited iterations.
Problem
Prefiltered discrete CS
Hybrid TS
GA
Unlimited  iterations
100000 iterations
Unlimited iterations
100000  iterations
Unlimited iterations
100000 iterations
Easy a
30
30
30
30
30
29
Easy b
30
30
30
30
30
30
Easy c
30
30
30
30
30
30
Medium a
30
30
30
30
30
10
Medium b
30
30
30
30
—
—
Medium c
30
30
30
30
—
—
Hard a
30
30
30
30
30
2
Hard b
30
30
30
30
—
—
Hard c
30
30
30
30
—
—


## 8. Conclusions and Future Work

In this paper, we have presented a prefiltered cuckoo search algorithm tuned with geometric operators. The geometric operators allow one to drive the search to promising regions of a discrete space of solutions, while the prefiltering phase attempts to previously delete from domains the values that do not conduct to any feasible solution. In this way, the work of the metaheuristic is alleviated leading to a faster solving process. We have performed a set of experiments in order to compare our approach with the best-performing approximate methods reported in the literature. We have considered Sudokus from different difficulty levels: easy, medium, and hard. In the presence of easy Sudokus, the proposed cuckoo search is able to reach a 100% of success. When solving medium difficulty Sudokus, the cuckoo search keeps its 100% of success, while the best GA reported is able only to solve 10 out of 30 tries. Finally, regarding hard Sudokus, the cuckoo search noticeably competes against the best incomplete method reported for Sudokus, both reaching a 100% of success considering 100000 iterations.We visualize different directions for future work; perhaps the clearest one is the introduction of prefiltering phases to additional metaheuristics such as particle swarm optimization, ant, or bee colony algorithms to solve Sudokus or any combinatorial problem. Evaluating the behaviour of geometric operators in other swarm-based metaheuristics is another interesting work to develop. Finally, the use of autonomous search [25–28] for the self-tuning of a metaheuristic interacting with prefiltering phases will be also an appealing research direction to pursue.



---

*Source: 465359-2014-02-23.xml*