Recommended improved match-finding algorithm for Bejeweled game?

Question

I'm trying to determine a sensible method of finding matches of 3, 4, or 5, for each rows and column. The player looks for areas (rows or columns) in the game board where the same "gem" will, after swapping two adjacent pieces (one swap each turn), repeat for 3-5 consecutive spots.

Here's an example scenario of a match-making move:

• Board before player move (bolded is necessary swap):

  A C B B C

  D D B A D

  D A A C C

  A D B B A

  D C D A A

• Board after player move (bolded is resulting match):

  A C B B C

  D D B A D

  D A A C C

  D A B B A

  D C D A A

In this example, there is a 4-match of "D" in the first column, after the first row. I'm trying to figure out how to find such matches after 1.) the board is created at the start of the game and the board randomizes a number of times to eliminate immediate matches, and 2.) after the player makes a move. If working correctly, the program will be able to detect a match after the correct swap is made by the program itself or the player.

Every algorithm I've attempted have caused the looping to go out of bounds and/or improperly find all resulting matches after a swap. By this, I mean that the program would sometimes try to search outside the array because I'm unsuccessfully telling the program how to "adjust" its array-searching based on where the current spot is. Even when it does not cause runtime errors, it still shows improper results. For instance, the player will see that the board has at least one complete match shown, which isn't good.

Here are explanations for two procedures I've attempted:

