CODEWITHSUNDEEP
clinked-listtic-tac-toe
mdibound
mdibound

Reputation: 101

Where have I gone wrong? Generating tictactoe game tree

I am trying to generate a tree of tic-tac-toe moves with a linked-list implementation. I am starting the board with three cells filled in, so the tree should have (9-3)! = 720 nodes in total, but after running my program, it quickly hangs. Where have I gone wrong?

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

struct Node {

    struct Node *next_move;
    int cell[3][3];

};

struct Node *root, *position, *temp;
void generate_tree(struct Node *, int move);

int main() {

    root = (struct Node *) malloc (sizeof (struct Node));
    root->next_move = NULL;

     root->cell[0][0] = 1;
     root->cell[0][1] = 1;
     root->cell[0][2] = 1;

     generate_tree(root, 1); // computer's next move

    return 0;
}

void generate_tree(struct Node *root, int move) {

    position = root;    // use position to move down the linked list
    print_board(root);

    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {   // for all cells in root

            if (root->cell[j][i] == 0) { // if cell is empty

                temp = root;    // copy board
                temp->cell[j][i] = move; // make move

                while(1) {  // move to end of list
                    if (position->next_move == NULL) {
                        position->next_move = temp; // link new board at end of list
                        break;
                    } else { // move down list by 1
                        position = position->next_move; 
                        }
                }

                if (move == 1) {    // if it was the computers move
                    generate_tree(position, 2); // call self, with temp as new root, and opponent's move next
                } else {
                    generate_tree(position, 1); // call self, with temp as new root, and computers's move next
                }

            }

        }

    }

}
void print_board(struct Node *node) {

    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {

            printf("%d ",node->cell[j][i]);

        }
        printf("\n");
    }
}

Upvotes: 0

Views: 124

Answers (1)

paddy
paddy

Reputation: 63481

Eventually, you hit this a second time:

while(1) {  // move to end of list
    if (position->next_move == NULL) {
        position->next_move = temp; // link new board at end of list
        break;
    } else { // move down list by 1
        position = position->next_move; 
    }
}

The first time you hit it, you replaced root->next_move with root, turning your list into a single node that points to itself. The next time, you hit this loop, the first condition will never be met and the loop will not terminate.

It looks like the problem is here:

temp = root;    // copy board

Surely, this line should be allocating a new, empty node:

temp = (struct Node *) malloc (sizeof (struct Node));
temp->next_move = NULL;

That's not to say that this will make your program work the way you intended, but it ought to help get past the hang you were asking about.

Upvotes: 1

Related Questions