Knights on a Chessboard

Loading...

Aus dem Kurs von University of California San Diego

Mathematical Thinking in Computer Science

473 Bewertungen

University of California San Diego

Mathematical Thinking in Computer Science

473 Bewertungen

Kurs 1 von 5 in Specialization Introduction to Discrete Mathematics for Computer Science

Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In the course, we use a try-this-before-we-explain-everything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself. Prerequisites: 1. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.

Aus der Unterrichtseinheit

How to Find an Example?

How can we be certain that an object with certain requirements exist? One way to show this, is to go through all objects and check whether at least one of them meets the requirements. However, in many cases, the search space is enormous. A computer may help, but some reasoning that narrows the search space is important both for computer search and for "bare hands" work. In this module, we will learn various techniques for showing that an object exists and that an object is optimal among all other objects. As usual, we'll practice solving many interactive puzzles. We'll show also some computer programs that help us to construct an example.

Subset without x and 100-x4:10

Rooks on a Chessboard2:39

Knights on a Chessboard5:09

Bishops on a Chessboard2:42

Subset without x and 2x6:24

Treffen Sie die Kursleiter

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

Our next puzzle is about knights on a chessboard.

Knight moves in an L-shape.

For example,

the knight shown here on this slide can move to any of the shown eight positions.

The knight moves by one cell vertically and

two cells horizontally, or vice versa.

Okay, so the natural question, you can guess it already, of course, is,

what is the maximum number of knights that one can place on a chessboard

such that no two knights attack each other?

While trying to solve this problem,

let's take a look once again on the allowed moves for the knight.

Okay, as we see, the knight here stays on a white cell.

And all the eight cells that it attacks, are actually of an opposite color.

They're all black, right?

So this already tells us something.

So it tells us that if we place

knights on all 32 white cells like here,

then definitely no two of them are going to attack each other.

So you can either check this manually, or you can either once again notice that

a knight standing on a white cell only attacks black cells.

Right, so this is already good.

We have a solution where we have 32 knights.

It is still at the same time not clear whether it is optimal or not.

It is clear that this one cannot be expanded,

we cannot put more knights here on the chess board.

At the same time, it is still not excluded that there is some

other solution whose size is greater than 32.

So let's try to understand how one would show that it

is not possible to place more than 32 knights.

First of all, why we cannot just place knights to all 64 cells?

Just because in particular, it is not possible to

place knights simultaneously to these two cells,

to the left bottom corner and to the position shown here on this slide.

So in a sense, these two cells form a pair.

For this pair of cells, we can select only one of them.

We cannot select them simultaneously.

Like in one of the examples shown,

considered before.

To reflect this fact, let's connect them by a segment.

And now let's realize the following.

It would be great if we could partition all our 64 cells into such pairs.

In this case, we would be done, just because this would mean that

everything is partitioned into pairs, and so the number of pairs is 32.

And for every pair, we know that we can make at most one cell.

We can place at most one knight into these two cells.

This will immediately mean that 32 is indeed optimal.

The only thing which is still not clear is how to partition

the whole work in to such pairs.

So let's at least try to do this.

So first of all we have this pair.

Let's add this symmetrical pair.

Let's now add two more pairs, which are also, in a sense, similar.

And now, we have this nice feature.

Why it is nice?

Because it is already a rectangle.

It is a two by four rectangle.

And so what we already know is that for this two by four rectangle, the number

of knights that can be placed inside this rectangle is at most four, right?

Because there are eight cells in this rectangle.

And all these eight cells are partitioned into four pairs.

For each pair, we know that, for each pair of such cells,

we know that we can place at most one knight into them.

So there are four pairs, and for each pair we can place at most one knight.

So at most four knights.

Which is great, already.

And the fact that this rectangle is of size two by four actually implies

that we can partition the whole board into such rectangles, right?

Like these, which in turn means that we can

partition the whole board into such pairs, which finally proves

that 32 is indeed the answer for our initial problem.

Durchsuchen Sie unseren Katalog

Melden Sie sich kostenlos an und erhalten Sie individuelle Empfehlungen, Aktualisierungen und Angebote.

Coursera arbeitet mit erstklassigen Universitäten und Organisationen zusammen, um Online-Kurse anzubieten und dadurch universellen Zugriff auf die weltweit beste Ausbildung zu ermöglichen.

© 2019 Coursera Inc. Alle Rechte vorbehalten.

Aus dem App Store herunterladen

Erhältlich bei Google Play