Recursion

I'm going to throw out a couple of thoughts to consider. I haven't actually done this, so I'm not guaranteeing success.

Say you start in the top left corner of your grid. You have the entire diagonal, the horizontal, and the vertical. Try picturing this as a tree with 3 rather than the usual 2 branches to start with. Now, consider this:

There are only TWO potential diagonal cases regardless of the size of your tic tac toe grid: One starting in the upper left corner, one starting in the upper right.

This means that the two diagonal cases can be checked independently, and actually pretty easily, I'm sure you can do this one. The diagonal cases can therefore be excluded from the recursion. Yay! BSP tree!

Now, for the actual tree, follow closely here, this could hurt a bit:

ALL vertical wins can be extrapolated recursively from the top row

ALL horizontal wins can be extrapolated recursively from the left column

This is regardless of actual size of grid. Consider:


1 2 3
4 5 6
7 8 9

Head node = 1
Consider: squares in the main branches (top row, left column) have a greater "value" than sub branches (those spawning vertically from the top row and those spawning horizontally from the left column). I add this consideration simply for visual reasons.

Tree: (this had BETTER show up right...)

...............1
......_________/\__________
.....4.....................2
..../.\.................../.\
..5....7.................5...3
./..../................./.../
6....8.................8...6
..../...................../
...9.....................9

Anyway, I think you can see how it would be possible to recursively determine if any of the 2 major paths or N minor paths contain a win.

Disclaimer: I did this off the top of my head. I refuse responsibility to any brain cell damage or frustration it might cause.

-fel

Edit: GRRRRRR. *sigh* *tries dots*

Edited by - felisandria on December 1, 2000 2:31:36 PM

I had to do a simillar program some time ago, checking all the possible wins on a chessboard with 8 queens, so it''s simillar to your problem. I used recursion and was able to check the diagnoal quite easily.


Just replace the board[8][8] with the 2d array (if that is what you''re using) for your board.

Also, this wasn''t written to be reused, so you''ll have to change the if statements to whatever numbers you need (possibly using min and max to find how many spots there are).

Sorry if this doesn''t make sense, haven''t had a lot of sleep lately.


//dir[2] doesn''t really need to be an array, it could simply be
//2 variables which tell the function what direction the program
//should check

int chkDiag (int board[8][8], int x, int y, int dir[2])
{
int i,j;

//in other words... if there are any more spots it can go diagnoly
if (x+dir[0] > -1 && x+dir[0] < 8 && y+dir[1] > -1 && y+dir[1] < 8)
{
if (board[ x+dir[0] ][ y+dir[1] ] == 1) //queen at spot
return(1);
else
return( chkDiag(board, x+dir[0], y+dir[1], dir) ); //else, no queen and keep caling function
//until end of diagnol or 2 queens found
}


return(0); //returns 0 meaning it made it to the end of the board with no other queens
}

I threw something together just to see if it was easy or not. It is.

The algorithm is real simple, what''s my prize for it?

I wrote a console app to go with it. You can download the exe.

tictactoe

Note, the exec does not check to see if you are trying to overwrite another move, and the top left corner is row 0, col 0.

I forgot to compress the file, and the only reason there is a limit of 30 on the size of the board is I was to lazy to make the board a dynamic 2D array.

Ok, the way I see it the most general instance of the problem is to look for a run of length R in for one player in an A x B board. So for standard tic-tac-toe it''s R = 3, A = 3, B = 3. For go-maku it''d be something like R = 5, A = 13, B = 13. (Not sure about the A and B there).

The iterative method would be, assuming that our board data is in an A x B array:

