JavaRush /Курсы /Harvard CS50 /Пятнашки: начало

Пятнашки: начало

Harvard CS50

3 уровень , 14 лекция

Открыта

Настало время поиграть! Большинство людей знакомы с головоломкой «Пятнашки». Если формализовать, «Пятнашки» — это двумерное поле 4х4, в этом поле расположены не 16, а 15 квадратиков, то есть один слот остается пустым. Каждый из квадратиков пронумерован и может двигаться внутри поля по горизонтали или вертикали (если, конечно, есть куда двигаться). Цель — расположить числа по порядку, от 1 до 15 слева направо сверху вниз. Тогда пустое место окажется в правом нижнем углу.

Движение любой плитки (или нескольких) является «шагом» в этом игровом пространстве. Представленная на картинке выше комбинация уже сложена, но обратите внимание, что плитки 12 или 15 могут быть сдвинуты в пустое пространство. Правила гласят, что плитка не может перемещаться по диагонали или извлекаться из игральной доски.

На самом деле конфигураций для начала игры — много (можете посчитать, сколько именно), но давайте для простоты расположим плитки в порядке от наибольшей к наименьшей, и оставим пустое пространство в правом нижнем углу доски. Единственное, давайте поменяем местами 1 и 2, чтобы головоломка была разрешимой.

Кстати: если высыпать все плитки из поля, а затем вставить их обратно в случайном порядке, то после этого вы сможете расположить их в правильном порядке (то есть решить задачу) только в половине случаев! Этот факт математически доказан.

Теперь перейдите в директорию ~/ рабочей среды, затем — в /pset3/fifteen и откройте файл fifteen.c.

В нем — код «движка» игры. Задание состоит в том, чтобы дописать код игры.

Но для начала давайте откомпиллируем наш «движок» (вы наверняка уже знаете, как это сделать). Невзирая на то, что игра не закончена, запустить приложение можно.

Будет удобнее запустить его в большем, чем обычно, окне терминала, которое можно открыть, нажав на зеленый плюс (+) рядом с одной из вкладок кода и выбрав New Terminal. Или же можно открыть терминальное окно на полный экран, кликнув на иконку Maximize в правом верхнем углу консоли.

Вы видите, что кое-что кое-как работает. Но на самом деле большая часть игры ещё не написана. И вот тут — приготовьтесь — ваш выход!

Исследование

Изучите код и комментарии fifteen.c, после чего ответьте на вопросы ниже:

Помимо доски 4х4, какую размерность поля допускает наш движок?
Какой структурой данных является игровое поле?
Какая функция вызывается для приветствия игрока в начале игры?
Какие функции вам необходимо реализовать?

Реализация

Что ж, начнём реализовывать игру. Помните, мы двигаемся крохотными шажками, не нужно пытаться сделать всё и сразу. Вместо этого будем реализовывать функции по очереди. Убедитесь, что они работают прежде, чем двигаться вперед. Мы предлагаем вам реализовать функции игры в следующем порядке: init (инициализация), draw (прорисовка), move (сделать шаг), won (выигрыш). Дизайнерские решения (например, сколько пробелов нужно вставлять между нашими плитками-числами) — остаются за вами. Игровое поле должно выглядеть примерно так:

15 14 13 12

11 10  9  8

7  6  5  4

3  1  2  _

Еще раз обращаем внимание, что в стартовой позиции 1 и 2 расположены в обратном порядке (это касается классического поля 4х4 если количество плиток — нечетное). Если количество плиток чётное, а поле — 3х3, менять две «младшие» плитки местами не нужно.

Чтобы протестировать вашу реализацию «Пятнашек», нужно попробовать поиграть в них (не забывайте, аварийный выход из программы до её естественного завершения можно вызвать комбинацией клавиш crtl+c). Убедитесь, что программа будет работать, если будут введены неправильные числа. И помните, что точно так же, как вы автоматизировали ввод в find, вы можете автоматизировать «прохождение» игры.

