Why do I get an infinite loop when processing neighbouring cells in Minesweeper using a queue?

Question

I'm coding a minesweeper game, and when the user clicks an empty cell, all the reachable empty cells must be opened as well.

I'm using a queue to do so, but it seems like I'm having a trouble with an infinite loop.

The part of the code with the problem:

queue<int> q;
q.push(row);
q.push(col);

while(!q.empty()){
    int tempRow = q.front();
    int tempCol = q.front();

    if((tempRow-1)>=0 && (tempRow-1)<s && (tempCol-1)>=0 && (tempCol-1)<s && table[tempRow-1][tempCol-1]==' '){q.push(tempRow-1);q.push(tempCol-1);}
    if((tempRow-1)>=0 && (tempRow-1)<s && (tempCol)>=0 && (tempCol)<s && table[tempRow-1][tempCol]==' '){q.push(tempRow-1);q.push(tempCol);}
    if((tempRow-1)>=0 && (tempRow-1)<s && (tempCol+1)>=0 && (tempCol+1)<s && table[tempRow-1][tempCol+1]==' '){q.push(tempRow-1);q.push(tempCol+1);}
    if((tempRow)>=0 && (tempRow)<s && (tempCol-1)>=0 && (tempCol-1)<s && table[tempRow][tempCol-1]==' '){q.push(tempRow);q.push(tempCol-1);}
    if((tempRow)>=0 && (tempRow)<s && (tempCol+1)>=0 && (tempCol+1)<s && table[tempRow][tempCol+1]==' '){q.push(tempRow);q.push(tempCol+1);}
    if((tempRow+1)>=0 && (tempRow+1)<s && (tempCol-1)>=0 && (tempCol-1)<s && table[tempRow+1][tempCol-1]==' '){q.push(tempRow+1);q.push(tempCol-1);}
    if((tempRow+1)>=0 && (tempRow+1)<s && (tempCol)>=0 && (tempCol)<s && table[tempRow+1][tempCol]==' '){q.push(tempRow+1);q.push(tempCol);}
    if((tempRow+1)>=0 && (tempRow+1)<s && (tempCol+1)>=0 && (tempCol+1)<s && table[tempRow+1][tempCol+1]==' '){q.push(tempRow+1);q.push(tempCol+1);}

    view[tempRow][tempCol]=' ';

    q.pop();
    q.pop();
}

Why do I get an infinite loop?

Answer 1

This kind of problem appears in multiple situations. It's actually calculating the 'closure' of a set of instances. Often also found when handling graphs, ...

It's typically solved in the following way:

• Define a queue that will store all the elements that need to be processed.
• Define an associative container (set) with a key that identifies the items to process and make sure look up is fast (in your case, the key could be the coordinates of the cell)
• Add the first element to the queue and set
• In a loop, do the following
  • Pop the first element from the queue
  • Do whatever you need to do with this element (e.g. element.process())
  • Take all the connected elements (in your case the neighbors) and do the following:
    • if the element is already in the set, ignore it
    • if it is not in the set, add it to the set and push it on the queue

The principle is that you push neighbors on the queue if they are not yet in the queue or have not yet been processed (that's why we need the set, to do the efficient look up).

Depending on your exact problem, you could optimize some things, e.g. instead of using a set, use a 2-dimensional matrix, or bitset. This will probably take more memory (depending on your grid size), and might give performance problems if you need to reset the matrix often, but will give an O(1) lookup instead of O(log N) look up for the set (even an std::unordered_set is slower than a simple indexing lookup in a matrix).

Answer 2

The problem is your loop reprocesses cells it's already processed, never stopping.

I would normally go into detail, but frankly your code is difficult to follow, so I've rewritten it for clarity and future readers.

Note that this should be correct but I haven't tested to confirm.

const char empty_cell = ' ';
const char open_cell = 'O'; // This should be something different from empty_cell to help you debug.

const int max_rows = 100; // Replace with your max rows.
const int max_cols = 100; // Replace with your max cols.

// For clarity; means "cell position".
typedef std::pair<int, int> cell_pos;

std::queue<cell_pos> pending;
std::vector<cell_pos> skip; 
// skip should really be an std::unordered_set,
// but I leave it as an exercise for the reader.

// Renamed "row" to "start_row"
// Renamed "col" to "start_col"
pending.push(cell_pos(start_row, start_col));

while (!pending.empty()) {
    auto current = pending.front();
    auto row = current.first;
    auto col = current.second;

    // Requires <algorithm>. This skips the current cell if it's already been processed.
    if (std::find(skip.begin(), skip.end(), current) != skip.end()) {
        continue;
    }

    auto left_row = row - 1;
    auto right_row = row + 1;
    auto top_col = col - 1;
    auto bottom_col = col + 1;

    // Is the left cell empty?
    if (left_row >= 0 && table[left_row][col] == empty_cell) {
        pending.push(cell_pos(left_row, col));
    }
    // Is the right cell empty?
    if (right_row < max_rows && table[right_row][col] == empty_cell) {
        pending.push(cell_pos(right_row, col));
    }
    // Is the top cell empty?
    if (top_col >= 0 && table[row][top_col] == empty_cell) {
        pending.push(cell_pos(row, top_col));
    }
    // is the bottom cell empty?
    if (bottom_col < max_cols && table[row][bottom_col] == empty_cell) {
        pending.push(cell_pos(row, bottom_col));
    }
    // Is the top-left cell empty?
    if (left_row >= 0 && top_col >= 0 && table[left_row][top_col] == empty_cell) {
        pending.push(cell_pos(left_row, top_col));
    }
    // Is the top-right cell empty?
    if (right_row < max_rows && top_col >= 0 && table[right_row][top_col] == empty_cell) {
        pending.push(cell_pos(right_row, top_col));
    }
    // Is the bottom-left cell empty?
    if (left_row >= 0 && bottom_col < max_cols && table[left_row][bottom_col] == empty_cell) {
        pending.push(cell_pos(left_row, bottom_col));
    }
    // Is the bottom-right cell empty?
    if (right_row < max_rows && bottom_col < max_cols && table[right_row][bottom_col] == empty_cell) {
        pending.push(cell_pos(right_row, bottom_col));
    }

    view[row][col] = open_cell;
    pending.pop();
    skip.push_back(current);
}