Skip to content

21.y — Chapter 21 project ​


🎯 Mục Tiêu Bài Học ​

  • Nắm vững bản chất lý thuyết và cơ chế hoạt động của Chapter 21 project trong tiêu chuẩn ISO C++.
  • Hiểu rõ cách máy tính tổ chức bộ nhớ (RAM, CPU registers) khi thực thi mã nguồn liên quan.
  • Nhận biết các cạm bẫy lỗi kinh điển (Undefined Behavior, Memory Leak, Bug logic) và cách phòng tránh.
  • Áp dụng các quy tắc thực hành tốt nhất (Best Practices) chuẩn công nghiệp và cập nhật C++20/C++23 hiện đại.

21.y — Chapter 21 project ​

A tip o’ the hat to reader Avtem for conceiving of and collaborating on this project.

Project time ​

Let’s implement the classic game 15 Puzzle!

In 15 Puzzle, you begin with a randomized 4×4 grid of tiles. 15 of the tiles have numbers 1 through 15. One tile is missing.

For example:

cpp
15   1   4
  2   5   9  12
  7   8  11  14
 10  13   6   3

In this puzzle, the missing tile is in the upper-left corner.

Each turn of the game, you pick one of the tiles that is adjacent to the missing tile, and slide it into the spot occupied by the missing tile.

The goal of the game is to slide tiles around until they are in numerical order, with the missing tile in the bottom right corner:

cpp
1   2   3   4
  5   6   7   8
  9  10  11  12
 13  14  15

You can play a few rounds on this site. It will help you to understand how this game works and how it should be implemented.

In our version of the game, each turn the user will enter a single letter command. There are 5 valid commands:

  • w - slide tile up

  • a - slide tile left

  • s - slide tile down

  • d - slide tile right

  • q - quit game

Because this is going to be a longer program, we’ll develop it in stages.

One more thing: at each step, we’ll present two things: a goal and tasks. The goal defines the outcome that the step is trying to achieve, along with any additional relevant information. The tasks provide detail and hints about how to implement the goal.

The tasks will initially be hidden from view, to encourage you to see if you can complete each step using just the goal and sample output or sample program. If you are unsure how to start, or are feeling stuck, you can unhide the tasks. They should help get you moving forward.

> Step #1

Because this is going to be a bigger program, let’s start with a design exercise.

Author’s note

If you don’t have much experience designing programs up-front, you may find this a bit difficult. That’s expected. It’s less important that you get it right, and more important that you participate and learn.

We will go into more detail on all of these items in subsequent steps, so if you are feeling completely lost, feel free to skip this step.

Goal: Document the key requirements for this program, and plan how your program will be structured at a high level. We will do this in three parts.

A) What are the top-level things that your program needs to do? Here are a few to get you started:

Board things:

  • Display the game board

  • …

User things:

  • Get commands from user

  • …

Xem lời giải (Solution)

Board things:

  • Display the game board

  • Display an individual tile

  • Randomize the starting state

  • Slide tiles

  • Determine if win condition reached

User things:

  • Get commands from user

  • Handle invalid input

  • Allow the user to quit before winning

B) What primary classes or namespaces will you use to implement the items outlined in Step 1? Also, what will your main() hàm do?

You can create a diagram, or use two tables like this:

Primary class/namespace/main Implements top-level items Members

class Board Display the game board … …

hàm main Main game logic loop … …

Xem lời giải (Solution)

Primary class/Namespace/main Implements top-level items Members (type)

class Board Display the game board Randomize the starting state Slide tiles Determine if win condition reached 2d array of Tile

class Tile Display an individual tile int display number

namespace UserInput Get commands from user Handle invalid input none

hàm main() Main game logic loop Allow user to quit before winning none

Here is some rationale behind the choices above.

  • class Board: Our game is a 4×4 grid of tiles. The main purpose of this class is to store and manage the 2-dimensional array of tiles. This class is also responsible for randomizing, moving tiles, displaying the board, and checking whether our board is solved.

  • class Tile: This class represents a single tile within the game board. Using a class here allows us to overload the output toán tử to output a tile in the format we desire. It also allows us to have well-named member các hàm that will increase the readability of code related to a single tile.

  • namespace UserInput: This namespace has các hàm to get input from the user, to check whether the user input is valid, and to handle invalid input. Because this doesn’t have any state, we don’t need a class here.

  • hàm main(): This is where our main game loop will be written. This will handle setup of the game board, coordinate retrieving user input and command processing, and handle exit conditions (when the user wins or enters the quit command).

We also will make use of two helper classes. The need for these classes may not be obvious at first glance, so don’t worry if you didn’t come up with anything similar. Often the need for (or benefit of) helper classes isn’t apparent into you get further into the implementation of your program.

C) (extra credit) Can you think of any helper classes or capabilities that will make implementing the above easier or more cohesive?

Xem lời giải (Solution)

Helper class/Namespace What does this help with? Members (type)

class Point Indexing the game board tiles int x-axis and y-axis coordinates

class Direction Make working with Directional commands easier and more intuitive
enum direction

  • class Point: Accessing a specific tile in our 2d array of tiles will require 2 indices. We can think of these as { x-axis, y-axis } index pairs. This Point class implements such an index pair, to make it easy to pass or return a pair of indices.

  • class Direction: The user will be entering single-letter (char) commands on the keyboard to slide tiles in cardinal directions (e.g. 'w'=up, 'a'=left). Converting these char commands into a Direction object (representing a cardinal direction) will make our code more intuitive and prevent our code from being littered with char các hằng giá trị (literals) (Direction::left is more meaningful than 'a').

If you had a hard time with this exercise, that’s okay. The goal here was mainly to get you thinking about what you’re going to do before you start doing it.

Now, it’s time to get implementing!

> Step #2

Goal: Be able to display individual tiles on the screen.

Our game board is a 4×4 grid of tiles that can slide around. Therefore, it will be useful to have a Tile class that represents one of the numbered tiles on our 4×4 grid or the missing tile. Each tile should be able to:

  • Be given a number or be set as the missing tile

  • Determine whether it is the missing tile.

  • Draw to the console with the appropriate spacing (so the tiles will line up when the board is displayed). See the sample output below for an example indicating how tiles should be spaced.

