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