OK, this example is referring to the problem of minimum queen to cover the whole chessboard.
OK, suppose we have a chess board with a given size special given size.
As you know, chess boards are eight by eight, but suppose a very special case.
It is four by four.
And we want to know what is the minimum number of queens required to protect all of the cells, OK?
And these queens should not attack each other.
So one of the configuration is shown on this graph.
So here you can see that there are three queens.
This is the minimum number of queens required and all of the rows are protected.
For example, this row, the D row and this column are protected by this one.
This column and this row is protected by this one and also.
And you can see here that this guy is protecting this column and Israel and also these two cells and
this cell and this.
OK, so we treat acquis queens.
I have covered all the cells.
OK, but how can we solve this in general mode?
So if you are given in by any chess board, how many queens are required?
What is the minimum number of them required?
OK, so we want to minimize the number of them.
So I have to define a binary value called UIGEA, which is telling us at Cell I and J if there is a
queen or there is not a queen.
OK, so here I am.
This is what we are doing for every given column.
J summation over.
I should be less than equal to one.
It means they are not more than one queen can exist on each column.
Not more than one queen can exist in each row and also on each diagonal.
The number of queens should be less than one, one or less than equal to one.
So it can be won or not.
Nobody.
And also, um.
Um.
For every, um.
Every effort for the anti diagonal cells, the same condition should happen as well.
OK, so let's continue.
The last condition, so whatever we talked about is, um.
This problem is called minimum queen to uncover the chessboard.
So it is a specific problem.
We are trying to find out what is the minimum number of queen required for protecting or covering all
the cells.
And I suppose this example is going to be solved for a very special case of an chessboard with four
by four dimensions.
As we know, usually they have eight by eight.
But this is a special case.
And so you can see here by only three screens located at this specific location, all of the cells are
protected.
For example, this cell is being protected by these two queens and no two ones are attacking each other.
Then we need to define it as an optimization problem, and if we want to solve it for general case,
so we do the summation over IFJ.
Hmm.
And, um, UIGEA is a binary variable and representing the fact that if a queen exists on the cell,
I and J and also for every um, um, given column like J.
Um, if we do the summation over the rows then there will be not more than one queen on each column
and also and there will be not more than one queen on each row on on each a..
Diagonal, on each diagonal.
Uh, rows of cells.
OK, and and so these four conditions are designed for Queenie's not to attack each other.
And also we need another one.
OK, so if we just use these four, then, um, the obvious solution to this problem will be no queen
at all.
OK, so we need another kind of, um, uh, constraint saying that for every IFJ.
Um, if we do the summation of why you see an R and then, um, for every, um, diagonal or A. diagonal
or every row or every column passing through that cell, the summation should be bigger than equal to
one.
OK, so it means that, um, it should be protected by at least one, um, queen.
OK, so, um, if we solve that, we can see the results for the four by four, uh, case, so if N
is for, then the solution is done and also we can test it for a bigger chessboards, six by six or
eight by eight, the traditional one.
So the eight by eight, uh, chessboard can be protected by only five queens.
Hmm.
And if we make it bigger, let's make it ten then it can be protected by six queens.
OK, so I'll show you the Python code for solving this specific optimization problem, which is a linear
programming mix in a linear programming.
As usual, we import the required packages.
Mm.
And is representing the size of size and dimension of the chessboard, I is representing the queens,
different queens and is the areas of I you is a binary variable defined or I and J.
Um, so we need to define some rules for not attacking to each other.
So these three rules are, um, designed in order to um.
Um, sorry, the first one.
Let's have a look at this one first, so the first one is telling us that each cell I and J should be
protected by at least one of these conditions.
So there should be a crane on the diagonal or a. diagonal or is equal to or J is equal to see or from
the same roll.
From the same column or from the diagonal or a. diagonal.
Um, and also the remaining ones are designed in order to not the queen.
Do not attack each other.
As I explained, and the objective function is the summation over UIGEA for every eye in model eye and
for every J in Model J.
The solver is chosen to be good pick because it's integer programming, and then we provide the and
the model to the, um, instance creation, the instance will be created and the results are obtained
after the solve.
And finally, the, uh, solutions are graphically shown here.
OK, and finally, it can be saved somewhere on your machine as a, um, Jimin and Queen Dot PJI, for
example.
OK, so I run the code for you.
Um, it is raining now.
So for simplicity, we have assumed that, um.
Uh, and it's changing between four, six, eight and 10.
You can change that number as well.
OK, I hope you learned something useful in this lecture.
Thank you very much.