After coding tic-tac-toe for my HackerSchool application, I decided to try Connect Four.
One of the things I didn't like about my tic-tac-toe implementation was the brute-force method of checking for a win or a tie. Because there were only 9 squares, I simply checked all the rows, columns, and diagonals to see if the player had won. The Connect Four board is 7 x 6 with 42 squares, so manually checking all the possibilities would be impractical.
I also vaguely recalled from my long ago Data Structures and Algorithms class that you can use a simple array to represent grids and trees by calculating the index in different ways, and wanted to try that, rather than the array-of-arrays I used for tic-tac-toe.
After rather more work than I really want to admit to, I came up with:
which displays the row and column of each position, along with the index into the
So now if I know the row and column I want, I can calculate the index into the array with
The next bits were very similar to tic-tac-toe -- loop and alternate between the players, complain and re-prompt if they pick a column that's full, and detect a tie.
Now I'm up to the point where I knew I'd get stuck: detecting four adjacent spots with the same letter.
The code is here: https://github.com/wsmoak/hackerschool/blob/master/connect-four.rb
Ah ha! Repeated rambling pleas to the Google finally turned up A* Pathfinding. http://www.policyalmanac.org/games/aStarTutorial.htm
I started writing a message to devchix this morning and realized that I *don't* have to check the entire board, I only have to check paths of length 4 starting where the last piece was placed! I sent it anyway, even though it's not the typical sort of message for that group. Either it will be a fun discussion, or I'll learn not to do that again.
Here is some exploratory code around finding the neighbors of the last move:
That eventually turned into this, which is horribly ugly and very, very wrong. Because it traverses the path without keeping track of where it has been, it declares a winner when it finds two adjacent squares. It just moves back and forth until it counts to four! If you start with a partially completed board, it will also allow things like an L-shaped path, or a zig-zag, or any combination thereof. So, tomorrow this will be deleted and I'll start over.
Success! Now we only move in STRAIGHT lines:
and it gets called like this:
The code is (still) at https://github.com/wsmoak/hackerschool/blob/master/connect-four.rb