На деле, в папке ~cs50/pset3 есть файлы 3×3.txt и 4×4.txt, где собраны все последовательности шагов для победы на полях размерности 3х3 и 4х4. Чтобы протестировать программу, например, с помощью первого из файлов, выполните следующую команду:

./fifteen 3 < ~cs50/pset3/3x3.txt

Настройте нужный вам аргумент для ускорения анимации. Да и вообще, при желании вы всегда можете изменить игру. Чтобы поразвлекаться с «управляющими последовательностями ANSI», включая цвет. Обратите внимание на нашу реализацию clear и проверьте http://isthe.com/chongo/tech/comp/ansi_escapes.html чтобы усвоить новые трюки.

При желании напишите свои собственные функции или поменяйте прототипы функций, которые писали мы. Единственное ограничение — не меняйте логику функции main, иначе мы не сможем применить к ней некоторые автоматические тесты для подтверждения корректности работы вашей программы. В частности, main должна возвращать 0, в том и только том случае, если пользователь сложил головоломку. Не нулевые значения нужно вернуть для всех вариантов ошибок.

Если возникают какие-то ошибки, пишите нам. Ну а если захотите поиграть с реализацией приложения, подготовленного ассистентами CS50, выполните следующую команду:

~cs50/pset3/fifteen

Если вам интересно увидеть более крутую реализацию, с автоматическим решением головоломки, посмотрите «Хакерскую» версию программы:

~cs50/hacker3/fifteen

Вместо того чтобы ввести номер в окошке игры, напечатайте слово GOD. Здорово, не так ли?

Если хотите проверить правильность вашей программы официально с check50, обратите внимание, что check50 предполагает, что пустое пространство игрового поля заполнено 0; если вы выбрали другое значение, для корректной проверки замените его на нуль. Кроме того, check50 предполагает, что вы индексируете поля игрового поля в порядке [ряд] [столбец], а не доска [столбец] [строка].

check50 2015.fall.pset3.fifteen fifteen.c

Подробнее о реализации функций игры `Fifteen`

init (инициализация)
draw (прорисовка)
move (сделать шаг)
won (выигрыш)

init

В этой функции мы представляем игровое поле. Для этого используем двумерный массив целых чисел. Размерность массива — MAXxMAX, где MAX — константа, обозначающая максимальное количество плиток, которые могут поместится в строке или столбце поля.

Таким образом нам нужно определить переменную int board[MAX][MAX]

Однако вспомним, что размерность игрового поля определяет пользователь. Поэтому нужно определить переменную, которая бы обозначала размерность доски, которую должен ввести пользователь. Это int d.

где d — размерность доски, d <= MAX. Однако в Cи вы не можете менять размер массива, поэтому придется довольствоваться максимальной размерностью. В init вам нужно поместить значения на доску.

Почитайте больше о двумерных массивах, если вы с ними ещё не работали. Вкратце, у них два индекса, первый обозначает номер строки, второй — номер столбца. Для нашей задачи мы начинаем с максимального числа и заканчиваем в случае d = 3 («Восьмяшки») единицей и пустым углом. Если у нас все-таки «Пятнашки», тогда 1 и 2 меняем местами. Что же делать с пустым местом? Наш массив состоит из целых чисел, поэтому и пустота должна быть заполнена неким целым. Поэтому вы должны выбрать некое целое число для инициализации пустой плитки (а в случае физической игры, её отсутствие).

Чтобы инициализировать игровое поле и заполнить его стартовым набором плиток, можно использовать циклы.

Ведем циклы по индексам i и j, где board[i][j] — плитка, которая находится в строке номер i и столбце номер j. Заполняем доску в убывающем порядке. В случае, если количество плиток (без пустой) — нечетное, меняем местами 1 и 2.

draw

