The CISC181 honors Fall 2004 Lab07 was described on the chalkboard and in an example file at the following link:
and the students seemed to be able to complete it without any particular problem. However, I wanted to put a description of the lab up on line just for future reference.
The game "hex" is a board game that is in some way similar to tic-tac-toe, but played on a board made of hexagons rather than squares. This variation makes the game much more strategic and interesting, and quite difficult to master for boards of larger sizes.
A 3 x 3 board looks like this:
__
/ \__
\__/ \__
/ \__/ \
\__/ \__/
/ \__/ \
\__/ \__/
\__/ \
\__/
However, 3x3 is not a particular interesting game to play. A more common size of game among serious hex players is 11x11, e.g.:
__ / \__ \__/ \__ / \__/ \__ \__/ \__/ \__ / \__/ \__/ \__ \__/ \__/ \__/ \__ / \__/ \__/ \__/ \__ \__/ \__/ \__/ \__/ \__ / \__/ \__/ \__/ \__/ \__ \__/ \__/ \__/ \__/ \__/ \__ / \__/ \__/ \__/ \__/ \__/ \ \__/ \__/ \__/ \__/ \__/ \__/ / \__/ \__/ \__/ \__/ \__/ \ \__/ \__/ \__/ \__/ \__/ \__/ / \__/ \__/ \__/ \__/ \__/ \ \__/ \__/ \__/ \__/ \__/ \__/ / \__/ \__/ \__/ \__/ \__/ \ \__/ \__/ \__/ \__/ \__/ \__/ / \__/ \__/ \__/ \__/ \__/ \ \__/ \__/ \__/ \__/ \__/ \__/ / \__/ \__/ \__/ \__/ \__/ \ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \ \__/ \__/ \__/ \__/ \__/ \ \__/ \__/ \__/ \ \__/
The rules are fairly simple. The players alternate filling in empty squares with X's and O's just like in Tic-tac-toe. Each player may choose any open square to make the next move. The X player tries to make a continuous region of X's from left to right, while the O player tries to make a contiguous region of O's from top to bottom. Unlike tic-tac-toe, the X's and O's don't have to be in a straight line, as long as they are all connected. As in tic-tac-toe, players can play offensively or defensively; defensive moves are those that block the other player from completing a line.
The game was invented separately by Piet Hein (Danish Poet and Scientist, who is also famous for his humorous poems called "Grooks") and John Nash (of "A Beautiful Mind"/Nobel Prize/Nash Equilibrium fame). A web search on "hex piet hein john nash" will turn up lots of material on this game including more detailed rules, example games, and strategies.
The program in the lab07 directory shows how to draw a 3x3 board for the game "hex". The assignment is to write a program which will draw any size board.
The program should take three command line parameters: size, filename and indent. The size parameter is the size of the board (e.g. 11). The filename parameter is the name of an output file (e.g. hex11.txt). The indent parameter indicates how far the board should be indented from the left margin.
I originally assigned this with the idea in mind that if one were going to write a hex program, one would need a simple way to draw a hex board in ASCII art. I later discovered a web page containing a Hex-related homework assignment written by Daniel Sleator, a Professor at Carnegie Mellon, that had a simpler solution to the problem of representing a hex board in ASCII. Prof. Sleator's assignment involved representing the board in the following fashion:
A B C D E F G
1 - - - - - - -
2 - - V - - - -
3 - - - - H - -
4 - - - V - - -
5 - - V H V - -
6 - - - - - - -
7 - - - - - H -
If I were to give a future assignment based on determining strategy
for the game, or the problem of determining a winner (using graph search or
union/find), I might well prefer this representation because it is simpler.
On the other hand, the task of drawing the full ASCII art hex board is, in
and of itself, an interesting assignment that illustrates the problems that
arise from "hacking" out a solution rather than designing a correct algorithm.