- #1
thomas49th
- 655
- 0
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 [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