# Trying to solve a puzzle

**URL:** <https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515>\
**Category:** Optimization (Mathematical)\
**Created:** [May 20, 2021, 1:05pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515 "2021-05-20T13:05:25Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![sogrbilja](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sogrbilja/32/17521_2.png) [@sogrbilja](https://discourse.julialang.org/u/sogrbilja)\
**Post date:** [May 20, 2021, 1:05pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/1 "2021-05-20T13:05:25Z")

</div>

Just recently I bumped on this: [The PuzzlOR](http://www.puzzlor.com/2016-04_CellTowers.html) and I want to play a bit with that and solve it using JuMP.

My approach is not yet certain, but something like this:

1. load data into DICT(string, int) \* actually just 0 or 1
2. total houses \* 0.7 will be maximum for the objective function

Now, can I use indicator constraints to set value for my variables?

If cell A2 will hold a value then that value should be equal to sum from all adjusting cells in DICT (including that cell), and then set adjusting cells variables to be = 0.

Is it possible to set variables based with indicator constraints?

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [May 20, 2021, 1:40pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/2 "2021-05-20T13:40:16Z")

</div>

`amount_covered_houses >= 0.7*total_houses` should be a constraint, not an objective, and your objective should be to minimize the amount of antennas

I think I solved it with JuMP, using only Binary variables  
I used matrices rather than Dicts to store data and variables

to know if a cell is covered, your constraint can be  
`iscovered <= sum(isantenna.(neighbors))`  
since these are binary variables and the solver will try to maximize `iscovered`, it’s equivalent to  
`iscovered == |(isantenna.(neighbors)...)`

I don’t know how much help you want

---

<div class="post-metadata">

**Author:** ![sogrbilja](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sogrbilja/32/17521_2.png) [@sogrbilja](https://discourse.julialang.org/u/sogrbilja)\
**Post date:** [May 20, 2021, 2:10pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/3 "2021-05-20T14:10:44Z")

</div>

> [@MarcMush](#):
>
> isantenna.(neighbors)

First, thanks for your answer, but what is this syntax? Is isantenna also a variable?

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [May 20, 2021, 2:20pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/4 "2021-05-20T14:20:20Z")

</div>

this is kinda pseudo code, with `isantenna` represented as a function  
in my solution `isantenna` is a Matrix, so this syntax would cleary not work

---

<div class="post-metadata">

**Author:** ![sogrbilja](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sogrbilja/32/17521_2.png) [@sogrbilja](https://discourse.julialang.org/u/sogrbilja)\
**Post date:** [May 20, 2021, 3:41pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/5 "2021-05-20T15:41:36Z")

</div>

OK, I changed loading data from dict to matrix.

I suppose this is the way to declare those variables and constraints:

```julia
     @variable(prmx, 
                isCovered[1:_ROWS, 1:_COLUMNS], 
                Bin)

    @variable(prmx, 
                isAntenna[1:_ROWS, 1:_COLUMNS], 
                Bin)

   @objective(
        prmx,
        Min,
        sum(isCovered[i, j] * isHouse[i, j]
            for i in 1:_ROWS, j in 1:_COLUMNS
        )
    )

    @constraint(
        prmx,
        sum(isCovered[i, j] * isHouse[i, j]
            for i in 1:_ROWS, j in 1:_COLUMNS
        )
        >= _TOTAL * 0.7
    )
    

```

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [May 20, 2021, 6:16pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/6 "2021-05-20T18:16:18Z")

</div>

It looks good

Your last set of constraints is useless I think

And the objective should be to minimize the amount of Antennas, you already have the 70% rule as a constraint

---

<div class="post-metadata">

**Author:** ![sogrbilja](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sogrbilja/32/17521_2.png) [@sogrbilja](https://discourse.julialang.org/u/sogrbilja)\
**Post date:** [May 20, 2021, 6:31pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/7 "2021-05-20T18:31:31Z")

</div>

Yes, they say “at least 70%” so it has to bi Min with constraint sum(…) \>= \_TOTAL \* 0.7.

Now I can;t quite define constraints for isAntenna → isCovered. Per my logic it should be if there is Antenna it should cover adjusting cells, but still dont know how to write constraints for that.

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [May 20, 2021, 7:01pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/9 "2021-05-20T19:01:53Z")

</div>

I think it worked with

```julia
    @constraint(
        prmx, 
        [i in 1:_ROWS, j in 1:_COLUMNS],
        isCovered[i, j]
        <=
        isAntenna[i, j] 
        + sum(
            isAntenna[r, c]
            for r in i - 1:i + 1, c in j - 1:j + 1
                if r != i && r >= 1 && r <= _ROWS && c != j && c >= 1 && c <= _COLUMNS
        )   
    )

```

you can simplify a bit:

```julia
    @constraint(
        prmx, 
        [i in 1:_ROWS, j in 1:_COLUMNS],
        isCovered[i, j]
        <=
        sum(
            isAntenna[r, c]
            for r in i - 1:i + 1, c in j - 1:j + 1
            if 1 <= r <= _ROWS && 1 <= c <= _COLUMNS
        )   
    )

```

and the objective should simply be the total amount of antennas:

```julia
@objective(prmx, Min, sum(isAntenna))

```

then it should be good I think

---

<div class="post-metadata">

**Author:** ![sogrbilja](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sogrbilja/32/17521_2.png) [@sogrbilja](https://discourse.julialang.org/u/sogrbilja)\
**Post date:** [May 20, 2021, 7:10pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/10 "2021-05-20T19:10:15Z")

</div>

for @objective I agree and understand, but can’t visualize that isCovered and isAntenna relationship, here it says that isCovered \<= sum(isAntenna), hm…, should it be other way around like isCovered \>= sum(isAntenna)?

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [May 20, 2021, 7:13pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/11 "2021-05-20T19:13:51Z")

</div>

if you have `isCovered >= sum(isAntenna)`, your solver will say,  
“ok, isAntenna = 0 everywhere and isCovered = 1 everywhere”

which is of course not want we want (although coverage without antennas would be great 😃)

there is proper maths explanations to transform `and` and `or` into linear constraints but I couldn’t explain the proper maths theory

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [May 20, 2021, 7:24pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/12 "2021-05-20T19:24:57Z")

</div>

I found [this post](https://cs.stackexchange.com/a/12118) that explains how to transform boolean logic in linear equations

the proper complete way to do a `or` is (if b is a list):

```julia
a = |(b...)

```

is equivalent to

```julia
a <= sum(b)
a .>= b

```

in this case the `a .>= b` isn’t strictly needed (I think) since the solver will try to minimize b and maximize a anyway

---

<div class="post-metadata">

**Author:** ![sogrbilja](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sogrbilja/32/17521_2.png) [@sogrbilja](https://discourse.julialang.org/u/sogrbilja)\
**Post date:** [May 20, 2021, 8:03pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/13 "2021-05-20T20:03:24Z")

</div>

What do you think about this:

```julia
    @constraint(
        prmx, 
        [i in 2:_ROWS-1, j in 2:_COLUMNS-1],
          sum(
            isCovered[r, c]
            for r in i - 1:i + 1, c in j - 1:j + 1
          ) - 9 * isAntenna[i, j] >= 0
    )

```

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [May 20, 2021, 8:25pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/14 "2021-05-20T20:25:31Z")

</div>

```julia
isCovered[i, j] <=
sum(
    isAntenna[r, c]
    for r in i-1:i+1, c in j-1:j+1
    if 1 <= r <= _ROWS && 1 <= c <= _COLUMNS
) 

```

corresponds to

```julia
isCovered[i, j] ==
|([
    isAntenna[r, c]
    for r in i-1:i+1, c in j-1:j+1
    if 1 <= r <= _ROWS && 1 <= c <= _COLUMNS
]...) 

```

and for completeness you can add:

```julia
isCovered[i, j] .>=
[
    isAntenna[r, c]
    for r in i-1:i+1, c in j-1:j+1
    if 1 <= r <= _ROWS && 1 <= c <= _COLUMNS
]

```

this works fine for me and I find the right answer (6 antennas for 29 houses covered)  
I don’t understand what you’re trying to do in your last post

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [May 20, 2021, 8:36pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/15 "2021-05-20T20:36:26Z")

</div>

Here’s a more compact way to write it:

```nohighlight
using JuMP, Cbc
function main(; houses::Vector{Tuple{Int,Int}}, ratio::Float64)
    M = maximum(h[1] for h in houses)
    N = maximum(h[2] for h in houses)
    model = Model(Cbc.Optimizer)
    @variable(model, cell_tower[1:M, 1:N], Bin)
    @variable(model, is_covered[houses], Bin)
    @objective(model, Min, sum(cell_tower))
    stencil(i, j) = cell_tower[max(i-1,1):min(i+1,M), max(j-1,1):min(j+1,N)]
    @constraint(model, [h in houses], is_covered[h] <= sum(stencil(h[1], h[2])))
    @constraint(model, sum(is_covered) >= ratio * length(houses))
    optimize!(model)
    return value.(cell_tower)
end
houses = [(1, 9), (3, 2), (4, 4), (5, 6), (8, 9), (9, 1)]
main(houses, ratio = 0.7)

```

---

<div class="post-metadata">

**Author:** ![sogrbilja](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sogrbilja/32/17521_2.png) [@sogrbilja](https://discourse.julialang.org/u/sogrbilja)\
**Post date:** [May 21, 2021, 7:29am UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/16 "2021-05-21T07:29:55Z")

</div>

The most important, what I failed to understand, is that isCovered is in the function of houses. I was thinking about the grid that one antenna can cover, but I should think about which houses antenna(s) can cover instead.

Here is the model:

```julia
using JuMP, Cbc, XLSX

mat = XLSX.readdata("data/input.xlsx", "sheet1", "A1:J10")

M = size(mat, 1)
N = size(mat, 2)
ratio = 0.7

houses = []
for i = 1 : M
  for j = 1 : N
    if mat[i,j] == 1
      push!(houses, (i,j))
    end
  end
end

model = Model(Cbc.Optimizer)

@variable(model, 
            isCovered[houses], 
            Bin)

@variable(model, 
            isAntenna[1:M, 1:N], 
            Bin)

@objective(
    model,
    Min,
    sum(isAntenna)
)

@constraint(
    model,
    sum(isCovered) >= length(houses) * ratio
)

@constraint(
    model, 
    [h in houses],
    isCovered[h] <=
    sum(
        isAntenna[r, c]
        for r in h[1]-1:h[1]+1, c in h[2]-1:h[2]+1
        if 1 <= r <= M && 1 <= c <= N
    ) 
)

optimize!(model)

res = primal_status(model)

if res == MOI.FEASIBLE_POINT
    val = value.(isAntenna)
    open("out/result.txt","w") do io
        for i in 1:M
            for j in 1:N
                print(io, floor(Int, val[i,j]))
                print(io, '\t')
            end
            print(io, "\n")
        end
    end
end

```

---

<div class="post-metadata">

**Author:** ![sogrbilja](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sogrbilja/32/17521_2.png) [@sogrbilja](https://discourse.julialang.org/u/sogrbilja)\
**Post date:** [May 21, 2021, 8:18am UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/17 "2021-05-21T08:18:13Z")

</div>

Got it finally! 6 antennas → 29 houses

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [May 21, 2021, 11:58am UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/18 "2021-05-21T11:58:58Z")

</div>

Great!

To see a Matrix approach, here was my take on the problem:

```julia
using JuMP, Cbc
m = Model(Cbc.Optimizer)
set_silent(m)

houses = [
0 0 1 0 1 1 0 1 0 0
1 0 0 0 1 0 0 0 0 0
0 0 0 1 0 1 1 0 1 1
0 0 0 0 1 0 1 0 1 0
0 0 1 0 0 1 1 1 1 0
1 0 0 1 1 0 1 0 0 0
1 1 1 1 1 0 0 0 0 1
0 0 0 0 1 0 1 0 0 0
1 0 1 0 0 0 1 1 0 1
1 0 0 0 1 1 0 0 1 1
]

@variables m begin 
    isantenna[1:12,1:12], Bin
    iscovered[1:10,1:10], Bin
end

@constraints m begin 
    isantenna[1, :] .== 0
    isantenna[end, :] .== 0
    isantenna[:, 1] .== 0
    isantenna[:,end] .== 0
        
    iscovered .<= sum(isantenna[i:end-3+i, j:end-3+j] for i in 1:3, j in 1:3)

    sum(iscovered .* houses) >= 0.7*sum(houses)
end

@objective m Min sum(isantenna)

optimize!(m)

result = Int.(value.(isantenna[2:end-1, 2:end-1]))
println(sum(result))
display(result)

```

---

<div class="post-metadata">

**Author:** ![sogrbilja](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sogrbilja/32/17521_2.png) [@sogrbilja](https://discourse.julialang.org/u/sogrbilja)\
**Post date:** [May 21, 2021, 12:32pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/19 "2021-05-21T12:32:13Z")

</div>

Great! But I am still a conventional programmer though 😄 and will need some time to understand and start using those operators like `.` Anyway I am already on another page: [puzzlor.com](http://www.puzzlor.com/2014-12_Electrifying.html) did you solve that too?

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [May 21, 2021, 12:50pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/20 "2021-05-21T12:50:45Z")

</div>

hmmm, that’s not linear (and possibly not convex)

I might try it when I have some time

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [May 21, 2021, 4:58pm UTC](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515/21 "2021-05-21T16:58:47Z")

</div>

with 1,000,000 possibilities only, it’s totaly reasonable to brute-force the problem  
without optimizing my code, I find the solution in 7 seconds

[Next page](https://discourse.julialang.org/t/trying-to-solve-a-puzzle/61515.md?page=2)