/* Program to solve the matchstick game for up to 7 matches.  */

#define MAXSIZE (7)     /* Max. matches on each side of the space */

#include <stdio.h>
#include <stdlib.h>     /* for exit() */

typedef struct {
    signed char piece[MAXSIZE*2+1];     /* MAXSIZE each way + space */
    /* Note: a 'piece' is either a matchstick or the vacant space. */
    char spaceloc;                      /* where is the space? */
} gamestate;

gamestate current, win_state;   /* The game during play & target position */
int gamesize;                   /* matches each way */
int positions;                  /* Size of playing area (gamesize*2+1) */

void initialise(void);          /* Sets up current & win_state */
int seek_win(void);             /* Returns 1 for win, 0 for failure */

main() {
    printf("   The Matchstick Game\nHow many matches (max %d)? ", MAXSIZE);
    do {
        scanf("%d", &gamesize);
        if (gamesize>MAXSIZE) {
            printf("Too big (maximum %d), please re-enter: ", MAXSIZE);
        }
    } while (gamesize>MAXSIZE);
    positions = gamesize*2 + 1;
    initialise();       /* Set up current and win_state to represent
                           the first and final state of the matches. */
    seek_win();         /* Do it all! */
    return 0;
}

/****** initialise: **********************
On entry: gamesize is the number of matches each way, positions is
          gamesize*2+1.
On exit:  Variables current & win_state are set up to represent the
          initial & final states respectively for a game of size gamesize.
*/
void initialise(void) {
    /* current should be as shown below. (e.g. for gamesize == 3):
       +----+----+----+----+----+----+----+
       | 1  | 1  | 1  | 0  | -1 | -1 | -1 |
       +----+----+----+----+----+----+----+
       The win_state has the match directions reversed.
    */
    int i, rhs;
    rhs = gamesize + 1;
    for (i=0; i<gamesize; i++) {
        current.piece[i] = win_state.piece[rhs+i] = 1;
        win_state.piece[i] = current.piece[rhs+i] = -1;
    }
    current.piece[gamesize] = win_state.piece[gamesize] = 0;
    current.spaceloc = win_state.spaceloc = gamesize;
}

/****** seek_win: ***********************
On entry: The global current tells the existing game state, win_state
          tells the state needed for a win, gamesize is the number of
          matches each way, positions is gamesize*2+1.
On exit:  If a win is found, all game positions from the win backward to
          the current will be displayed backwards, resulting in a printout
          that appears to be moving forwards from the start; returns 1.
          If a win is not found, nothing is displayed; returns 0.
          All globals will be exactly as they were on entry.
*/
int move_is_legal(char spaceloc, char current_spaceloc);
void alter_position(char spaceloc, char current_spaceloc);
void undo_changes(char spaceloc, char current_spaceloc);
int found_a_win(void);
void display_position(void);

int seek_win(void) {
    /* How to seek_win:
        For each possible move from the present position:
            Alter the position.
            seek_win from the new position.
            Undo the change to the position.
            If a win was found by seek_win,
                (This game position is on the route to victory:)
                Display the matches.
                Return, indicating a win to the caller.
        (After trying each possible move, game must be blocked:)
        Check if matches are in the final position, if so,
            Display the matches,
            Return, indicating a win to the caller.
        else
            Return, indicating failure to the caller.
    */
    /* We can undo a move easily if we remember the old location of the
       space: whatever is there after moving must have come from where the
       space is now; undo by putting it back where it came from. */
    char spaceloc, current_spaceloc;    /* Space location after & before */
    current_spaceloc = current.spaceloc;/* Remember 'before' location */

    /* Try all possible new locations of the space: up to 2 either side. */
    for (
        spaceloc = current_spaceloc - 2;
        spaceloc <= current_spaceloc + 2;
        spaceloc++
    ) {
        if ( move_is_legal(spaceloc, current_spaceloc) ) {
            int we_won;
            alter_position(spaceloc, current_spaceloc);
            we_won = seek_win();
            undo_changes(spaceloc, current_spaceloc);
            if (we_won) {
                display_position();
                return 1;                       /* Indicate win */
            }
        }
    } /* end of for loop */

    /* Here, nothing has worked, so check if we are at the final position */
    if (found_a_win()) {
        display_position();
        return 1;                               /* win */
    } else {
        return 0;                               /* failure */
    }
}

/****** move_is_legal: *********************
On entry: spaceloc is location of match to be moved into the space now
          at current_spaceloc.
On exit:  Returns 1 if the following tests are passed, 0 otherwise:
              spaceloc is within the limits of the game
              spaceloc is not the same as current_spaceloc (because a
                  piece MUST be moved)
              the shift will move a match forwards.
*/
int move_is_legal(char spaceloc, char current_spaceloc) {
    return (
        spaceloc >= 0 &&                 /* Space not fallen off LHS */
        spaceloc < positions &&          /* Space not fallen off RHS */
        spaceloc != current_spaceloc &&  /* Space HAS been moved */
        current.piece[spaceloc] * (current_spaceloc-spaceloc) > 0
                      /* Matchstick is moving forward. (Think about it.) */
    );
}

/****** alter_position: *****************
On entry: spaceloc is location of match to be moved to current_spaceloc.
On exit:  current structure updated to reflect the move.
*/
void alter_position(char spaceloc, char current_spaceloc) {
    current.piece[current_spaceloc] = current.piece[spaceloc];
                                         /* Shift piece into space */
    current.piece[spaceloc] = 0;         /* Set its old spot empty */
    current.spaceloc = spaceloc;         /* Record new position of space */
}

/****** undo_changes: ******************
On entry: spaceloc is the old location of the match that was moved into
          the space at current_spaceloc.
On exit:  current structure updated to undo the move.
*/
void undo_changes(char spaceloc, char current_spaceloc) {
    current.spaceloc = current_spaceloc; /* Reset space position */
    current.piece[spaceloc] = current.piece[current_spaceloc];
                                         /* Reverse piece */
    current.piece[current_spaceloc] = 0; /* Put space where it was before */
}

/****** found_a_win: ******************
On entry: current is the current state of the game, win_state is the
          target state (the position when a win is found).
On Exit:  Returns 1 if current is the winning position, 0 otherwise.
*/
int found_a_win(void) {
    int pos;
    if (current.spaceloc != win_state.spaceloc) {
        return 0; /* If the spaces are at different places, states differ */
    }
    for (pos=0; pos<positions; pos++) { /* Check all match positions */
        if (current.piece[pos] != win_state.piece[pos]) {
            return 0;                   /* Found a difference */
        }
    }
    return 1;                           /* Passed all tests, have win. */
}

/**** display_position ****
On entry: current tells the state to be displayed.
On exit:  A 'picture' of the current state is shown on the screen,
          but with directions of the matches reversed.
*/
void display_position(void) {
    /* Draw forward matches as "<---" and reverse matches as "--->" */
    int i;
    for (i=0; i<positions; i++) {
        switch (current.piece[i]) {
        case -1:
            printf("---> ");
            break;
        case 0:
            printf("     ");
            break;
        case 1:
            printf("<--- ");
        }
    }
    putchar('\n');      /* End the line */
}