Show Tasks

Our Tile class should have this functionality:

  • A default hàm tạo (constructor).

  • A hàm tạo (constructor) that lets us create a Tile with a display value. Because we are not using 0 as a display value, we can use value 0 to identify our missing tile.

  • A getNum() access hàm that returns the value held by the tile.

  • An isEmpty() member hàm that returns a bool indicating whether the current tile is the missing tile.

  • An overloaded toán tử<< that will display the value held by the tile.

The following code should compile and produce the output result you can see below the code:

cpp
int main()
{
    Tile tile1{ 10 };
    Tile tile2{ 8 };
    Tile tile3{ 0 }; // the missing tile
    Tile tile4{ 1 };

    std::cout << "0123456789ABCDEF\n"; // to make it easy to see how many spaces are in the next line
    std::cout << tile1 << tile2 << tile3 << tile4 << '\n';
    
    std::cout << std::boolalpha << tile1.isEmpty() << ' ' << tile3.isEmpty() << '\n';
    std::cout << "Tile 2 has number: " << tile2.getNum() << "\nTile 4 has number: " << tile4.getNum() << '\n';
    
    return 0;
}

Expected output (pay attention to the white spaces):

cpp
0123456789ABCDEF
 10   8       1 
false true
Tile 2 has number: 8
Tile 4 has number: 1
Xem lời giải (Solution)
cpp
#include <iostream>

class Tile
{
public:
    Tile() = default;
    explicit Tile(int number)
        :m_num(number)
    {
    }

    bool isEmpty() const
    {
        return m_num == 0;
    }

    int getNum() const { return m_num; }

private:
    int m_num { 0 };
};

std::ostream& operator<<(std::ostream& stream, Tile tile)
{
    if (tile.getNum() > 9) // if two digit number
        stream << " " << tile.getNum() << " ";
    else if (tile.getNum() > 0) // if one digit number
        stream << "  " << tile.getNum() << " ";
    else if (tile.getNum() == 0) // if empty spot
        stream << "    ";
    return stream;
}

int main()
{
    Tile tile1{ 10 };
    Tile tile2{ 8 };
    Tile tile3{ 0 }; // the missing tile
    Tile tile4{ 1 };

    std::cout << "0123456789ABCDEF\n"; // to make it easy to see how many spaces are in the next line
    std::cout << tile1 << tile2 << tile3 << tile4 << '\n';

    std::cout << std::boolalpha << tile1.isEmpty() << ' ' << tile3.isEmpty() << '\n';
    std::cout << "Tile 2 has number: " << tile2.getNum() << "\nTile 4 has number: " << tile4.getNum() << '\n';

    return 0;
}

> Step #3

Goal: Create a solved board (4×4 grid of tiles) and display it on the screen.

Define a Board class that will represent 4×4 grid of tiles. A newly created Board object should be in the solved state. To display the board, first print g_consoleLines (defined in code snippet below) empty lines and then print the board itself. Doing so will ensure that any prior output is pushed out of view so that only the current board is visible on the console.

Why initiate the board in the solved state? When you buy a physical version of these puzzles, the puzzles typically start in the solved state -- you have to manually mix them up (by sliding tiles around) before trying to solve them. We will mimic that process in our program (we’ll do the mixing up in a future step).

Show Tasks

The Board class should have the following functionality:

  • A constexpr symbolic hằng số, set to the size of the grid (you can assume the grid is square).

  • A two-dimentional array of Tile đối tượng, which will hold our 16 numbers. These should start in the solved state.

  • A default hàm tạo (constructor).

  • An overloaded toán tử<< which will print N blank lines (where N = the value of g_consoleLines) and then draw the board to the console.

The following program should run:

cpp
// Increase amount of new lines if your board isn't
// at the very bottom of the console
constexpr int g_consoleLines{ 25 };

// Your code goes here

int main()
{
    Board board{};
    std::cout << board;

    return 0;
}

and output the following:

cpp
1   2   3   4
  5   6   7   8
  9  10  11  12
 13  14  15
Xem lời giải (Solution)
cpp
#include <iostream>

// Increase amount of new lines if your board isn't
// at the very bottom of the console
constexpr int g_consoleLines{ 25 };

class Tile
{
public:
    Tile() = default;
    explicit Tile(int number)
        :m_num(number)
    {
    }
    
    bool isEmpty() const
    {
        return m_num == 0;
    }

    int getNum() const { return m_num; }

private:
    int m_num { 0 };
};

std::ostream& operator<<(std::ostream& stream, Tile tile)
{
    if (tile.getNum() > 9) // if two digit number
        stream << " " << tile.getNum() << " ";
    else if (tile.getNum() > 0) // if one digit number
        stream << "  " << tile.getNum() << " ";
    else if (tile.getNum() == 0) // if empty spot
        stream << "    ";
    return stream;
}

class Board
{
public:

    Board() = default;

    friend std::ostream& operator<<(std::ostream& stream, const Board& board)
    {
        // Before drawing always print some empty lines
        // so that only one board appears at a time
        // and it's always shown at the bottom of the window
        // because console window scrolls automatically when there is no
        // enough space. 
        for (int i = 0; i < g_consoleLines; ++i)
            std::cout << '\n';

        for (int y = 0; y < s_size; ++y)
        {
            for (int x = 0; x < s_size; ++x)
                stream << board.m_tiles[y][x];
            stream << '\n';
        }

        return stream;
    }

private:
    static constexpr int s_size { 4 };
    Tile m_tiles[s_size][s_size]{
        Tile{ 1 }, Tile { 2 }, Tile { 3 } , Tile { 4 },
        Tile { 5 } , Tile { 6 }, Tile { 7 }, Tile { 8 },
        Tile { 9 }, Tile { 10 }, Tile { 11 }, Tile { 12 },
        Tile { 13 }, Tile { 14 }, Tile { 15 }, Tile { 0 } };
};

int main()
{
    Board board{};
    std::cout << board;

    return 0;
}