int FindWinner(int ** board, int R, int A, int B) {
  int i, j, k, p;
  // check for verticle runs
  for (i = 0; i < A - R + 1; i ++) {
    for (j = 0; j < B; j ++) {
      p = board[ i ][ j ];
      for (k = 0; k < R && p != 0; k++) {
        if (board[ i + k ][ j ] != p) p = 0;
      }
      if (p != 0) return p;
    }
  }
  // check for horizontal runs
  for (i = 0; i < A; i ++) {
    for (j = 0; j < (B - R + 1); j++) {
      p = board[ i ][ j ];
      for (k = 0; k < R && p != 0; k++) {
        if (board[ i ][ j + k ] != p) p = 0;
      }
      if (p != 0) return p;
    }
  }
  // check for diagonal runs
  for (i = 0; i < A - R + 1; i ++) {
    for (j = 0; j < (B - R + 1); j++) {
      p = board[ i ][ j ];
      for (k = 0; k < R && p != 0; k++) {
        if (board[ i + k ][ j + k ] != p) p = 0;
      }
      if (p != 0) return p;
    }
  }
  return 0;
}
 

From here you can turn it into multiple recursive functions or try to turn it into a single recursive function. With multiple recursive functions it''d look like:

int FindVerticle(board, int i, int j, int R, int A, int B) {
  int k, p;
  p = board[ i ][ j ];
  for (k = 1; k < R && p != 0; k++) {
    if (board[ i + k ][ j ] != p) p = 0;
  }
  if (p != 0) return p;

  if (j + 1 < B) {
    p = FindVerticle(board, i, j + 1, R, A, B);
    if (p != 0) return p;
  }

  // only recurse on i, if j == 0 in order to
  // prevent overlap recursion
  if (j == 0 && (i + 1) < (A - R + 1)) {
    p = FindVerticle(board, i + 1, 0, R, A, B);
    if (p != 0) return p;
  }

  return 0;
}

int FindHorizontal(board, int i, int j, int R, int A, int B) {
  // you can fill in yourself
}

int FindDiagonal(board, int i, int j, int R, int A, int B) {
  // you can fill in yourself
}

int FindWinner(int ** board, int R, int A, int B) {
  int p;

  p = FindVerticle(board, 0, 0, R, A, B);
  if (p != 0) return p;

  p = FindHorizontal(board, 0, 0, R, A, B);
  if (p != 0) return p;

  p = FindDiagonal(board, 0, 0, R, A, B);
  return p;
}
 

Of course FindVertical, FindHorizontal, FindDiagonal still have a loop in them, so you can either leave it be, introduce more recursive helper functions, or do something evil like:

int FindVerticle(board, int i, int j, int k, int p, int R, int A, int B) {
  // see if we have a verticle run
  int p_prime;
  p_prime = board[ i ][ j ];

  // if k > 0, then this was a continuation of a run check
  if (k > 0) {
    if (p != p_prime) return 0;
    if (k + 1 == R) return p;
    return FindVerticle(board, i + 1, j, k + 1, p, R, A, B);
  } else { // k == 0
    // begin run check
    if (p_prime != 0) {
      p_prime = FindVerticle(board, i + 1, j, 1, p_prime, R, A, B);
      if (p_prime != 0) return p_prime;
      // otherwise recurse
    }

    // recurse on j
    if (j + 1 < B) {
      p_prime = FindVerticle(board, i, j + 1, 0, 0, R, A, B);
      if (p_prime != 0) return p_prime;
    }

    // only recurse on i, if j == 0 in order to
    // prevent overlap recursion
    if (j == 0 && (i + 1) < (A - R + 1)) {
      p_prime = FindVerticle(board, i + 1, 0, 0, 0, R, A, B);
      if (p != 0) return p_prime;
    }
  }

  return 0;
}
 

If you want to take the original FindWinner function and turn it into a single recursive function, first combine the loops:

