This is a small project that is intended to be an educational exercise in learning and consolidating basic syntax and concepts of C. It is a simple console-based implementation of TicTacToe which prints the game state on each turn and takes input accordingly. In each step, it checks if any player has won.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define WIDTH 3
#define SIZE WIDTH * WIDTH
#define MOVE_COUNT 8

const char *DIVIDER = "n---+---+---n";
const char *NUM_STR = "123456789";

const char EMPTY = ' ';
const char PLAYER1 = 'X';
const char PLAYER2 = 'O';

/**
 * The container of all the positions that must
 * be occupied by a player to score a win.
 */
const size_t WINNING_MOVES[MOVE_COUNT][3] = 
 // Horizontal streaks
 0, 1, 2,
 3, 4, 5,
 6, 7, 8,
 // Vertical streaks
 0, 3, 6,
 1, 4, 7,
 2, 5, 8,
 // Diagonal streaks
 0, 4, 8,
 2, 4, 6

;

typedef struct state_t 
 char values[SIZE];
 struct state_t *next;
 State;

/**
 * @return A new State with all blanks and navigation cleared.
 */
State *new_state() 
 State *state = malloc(sizeof(State));
 for (size_t i = 0; i < SIZE; ++i) 
 state->values[i] = EMPTY;
 
 state->next = NULL;


/**
 * @param state The parent state.
 * @param index The (free) position to mark.
 * @param player The player which sill mark the cell.
 * @return A new state from a parent with the requested
 * position marked by the given player mark.
 */
State *derive(State *state, size_t index, char player) 
 state->next = new_state();
 // Copy values
 for (size_t i = 0; i < SIZE; ++i) 
 state->next->values[i] = state->values[i];
 
 state = state->next;
 state->values[index] = player;

 return state;


/**
 * Frees the space occupied by the given State and its
 * successors.
 * @param state The state to deallocate.
 */
void free_state(State *state) 
 if (state == NULL)
 return;
 free(state->values);
 free(state->next);
 state->next = NULL;
 free(state);


/**
 * Pretty prints the given state with evenly spaced
 * symbols and dividers and indices in place of blanks.
 * @param state The state to be pretty-printed.
 */
void print_state(State *state) 
 for (size_t row = 0; row < WIDTH; ++row) 
 if (row != 0) printf(DIVIDER); 
 for (size_t col = 0; col < WIDTH; ++col) 
 if (col != 0) printf("
 int index = row * WIDTH + col;
 char value = state->values[index];
 printf(" %c ", (value == EMPTY ? NUM_STR[index] : value));
 
 
 printf("nn");


/**
 * @param player The player who's win to check.
 * @param state The state to check for win in.
 * @return true if the player has won.
 */
bool has_won(char player, State *state) 
 for (size_t move = 0; move < MOVE_COUNT; ++move) 
 int count = 0;
 for (size_t index = 0; index < WIDTH; ++index) 
 size_t move_idx = WINNING_MOVES[move][index];
 if (state->values[move_idx] == player) 
 count++;
 else // no point in checking any further for this move
 break;
 
 
 if (count == WIDTH) 
 print_state(state);
 printf("n%c wins!!n", player);
 return true;
 
 
 return false;


/**
 * Creates a new state from the given state using input
 * provided by the human player.
 *
 * @param player The character designated to the human player.
 * @param current The current state to move from.
 * @return A new state based on the input given by the human player.
 */
State *take_input(char player, State *current) index > SIZE 

int main() 
 State *state = new_state();
 State *head = state;
 char player = PLAYER1;

 while (!has_won(PLAYER1, state) && !has_won(PLAYER2, state)) 
 state = take_input(player, state);

 // Change player
 player = player == PLAYER1 ? PLAYER2 : PLAYER1;
 
 free_state(head);
 return 0;

Suggestions on all aspects of the code are welcome. Including improving performance, increasing simplicity, finding critical errors, etc.

this function:

State *new_state() 
 State *state = malloc(sizeof(State));
 for (size_t i = 0; i < SIZE; ++i) 
 state->values[i] = EMPTY;
 
 state->next = NULL;

has a signature that claims that it will return a pointer to a State. However, there is no return state; statement in the code.
Suggest changing the function signature to:

void new_state()

regarding the statements like:

scanf("%d", &index); // NOLINT

1. the declaration of index is size_t which is nothing like a int so the input format specifier should be similar to: %lu. (there is also a 'special' format specifier for size_t however, this will do.

when calling any of the scanf() family of functions, always check the returned value (not the parameter values) to assure the operation was successful. for statements like:

scanf("%d", &index); // NOLINT

the only 'good' return value would be 1. Anything else indicates an error occurred.

Note: the scanf() family of functions does not set errno when some format specifier fails

Suggest :

if( 1 != scanf("%d", &index) )

 fprintf( stderr, "scanf for the next location to place a token failed" );

for ease of readability and understanding: follow the axiom: only one statement per line and (at most) only one variable declaration per statement.

so this:

if (row != 0) printf(DIVIDER); 

should be written as:

if( row )

 printf( DIVIDER );

Jamming all the code blocks together, with no separation makes the code much more difficult to understand, debug, etc. Suggest: separate code blocks (for if else while do...while switch case default ) via a single blank line.

regarding:

void free_state(State *state) 
 if (state == NULL)
 return;
 free(state->values);
 free(state->next);
 state->next = NULL;
 free(state);

this only returns a single 'State' to the heap. However, those 'State's are a linked list. so should be in a loop, returning allocated memory for each state until the 'next' field is NULL.

when calling any of the heap allocation functions: (malloc, calloc, realloc) always check (!=NULL) the returned value to assure the operation was successful.

in function: has_won(), suggest:

bool done = false;
for (size_t move = 0; !done && move < MOVE_COUNT; ++move)

 int count = 0;
 for (size_t index = 0; index < WIDTH; ++index)
 
 size_t move_idx = WINNING_MOVES[move][index];
 if (state->values[move_idx] == player)
 
 count++;
 

 else
 // no point in checking any further for this move
 break;
 
 

 if (count == WIDTH)
 
 done = true;
 


if( done )

 print_state(state);
 printf("n%c wins!!n", player);


return done; 

Check the result of I/O functions

This code may fail to initialize index:

int index;
scanf("%d", &index); // NOLINT

while (index < 1 || index > SIZE || current->values[index - 1] != EMPTY) 
 printf("Invalid position! Try again : ");
 scanf("%d", &index); // NOLINT

We need to use the return value from scanf() to determine whether index has been assigned. Also, if the input fails, there's no point re-trying if the stream is in error or at EOF:

size_t index;
int nread;
while ((nread = scanf("%zd", &index)) != 1)
 || !index || index > SIZE
 || current->values[index - 1] != EMPTY)

 if (nread == EOF) 
 /* serious error - indicate failure */
 return NULL;
 
 printf("Invalid position! Try again : ");

Obviously, you'll need to adapt main() to handle a null return from take_input().