> Step #4

Goal: In this step, we’ll allow the user to repeatedly input game commands, handle invalid input, and implement the quit game command.

These are the 5 commands our game will support (each of which will be input as a single character):

  • ‘w’ - slide tile up

  • ‘a’ - slide tile left

  • ‘s’ - slide tile down

  • ‘d’ - slide tile right

  • ‘q’ - quit game

When the user runs the game, the following should occur:

  • The (solved) board should be printed to the console.

  • The program should repeatedly get valid game commands from the user. If the user enters an invalid command or extraneous input, ignore it.

For each valid game command:

  • Print "Valid command: " and the character the user input.

  • If the command is the quit command, also print "\n\nBye!\n\n" and then quit the app.

Because our user input routines do not need to maintain any state, implement them inside a namespace named UserInput.

Show Tasks

Implement the UserInput namespace:

  • Create a hàm named getCommandFromUser(). Read in a single character from the user. If the character is not a valid game command, clear any additional extraneous input, and read in another character from the user. Repeat until a valid game command is entered. Return the valid command to the caller.

  • Create as many helper các hàm as you need.

In main():

  • Implement an infinite loop. Inside the loop, fetch a valid game command, and then handle the commands per the above requirements.

The output of the program should match the following:

cpp
1   2   3   4
  5   6   7   8
  9  10  11  12
 13  14  15
w
Valid command: w
a
Valid command: a
s
Valid command: s
d
Valid command: d
f
g
h
Valid command: q

Bye!
Xem lời giải (Solution)
cpp
#include <iostream>
#include <limits>

// Increase amount of new lines if your board isn't
// at the very bottom of the console
constexpr int g_consoleLines{ 25 };

namespace UserInput
{
    bool isValidCommand(char ch)
    {
        return ch == 'w'
            || ch == 'a'
            || ch == 's'
            || ch == 'd'
            || ch == 'q';
    }

    void ignoreLine()
    {
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }

    char getCharacter()
    {
        char operation{};
        std::cin >> operation;
        ignoreLine(); // remove any extraneous input
        return operation;
    }

    char getCommandFromUser()
    {
        char ch{};
        while (!isValidCommand(ch))
            ch = getCharacter();

        return ch;
    }
};

class Tile
{
public:
    Tile() = default;
    explicit Tile(int number)
        :m_num(number)
    {
    }
    
    bool isEmpty() const
    {
        return m_num == 0;
    }

    int getNum() const { return m_num; }

private:
    int m_num { 0 };
};

std::ostream& operator<<(std::ostream& stream, Tile tile)
{
    if (tile.getNum() > 9) // if two digit number
        stream << " " << tile.getNum() << " ";
    else if (tile.getNum() > 0) // if one digit number
        stream << "  " << tile.getNum() << " ";
    else if (tile.getNum() == 0) // if empty spot
        stream << "    ";
    return stream;
}

class Board
{
public:

    Board() = default;

    friend std::ostream& operator<<(std::ostream& stream, const Board& board)
    {
        // Before drawing always print some empty lines
        // so that only one board appears at a time
        // and it's always shown at the bottom of the window
        // because console window scrolls automatically when there is no
        // enough space. 
        for (int i = 0; i < g_consoleLines; ++i)
            std::cout << '\n';

        for (int y = 0; y < s_size; ++y)
        {
            for (int x = 0; x < s_size; ++x)
                stream << board.m_tiles[y][x];
            stream << '\n';
        }

        return stream;
    }

private:
    static constexpr int s_size { 4 };
    Tile m_tiles[s_size][s_size]{
        Tile{ 1 }, Tile { 2 }, Tile { 3 } , Tile { 4 },
        Tile { 5 } , Tile { 6 }, Tile { 7 }, Tile { 8 },
        Tile { 9 }, Tile { 10 }, Tile { 11 }, Tile { 12 },
        Tile { 13 }, Tile { 14 }, Tile { 15 }, Tile { 0 } };
};

int main()
{
    Board board{};
    std::cout << board;

    while (true)
    {
        char ch{ UserInput::getCommandFromUser() };

        // If we reach the line below, "ch" will ALWAYS be a correct command!
        std::cout << "Valid command: " << ch << '\n';
        
        // Handle non-direction commands
        if (ch == 'q')
        {
            std::cout << "\n\nBye!\n\n";
            return 0;
        }
    }

    return 0;
}

> Step #5

Goal: Implement a helper class that will make it easier for us to handle directional commands.

After implementing the prior step, we can accept commands from the user (as characters ‘w’, ‘a’, ‘s’, ‘d’, and ‘q’). These characters are essentially magic numbers in our code. While it’s fine to handle these commands in our UserInput namespace and hàm main(), we don’t want to propagate them throughout our whole program. For example, the Board class should have no knowledge of what ‘s’ means.

Implement a helper class named Direction, which will allow us to create đối tượng that represent the cardinal directions (up, left, down, or right). toán tử- should return the opposite direction, and toán tử<< should print the direction to the console. We will also need a member hàm that will return a Direction object containing a random direction. Lastly, add a hàm to namespace UserInput that converts a directional game command (‘w’, ‘a’, ‘s’, or ‘d’) to a Direction object.

The more we can use Direction instead of directional game commands, the easier our code will be to read and understand.

Show Tasks

Implement the class Direction, which has:

  • A public nested enum named Type with enumerators up, down, left, right, and maxDirections.

  • A private member that stores the actual direction.

  • A single đối số hàm tạo (constructor) which allows us to khởi tạo a Direction with a Type initializer.

  • An overloaded toán tử-, which takes a Direction and returns the opposite Direction.

  • An overloaded toán tử<<, which outputs the Direction name to the console.

  • A static hàm that returns a Direction with a randomized Type. You can use the Random::get() hàm from the “Random.h” header to generate a random number.

Also, in the UserInput namespace, add the following:

  • A hàm that will convert a directional game command (character) to a Direction object.

Finally, modify the program you wrote in the prior step so that the output matches the following:

cpp
1   2   3   4
  5   6   7   8
  9  10  11  12
 13  14  15