• Following spaces. From the current spot, check ahead four spaces across in same row (or less if there's less than four spaces remaining in the row). First check for a match of five, including the current spot; if none, check for four (minus a spot); if none, check for three (minus a spot); if none, no match found. Repeat the same check for the below column.

• Preceding spaces. From the current spot, check back four spaces across in same row (or less if there's less than four spaces in between the first spot in the row and the current spot). First check for a match of five, including the current spot; if none, check for four (minus a spot); if none, check for three (minus a spot); if none, no match found. Repeat the same check for the above column.

Here's the primary function where such working algorithm is needed. The use of my Gem class here (which is currectly broken) may not be important to the request, so I won't add it unless it's helpful.

bool Board::findMatches(bool scoringMove) // false if board is being setup before game
{
    bool matchesFound = false;

    // loops through entire board, where "size" is the width, not the number of spots
    for (int i = 0; i < size.getSize()*size.getSize(); i++)
    {
        // loops for each type of Gem, six total (_not identical to given example_)
        for (int k = 0; k < gems.getNumGems(); k++)
        {
            Gem traverseGems(k); // next Gem (in sequence)
            char nextGem = traverseGems.getGem(); // next Gem set to a char

            // ROWS check
            // default match search for 3-match
            if ((i < (size.getSize()*size.getSize())-4)
            && (board[i]->getGem() == nextGem)
            && (board[i+1]->getGem() == nextGem)
            && (board[i+2]->getGem() == nextGem))
            {
                // if the player is making a move
                if (!scoringMove)
                    return true;

                matchesFound = true;

                // just adds points to score; irrelevant to algorithm
                scoreMatches(3, 'R', i, 3);

                // no 4-match, but a 3-match
                if (board[i+3]->getGem() != nextGem)
                    scoreMatches(3, 'R', i, 3);
                else
                    scoreMatches(4, 'R', i, 4);

                // 5-match found
                if (board[i+3]->getGem() == nextGem && board[i+4]->getGem() == nextGem)
                    scoreMatches(5, 'R', i, 5);
            }

            // COLUMNS check (comments for rows check apply here as well)

            if ((i <= (size.getSize()-1))
            && (board[i]->getGem() == nextGem)
            && (board[i+size.getSize()]->getGem() == nextGem)
            && (board[i+(size.getSize()*2)]->getGem() == nextGem))
            {
                if (!scoringMove)
                    return true;

                matchesFound = true;

                scoreMatches(3, 'C', i, 3);

                if (board[i+(size*3)]->getGem() != nextGem)
                    scoreMatches(3, 'C', i, 3);
                else
                    scoreMatches(4, 'C', i, 4);
                if (board[i+(size*3)]->getGem() == nextGem && board[i+(size*4)]->getGem() == nextGem)
                    scoreMatches(5, 'C', i, 5);
            }
        }
    }

    return matchesFound;
}

Board.h

#ifndef BOARD_H
#define BOARD_H

#include "Size.h"
#include "Score.h"
#include "Move.h"
#include "Gem.h"

#include <iostream>
#include <iomanip>
#include <ctime>

class Board
{
private:
    Size size;
    Score score;
    Gem **board;
    bool moreSwaps;

    void swapGems(Move);
    void swapGems(int, int);
    void setNewRandGem(int);
    void findMoreSwaps();
    void scoreMatches(int, char, int, int);
    bool findMatches(bool);

public:
    Board();
    Board(Size, Score&);
    ~Board();
    void displayBoard() const;
    bool isMatch(Move);
    bool moreMovesFound() const;
};

#endif

Board Constructor

Board::Board(Size size, Score &score)
{
    srand((unsigned int)time(NULL)); // I can always move this to main()

    this->size = size;
    this->score = score;

    board = new Gem *[size.getSize()*size.getSize()];

    for (int i = 0; i < size.getSize()*size.getSize(); i++)
        board[i] = new Gem;

    //This is the "pre-game" block.
    //As long as the program finds a new match after performing its
    //own swaps, it'll randomize the entire board and start over again.
    //This is incredibly unefficient, but I will try to fix it later.
    do
    {
        for (int i = 0; i < size.getSize()*size.getSize(); i++)
            setNewRandGem(i);

    } while (findMatches(false));
}

Answer 1

Having reread the updated question, I think your goal is to test whether, for a given 5x5 board, there is any possible swap of two adjacent symbols that will produce a board with 3 or more identical symbols in a row or column.

If the previous attempts produced out-of-bounds errors, that would imply a bug in the implementation, not a bug in the algorithm. So using a different algorithm would do nothing to solve that problem, you still need to implement proper array boundary checks. There is no way around that, but on the plus side it is not particularly hard. Simply check each index on whether it is smaller than zero or larger than the array dimension size, before accessing the array. If it is, trace back the steps your program used to get to that value, and find the bug that must be there.

Of course, if the program produces the wrong results in addition to out-of-bounds errors, then your algorithm might also be wrong.

Having said that, I am still not sure I understand the algorithms you describe, but they seem too complex for this problem. Unless you need to evaluate thousands of boards per second, a simple brute force algorithm will suffice. Just try out all possible swaps, and for each swap check if the board contains 3 or more identical symbols in a row or column.

Here is a description in pseudocode:

function is_there_a_valid_move(board)
// returns true if there is a valid bejewelled move

   // test all horizontal swaps
   for (x = 0; x++; x< board-width - 1):
      for (y = 0; y++; y < board-height):
         make a copy of the board: board2
         swap board2[x,y] and board2[x+1,y]
         check_matches(board2, 3)
         if match found: return true

   // test all vertical swaps
   for (x = 0; x++; x< board-width):
      for (y = 0; y++; y < board-height - 1):
         make a copy of the board: board2
         swap board2[x,y] and board2[x,y+1]
         check_matches(board2, 3)
         if match found: return true

   return false

function check_matches(board, num_matches)
// returns true if there are num_matches or more of the same symbol in a row or column

   // check rows
   for (y = 0; y++; y < board-height):
      consecutive_symbols = 0
      for (x = 0; x++; x< board-width - 1):
         if board[x,y] == board[x+1,y]: consecutive_symbols++
         else: consecutive_symbols = 0
         if consecutive_symbols >=num_matches: return true

   // check columns
   for (x = 0; x++; x< board-width):
      consecutive_symbols = 0
      for (y = 0; y++; y < board-height - 1):
         if board[x,y] == board[x,y+1]: consecutive_symbols++
         else: consecutive_symbols = 0
         if consecutive_symbols >=num_matches: return true     

   return false

This is certainly not the fastest method, but for a 5x5 board everything else is overkill.