Imagine having a standard 8x8 chessboard. We want to use integer programming to find a way to place the maximum number of Queens to the chessboard so that they do not attack each other. (The Queen can move in any direction, up, down, left, right, or diagonal!) 8 0Z0Z0Z0Z 7 Z0Z0Z0Z0 6 0Z0Z0Z0Z 5 Z0ZQZ0Z0 4 0Z0Z0Z0Z 3 Z0Z0Z0L0 2 0Z0Z0Z0Z 1 L0Z0Z0Z0 a b c d e f g h This is an example board where 3 queens are placed so that they cannot attack each other. a) Let Q be the maximum number of Queens that can be placed on this board. Without solving the problem, show that Q 8, that is, the maximum number of queens that can be placed is upper bounded by 8. Be rigorous! Do not just tell me that it cannot be more than 8. Clearly explain your reasoning! b) Model this problem as an integer programming problem. Clearly describe your model, constraints and variables. c) Solve the model you have described in part b) with gurobipy. What is Q? What is the optimum chess board (the location of the queens)?

(30pts) Imagine having a standard 88 chessboard. We want to use integer programming to find a way to place the maximum number of Queens to the chessboard so that they do not attack each other. (The Queen can move in any direction, up, down, left, right, or diagonal!) This is an example board where 3 queens are placed so that they cannot attack each other. a) Let Q be the maximum number of Queens that can be placed on this board. Without solving the problem, show that Q8, that is, the maximum number of queens that can be placed is upper bounded by 8 . Be rigorous! Do not just tell me that it cannot be more than 8 . Clearly explain your reasoning! b) Model this problem as an integer programming problem. Clearly describe your model, constraints and variables. c) Solve the model you have described in part b ) with gurobipy. What is Q ? What is the optimum chess board (the location of the queens)