-
Notifications
You must be signed in to change notification settings - Fork 10
/
latin.jl
74 lines (69 loc) · 2.35 KB
/
latin.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
"""LatinGenerator <: AbstractModelGenerator
Generator for the latin square problem: https://en.wikipedia.org/wiki/Latin_square
"""
mutable struct LatinGenerator <: AbstractModelGenerator
N::Int
p::Float64
A::Union{Nothing,Matrix{Int}}
function LatinGenerator(N, p)
new(N, p, nothing)
end
end
function proper_move(A::Matrix{Int}, x::Int, y::Int, z::Int, v::Int)
z2 = A[x, y]
if z2 == v
A[x, y] = z
else
y2 = rand(findall(k -> k == v, A[x, :]))
x2 = rand(findall(k -> k == v, A[:, y]))
A[x, y] = z
A[x, y2] = z2
A[x2, y] = z2
proper_move(A, x2, y2, v, z2)
end
end
"""
fill_with_generator!(cpmodel::CPModel, gen::GraphColoringGenerator)
Fill a CPModel with the variables and constraints generated. We fill it directly instead of
creating temporary files for efficiency purpose.
Rng is a random number generator used to ensure experiment reproductibility accross devices. It is often set at the beginning of an experiment to generate deterministic training samples.
"""
function fill_with_generator!(cpmodel::CPModel, gen::LatinGenerator; rng::AbstractRNG=MersenneTwister())
N = gen.N
p = gen.p
cpmodel.limit.numberOfSolutions = 1
if isnothing(gen.A)
gen.A = Matrix{Int}(undef, N, N)
for i in 1:N
gen.A[i, :] = [(i + j - 2) % N + 1 for j in 1:N]
end
end
A = gen.A
for i in 1:N^3
x, y, z = rand(rng, 1:N, 3)
proper_move(A, x, y, z, z)
end
B = copy(A)
n = floor(Int, p * N^2)
indicies = shuffle(rng, 1:N^2)[1:n]
for x in indicies
i = div(x - 1, N) + 1
j = (x - 1) % N + 1
B[i, j] = 0
end
puzzle = Matrix{SeaPearl.AbstractIntVar}(undef, N, N)
for i = 1:N
for j in 1:N
puzzle[i, j] = SeaPearl.IntVar(1, N, "puzzle_" * string(i) * "," * string(j), cpmodel.trailer)
SeaPearl.addVariable!(cpmodel, puzzle[i, j]; branchable=true)
if B[i, j] > 0
SeaPearl.addConstraint!(cpmodel, SeaPearl.EqualConstant(puzzle[i, j], B[i, j], cpmodel.trailer))
end
end
end
for i in 1:N
SeaPearl.addConstraint!(cpmodel, SeaPearl.AllDifferent(puzzle[i, :], cpmodel.trailer))
SeaPearl.addConstraint!(cpmodel, SeaPearl.AllDifferent(puzzle[:, i], cpmodel.trailer))
end
return nothing
end