#include <stdio.h>

char marker[] = {'X', 'O'};
#define EMPTY '_'

void print_board(int winning_marker, char *board, int ply);
int win(char *board);

int winning[8][3] = {
	/* across */
	{0, 1, 2},
	{3, 4, 5},
	{6, 7, 8},

	/* down */
	{0, 3, 6},
	{1, 4, 7},
	{2, 5, 8},

	/* diagonal */
	{0, 4, 8},
	{2, 4, 6}
};

/* Enumerate all possible tictactoe games */

int
win(char *board)
{
	int i, wins = -1;

	for (i = 0; i < 8; ++i)
	{
		if (EMPTY != board[winning[i][0]]
			&& board[winning[i][0]] == board[winning[i][1]]
			&& board[winning[i][1]] == board[winning[i][2]]
		) {
			wins = board[winning[i][0]];
			break;
		}
	}
	return wins;
}

void
print_board(int winning_marker, char *board, int ply)
{
	printf("%c\t%s\t%d\n", winning_marker, board, ply);
}

void
moves(int who, char *current_board, int ply)
{
	char board[10];
	int i, open_space_cnt = 0;

	for (i = 0; i < 9; ++i)
	{
		if (EMPTY == current_board[i])
		{
			int who_won;

			++open_space_cnt;

			/* this spot available for a marker */
			memcpy(board, current_board, 10);  /* pick up ASCII Nul termination */
			board[i] = marker[who];

			if (-1 != (who_won = win(board)))
				print_board(who_won, board, ply);
			else
				moves(who^1, board, ply+1);
		}
	}

	/* if flow-of-control gets here and current_board has
	 * no open spaces, we have a cat game - the last move
	 * got made one ply up, and it didn't result in a win.
	 * moves() one ply up called moves() again (this invocation)
	 * with a full board.
	 */
	if (0 == open_space_cnt)
		print_board('D', current_board, ply);
}

int
main(int ac, char **av)
{
	char board[10];
	memset(board, EMPTY, 9);
	board[9] = '\0';
	moves(0, board, 1);
	return 0;
}