# Integer Programming: Chess - n° of knights needed so that every square is covered

1. Nov 24, 2012

### thomas49th

1. The problem statement, all variables and given/known data
On a 8x8 chess board format an Integer program to optimize the amount of knights required such that every square is covered by at least one knight.

2. Relevant equations
I know of a similar problem where we use duality for the placing 5 queens such that the maximum number of pawns can be placed as to not be covered by the queens, but I don't think we need to us the duality here as duality is useful for problems where by taking the dual, the problem size decreases.

3. The attempt at a solution
There was a hint to introduce artificial rows (2 either side, so our chess board becomes 12x12). Let's say the board goes from -1 to 10, where 1 to 8 is the original chess board. This may be helpful as if you stick a knight at the corner of the 8x8 board it will cover the 12x12... I think this may somehow reduce some constraints (see below).

If I let $$x_{ij}$$ be the binary variable which states if a knight is placed on square x at row i, column j

I think I should also introduced a binary variable $$c_{ij}$$, which if 1 implies the square is covered by at least one knight.

I have written out the 8 positions a knight can cover with respect to itself i.e: $$c_{i-1,j-2}$$. If a knight was placed at (4,4) then one of the 8 spots it covers is (3,2).

The objective function of the program should be

$\sum_{j=1 to 8} \sum_{i = 1 to 8} x_{ij}$

Some constraints
Other things such as the sum of c over i and j should be at least 64 and the independent row and column sum should be 8.

$\sum_{j=1 to 8} \sum_{i = 1 to 8} x_{ij} ≥ 64$

Also no knight can be placed outside the original 8x8 chess board. I can only see
$\sum_{j=-1 to 0, j = 9,10} \sum_{all i} x_{ij}$
$\sum_{j = 1 to 8, j = 9 to 10} \sum_{i = -1 to 0, i = 9, 10} x_{ij}$

I like to think I can somehow get rid of having 4 discrete regions here.

Any hints of where I can go now? Or is that my linear program?
Thanks
Thomas

2. Jun 10, 2017

### ChristinaK

Thomas,

Have you ever found the solution to this problem?

Many thanks,
Christina

3. Jun 11, 2017

### willem2

linear programming is too much work.
Simple backtracking gets you the solution in 4 minutes.
00000000
00000000
01111110
00000000
01100110
00000000
00111100
00000000
14 knights. 48 billion recursive calls.

4. Jun 13, 2017

### StoneTemplePython

This problem made a nice little exercise in Julia. Note that if you don't have Julia installed locally, you can run it for free here:

https://juliabox.com/

- - - -

Code (Text):

using JuMP
using Cbc

m = 8

mymodel = Model(solver= CbcSolver())

@variable(mymodel, x[i = 1:m^2], Bin)
@variable(mymodel, y[i = 1:m^2] >=0)

X_matrix = reshape(x, (m, m)) # game board with knight positions
Y_matrix = reshape(y, (m, m)) # squares covered by the knights

i_shifts = [ 1, 1,  2, 2, -1, -1, -2, -2]  # [u 1, u 1, u 2, u 2, d 1, d 1, d 2, d 2]
j_shifts = [-2, 2, -1, 1, -2,  2, -1, 1]   # [l 2, r 2, l 1, r 1, l 2, r 2, l 1, r 1]
shift_size = size(i_shifts)[1]

for i = 1:m
for j = 1:m
running_sum = 0
for idx = 1:shift_size
if (1 <= i + i_shifts[idx] <= m) && (1 <= j + j_shifts[idx] <= m)
# && == "and"
# this checks that your reachable position is not off the board
# if you don't want if stmts, the easiest alternative is to use the padding method suggested by OP
running_sum += X_matrix[i + i_shifts[idx], j + j_shifts[idx]]
end
end
@constraint(mymodel, Y_matrix[i,j] == running_sum)
@constraint(mymodel, Y_matrix[i,j] >= 1)
end
end

@objective(mymodel, Min, sum(X_matrix))

solve(mymodel)

# formatting for a printable output is done below
output = getvalue(X_matrix)
answer_matrix = round(Int64, output)

print("total knights = ", sum(answer_matrix),"\n")
print(isapprox(sum(answer_matrix) - sum(output),0), "\n")
# just a check on floating point nits -- should print "true"

for i = 1:m
print(answer_matrix[i,:],"\n")
end

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted