2048 game problem

[david73]

Hi,
I've got one question. Imagine that you are making 2048 and you want to chceck whether game is over (what means that there are no empty places on the board and there are not the same numbers next to each other).

The only option which come to my mind is write function like this (board is a vector< vector<int> > board{ { 0,0,0,0 },{ 0,0,0,0 },{ 0,0,0,0 },{ 0,0,0,0 } }):

bool game_end() {
	bool end = true;
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			if (board[i][j] == 0 || board[i][j] == board[i + 1][j] || board[i][j] == board[i - 1][j] || board[i][j] == board[i][j + 1] || board[i][j] == board[i][j - 1])
				return false;
		}
	}
return end;
}

The problem is that when I'm on the position, let's say, board[0][0], there is no position such as board[-1][0] and it will cause the error. Creating border like this would do the job
1 1 1 1 1 1
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
but this would require a lot of changes in the code.
So, is there any better you can think of?
Thanks for your answer.

[mbozzi]

If and only if the board is full (has 16 pieces that are nonzero), perform a confirmation check to verify that the game is over according to the following psuedocode:

Save the original game state
Slide the board in all four directions -- left, right, up, down.
If the original game state is the same as the current game state 
  then quit; the game is over.
else 
  restore the original game state; the game may continue.

On a 4x4 board anything more complicated seems like overkill.

[lastchance]

bool game_end()
{
   // Check for zero
   for ( int i = 0; i < 4; ++i ) 
   {
      for ( int j = 0; j < 4; ++j ) if ( board[i][j] == 0 ) return false;
   }
                           
   // Check within-row (i) adjacency
   for ( int i = 0; i < 4; ++i ) 
   {
      for ( int j = 0; j < 3; ++j ) if ( board[i][j] == board[i][j+1] ) return false;
   }
                           
   // Check within-column (j) adjacency
   for ( int j = 0; j < 4; ++j )
   {
      for ( int i = 0; i < 3; ++i ) if ( board[i][j] == board[i+1][j] ) return false;
   }

   return true;
}

[Chervil]

edit: this is a long post, but I overlooked something - it contained a bug. I believe it is corrected now.

Since the code uses vectors, there's no need to use hard-coded integers such as 4.

I found it convenient to test for zeros separately - because during testing I didn't want to print out the board if it contained a zero.

Hence two functions:

bool contains_zero(const vector<vector<int>> & board ) 
{
    for (const auto & row : board)
        for (const auto & col : row)
            if (col == 0) return true;
            
    return false;            
}

bool game_end(const vector<vector<int>> & board )
{
    if (contains_zero(board)) return false;

    for (size_t i = 1; i < board.size(); ++i)
        for (size_t j = 0; j < board[i].size(); ++j)
            if (board[i][j] == board[i-1][ j ])
                return false;
                
    for (size_t i = 0; i < board.size(); ++i)
        for (size_t j = 1; j < board[i].size(); ++j)
            if (board[i][j] == board[ i ][j-1])
                return false;

    return true;
}
bool game_end(const vector<vector<int>> & board ) 
{
    if (contains_zero(board)) return false;
    
    for (size_t i = 1; i < board.size(); ++i)
    {
        for (size_t j = 1; j < board[i].size(); ++j) 
        {
            if (   board[i][j] == board[i-1][ j ]
                || board[i][j] == board[ i ][j-1]  )
                return false;
        }
    }
    
    return true;
}

And just out of interest, a complete program I used for test purposes:

#include <iostream>
#include <iomanip>
#include <vector>
#include <random>

using namespace std;

bool game_end(const vector<vector<int>> & board ) ;
void fill(vector<vector<int>> & board);
void print(const vector<vector<int>> & board);
bool contains_zero(const vector<vector<int>> & board );

int main()
{
    vector<vector<int>> board (4, vector<int>(4));

    bool done = false;
    const int limit = 1000;

    int count = 0;

    cout << boolalpha;

    while (!done &&  count < limit)
    {
        fill(board);

        done = game_end(board);

        if (!contains_zero(board))
        {
            print(board);

            cout << "done = " << done <<  "    count = " << count <<  "\n\n";
        }

        ++count;
    }

}

bool contains_zero(const vector<vector<int>> & board )
{
    for (const auto & row : board)
        for (const auto & col : row)
            if (col == 0) return true;

    return false;
}

bool game_end(const vector<vector<int>> & board )
{
    if (contains_zero(board)) return false;

    for (size_t i = 1; i < board.size(); ++i)
        for (size_t j = 0; j < board[i].size(); ++j)
            if (board[i][j] == board[i-1][ j ])
                return false;
                
    for (size_t i = 0; i < board.size(); ++i)
        for (size_t j = 1; j < board[i].size(); ++j)
            if (board[i][j] == board[ i ][j-1])
                return false;

    return true;
}

int power(int n)
{
    if (n < 0)
        return 0;
    return (1 << n);
}

int randm()
{
    static std::mt19937 generator(time(nullptr));
//    static std::mt19937 generator(7929);
    static std::uniform_int_distribution<int> dist(-5, 15);

    return power(dist(generator));
}

void fill(vector<vector<int>> & board )
{
    for (auto & row : board)
        for (auto & col : row)
            col = randm();
}

void print(const vector<vector<int>> & board )
{
    for (const auto & row : board)
    {
        for (const auto & col : row)
            cout << setw(10) << col;
        cout << '\n';
    }
}

[lastchance]

Post removed as redundant

[Chervil]

lastchance wrote:

I'm missing something. For what values of i,j does this access 0,0? Or compare 0,0 with 0,1 for instance.

Quite so. Thank you.

The corrected version should look more like this:

bool game_end(const vector<vector<int>> & board )
{
    if (contains_zero(board)) return false;

    for (size_t i = 1; i < board.size(); ++i)
        for (size_t j = 0; j < board[i].size(); ++j)
            if (board[i][j] == board[i-1][ j ])
                return false;
                
    for (size_t i = 0; i < board.size(); ++i)
        for (size_t j = 1; j < board[i].size(); ++j)
            if (board[i][j] == board[ i ][j-1])
                return false;

    return true;
}

On the one hand - I spent longer building the test program than I did on the function to be tested. On the other - it did allow me to notice the error when I saw the incorrect output.

[david73]

I highly appreciate your help guys. Lastchance's program did the job for me so thanks a lot. All ideas seemed good but this one was easiest for me. Great community.