Loading...

The Rules of 15-Puzzle

Course video 61 of 68

In this module, we consider a well known 15-puzzle where one needs to restore order among 15 square pieces in a square box. It turns out that the behavior of this puzzle is determined by mathematics: it is solvable if and only if the corresponding permutation is even. We will learn the basic properties of even and odd permutations. The task is to write a program that determines whether a permutation is even or odd. There is also a more difficult bonus task: to write a program that actually computes a solution (sequence of moves) for a given position assuming that this position is solvable.

Mathematical Thinking in Computer Science

캘리포니아 샌디에고 대학교

Introduction to Discrete Mathematics for Computer Science 전문 분야에서 5의 강좌 1

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.

강의 계획서 보기

배우게 될 기술

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

강사:

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Vladimir Podolskii
Associate Professor

스크립트

Now, we are looking at an old puzzle of more than a century.

Old, it's called 15-puzzle.

And let me explain the rules.

So you have a small rectangular board, and there are 15 small pieces, small squares.

And what you can do, you can move them.

There is one empty space here.

And if you have an empty space, you can move a piece to this space.

So here are the game rules.

So you can move pieces and the goal is to reach some configuration.

So for example, you start with the initial configuration as you have seen.

And you want to get the same configuration with one change,

14 and 15 are interchanged.

So the question is, of course, whether it's possible or not?

And if you want to do this, maybe it's more convenient to start with

the configuration you want and then to get back the initial configuration.

Of course, it's just like you can go back and

forth if you can get a new configuration from the first one.

Then you can go back and then return to the standard position from a new one,

so it's equivalent question.

And try this, if you succeed, if you can get exchange to pieces 14 and

15, we will pay you some prize, not much, but reasonable.

So would you try?

Let me tell you a story of this game.

It's not very clear actually.

It's clear that it's invented in 19th century and

there is some complicated history, I looked in Wikipedia and

you can look yourselves, but it's not very clear who invented it the first time.

But what is clear, that it was popular at some time.

And indeed like in our case, there were cash prizes announced in the newspaper,

so a lot of people were trying to do this.

And so the question is how the organizer,

why decided that they could do this, why they take the risk?

Because, of course, if many people will ask for a prize,

they will not have enough money to pay them.

So why they take this problem not seriously?

Because they have a proof.

At that moment before they started this publication,

there was a proof that such a thing is not possible.

And so okay, maybe you believe that our proof is incorrect, so

you still can try to get your prize.

But at least it's not that easy.

And for now, our challenge is to reinvent this proof.

So we want to understand what is the proof of possibility.

And in this way, we will develop some small part of

group theory about permutation group specificity but

forget about this mathematical words, we just want to solve the puzzle.

Coursera 소개

세계 최고의 대학교와 교육 기관의 최상위 강사가 가르쳐주는 강좌와 전문 강좌를 듣고 온라인 학위를 취득하세요.

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera는 세계 최고의 교육에 대한 보편적인 접근 기회를 제공하며, 최고의 대학 및 기관들과 제휴하여 온라인 강좌를 제공합니다.

© 2019 Coursera Inc. All rights reserved.

앱스토어에서 다운로드하기

구글 플레이에서 받기