Эта функция должна напечатать текущее состояние игрового поля. Помним, что у нас могут быть значения с одним или двумя разрядами, поэтому для красивого форматирования после чисел 1-9 функция должна печатать пробел (#s). Это можно организовать с помощью плейсхолдера %2d.

printf (“%2d”, board[i][j]);

Также не забывайте о пустой клетке. Выберите символ, который будет её представлять (в нашем примере — это нижнее подчеркивание). Функция draw должна отрисовывать этот символ, как только вы попадаете на пустую клетку. Итак, наш цикл будет примерно таким:

for каждой строки 
for каждого элемента строки 
print значение и пробел 
print новую строку

Запомните, что порядок, в котором функция draw выводит на экран плитки, должен отображать порядок, в котором они находятся в массиве, определенном в функции init.

move

Как только вы инициализировали игровое поле и нарисовали начальные позиции плиток, нужно позволить пользователю редактировать положение плиток, то есть, совершать движения.

Итак, в fifteen.c программа принимает вывод от пользователя, строит игровое поле и затем вызывает функцию move, и говорит, какую плитку он хочет подвинуть. Будьте внимательны: вы применяете функцию именно к номеру на плитке, а не к её положению на доске (в массиве). Таким образом, вам нужно найти актуальное положение плитки. Кроме того, вы должны позволить пользователю подвинуть плитку только тогда, когда это возможно.

На картинке выше мы можем подвинуть только плитки номер 2, 5 и 8. Как это определить? По значению пустой плитки. Таким образом, функция move работает примерно так:

Принимает номер плитки, который пользователь хочет подвинуть.
Ищет положение в массиве (на игровом поле) этой плитки.
Запоминает позицию пустой плитки.
Если пустая плитка соседствует с той, которую пользователь хочет подвинуть, они меняются местами в массиве.

won

Эта функция проверяет, завершилась ли игра после каждого шага пользователя. Она возвращает true, если плитки стоят в правильном порядке (в том числе и положение пустой плитки в правом нижнем углу). В таком случае программу можно завершить. Если же плитки всё еще разбросаны, функция возвращает false и передает бразды правления функции move.

Как организовать проверку? Как и в случае инициализации и рисования доски — с помощью двух вложенных циклов for. Например, можно задать условие, что каждое последующее число в массиве должно быть больше предыдущего. Обратите внимание на то, какое значение записано в пустой плитке. Или другой способ — используйте счетчик, чтобы убедиться, что все плитки на местах, если справитесь и напишете формулу, чтобы это получить. Желаем удачи в экспериментах!

Предыдущая Предыдущая лекция

Следующая Следующая лекция

Комментарии (33)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

Inna Уровень 32

11 декабря 2021

здесь все такие умные 😱 только ничего не понимаю 😞

Артём Венский Уровень 1

7 декабря 2021

void init(void) { // fill the array int count=d*d-1; for (int i=0; i<d; i++) { for (int j=0; j<d; j++) { board[i][j]=count; count--; } } if (d%2==0) { int buf=board[d-1][d-2]; board[d-1][d-2]=board[d-1][d-3]; board[d-1][d-3]=buf; } } /** * Prints the board in its current state. */ void draw(void) { // draw the board with tiles for (int i=0; i<d; i++) { for (int j=0; j<d; j++) { if (board[i][j]==0) printf(" \t"); else printf("%2d\t", board[i][j]); } printf ("\n"); } } /** * If tile borders empty space, moves tile and returns true, else * returns false. */ bool move(int tile) { //coordinats for tile and space int it, jt, io, jo; //find coordinats for (int i=0; i<d; i++) { for (int j=0; j<d; j++) { if (board[i][j]==tile) { it=i; jt=j; } if (board[i][j]==0) { io=i; jo=j; } } } //check if tiles free to go if ((io==it)&&(abs(jo-jt)==1)) { board[io][jo]=board[it][jt]; board[it][jt]=0; return true; } else if ((abs(io-it)==1)&&(jo==jt)) { board[io][jo]=board[it][jt]; board[it][jt]=0; return true; } return false; } /** * Returns true if game is won (i.e., board is in winning configuration), * else false. */ bool won(void) { //check if game is won int w=0; int wc=1; for (int i=0; i<d; i++) { for (int j=0; j<d; j++) { if (board[i][j]==wc) { w++; } } } if (w==15) { return true; } return false; }

Сергей Уровень 1

24 марта 2021

Народ, публикую свою версию кода. Взял идею у предыдущих студентов, немного доработал неясные для меня узлы. void init(void) { // Здесь мы устанавливаем количество заполненных ячеек const int count = d * d - 1; int n = count; int t; // Заполняем двумерный массив числами в обратном порядке for (int row = 0; row < d; row++) { for (int column = 0; column < d; column++) { //Здесь прописываем пустым последнюю клетку if (row == d - 1 && column == d - 1) { board[row][column] = '_'; } else { board[row][column] = n--; } } } // Здесь мы меняем последние два значения ячеек местами. { t = board[d - 1][d - 2]; board[d - 1][d - 2] = board[d - 1][d - 3]; board[d - 1][d - 3] = t; } } void draw(void) { for (int row = 0; row < d; row++) { for (int column = 0; column < d; column++) { if (board[row][column] == '_') { // здесь символ %2c означает два знака для пустой клетки printf(" %2c", (char) (board[row][column])); } else { // здесь символ %2d означает два знака для пустой клетки printf(" %2d", board[row][column]); } } printf("\n"); } }

Сергей Уровень 1

24 марта 2021

bool move(int tile) { int x; int y; int mx; int my; //Ищем введенное значение клетки и сравниваем ее с пустой клеткой for (int row = 0; row < d; row++) { for (int column = 0; column < d; column++) { if (board[row][column] == tile) { x = row; y = column; } else if (board[row][column] == '_') { mx = row; my = column; } } } if ((x == mx - 1 && y == my) || (x == mx + 1 && y == my) || (x == mx && y == my - 1) || (x == mx && y == my + 1)) { int t; t = board[x][y]; board[x][y] = board[mx][my]; board[mx][my] = t; return true; } return false; } bool won(void) { int win = 1; { for(int row = 0; row < d; row++) { for(int column = 0; (column < d) && (win < d * d); column++, win++) if (board[row][column] != win) return false; } } return true; }

Shahin Уровень 2

30 ноября 2022

как ты помещаешь символ '_' в массив целых чисел? По условию говорится,что в массиве пустая плитка должна быть заменена целым числом.

Ихтияр Кадыров Уровень 1

15 марта 2020


/**
 * Initializes the game's board with tiles numbered 1 through d*d - 1
 * (i.e., fills 2D array with values but does not actually print them).  
 */
void init(void)
{
    const int count_board = (d * d) - 1;
    int n = count_board;

    /**
     * Заполняет двумерный массив board
     * числами в обратном порядке.
     */
    for (int row = 0; row < d; row++)
    {
        for (int column = 0; column < d; column++)
        {
            if (row == d-1 && column == d-1)
            {
                board[row][column] = '_';
            }
            else
            {
                board[row][column] = n--;
            }
        }
    }

    // меняет местами 1 и 2 если count_board нечётное
    if ((count_board % 2) != 0)
    {
        swap_int(&board[d-1][d-2], &board[d-1][d-3]);
    }
}

/**
 * Prints the board in its current state.
 */
void draw(void)
{
    for (int row = 0; row < d; row++)
    {
        for (int column = 0; column < d; column++)
        {
            if (board[row][column] == '_')
            {
                printf(" %2c", (char) (board[row][column]));
            }
            else
            {
                printf(" %2d", board[row][column]);
            }
        }
        printf("\n");
    }
}

Ихтияр Кадыров Уровень 1

15 марта 2020


/**
 * If tile borders empty space, moves tile and returns true, else
 * returns false. 
 */
bool move(int tile)
{
    int tileX,
        tileY, 
        blankTileX, 
        blankTileY;

    /**
     * ищет положение плитки, которую хочет
     * передвинуть игрок, и положение пустой плитки
     */
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < d; j++)
        {
            if (board[i][j] == tile)
            {
               tileX = i; 
               tileY = j;
            }
            else if (board[i][j] == '_')
            {
               blankTileX = i;
               blankTileY = j;
            }
        }
    }

    /**
     * проверяет соседствует ли пустая плитка 
     * с тем что хочет передвинуть игрок 
     */
    if ((tileX != blankTileX) || (tileY != blankTileY))
    {
        if ((tileX == blankTileX-1 && tileY == blankTileY)   || 
            (tileX == blankTileX+1 && tileY == blankTileY)   ||
            (tileX == blankTileX   && tileY == blankTileY+1) ||
            (tileX == blankTileX   && tileY == blankTileY-1))
            {
                 swap_int(&board[tileX][tileY], &board[blankTileX][blankTileY]);
                 return true;
            }
    }

    return false;
}

/**
 * Returns true if game is won (i.e., board is in winning configuration), 
 * else false.
 */
bool won(void)
{
    /**
     * проверяет стоят ли все номера плиток
     * и пустая плитка на своих местах
     */
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < d; j++)
        {
            if (i == d-1 && j == d-1)
            {
                if (board[i][j] != '_')
                {
                     return false;
                }
            }

            if (i != d-1 && j != d-1)
            {
                if (board[i][j]+1 != board[i][j+1])
                {
                    return false;
                }



  Ихтияр Кадыров
      Уровень 1

      

      
    15 марта 2020
      
  

/**
 * swap_int производит обмен между двумя
 *          целочисленными переменными
 *          
 * @param left  [variable 1]
 * @param right [variable 2]
 */
void swap_int(int* left, int* right)
{
    
   if (*left == *right)
   {
      return;
   }

   register int tmp = *left;
                *left = *right;
                *right = tmp;
}



  Ихтияр Кадыров
      Уровень 1

      

      
    27 февраля 2020
      
  /* Комментарий удален */



  Алексей Кочергин
      Уровень 1

      

      
    26 октября 2018
      
  Друзья, а хакерскую версию с A* алгоритмом кто-нибудь решил? Очень хотелось бы видеть решение с пояснением.



  eight-bit-samurai
      Уровень 17

      

      
    10 сентября 2018
      
  Мои 4 функции:

/**
 * Initializes the game's board with tiles numbered 1 through d*d - 1
 * (i.e., fills 2D array with values but does not actually print them).
 */
void init()
{
    for (int i = 0, numTile = d*d - 1; i < d; i++)
        for (int j = 0; j < d; j++, numTile--)
            board[i][j] = numTile;

    if (d % 2 == 0)
        board[d-1][d-2] ^= board[d-1][d-3] ^= board[d-1][d-2] ^= board[d-1][d-3];
}

/**
 * Prints the board in its current state.
 */
void draw()
{
    for (int i = 0; i < d; i++) {
        for (int j = 0; j < d; j++) {
            board[i][j] ? printf("%3i", board[i][j]) : printf("___");

            if (j < d - 1)
                printf("|");
        }

        printf("\n");

        if (i < d - 1) {
            for (int j = 0; j < d - 1; j++)
                printf ("---+");
            printf ("---\n");
        }
    }
}


  

  jane_belousova
      Уровень 0

      

      
    20 октября 2018
      
  Где ещё две?

  


  eight-bit-samurai
      Уровень 17

      

      
    20 октября 2018
      
  комментом ниже

  


  jane_belousova
      Уровень 0

      

      
    24 октября 2018
      
  спасибо

  


  enot_00
      Уровень 1

      

      
    30 октября 2018
      
  Не работает.


  


  eight-bit-samurai
      Уровень 17

      

      
    1 ноября 2018
      
  Значит вы что-то неправильно делаете

  


  enot_00
      Уровень 1

      

      
    1 ноября 2018
      
  заработало. Все ок. И мой вариант, и ваш, и гибрид вашего и моего.

  


  Konstantin Shpilevski
      Уровень 2

      

      
    2 ноября 2018
      
  board[d-1][d-2] ^= board[d-1][d-3] ^= board[d-1][d-2] ^= board[d-1][d-3];
Как это работает? 

  


  eight-bit-samurai
      Уровень 17

      

      
    2 ноября 2018
      
  Это XOR своп значений двух переменных без использования временной третьей:
x ^= y;
y ^= x;
x ^= y;
Поскольку в Си допускаются последовательные присваивания, то эти 3 строки можно укоротить до одной с порядком вычисления справа налево:
x ^= y ^= x ^= y;



  eight-bit-samurai
      Уровень 17

      

      
    10 сентября 2018
      
  
/**
 * If tile borders empty space, moves tile and returns true, else
 * returns false.
 */
bool move(int tile)
{
    for (int i = 0; i < d; i++) {
        for (int j = 0; j < d; j++) {
            if (board[i][j] == 0) {
                if ((j < d - 1) && (board[i][j+1] == tile)) {
                    board[i][j] ^= board[i][j+1] ^= board[i][j] ^= board[i][j+1];
                    return true;
                }
                else if ((i < d - 1) && (board[i+1][j] == tile)) {
                    board[i][j] ^= board[i+1][j] ^= board[i][j] ^= board[i+1][j];
                    return true;
                }
                else if ((i > 0) && (board[i-1][j] == tile)) {
                    board[i][j] ^= board[i-1][j] ^= board[i][j] ^= board[i-1][j];
                    return true;
                }
                else if ((j > 0) && (board[i][j-1] == tile)) {
                    board[i][j] ^= board[i][j-1] ^= board[i][j] ^= board[i][j-1];
                    return true;
                }
                else
                    return false;
            }
        }
    }

    printf("Error 404: tile not found! Contact with developer for bug fixes\n");
    return false;
}

/**
 * Returns true if game is won (i.e., board is in winning configuration),
 * else false.
 */
bool won()
{
    for (int i = 0, numTile = 1; i < d; i++)
        for (int j = 0; (j < d) && (numTile < d*d); j++, numTile++)
            if (board[i][j] != numTile)
                return false;

    return true;
}


  

  Ilya Mikhailov
      Уровень 0

      

      
    17 января 2019
      
  интересное решение для побитового свапа, но мне кажется лучше было сделать переменную для координат пустой клетки нежели "прочесывать" массив в ее поиске 

  


  Александр
      Уровень 19

      

      
    28 февраля 2020
      
  твой вариант метода won() не рабочий


  


  eight-bit-samurai
      Уровень 17

      

      
    28 февраля 2020
      
  что именно не так?

  


  Александр
      Уровень 19

      

      
    5 марта 2020
      
  протестируйте, по крайней мере у меня с полем 3 на 3 при решенном поле, он не засчитывал мне победу

  


  eight-bit-samurai
      Уровень 17

      

      
    5 марта 2020
      
  Странно, у меня всё работает.


  


  Александр
      Уровень 19

      

      
    5 марта 2020
      
  понял, значит у меня что-то не так, буду дальше код ковырять)



  Артем
      Уровень 38

      

      
    7 марта 2018
      
  Команда для проверки: check50 cs50/2017/x/fifteen



  Дамир Хафизов
      Уровень 0

      

      
    2 марта 2018
      
  Прикольное задание. Но лучше всё после Подробнее о реализации функций игры Fifteen лучше спрятать под спойлер, потому что до этих решений нужно самому додумываться. На реальной работе никто алгоритм за нас не продумает.