Tip:
Highlight text to annotate it
X
In this session, we are going to introduce sets as another fundamental collection
type. We are then going to combine sets and for
expressions in a classical common for search problem.
Namely, the N-queens problem. So far all the collection that we've seen
were sequences of some sort or another. But actually also two other, fundamental
class of collections. One is sets and the other is map.
In this session, we're going to take a closer look at sets.
Sets are actually very close to sequences. You form sets just like sequences so you
could write fruit equals set of apple, banana, pears lets say or S equals one to
six toset. or two set is on operator that takes the sequence and converts the
sequence to a set. Most operations on sequences are also
available on sets. So you could write as map underscore plus
two and then you would. Expect to a set that goes from 3,4,5,6,7,
and eight. Or you could write fruit filter, where the
fruit must start with APP. So that would us a set of just apples.
Or you could ask whether a set is non empty say.
All these operations are shared between sequences and sets.
To find a complete set of operations, you could look in the class iterable.
The common sequence class of second sequence and find all the operations that
are supported there. Or you go and look at the operations in
class set and you find in addition the operation specific to sets.
Well the principal differences between sets and sequences are three.
The first one is that sets are unordered. That means the element of a set do not
have a predefined order in which they appear in the set.
So when I wrote here set of three, four, five, six, seven, eight that's actually
one plus ability but you might just as well see in the output something like set
of five, six three, eight, seven the element's in a different order.
So it's not guaranteed at all that the elements that you put, that you define a
set with will appear in the same order. The second difference is that sets do not
have duplicate elements. So if I would, let's say, map the set, and
I was going from one to six, and I would, So if I would map the set from.
Going from one to six with a function that divides each element by two.
I would obtain the set that contains elements zero, one, two, three.
So this set of six elements has just shrunk to four elements because duplicates
were removed. And the third operation is where, in a
sequence the fundamental operations would be head and tail for lists.
Or indexing for vectors. For set the fundamental operation is
contents. So.
The principal operation that you can do with a set is asking whether there is an
element in the set. So let's now use that eh data structure
and what we've seen so far. In a somewhat more involved problem that
highlights very well the techniques that you could apply to combinatory search.
The problem is one known one. So you start with a chess board Eight By
eight rows normally. I will, draw a smaller version with just
four by four. And the problem is to place queens into
every row of the chess board. Such, that none of the queens is
threatened by another. So, one way to do that here, would be to
place a queen here, and here, and here, and here.
Because in all of these cases, each queen sits in its own row, in its own column.
And it also cannot threaten another queen by following a diagonal.
So now we want to develop a solution for chessboards of any size, not just four or
eight. One way to solve the problem, would be to
place a queen in each row. So we start with the first row.
Place a queen there, then place a queen in the second row and so on.
Once we've placed a number of queens, we must check for the next queen in the
column that does not threaten any of the other queens.
So that it sits in it's own column and it doesn't threaten the other queen's by
following a diagonal. So let's.
That leads to an algorithm for solving the problem.
The algorithm is recursive. Says, suppose that we've already generated
all the solutions consisting of placing K minus one queens on a board of size N.
First question is how do we represent each solution.
So the idea there is you would just represented by their list of length K
minus one, obtaining the numbers of columns between zero and N minus one.
So let's see in this example how that would work.
So I number columns from zero. Something like that.
And then the solution of my first three queens, would be the list of Saying the
last queen that I've placed, that was the queen in the row two.
That column was zero. The one before that I've placed was the
queen in column three. And the first queen I've placed in the
zero row, had column one. So that would be as, partial solution of
the three greens. I can then complete it to a full solution
by adding another green in this column two that I've seen here.
So that solution would evolve to the solution two, zero, three, one that you've
seen on the board. But of course in general there can be more
solutions or none at all. So we're dealing not with a single
solution here, but with sets of solutions. So let's put this into an actual Scala
program. I've opened a new worksheet, call it n
queens. And I've given you already, the signature
of these queens method that finds all solutions to place n queens on a chess
board of n rows. So the input to queens would be the number
of rows of our chess board. And the output would be a set of
solutions. And each solution is a list of int, the
one we've seen. So to implement the queens method, we use
a recursive algorithm with an auxiliary method.
Call it place queens which places a number, K of queens to, on the board and
produces the set of solutions. So the initial call would be place queens
N, which means we place all N, Want to place all N-queens. So now we've
reduced the problem to how to implement the place queens.
Well, let's deal with the boundary case first.
If K equals zero, So if we don't need to place any queen, what do we return?
Well, you might be tempted to say, return the empty set of solutions but that's
actually not quite right, because if we're not asked to do anything that there is a
solution, namely, count to anything. So that means, we return just the empty
list as our solution here. Okay,
So that was the case where K equals zero so now, in the case where K is greater
than zero, we have to do some real work. So, what do we need to do?
So in general, we have to place K queens, we first have to solve the sub problem of
placing K minus one queens, so place the queens up to row K, so we call this.
Kind of way, lets . Now, we have to look at this again, from
the side. Oh, yeah.
So we call this, four queens coming from place queens, K minus one.
So that was the, the set of our partial solutions returned by placed queens K
minus one and we let queens range over it. Now the second thing we would have to
check for is we have to put our K queen into a certain column.
And we will simply try all the possible columns.
So we would say the column ranges from zero until N.
But we can't place the queen in any column we please because we still have to check
that it doesn't threaten any other queen. So we put a test in there, a filter, which
says that the column for the queen is safe with respect to the previous queens.
And if it is then we can yield a new solution.
What would that solution be? Well it would be our partial solution here
augmented by the queen in the new column. So it would be column followed by queens.
So that gives the outline of our solution. There's still one thing to do namely
define this method is safe. So I would like you to do that as an
exercise. So you should write a function is safe
that takes a column for the new green and partial solutions.
I'm sorry that's actually, So the exercise for you is to write a
function is safe. That takes a column for a new queen and an
existing solution call it queens and returns a boolean indicating whether it's
safe to put the new queen in the given column.
It's assumed, of course, that the new queen is placed in the next available role
after all the other placed queens. Well, let's say, if we had put three
queens in row zero to two, then the new queen would be put in row two.
No, no, row three, [laugh]. So, let's say, if we had put three queens
in row zero to two, then the new queen would be put in row three.
So let's see how we would solve this. I've already given you the sigma chart of
each site from the worksheet. The thing to do is work on its
implementation. The first thing I want to do is, I want to
add rows to all the queens that we look at here.
So, the row. Of the queen to be placed.
Let's call it row. So that would be simply queens.length,
because the other queens are in row zero to row minus one.
The next thing I want to do is I want to also add a row to each of these queens, so
transforming the list of INTs to, into a list of pairs of row and columns.
So what I want to do is, let's say if I have a solution, list of 031, partial
solution. Then I want to transform that into a
solution that adds the rows. So, the first element was actually the
last row to be placed, so it was row two. So I would get 2013.
And 01. So I want to go from here to here.
How can we do that? So the idea here is that we use a zip with
a range. So the range that we want to apply here
would be the range that goes from row minus one to zero, by minus one steps.
And that, sequence we zip with, the list of our queens.
And we call that with the row. So that would be now the partial solution
of queens represented with rows. So what we can do now is we can simply
check whether the queen at row, row, and column, column here is in check with any
of these here. So that would be, for all.
For all of these queens it must be that the new queen is not in check.
So when we go through these partial solutions, they're all pairs.
So let's immediately take the row and the column out of the pair.
And now comes our check. So what do we need to check here?
Well the first is of course that the current column is not the same as any
columns of the previous queens. So that would be called different or from
z. And the next the other thing to check is
that the queen is also not in check over any of the diagonals.
What that means is that the. Absolute difference between the two
columns. So call that math dot apps, call minus C
must not be the same as the absolute difference between the two rows.
So that's row minus R, because in this case we know that row is always bigger
than R. So, in that case, if that predicate is
true, then we know that the queen is not in check over any of the diagonals with
the queen in RC. So that's our definition of it's safe.
Let's try to test this with a simple example.
Let's just run queens of four and see what we get.
So what we get is a list of two solutions, 1302 and 2031.
And if you look at it, then it seems that the two solutions are both correct.
But it's better to actually visualize this.
So as a last step, I would like to add a component that shows all solutions as
actual chessboards. So let's try to do that.
I've put up a function here called show, that takes a solution and will print it as
a chess board. You can see that immediately how it would
work. Let's call it queens of four, that now map
would show. So, for each of the solutions, we want to
see that a check chess board, so that's what we get.
We get a set of solutions. And each solution is a four line string.
So here, is this rectangle you see the first one, and, in this rectangle you see
the second one. And as you see, yes it's true, that none
of the x's, which, which represent the queens is in check, with each of the
others, so they are all in their own column, in their own row, and none of them
are on the same diagonal. So let's have a quick look how we, printed
the queens here. So what I did is I had a list of lines,
and that's just essentially. I took the solution but I reversed it
because we know that in the solution later queens comes first.
So, we let the columns range over queens stop reverse.
And then for each of these rows I had to produce the string that consists of
asterisks and the x where the queen is. So the first thing I did, was I produced a
vector with n elements that each red star and a space.
And then I use the updated call, at the column, to replace the star enter space
with an X center space. And then I converted the whole vector of
string elements to a string. There's a handy utility function for that,
make string, will take any collection and simply print out all the elements in the
collection one after the other. So that was how we converted the single
line to a string. To actually Show a whole chessboard.
The idea is that we have to show each line and we have to separate them by new line
characters. So that's another usage of this make
string, which is a function that can also take a second argument.
In that case, it will print each lines separated by the, the second operand here.
So, in that case. That we've seen here.
Lines would be separated by new lines. And I proceeded by an additional new line
character. So that's what you saw here.
We can even make this somewhat nicer by saying.
Instead of the scaffolding with the set here, I just want to convert it directly
into a make string. And, I want to convert sets, maybe by
another new line character like that. So let's see what that would give.
So now I have the solutions in a nicer way.
Each set nicely separated by black lines. Let's play with it a little bit.
If you have some queens of eight. And, we will probably get too many
solutions. And it's a holt.
It's a whole lot of solutions that we get here.
So what we do instead is let's take the first three And there you would have all
the solution of size eight. And inspecting each of them you see that
yes indeed, it is a solution.