Optimizing Knights on 8x8 Chess Board with Integer Programming

[thomas49th]

Homework Statement

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.

Homework 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.

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

 

[ChristinaK]

Thomas,

Have you ever found the solution to this problem?

Many thanks,
Christina

 

[willem2]

Thomas,

Have you ever found the solution to this problem?

Many thanks,
Christina

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.

 

[StoneTemplePython]

Thomas,

Have you ever found the solution to this problem?

Many thanks,
Christina

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/

- - - -

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

 

[sneider]

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/

- - - -

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

Why de solution is this?
[0,0,0,0,0,0,0,0]
[0,0,1,0,0,1,0,0]
[0,0,1,1,1,1,0,0]
[0,0,0,0,0,0,0,0]
[0,0,1,1,1,1,0,0]
[0,1,1,0,0,1,1,0]
[0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0]
I do not understand the problem yet