Generating random direction... up
Generating random direction... down
Generating random direction... up
Generating random direction... left

Enter a command: w
You entered direction: up
a
You entered direction: left
s
You entered direction: down
d
You entered direction: right
q

Bye!
Xem lời giải (Solution)
cpp
#include <cassert>
#include <iostream>
#include <limits>
#include "Random.h"

// Increase amount of new lines if your board isn't
// at the very bottom of the console
constexpr int g_consoleLines{ 25 };

class Direction
{
public:
    enum Type
    {
        up,
        down,
        left,
        right,
        maxDirections,
    };

    Direction(Type type)
        :m_type(type)
    {
    }

    Type getType() const
    {
        return m_type;
    }

    Direction operator-() const
    {
        switch (m_type)
        {
        case up:    return Direction{ down };
        case down:  return Direction{ up };
        case left:  return Direction{ right };
        case right: return Direction{ left };
        default:    break;
        }

        assert(0 && "Unsupported direction was passed!");
        return Direction{ up };
    }
 
    static Direction getRandomDirection()
    {
        Type random{ static_cast<Type>(Random::get(0, Type::maxDirections - 1)) };
        return Direction{ random };
    }

private:
    Type m_type{};
};

std::ostream& operator<<(std::ostream& stream, Direction dir)
{
    switch (dir.getType())
    {
    case Direction::up:     return (stream << "up");
    case Direction::down:   return (stream << "down");
    case Direction::left:   return (stream << "left");
    case Direction::right:  return (stream << "right");
    default:                break;
    }

    assert(0 && "Unsupported direction was passed!");
    return (stream << "unknown direction");
}

namespace UserInput
{
    bool isValidCommand(char ch)
    {
        return ch == 'w'
            || ch == 'a'
            || ch == 's'
            || ch == 'd'
            || ch == 'q';
    }

    void ignoreLine()
    {
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }

    char getCharacter()
    {
        char operation{};
        std::cin >> operation;
        ignoreLine(); // remove any extraneous input
        return operation;
    }

    char getCommandFromUser()
    {
        char ch{};
        while (!isValidCommand(ch))
            ch = getCharacter();

        return ch;
    }

    Direction charToDirection(char ch)
    {
        switch (ch)
        {
        case 'w': return Direction{ Direction::up };
        case 's': return Direction{ Direction::down };
        case 'a': return Direction{ Direction::left };
        case 'd': return Direction{ Direction::right };
        }

        assert(0 && "Unsupported direction was passed!");
        return Direction{ Direction::up };
    }
};

class Tile
{
public:
    Tile() = default;
    explicit Tile(int number)
        :m_num(number)
    {
    }
    
    bool isEmpty() const
    {
        return m_num == 0;
    }

    int getNum() const { return m_num; }

private:
    int m_num { 0 };
};

std::ostream& operator<<(std::ostream& stream, Tile tile)
{
    if (tile.getNum() > 9) // if two digit number
        stream << " " << tile.getNum() << " ";
    else if (tile.getNum() > 0) // if one digit number
        stream << "  " << tile.getNum() << " ";
    else if (tile.getNum() == 0) // if empty spot
        stream << "    ";
    return stream;
}

class Board
{
public:

    Board() = default;

    static void printEmptyLines(int count)
    {
        for (int i = 0; i < count; ++i)
            std::cout << '\n';
    }

    friend std::ostream& operator<<(std::ostream& stream, const Board& board)
    {
        // Before drawing always print some empty lines
        // so that only one board appears at a time
        // and it's always shown at the bottom of the window
        // because console window scrolls automatically when there is no
        // enough space. 
        for (int i = 0; i < g_consoleLines; ++i)
            std::cout << '\n';

        for (int y = 0; y < s_size; ++y)
        {
            for (int x = 0; x < s_size; ++x)
                stream << board.m_tiles[y][x];
            stream << '\n';
        }

        return stream;
    }

private:
    static constexpr int s_size { 4 };
    Tile m_tiles[s_size][s_size]{
        Tile{ 1 }, Tile { 2 }, Tile { 3 } , Tile { 4 },
        Tile { 5 } , Tile { 6 }, Tile { 7 }, Tile { 8 },
        Tile { 9 }, Tile { 10 }, Tile { 11 }, Tile { 12 },
        Tile { 13 }, Tile { 14 }, Tile { 15 }, Tile { 0 } };
};

int main()
{
    Board board{};
    std::cout << board;

    std::cout << "Generating random direction... " << Direction::getRandomDirection() << '\n';
    std::cout << "Generating random direction... " << Direction::getRandomDirection() << '\n';
    std::cout << "Generating random direction... " << Direction::getRandomDirection() << '\n';
    std::cout << "Generating random direction... " << Direction::getRandomDirection() << "\n\n";

    std::cout << "Enter a command: ";
    while (true)
    {
        char ch{ UserInput::getCommandFromUser() };

        // Handle non-direction commands
        if (ch == 'q')
        {
            std::cout << "\n\nBye!\n\n";
            return 0;
        }

        // Handle direction commands
        Direction dir{ UserInput::charToDirection(ch) };

        std::cout << "You entered direction: " << dir << '\n';
    }

    return 0;
}

> Step #6

Goal: Implement a helper class that will make it easier for us to index the tiles in our game board.

Our game board is a 4×4 grid of Tile, which we store in two-dimensional array member m_tiles of the Board class. We will access a given tile using its {x, y} coordinates. For example, the top left tile has coordinate {0, 0}. The tile to the right of that has coordinate {1, 0} (x becomes 1, y stays 0). The tile one down from that has coordinate {1, 1}.

Since we’ll be working with coordinates a lot, create a helper class named Point that stores an {x, y} pair of coordinates. We should be able to compare two Point đối tượng for equality and inequality. Also implement a member hàm named getAdjacentPoint that takes a Direction object as a tham số and returns the Point in that direction. For example, Point{1, 1}.getAdjacentPoint(Direction::right) == Point{2, 1}.

Show Tasks

Implement a struct named Point. This should contain:

  • Two public data members to store the x-axis and y-axis coordinates.

  • An overloaded toán tử== and toán tử!= to compare two sets of coordinates.

  • A const member hàm Point getAdjacentPoint(Direction) that returns the Point in the direction of the Direction tham số. We do not need to do any validity checking here.

We’re using a struct instead of a class here because Point is simple bundle of data that would benefit little from being encapsulated.

Save your main() hàm from the prior step, as you’ll need it again in the next step.

The following code should run and print true for every test-case:

cpp
// Your code goes here

// Note: save your main() from the prior step, as you'll need it again in the next step
int main()
{
    std::cout << std::boolalpha;
    std::cout << (Point{ 1, 1 }.getAdjacentPoint(Direction::up)    == Point{ 1, 0 }) << '\n';
    std::cout << (Point{ 1, 1 }.getAdjacentPoint(Direction::down)  == Point{ 1, 2 }) << '\n';
    std::cout << (Point{ 1, 1 }.getAdjacentPoint(Direction::left)  == Point{ 0, 1 }) << '\n';
    std::cout << (Point{ 1, 1 }.getAdjacentPoint(Direction::right) == Point{ 2, 1 }) << '\n';
    std::cout << (Point{ 1, 1 } != Point{ 2, 1 }) << '\n';
    std::cout << (Point{ 1, 1 } != Point{ 1, 2 }) << '\n';
    std::cout << !(Point{ 1, 1 } != Point{ 1, 1 }) << '\n';

    return 0;
}
Xem lời giải (Solution)
cpp
#include <array>
#include <cassert>
#include <iostream>
#include <limits>
#include "Random.h"

// Increase amount of new lines if your board isn't
// at the very bottom of the console
constexpr int g_consoleLines{ 25 };

class Direction
{
public:
    enum Type
    {
        up,
        down,
        left,
        right,
        maxDirections,
    };

    Direction(Type type)
        :m_type(type)
    {
    }

    Type getType() const
    {
        return m_type;
    }

    Direction operator-() const
    {
        switch (m_type)
        {
        case up:    return Direction{ down };
        case down:  return Direction{ up };
        case left:  return Direction{ right };
        case right: return Direction{ left };
        default:    break;
        }

        assert(0 && "Unsupported direction was passed!");
        return Direction{ up };
    }

    static Direction getRandomDirection()
    {
        Type random{ static_cast<Type>(Random::get(0, Type::maxDirections - 1)) };
        return Direction{ random };
    }

private:
    Type m_type{};
};

std::ostream& operator<<(std::ostream& stream, Direction dir)
{
    switch (dir.getType())
    {
    case Direction::up:     return (stream << "up");
    case Direction::down:   return (stream << "down");
    case Direction::left:   return (stream << "left");
    case Direction::right:  return (stream << "right");
    default:                break;
    }

    assert(0 && "Unsupported direction was passed!");
    return (stream << "unknown direction");
}

struct Point
{
    int x{};
    int y{};

    friend bool operator==(Point p1, Point p2)
    {
        return p1.x == p2.x && p1.y == p2.y;
    }

    friend bool operator!=(Point p1, Point p2)
    {
        return !(p1 == p2);
    }

    Point getAdjacentPoint(Direction dir) const
    {
        switch (dir.getType())
        {
        case Direction::up:     return Point{ x,     y - 1 };
        case Direction::down:   return Point{ x,     y + 1 };
        case Direction::left:   return Point{ x - 1, y };
        case Direction::right:  return Point{ x + 1, y };
        default:                break;
        }

        assert(0 && "Unsupported direction was passed!");
        return *this;
    }
};

namespace UserInput
{
    bool isValidCommand(char ch)
    {
        return ch == 'w'
            || ch == 'a'
            || ch == 's'
            || ch == 'd'
            || ch == 'q';
    }

    void ignoreLine()
    {
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }

    char getCharacter()
    {
        char operation{};
        std::cin >> operation;
        ignoreLine(); // remove any extraneous input
        return operation;
    }

    char getCommandFromUser()
    {
        char ch{};
        while (!isValidCommand(ch))
            ch = getCharacter();

        return ch;
    }

    Direction charToDirection(char ch)
    {
        switch (ch)
        {
        case 'w': return Direction{ Direction::up };
        case 's': return Direction{ Direction::down };
        case 'a': return Direction{ Direction::left };
        case 'd': return Direction{ Direction::right };
        }

        assert(0 && "Unsupported direction was passed!");
        return Direction{ Direction::up };
    }
};

class Tile
{
public:
    Tile() = default;
    explicit Tile(int number)
        :m_num(number)
    {
    }
    
    bool isEmpty() const
    {
        return m_num == 0;
    }

    int getNum() const { return m_num; }

private:
    int m_num { 0 };
};

std::ostream& operator<<(std::ostream& stream, Tile tile)
{
    if (tile.getNum() > 9) // if two digit number
        stream << " " << tile.getNum() << " ";
    else if (tile.getNum() > 0) // if one digit number
        stream << "  " << tile.getNum() << " ";
    else if (tile.getNum() == 0) // if empty spot
        stream << "    ";
    return stream;
}

class Board
{
public:

    Board() = default;

    static void printEmptyLines(int count)
    {
        for (int i = 0; i < count; ++i)
            std::cout << '\n';
    }

    friend std::ostream& operator<<(std::ostream& stream, const Board& board)
    {
        // Before drawing always print some empty lines
        // so that only one board appears at a time
        // and it's always shown at the bottom of the window
        // because console window scrolls automatically when there is no
        // enough space. 
        for (int i = 0; i < g_consoleLines; ++i)
            std::cout << '\n';

        for (int y = 0; y < s_size; ++y)
        {
            for (int x = 0; x < s_size; ++x)
                stream << board.m_tiles[y][x];
            stream << '\n';
        }

        return stream;
    }

private:
    static constexpr int s_size { 4 };
    Tile m_tiles[s_size][s_size]{
        Tile{ 1 }, Tile { 2 }, Tile { 3 } , Tile { 4 },
        Tile { 5 } , Tile { 6 }, Tile { 7 }, Tile { 8 },
        Tile { 9 }, Tile { 10 }, Tile { 11 }, Tile { 12 },
        Tile { 13 }, Tile { 14 }, Tile { 15 }, Tile { 0 } };
};

int main()
{
    std::cout << std::boolalpha;
    std::cout << (Point{ 1, 1 }.getAdjacentPoint(Direction::up)    == Point{ 1, 0 }) << '\n';
    std::cout << (Point{ 1, 1 }.getAdjacentPoint(Direction::down)  == Point{ 1, 2 }) << '\n';
    std::cout << (Point{ 1, 1 }.getAdjacentPoint(Direction::left)  == Point{ 0, 1 }) << '\n';
    std::cout << (Point{ 1, 1 }.getAdjacentPoint(Direction::right) == Point{ 2, 1 }) << '\n';
    std::cout << (Point{ 1, 1 } != Point{ 2, 1 }) << '\n';
    std::cout << (Point{ 1, 1 } != Point{ 1, 2 }) << '\n';
    std::cout << !(Point{ 1, 1 } != Point{ 1, 1 }) << '\n';

    return 0;
}

> Step #7

Goal: Add the ability for players to slide the tiles on the board.

First, we should take a closer look at how sliding tiles actually works:

Given a puzzle state that looks like this:

cpp
15   1   4
  2   5   9  12
  7   8  11  14
 10  13   6   3

When the user enters ‘w’ on the keyboard, the only tile that can go up is tile 2.

After moving the tile, the board looks like this:

cpp
2  15   1   4
      5   9  12
  7   8  11  14
 10  13   6   3

So, essentially what happened is we swapped the empty tile with tile 2.

Let’s generalize this procedure. When the user enters a directional command, we need to:

  • Locate the empty tile.

  • From the empty tile, find the adjacent tile that is in the direction opposite of the direction the user entered.

  • If the adjacent tile is valid (it’s not off the grid), swap the empty tile and adjacent tile.

  • If the adjacent tile is not valid, do nothing.

Implement this by adding a member hàm moveTile(Direction) to the class Board. Add this to your game loop from step 5. If the user successfully slides a tile, the game should redraw the updated board.

Show Tasks

Implement the following member các hàm in our Board class:

  • A hàm which returns a bool indicating whether a given Point is valid (within our Board).

  • A hàm that finds and returns the position of empty tile as a Point. We could just keep track of where the empty tile is, but that introduces a class invariant, and finding the empty tile whenever we need it isn’t that expensive.

  • A hàm that will swap two tiles given their Point indices.

  • A moveTile(Direction dir) hàm that will try to move a tile in a given direction and will return true if it succeeds. This hàm should implement the procedure outlined above.

Modify the main() from step 5 so that moveTile() is called if a directional command is entered. If the move was successful, redraw the board.

Xem lời giải (Solution)
cpp
#include <array>
#include <cassert>
#include <iostream>
#include <limits>
#include "Random.h"

// Increase amount of new lines if your board isn't
// at the very bottom of the console
constexpr int g_consoleLines{ 25 };

class Direction
{
public:
    enum Type
    {
        up,
        down,
        left,
        right,
        maxDirections,
    };

    Direction(Type type)
        :m_type(type)
    {
    }

    Type getType() const
    {
        return m_type;
    }

    Direction operator-() const
    {
        switch (m_type)
        {
        case up:    return Direction{ down };
        case down:  return Direction{ up };
        case left:  return Direction{ right };
        case right: return Direction{ left };
        default:    break;
        }

        assert(0 && "Unsupported direction was passed!");
        return Direction{ up };
    }

    static Direction getRandomDirection()
    {
        Type random{ static_cast<Type>(Random::get(0, Type::maxDirections - 1)) };
        return Direction{ random };
    }

private:
    Type m_type{};
};

std::ostream& operator<<(std::ostream& stream, Direction dir)
{
    switch (dir.getType())
    {
    case Direction::up:     return (stream << "up");
    case Direction::down:   return (stream << "down");
    case Direction::left:   return (stream << "left");
    case Direction::right:  return (stream << "right");
    default:                break;
    }

    assert(0 && "Unsupported direction was passed!");
    return (stream << "unknown direction");
}

struct Point
{
    int x{};
    int y{};

    friend bool operator==(Point p1, Point p2)
    {
        return p1.x == p2.x && p1.y == p2.y;
    }

    friend bool operator!=(Point p1, Point p2)
    {
        return !(p1 == p2);
    }

    Point getAdjacentPoint(Direction dir) const
    {
        switch (dir.getType())
        {
        case Direction::up:     return Point{ x,     y - 1 };
        case Direction::down:   return Point{ x,     y + 1 };
        case Direction::left:   return Point{ x - 1, y };
        case Direction::right:  return Point{ x + 1, y };
        default:                break;
        }

        assert(0 && "Unsupported direction was passed!");
        return *this;
    }
};

namespace UserInput
{
    bool isValidCommand(char ch)
    {
        return ch == 'w'
            || ch == 'a'
            || ch == 's'
            || ch == 'd'
            || ch == 'q';
    }

    void ignoreLine()
    {
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }

    char getCharacter()
    {
        char operation{};
        std::cin >> operation;
        ignoreLine(); // remove any extraneous input
        return operation;
    }

    char getCommandFromUser()
    {
        char ch{};
        while (!isValidCommand(ch))
            ch = getCharacter();

        return ch;
    }

    Direction charToDirection(char ch)
    {
        switch (ch)
        {
        case 'w': return Direction{ Direction::up };
        case 's': return Direction{ Direction::down };
        case 'a': return Direction{ Direction::left };
        case 'd': return Direction{ Direction::right };
        }

        assert(0 && "Unsupported direction was passed!");
        return Direction{ Direction::up };
    }
};

class Tile
{
public:
    Tile() = default;
    explicit Tile(int number)
        :m_num(number)
    {
    }

    bool isEmpty() const
    {
        return m_num == 0;
    }

    int getNum() const { return m_num; }

private:
    int m_num { 0 };
};

std::ostream& operator<<(std::ostream& stream, Tile tile)
{
    if (tile.getNum() > 9) // if two digit number
        stream << " " << tile.getNum() << " ";
    else if (tile.getNum() > 0) // if one digit number
        stream << "  " << tile.getNum() << " ";
    else if (tile.getNum() == 0) // if empty spot
        stream << "    ";
    return stream;
}

class Board
{
public:

    Board() = default;

    static void printEmptyLines(int count)
    {
        for (int i = 0; i < count; ++i)
            std::cout << '\n';
    }

    friend std::ostream& operator<<(std::ostream& stream, const Board& board)
    {
        // Before drawing always print some empty lines
        // so that only one board appears at a time
        // and it's always shown at the bottom of the window
        // because console window scrolls automatically when there is no
        // enough space. 
        for (int i = 0; i < g_consoleLines; ++i)
            std::cout << '\n';

        for (int y = 0; y < s_size; ++y)
        {
            for (int x = 0; x < s_size; ++x)
                stream << board.m_tiles[y][x];
            stream << '\n';
        }

        return stream;
    }

    Point getEmptyTilePos() const
    {
        for (int y = 0; y < s_size; ++y)
            for (int x = 0; x < s_size; ++x)
                if (m_tiles[y][x].isEmpty())
                    return { x,y };

        assert(0 && "There is no empty tile in the board!!!");
        return { -1,-1 };
    }

    static bool isValidTilePos(Point pt)
    {
        return (pt.x >= 0 && pt.x < s_size)
            && (pt.y >= 0 && pt.y < s_size);
    }

    void swapTiles(Point pt1, Point pt2)
    {
        std::swap(m_tiles[pt1.y][pt1.x], m_tiles[pt2.y][pt2.x]);
    }

    // returns true if user moved successfully
    bool moveTile(Direction dir)
    {
        Point emptyTile{ getEmptyTilePos() };
        Point adj{ emptyTile.getAdjacentPoint(-dir) };

        if (!isValidTilePos(adj))
            return false;

        swapTiles(adj, emptyTile);
        return true;
    }

private:
    static const int s_size { 4 };
    Tile m_tiles[s_size][s_size]{
        Tile{ 1 }, Tile { 2 }, Tile { 3 } , Tile { 4 },
        Tile { 5 } , Tile { 6 }, Tile { 7 }, Tile { 8 },
        Tile { 9 }, Tile { 10 }, Tile { 11 }, Tile { 12 },
        Tile { 13 }, Tile { 14 }, Tile { 15 }, Tile { 0 } };
};

int main()
{
    Board board{};
    std::cout << board;

    std::cout << "Enter a command: ";
    while (true)
    {
        char ch{ UserInput::getCommandFromUser() };

        // Handle non-direction commands
        if (ch == 'q')
        {
            std::cout << "\n\nBye!\n\n";
            return 0;
        }

        // Handle direction commands
        Direction dir{ UserInput::charToDirection(ch) };

        bool userMoved { board.moveTile(dir) };
        if (userMoved)
            std::cout << board;
    }

    return 0;
}

> Step #8

Goal: In this step, we’ll finish our game. Randomize the initial state of the game board. Also, detect when user wins, so after that we can print a win message and quit the game.

We need to be careful about how we randomize our puzzle, because not every puzzle is solvable. For example, there is no way to solve this puzzle:

cpp
1   2   3   4 
  5   6   7   8
  9  10  11  12
 13  15  14

If we just blindly randomize the numbers in the puzzle, there is a chance that we will generate such an unsolvable puzzle. With a physical version of the puzzle, we’d randomize the puzzle by sliding tiles in random directions until the tiles were sufficiently mixed. The solution for such a randomized puzzle is to slide each tile in the opposite direction that it was slid to randomize it in the first place. Thus, randomizing puzzles this way always generates a solvable puzzle.

We can have our program randomize the board in the same way.

Once the user has solved the puzzle, the program should print "\n\nYou won!\n\n" and then exit normally.

Show Tasks

  • Add a randomize() member hàm to the Board class which randomizes the tiles in the game board. Pick a random direction and if the adjacent point is valid, then slide a tile in that direction. Doing this 1000 times should be sufficient to mix up the board.

  • Implement toán tử== in Board class which will compare if tiles of two given boards are identical.

  • Add playerWon() member hàm to the Board class that will return true if the current game board is solved. You can use the toán tử== you implemented to compare the current game board against a solved game board. Remember that Board đối tượng start in the solved state, so if you need a solved game board, just value khởi tạo a Board object!

  • Update your main() hàm to integrate randomize() and playerWon().

Here is the full solution for our 15 puzzle game:

Xem lời giải (Solution)
cpp
#include <array>
#include <cassert>
#include <iostream>
#include <limits>
#include "Random.h"

// Increase amount of new lines if your board isn't
// at the very bottom of the console
constexpr int g_consoleLines{ 25 };

class Direction
{
public:
    enum Type
    {
        up,
        down,
        left,
        right,
        maxDirections,
    };

    Direction(Type type)
        :m_type(type)
    {
    }
    Type getType() const
    {
        return m_type;
    }

    Direction operator-() const
    {
        switch (m_type)
        {
        case up:    return Direction{ down };
        case down:  return Direction{ up };
        case left:  return Direction{ right };
        case right: return Direction{ left };
        default:    break;
        }

        assert(0 && "Unsupported direction was passed!");
        return Direction{ up };
    }

    static Direction getRandomDirection()
    {
        Type random{ static_cast<Type>(Random::get(0, Type::maxDirections - 1)) };
        return Direction{ random };
    }

private:
    Type m_type{};
};

std::ostream& operator<<(std::ostream& stream, Direction dir)
{
    switch (dir.getType())
    {
    case Direction::up:     return (stream << "up");
    case Direction::down:   return (stream << "down");
    case Direction::left:   return (stream << "left");
    case Direction::right:  return (stream << "right");
    default:                break;
    }

    assert(0 && "Unsupported direction was passed!");
    return (stream << "unknown direction");
}

struct Point
{
    int x{};
    int y{};

    friend bool operator==(Point p1, Point p2)
    {
        return p1.x == p2.x && p1.y == p2.y;
    }

    friend bool operator!=(Point p1, Point p2)
    {
        return !(p1 == p2);
    }

    Point getAdjacentPoint(Direction dir) const
    {
        switch (dir.getType())
        {
        case Direction::up:     return Point{ x,     y - 1 };
        case Direction::down:   return Point{ x,     y + 1 };
        case Direction::left:   return Point{ x - 1, y };
        case Direction::right:  return Point{ x + 1, y };
        default:                break;
        }

        assert(0 && "Unsupported direction was passed!");
        return *this;
    }
};

namespace UserInput
{
    bool isValidCommand(char ch)
    {
        return ch == 'w'
            || ch == 'a'
            || ch == 's'
            || ch == 'd'
            || ch == 'q';
    }

    void ignoreLine()
    {
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }

    char getCharacter()
    {
        char operation{};
        std::cin >> operation;
        ignoreLine(); // remove any extraneous input
        return operation;
    }

    char getCommandFromUser()
    {
        char ch{};
        while (!isValidCommand(ch))
            ch = getCharacter();

        return ch;
    }

    Direction charToDirection(char ch)
    {
        switch (ch)
        {
        case 'w': return Direction{ Direction::up };
        case 's': return Direction{ Direction::down };
        case 'a': return Direction{ Direction::left };
        case 'd': return Direction{ Direction::right };
        }

        assert(0 && "Unsupported direction was passed!");
        return Direction{ Direction::up };
    }
};

class Tile
{
public:
    Tile() = default;
    explicit Tile(int number)
        :m_num(number)
    {
    }

    bool isEmpty() const
    {
        return m_num == 0;
    }

    int getNum() const { return m_num; }

private:
    int m_num { 0 };
};

std::ostream& operator<<(std::ostream& stream, Tile tile)
{
    if (tile.getNum() > 9) // if two digit number
        stream << " " << tile.getNum() << " ";
    else if (tile.getNum() > 0) // if one digit number
        stream << "  " << tile.getNum() << " ";
    else if (tile.getNum() == 0) // if empty spot
        stream << "    ";
    return stream;
}

class Board
{
public:

    Board() = default;

    static void printEmptyLines(int count)
    {
        for (int i = 0; i < count; ++i)
            std::cout << '\n';
    }

    friend std::ostream& operator<<(std::ostream& stream, const Board& board)
    {
        // Before drawing always print some empty lines
        // so that only one board appears at a time
        // and it's always shown at the bottom of the window
        // because console window scrolls automatically when there is no
        // enough space. 
        for (int i = 0; i < g_consoleLines; ++i)
            std::cout << '\n';

        for (int y = 0; y < s_size; ++y)
        {
            for (int x = 0; x < s_size; ++x)
                stream << board.m_tiles[y][x];
            stream << '\n';
        }

        return stream;
    }

    Point getEmptyTilePos() const
    {
        for (int y = 0; y < s_size; ++y)
            for (int x = 0; x < s_size; ++x)
                if (m_tiles[y][x].isEmpty())
                    return { x,y };

        assert(0 && "There is no empty tile in the board!!!");
        return { -1,-1 };
    }

    static bool isValidTilePos(Point pt)
    {
        return (pt.x >= 0 && pt.x < s_size)
            && (pt.y >= 0 && pt.y < s_size);
    }

    void swapTiles(Point pt1, Point pt2)
    {
        std::swap(m_tiles[pt1.y][pt1.x], m_tiles[pt2.y][pt2.x]);
    }

    // Compare two boards to see if they are equal
    friend bool operator==(const Board& f1, const Board& f2)
    {
        for (int y = 0; y < s_size; ++y)
            for (int x = 0; x < s_size; ++x)
                if (f1.m_tiles[y][x].getNum() != f2.m_tiles[y][x].getNum())
                    return false;

        return true;
    }

    // returns true if user moved successfully
    bool moveTile(Direction dir)
    {
        Point emptyTile{ getEmptyTilePos() };
        Point adj{ emptyTile.getAdjacentPoint(-dir) };

        if (!isValidTilePos(adj))
            return false;

        swapTiles(adj, emptyTile);
        return true;
    }

    bool playerWon() const
    {
        static Board s_solved{};  // generate a solved board
        return s_solved == *this; // player wins if current board == solved board
    }

    void randomize()
    {
        // Move empty tile randomly 1000 times
        // (just like you would do in real life)
        for (int i = 0; i < 1000; )
        {
            // If we are able to successfully move a tile, count this
            if (moveTile(Direction::getRandomDirection()))
                ++i;
        }
    }

private:
    static const int s_size { 4 };
    Tile m_tiles[s_size][s_size]{
        Tile{ 1 }, Tile { 2 }, Tile { 3 } , Tile { 4 },
        Tile { 5 } , Tile { 6 }, Tile { 7 }, Tile { 8 },
        Tile { 9 }, Tile { 10 }, Tile { 11 }, Tile { 12 },
        Tile { 13 }, Tile { 14 }, Tile { 15 }, Tile { 0 } };
};

int main()
{
    Board board{};
    board.randomize();
    std::cout << board;

    while (!board.playerWon())
    {
        char ch{ UserInput::getCommandFromUser() };

        // Handle non-direction commands
        if (ch == 'q')
        {
            std::cout << "\n\nBye!\n\n";
            return 0;
        }

        // Handle direction commands
        Direction dir{ UserInput::charToDirection(ch) };

        bool userMoved{ board.moveTile(dir) };
        if (userMoved)
            std::cout << board;
    }

    std::cout << "\n\nYou won!\n\n";
    return 0;
}

💡 Tóm Tắt Quy Tắc Vàng (Core Guidelines)

  1. Luôn hiểu rõ vòng đời và quyền sở hữu (Ownership) của dữ liệu trước khi viết code.
  2. Ưu tiên khởi tạo đồng nhất với dấu ngoặc nhọn {} để ngăn chặn lỗi thu hẹp kiểu dữ liệu (Narrowing conversions).
  3. Bật toàn bộ cờ cảnh báo -Wall -Wextra -Wpedantic để compiler giúp bạn phát hiện bug từ sớm!