title: Recommended improved match-finding algorithm for Bejeweled game?
body: <p>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.</p>
  
  <p>Here's an example scenario of a match-making move:</p>
  
  <ul>
  <li><p><em>Board before player move (bolded is necessary swap)</em>:</p>
  
  <p>A C B B C</p>
  
  <p>D D B A D</p>
  
  <p>D A A C C</p>
  
  <p><strong>A D</strong> B B A</p>
  
  <p>D C D A A</p></li>
  <li><p><em>Board after player move (bolded is resulting match)</em>:</p>
  
  <p>A C B B C</p>
  
  <p><strong>D</strong> D B A D</p>
  
  <p><strong>D</strong> A A C C</p>
  
  <p><strong>D</strong> A B B A</p>
  
  <p><strong>D</strong> C D A A</p></li>
  </ul>
  
  <p>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.</p>
  
  <p>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 <em>complete</em> match shown, which isn't good.</p>
  
  <p>Here are explanations for two procedures I've attempted:</p>
  
  <ul>
  <li><p><strong>Following spaces</strong>.  From the current spot, check <strong>ahead</strong> 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 <strong>below</strong> column.</p></li>
  <li><p><strong>Preceding spaces.</strong>  From the current spot, check <strong>back</strong> 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 <strong>above</strong> column.</p></li>
  </ul>
  
  <p>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.</p>
  
  <pre><code>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 &lt; size.getSize()*size.getSize(); i++)
      {
          // loops for each type of Gem, six total (_not identical to given example_)
          for (int k = 0; k &lt; 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 &lt; (size.getSize()*size.getSize())-4)
              &amp;&amp; (board[i]-&gt;getGem() == nextGem)
              &amp;&amp; (board[i+1]-&gt;getGem() == nextGem)
              &amp;&amp; (board[i+2]-&gt;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]-&gt;getGem() != nextGem)
                      scoreMatches(3, 'R', i, 3);
                  else
                      scoreMatches(4, 'R', i, 4);
  
                  // 5-match found
                  if (board[i+3]-&gt;getGem() == nextGem &amp;&amp; board[i+4]-&gt;getGem() == nextGem)
                      scoreMatches(5, 'R', i, 5);
              }
  
              // COLUMNS check (comments for rows check apply here as well)
  
              if ((i &lt;= (size.getSize()-1))
              &amp;&amp; (board[i]-&gt;getGem() == nextGem)
              &amp;&amp; (board[i+size.getSize()]-&gt;getGem() == nextGem)
              &amp;&amp; (board[i+(size.getSize()*2)]-&gt;getGem() == nextGem))
              {
                  if (!scoringMove)
                      return true;
  
                  matchesFound = true;
  
                  scoreMatches(3, 'C', i, 3);
  
                  if (board[i+(size*3)]-&gt;getGem() != nextGem)
                      scoreMatches(3, 'C', i, 3);
                  else
                      scoreMatches(4, 'C', i, 4);
                  if (board[i+(size*3)]-&gt;getGem() == nextGem &amp;&amp; board[i+(size*4)]-&gt;getGem() == nextGem)
                      scoreMatches(5, 'C', i, 5);
              }
          }
      }
  
      return matchesFound;
  }
  </code></pre>
  
  <p><strong>Board.h</strong></p>
  
  <pre><code>#ifndef BOARD_H
  #define BOARD_H
  
  #include "Size.h"
  #include "Score.h"
  #include "Move.h"
  #include "Gem.h"
  
  #include &lt;iostream&gt;
  #include &lt;iomanip&gt;
  #include &lt;ctime&gt;
  
  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&amp;);
      ~Board();
      void displayBoard() const;
      bool isMatch(Move);
      bool moreMovesFound() const;
  };
  
  #endif
  </code></pre>
  
  <p><strong>Board Constructor</strong></p>
  
  <pre><code>Board::Board(Size size, Score &amp;score)
  {
      srand((unsigned int)time(NULL)); // I can always move this to main()
  
      this-&gt;size = size;
      this-&gt;score = score;
  
      board = new Gem *[size.getSize()*size.getSize()];
  
      for (int i = 0; i &lt; 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 &lt; size.getSize()*size.getSize(); i++)
              setNewRandGem(i);
  
      } while (findMatches(false));
  }
  </code></pre>