int FindWinner(int ** board, int R, int A, int B) {
  int i, j, k, p_v, p_h, p_d;

  for (i = 0; i < A; i ++) {
    for (j = 0; j < B; j ++) {
      if (i < (A - R + 1)) p_v = board[ i ][ j ];
      else p_v = 0;
      if (j < (B - R + 1)) p_h = board[ i ][ j ];
      else p_h = 0;
      if (i < (A - R + 1) && j < (B - R + 1)) p_d = board[ i ][ j ];
      else p_d = 0;

      for (k = 1; k < R && (p_v != 0 || p_h != 0 || p_d != 0); k++) {
        if (i < (A - R + 1)) {
          if (board[ i + k ][ j ] != p_v) p_v = 0;
        }
        if (j < (B - R + 1)) {
          if (board[ i ][ j + k ] != p_h) p_h = 0;
        }
        if (i < (A - R + 1) && j < (B - R + 1)) {
          if (board[ i + k ][ j + k ] != p_d) p_d = 0;
        }
      }
      if (p_h != 0) return p_h;
      if (p_v != 0) return p_v;
      if (p_d != 0) return p_d;
    }
  }
  return 0;
}
 

Now transform the FindWinner with combined loops into a recursive function with a single for loop:

int FindWinner(int ** board, int i, int j, int R, int A, int B) {
  int k, p_v, p_h, p_d;

  if (i < (A - R + 1)) p_v = board[ i ][ j ];
  else p_v = 0;
  if (j < (B - R + 1)) p_h = board[ i ][ j ];
  else p_h = 0;
  if (i < (A - R + 1) && j < (B - R + 1)) p_d = board[ i ][ j ];
  else p_d = 0;

  for (k = 1; k < R && (p_v != 0 || p_h != 0 || p_d != 0); k++) {
    if (i < (A - R + 1)) {
      if (board[ i + k ][ j ] != p_v) p_v = 0;
    }
    if (j < (B - R + 1)) {
      if (board[ i ][ j + k ] != p_h) p_h = 0;
    }
    if (i < (A - R + 1) && j < (B - R + 1)) {
      if (board[ i + k ][ j + k ] != p_d) p_d = 0;
    }
  }
  if (p_h != 0) return p_h;
  if (p_v != 0) return p_v;
  if (p_d != 0) return p_d;

  int p;
  if (j + 1 < B) {
    p = FindWinner(board, i, j + 1, R, A, B);
  }

  if (j == 0 && (i + 1) < A) {
    p = FindWinner(board, i + 1, 0, R, A, B);
  }

  return 0;
}
 

From there you can recurse on k like before. (but more painfully)

int FindWinner(int ** board, int i, int j, int k, int p_v, int p_h, int p_d, int R, int A, int B) {
  int p_prime;

  if (k > 0) { // continuation of run check
    if (p_v == 0 && p_h == 0 && p_d == 0) return 0;
    if (i < (A - R + 1)) {
      if (board[ i + k ][ j ] != p_v) p_v = 0;
    }
    if (j < (B - R + 1)) {
      if (board[ i ][ j + k ] != p_h) p_h = 0;
    }
    if (i < (A - R + 1) && j < (B - R + 1)) {
      if (board[ i + k ][ j + k ] != p_d) p_d = 0;
    }
    if (k + 1 == R) {
      if (p_v != 0) return p_v;
      if (p_h != 0) return p_h;
      if (p_d != 0) return p_d;
      return 0;
    }
    return FindWinner(board, i, j, k + 1, p_v, p_h, p_d, R, A, B);
  } else { // k == 0
    if (i < (A - R + 1)) p_v = board[ i ][ j ];
    else p_v = 0;
    if (j < (B - R + 1)) p_h = board[ i ][ j ];
    else p_h = 0;
    if (i < (A - R + 1) && j < (B - R + 1)) p_d = board[ i ][ j ];
    else p_d = 0;
    p_prime = FindWinner(board, i, j, 1, p_v, p_h, p_d, R, A, B);
    if (p_prime != 0) return p_prime;

    // no winner, so recurse
    if (j + 1 < B) {
      p = FindWinner(board, i, j + 1, 0, 0, 0, 0, R, A, B);
    }

    if (j == 0 && (i + 1) < A) {
      p = FindWinner(board, i + 1, 0, 0, 0, 0, 0, R, A, B);
    }
  }
  return 0;
}
 

Of course, I didn''t compile or check any of these. But you should be able to see enough of how it''s done to fix them yourselves.