1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Nov 24, 2012 #1
    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 [tex]x_{ij}[/tex] 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 [tex]c_{ij}[/tex], 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: [tex]c_{i-1,j-2}[/tex]. 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

    [itex]\sum_{j=1 to 8} \sum_{i = 1 to 8} x_{ij}[/itex]

    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.

    [itex]\sum_{j=1 to 8} \sum_{i = 1 to 8} x_{ij} ≥ 64 [/itex]

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

    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. jcsd
  3. Jun 10, 2017 #2
    Thomas,

    Have you ever found the solution to this problem?

    Many thanks,
    Christina
     
  4. Jun 11, 2017 #3
    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.
     
  5. Jun 13, 2017 #4

    StoneTemplePython

    User Avatar
    Gold Member

    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



Similar Discussions: Integer Programming: Chess - n° of knights needed so that every square is covered
  1. C program help needed (Replies: 3)

Loading...