Information Technology Reference
In-Depth Information
n
∑
=
x
=
1
1
≤
i
,
k
≤
n
(3)
ijk
j
1
∑
∈
x
l
=
1
1
≤
k
,
l
≤
n
(4)
ijk
i
,
j
G
n
∑
=
x
=
1
1
≤
i
,
j
≤
n
(5)
ijk
k
1
n
∑
=
x
=
1
∀
(
i
,
j
)
∈
N
(6)
ijk
k
1
x
∈
{
1
(7)
ijk
where
G
stands for the submatrix
l
, and
N
contains elements in the matrix, which
have no value in the initial puzzle. Constraints 2, 3, and 4 guarantee
that only one
k
exists in each column, row, and submatrix respectively. Constraint 5 forces every po-
sition in the matrix to be filled. Please note that it is possible to formulate the problem
as an integer linear program (ILP) by letting the integer variables take the values from
1 to 9.
In [1], Geem employed a formulation with penalties as follows:
9
9
9
9
9
∑
∑
∑
∑
∑
∑
(8)
Minimize
Z
=
|
x
−
45
|
+
|
x
−
45
|
+
|
x
−
45
|
ij
ij
ij
i
=
1
j
=
1
j
=
1
i
=
1
l
=
1
(
i
,
j
)
∈
G
where
i
x
= cell at row
i
and column
j
, which has an integer value from 1 to 9.
The first term in Equation 8 represents the penalty function for each horizontal
row; the second term for each vertical column; and the third term for each block. It
should be noted that, although the sum of each row, each column, or each block
equals 45, it does not guarantee that the numbers 1 through 9 are used exactly once.
However, any violation of the uniqueness affects other row, column, or block which
contains the wrong value jointly.
2.2 Example Puzzle
The HS algorithm application was applied to the Sudoku puzzle proposed by Nicolau
and Ryan [2] with 40 given values (white cells in Figure 1). The total searching space
for this case is
41
39
if integer programming formulation is considered.
The proposed HS model found the unique global optimum without any row, col-
umn or block violation after 285 function evaluations, taking 9 seconds on Intel Cel-
eron 1.8 GHz Processor as shown in Figure 1 [1].
9
=
1
.
33
×
10
Search WWH ::
Custom Search