In this homework, you will implement a Python script that solves the non$-$attacking knights problem using CPLEX. The task is to find the maximum number of knights that can be placed on an M $\backslash$times N chessboard such that no knight attack some other knight. The decision variables can be formulated as

$1$ if a knight is placed at location $($i$,$j$),$ xij $=0$ otherwise.

The integer linear programming formulation of this problem becomes

NM maximize z $=$ xij

i$=1$ j$=1$

subject to: xij $+$ xkl $<=1($i$,$ j$,$ k$,$ l$)$ where $($i$,$ j$)$ and $($k$,$ l$)$ are attacking locations

xij in $\{0,1\}$ i $=1,2,...,$M; j $=1,2,...,$N$.$

An example of the non$-$attacking knights problem with a $2\backslash$times $6$ chessboard can be given as

maximize subject to:

z$=$x$11+$x$12+$x$13+$x$14+$x$15+$x$16+$x$21+$x$22+$x$23+$x$24+$x$25+$x$26$ x$11+$x$23<=1$

x$12+$ x$24<=1$

x$13+$ x$25<=1$

x$13+$ x$21<=1$ x$14+$ x$26<=1$ x$14+$ x$22<=1$ x$15+$ x$23<=1$ x$16+$ x$24<=1$ x$11$ in $\{0,1\}$ x$21$ in $\{0,1\}$

x$12$ in $\{0,1\}$ x$22$ in $\{0,1\}$

x$13$ in $\{0,1\}$ x$23$ in $\{0,1\}$

x$14$ in $\{0,1\}$ x$24$ in $\{0,1\}$

x$15$ in $\{0,1\}$ x$25$ in $\{0,1\}$

x$16$ in $\{0,1\}$ x$26$ in $\{0,1\}.$

An optimum solution of the example problem with a $2\backslash$times $6$ chessboard is as follows: x$11=1$ x$12=1$ x$13=0$ x$14=0$ x$15=1$ x$16=1$

x$21=1$ x$22=1$ x$23=0$ x$24=0$ x$25=1$ x$26=1$

An example of the non$-$attacking knights problem with a $3\backslash$times $3$ chessboard can be given as

maximize z$=$x$11+$x$12+$x$13+$x$21+$x$22+$x$23+$x$31+$x$32+$x$33$ subject to: x$11+$ x$32<=1$

NM$0$ZNM

MNZ$0$MN

$1$

x$11=0$ x$21=1$ x$31=0$

x$12=1$ x$22=1$ x$32=1$

x$13=0$ x$23=1$ x$33=0$

x$11+$ x$23<=1$ x$12+$ x$33<=1$ x$12+$ x$31<=1$ x$13+$ x$32<=1$ x$13+$ x$21<=1$ x$21+$ x$33<=1$ x$23+$ x$31<=1$ x$11$ in $\{0,1\}$ x$21$ in $\{0,1\}$ x$31$ in $\{0,1\}$

x$12$ in $\{0,1\}$ x$22$ in $\{0,1\}$ x$32$ in $\{0,1\}$

x$13$ in $\{0,1\}$ x$23$ in $\{0,1\}$ x$33$ in $\{0,1\}.$

An optimum solution of the example problem with a $3\backslash$times $3$ chessboard is as follows:

ZNZ NMN ZNZ

Implement your algorithm to solve the non$-$attacking knights problem in a single interactive Python notebook using Azure Lab Services. Your notebook should include at least the following function definition that takes the number of rows and columns as parameters and returns the solution found.

def nonattacking$\_$knights$\_$problem$($M$,$ N$)$:

#implement your algorithm here

return$($X$\_$star, obj$\_$star$)$