URGENT HELP WITH TREES and recursion
Author Message
URGENT HELP WITH TREES and recursion

hello! my name is Donaji Trejo I have to do an tic tac toe the point is to
do a recursive function to create all kind of posible boards. We do this in
a tree.. first we create a blank board that has nothing but spaces in it.
that's the root board.. we pas that to the recursive function (buildtree)
then we create 9 children boards.. with one x in each board.. and then we
make another 9 children for that 9 boards adding the 'o' . i can't get it to
work. the recursion my code gets the first child of the root and then the 9
childs using all the available convinations for "X' and "o' but then i'm
stuck i don't know how to tell the function to keep doing it until the game
is over or the board is full any ideas this is my code

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

struct Node   /* structure to represent a board */
{
char board[BOARD_SIZE]; /* ' ', 'X' or 'O' in each element */

int score;   /* evaluation of board   */

struct Node *next[BOARD_SIZE];
/* pointers to new boards for each  */
/* potential move, illegal moves are */
/* represented by NULL pointers  */

Quote:
};

/************************************************************************/

struct Table    /* structure to represent table of all */
/* possible boards   */
{
struct Node * boards[MAX_UNIQUE_BOARDS];
/* all possible boards in game  */

unsigned int num;  /* number of boards in array   */

Quote:
};

/************************************************************************/

void buildTree (struct Node *, struct Table *, char);
char turnplayer(char);
int fullboard(struct Node *);
int wins (struct Node *);
/*int compare ( const void *, const void *);       */

int main()
{
struct Table *tables;
struct Node *blankboard;
int i, k;
char player = 'X';

if( (blankboard = (struct Node *)malloc(sizeof(struct Node)))==NULL)
{
printf("out of memory\n");
exit(-1);
}

if((tables = (struct Table *)malloc(sizeof(struct Table)))==NULL)
{
printf("out of memory\n");
exit(-1);
}

/*initialize the blankboard->board to empty*/
for (i=0; i<9; i++)
{
blankboard->board[i]=' ';

}

/*initialize the score to 0*/
blankboard->score = 0;

/*put blank boards in table boards*/
tables->boards[0] = blankboard;

/*initialize num to one*/
tables-> num = 1;

buildTree(blankboard, tables, player);

for(k=0; k<tables->num; k++)
{
printf("Line %d:", k );
printf("%s\n", tables->boards[k]);
}

return 0;

Quote:
}

void buildTree (struct Node *rootptr, struct Table *tables, char player)
{
struct Node *curbrd;
struct Node *tempbrd;
int j, k, g;
int fullboard = 0;

/*if(*rootptr == NULL)
{
*rootptr = malloc(sizeof(struct Node));
} */

if( (curbrd = (struct Node *)malloc(sizeof(struct Node)))==NULL)
{
printf("out of memory\n");
exit(-1);
}

for(j=0; j<9; j++)
{
curbrd->board[j]=rootptr->board[j];
}

rootptr-> next[0] = curbrd;
curbrd -> board[0] = player;
tables -> boards[tables->num] = curbrd;
tables -> num ++;

for(k = 0; k <9; k++)
{
if( (tempbrd = (struct Node *)malloc(sizeof(struct Node)))==NULL)
{
printf("out of memory\n");
exit(-1);
}

for(j=0; j<9; j++)
{
tempbrd->board[j]=curbrd->board[j];
}

curbrd-> next[k] = tempbrd;
if(tempbrd -> board[k] == ' ')
{
tables -> num ++;
tempbrd -> board[k] = turnplayer(player);
tables -> boards[tables->num] = tempbrd;

}

else
tempbrd = NULL;

/* for(g=0; g,9; g++) /*if i put this code on i get a segmentation
fault*/
{
if(tempbrd->board[g] == ' ')
{
fullboard++;
}
}

if (fullboard > 0)
{
buildTree(tempbrd, tables, turnplayer(player)); /*calling recursion*/
}  */
}

Quote:
}

char turnplayer(char player)/*swithcing the players*/
{
if(player == 'X')
{
player = 'O';
}
else if(player == 'O')
{
player = 'X';
}
return player;

Quote:
}

int fullboard(struct Node *cubrd) /*check if the board is full*/
{
int i;

for( i = 0; i<9; i++)
{
if(cubrd->board[i] == ' ')
return 1;
else
return 0;
}

Quote:
}

int wins (struct Node *winner) /*checking if there is a winner*/
{
int i;
int win=0;

for( i= 0; i<9; i++)
{

if ( winner -> board [i] != ' ')
{
if(i == 0 || i == 3 || i == 6)
{
if (( winner -> board[i]== winner -> board [i+1]) && (winner->board[i]
== winner -> board[i+2]))
win = 1;
}

if (( winner -> board[i] == winner -> board [i+3]) && (winner -> board[i]
== winner -> board[i+6]))
win = 1;

if (( winner -> board[0] == winner -> board [4]) && (winner ->
board[4] == winner -> board[8]))
win = 1;

if (( winner -> board[2] == winner -> board [4]) && (winner ->
board[4] == winner -> board[6]))
win = 1;
}
}
return win;

Quote:
}

*/

donaji trejo

Wed, 24 Sep 2003 02:46:43 GMT
URGENT HELP WITH TREES and recursion
Hi Donaji,
no idea what your code is supposed to do. Try this:

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

#define BOARD_SIZE 3

void print_board(char board[BOARD_SIZE][BOARD_SIZE],int level){

int i,j;

printf("%*.s/",level,"");
for(j=0;j<BOARD_SIZE-1;j++)
fputs("--",stdout);
puts("-\\");

for(i=0;i<BOARD_SIZE;i++){
printf("%*.s|",level,"");
for(j=0;j<BOARD_SIZE;j++){
printf("%c|",board[i][j]);
}
puts("");
}

printf("%*.s\\",level,"");
for(j=0;j<BOARD_SIZE-1;j++)
fputs("--",stdout);
puts("-/");

Quote:
}

int is_last(char board[BOARD_SIZE][BOARD_SIZE],int i,int j,char type){

int k;

/* check rows and columns */

for(k=0;k<BOARD_SIZE;k++)
if(board[i][k]!=type)
break;
if(k==BOARD_SIZE){
printf("%c wins on row %d\n",type,i);
return 1;
}

for(k=0;k<BOARD_SIZE;k++)
if(board[k][j]!=type)
break;
if(k==BOARD_SIZE){
printf("%c wins on column %d\n",type,j);
return 1;
}

/* check diagonals */

if(i==j){
for(k=0;k<BOARD_SIZE;k++)
if(board[k][k]!=type)
break;
if(k==BOARD_SIZE){
printf("%c wins on diagonal \\\n",type);
return 1;
}
}

if(i==BOARD_SIZE-j-1){
for(k=0;k<BOARD_SIZE;k++)
if(board[k][BOARD_SIZE-k-1]!=type)
break;
if(k==BOARD_SIZE){
printf("%c wins on diagonal /\n",type);
return 1;
}
}

return 0;

Quote:
}

void recurse(char board[BOARD_SIZE][BOARD_SIZE],int level,char type){

char new_board[BOARD_SIZE][BOARD_SIZE];
int i,j;

memcpy(new_board,board,BOARD_SIZE*BOARD_SIZE);

for(i=0;i<BOARD_SIZE;i++){
for(j=0;j<BOARD_SIZE;j++){
if(board[i][j]==' '){
new_board[i][j]=type;
print_board(new_board,level);
if(is_last(new_board,i,j,type)){
getchar();
}else{
recurse(new_board,level+1,(type=='x') ? 'o' : 'x');
}
new_board[i][j]=' ';
}
}
}

Quote:
}

int main(void){

char board[BOARD_SIZE][BOARD_SIZE];
int i,j;

memset(board,' ',BOARD_SIZE*BOARD_SIZE);

recurse(board,0,'x');

Quote:
}

Wed, 24 Sep 2003 04:21:41 GMT
URGENT HELP WITH TREES and recursion
/*
Still lots of stuff completely hosed in here, especially the memory
management.
However, this might get you started.
*/
#include <search.h>
#include <stdio.h>
#include <stdlib.h>

#define BOARD_SIZE 9
#define MAX_UNIQUE_BOARDS 19683
struct Node {                   /* structure to represent a board */
char            board[BOARD_SIZE];  /* ' ', 'X' or 'O' in each element */

int             score;      /* evaluation of board   */

struct Node    *next[BOARD_SIZE];
/* pointers to new boards for each  */
/* potential move, illegal moves are */
/* represented by NULL pointers  */

Quote:
};

/*

ROWS ARE A-B-C, COLS ARE 0-1-2:

A  A0|A1|A2
--+--+--
B  B0|B1|B2
--+--+--
C  C0|C1|C2

0  1  2
*/
#define A0 0
#define A1 1
#define A2 2
#define B0 3
#define B1 4
#define B2 5
#define C0 6
#define C1 7
#define C2 8

/************************************************************************/

struct Table {                  /* structure to represent table of all */
/* possible boards   */
struct Node    *boards[MAX_UNIQUE_BOARDS];
/* all possible boards in game  */

unsigned int    num;        /* number of boards in array   */

Quote:
};

/************************************************************************/

void            buildTree(struct Node *, struct Table *, char);
char            turnplayer(char);
int             fullboard(struct Node *);
int             wins(struct Node *);
/*int compare ( const void *, const void *);       */

int             main()
{
struct Table   *tables;
struct Node    *blankboard;
int             i,
k;
char            player = 'X';
/* LOSE THE CASTS! */
if ((blankboard = malloc(sizeof(struct Node))) == NULL) {
printf("out of memory\n");
exit(-1); /* the exit function returns 0, EXIT_SUCCESS or EXIT_FAILURE
*/
}
if ((tables = malloc(sizeof(struct Table))) == NULL) {
printf("out of memory\n");
exit(-1);
}
/* initialize the blankboard->board to empty */
for (i = 0; i < BOARD_SIZE; i++) {
blankboard->board[i] = ' ';
}

/* initialize the score to 0 */
blankboard->score = 0;

/* put blank boards in table boards */
tables->boards[0] = blankboard;

/* initialize num to one */
tables->num = 1;

buildTree(blankboard, tables, player);

for (k = 0; k < tables->num; k++) {
int             l;
printf("Line %d:", k);
/* this printout was tragically broken before: */
for (l = 0; l < 9; l++) /* all in a row, but OK */
printf("%c", tables->boards[k]->board[l]);
putchar('\n');
}
return 0;

Quote:
}

void            buildTree(struct Node * rootptr, struct Table * tables, char
player)
{
struct Node    *curbrd;
struct Node    *tempbrd;
int             j,
k,
g;
int             fb = 0;

/* if(*rootptr == NULL) { rootptr = malloc(sizeof(struct Node)); } */

if ((curbrd = malloc(sizeof(struct Node))) == NULL) {
printf("out of memory\n");
exit(-1);
}
for (j = 0; j < BOARD_SIZE; j++) {
curbrd->board[j] = rootptr->board[j];
}

rootptr->next[0] = curbrd;
curbrd->board[0] = player;
tables->boards[tables->num] = curbrd;
tables->num++;

for (k = 0; k < BOARD_SIZE; k++) {
if ((tempbrd = malloc(sizeof(struct Node))) == NULL) {
printf("out of memory\n");
exit(-1);
}
for (j = 0; j < BOARD_SIZE; j++) {
tempbrd->board[j] = curbrd->board[j];
}

curbrd->next[k] = tempbrd;
if (tempbrd->board[k] == ' ') {
tables->num++;
tempbrd->board[k] = turnplayer(player);
tables->boards[tables->num] = tempbrd;
for (g = 0; g < BOARD_SIZE; g++) {  /* if i put this code on i
* get a segmentation fault */
if (tempbrd->board[g] == ' ') {
fb++;
}
}

} else
tempbrd = NULL;

if (fb > 0) {
buildTree(tempbrd, tables, turnplayer(player));     /* calling
recursion */
}
}

Quote:
}

char            turnplayer(char player)
{                               /* swithcing the players */
if (player == 'X') {
player = 'O';
} else if (player == 'O') {
player = 'X';
}
return player;
Quote:
}

/*
O| |X
-+-+-
O| |X
-+-+-
O| |X

The board is not full, and yet by rule this board cannot exist.

*/
int             fullboard(struct Node * cubrd)
{                               /* check if the board is full */
int             i;

for (i = 0; i < BOARD_SIZE; i++) {
if (cubrd->board[i] == ' ')
return 1;
}                           /* You must check them all to be sure it is
* full */
return 0;

Quote:
}

int             d1win(struct Node * winner)
{
int             win = 0;
if (winner->board[A0] != ' ')
if (winner->board[B1] == winner->board[A0])
if (winner->board[C2] == winner->board[A0])
win = winner->board[A0];
return win;

Quote:
}

int             d2win(struct Node * winner)
{
int             win = 0;
if (winner->board[A2] != ' ')
if (winner->board[B1] == winner->board[A2])
if (winner->board[C0] == winner->board[A2])
win = winner->board[A2];
return win;

Quote:
}

int             rowwin(struct Node * winner)
{
int             i;
int             win = 0;
for (i = 0; i < 7; i += 3)
if (winner->board[i] != ' ')
if (winner->board[i] == winner->board[i + 1])
if (winner->board[i] == winner->board[i + 2])
win = winner->board[i];
return win;

Quote:
}

int             colwin(struct Node * winner)
{
int             i;
int             win = 0;
for (i = 0; i < 3; i++)
if (winner->board[i] != ' ')
if (winner->board[i] == winner->board[i + 3])
if (winner->board[i] == winner->board[i + 6])
win = winner->board[i];
return win;

Quote:
}

int             wins(struct Node * winner)
{                               /* checking if there is a winner */
int             win = 0;
win = d1win(winner);
if (win)
return win;
win = d2win(winner);
if (win)
return win;
win = rowwin(winner);
if (win)
return win;
win = colwin(winner);
return win;

Quote:
}

/*
LCLint 2.5q --- 26 July 2000

foo.c: (in function main)
foo.c(74,14): Argument to exit has implementation defined behavior: -1
The argument to exit should be 0, EXIT_SUCCESS or EXIT_FAILURE (-exitarg
will
suppress message)
foo.c(78,14): Argument to exit has implementation defined behavior: -1
foo.c(96,17): Operands of < have incompatible types (int, unsigned int):
k < tables->num
To ignore signs in type comparisons use +ignoresigns
foo.c(101,26): Value tables->boards[0]->board[] used before definition
An rvalue is used that may not be initialized to a value on some execution
path. (-usedef will suppress message)
foo.c(102,9): Return value (type int) ignored: putchar('\n')
Result returned by function call is not used. If this is intended, can cast
result to (void) to eliminate message. (-retvalint will suppress message)
foo.c(104,14): Fresh storage tables not released before return
A memory leak has been detected. Newly-allocated or only-qualified storage
is
not released before the last reference to it is lost. (-mustfree will
suppress message)
foo.c(76,10): Fresh storage tables allocated
foo.c: (in function buildTree)
foo.c(120,14): Argument to exit has implementation defined behavior: -1
foo.c(135,18): Argument to exit has implementation defined behavior: -1
foo.c(142,13): Value tempbrd->board[] used before definition
foo.c(158,23): Possibly null storage tempbrd passed as non-null param:
buildTree (tempbrd, ...)
A possibly null pointer is passed as a parameter corresponding to a formal

(-nullpass will suppress message)
foo.c(154,23): Storage tempbrd may become null
foo.c(158,23): Passed storage *tempbrd contains 1 undefined field: score
Storage derivable from a parameter, return value or global is not defined.

(-compdef will suppress message)
foo.c: (in function d1win)
foo.c(201,17): Assignment of char to int: win = winner->board[0]
To make char and int types equivalent, use +charint.
foo.c: (in function d2win)
foo.c(211,17): Assignment of char to int: win = winner->board[2]
foo.c: (in function rowwin)
foo.c(223,21): Assignment of char to int: win = winner->board[i]
foo.c: (in function colwin)
foo.c(235,21): Assignment of char to int: win = winner->board[i]
foo.c: (in function wins)
foo.c(243,9): Test expression for if not boolean, type int: win
Test expression type is not boolean or int. (-predboolint will suppress
message)
foo.c(246,9): Test expression for if not boolean, type int: win
foo.c(249,9): Test expression for if not boolean, type int: win
foo.c(252,9): Test expression for if not boolean, type int: win
foo.c(58,17): Function exported but not used outside foo: buildTree
A declaration is exported, but not used outside this module. Declaration can
use static qualifier. (-exportlocal will suppress message)
foo.c(161,1): Definition of buildTree
foo.c(59,17): Function exported but not used outside foo: turnplayer
foo.c(171,1): Definition of turnplayer
foo.c(195,17): Function exported but not used outside foo: d1win
foo.c(203,1): Definition of d1win
foo.c(205,17): Function exported but
...

Wed, 24 Sep 2003 05:32:57 GMT
URGENT HELP WITH TREES and recursion

Quote:
> hello! my name is Donaji Trejo I have to do an tic tac toe the point is to
> do a recursive function to create all kind of posible boards. We do this in
> a tree.. first we create a blank board that has nothing but spaces in it.
> that's the root board.. we pas that to the recursive function (buildtree)
> then we create 9 children boards.. with one x in each board.. and then we
> make another 9 children for that 9 boards adding the 'o' . i can't get it to
> work. the recursion my code gets the first child of the root and then the 9
> childs using all the available convinations for "X' and "o' but then i'm
> stuck i don't know how to tell the function to keep doing it until the game
> is over or the board is full any ideas this is my code

Consider a 3 by 3 tic tac toe game.
Assign each place on the board a number. for e.g.,

1|2|3
--+-+--
4|5|6
--+-+--
7|8|9

To generate all possible boards turns out to be equvalent to
do permutation on the 9 digitals.
There are totally 9!=362880 permutations.

For example,

952173846 correspond to put x on place 9, then put o on place 5,
then x on place 2,... and so on.

Of course, for some permutation, we may not play the game untill the
last step since the winner has appeared before it.

You need to write a permutation function.
(It should be found in many books.)
Also you need to write a function to determine who wins the game.

paiyi

Wed, 24 Sep 2003 15:59:59 GMT
URGENT HELP WITH TREES and recursion

Quote:

>> hello! my name is Donaji Trejo I have to do an tic tac toe the point is to
>> do a recursive function to create all kind of posible boards. We do this in
>> a tree.. first we create a blank board that has nothing but spaces in it.
>> that's the root board.. we pas that to the recursive function (buildtree)
>> then we create 9 children boards.. with one x in each board.. and then we
>> make another 9 children for that 9 boards adding the 'o' . i can't get it to
>> work. the recursion my code gets the first child of the root and then the 9
>> childs using all the available convinations for "X' and "o' but then i'm
>> stuck i don't know how to tell the function to keep doing it until the game
>> is over or the board is full any ideas this is my code

>Consider a 3 by 3 tic tac toe game.
>Assign each place on the board a number. for e.g.,

>  1|2|3
> --+-+--
>  4|5|6
> --+-+--
>  7|8|9

>To generate all possible boards turns out to be equvalent to
>do permutation on the 9 digitals.
>There are totally 9!=362880 permutations.

>For example,

>  952173846 correspond to put x on place 9, then put o on place 5,
>then x on place 2,... and so on.

Don't you think it's irrelevant how a constellation originated if we're
simply want all boards? I think 1234 and 3412 should be the same board.
That would make less than 3^9 = 19683 possibilities.

Quote:
>Of course, for some permutation, we may not play the game untill the
>last step since the winner has appeared before it.

This still applies.

Stefan

Thu, 25 Sep 2003 00:04:33 GMT
URGENT HELP WITH TREES and recursion

Quote:

> >Consider a 3 by 3 tic tac toe game.
> >Assign each place on the board a number. for e.g.,

> >  1|2|3
> > --+-+--
> >  4|5|6
> > --+-+--
> >  7|8|9

> >To generate all possible boards turns out to be equvalent to
> >do permutation on the 9 digitals.
> >There are totally 9!=362880 permutations.

> >For example,

> >  952173846 correspond to put x on place 9, then put o on place 5,
> >then x on place 2,... and so on.

> Don't you think it's irrelevant how a constellation originated if we're
> simply want all boards? I think 1234 and 3412 should be the same board.
> That would make less than 3^9 = 19683 possibilities.

It depends on the point of view.
1234 means first player puts x on 1, then sencond player puts o on 2
, then first player puts x on 3. then 2nd one puts o on 4.

There exists the ORDER in this game.

If you change the order, the winner will change.
The game is stop when there is a winner or there is no more step to play.
for e.g., for the case, 14253... the 'x' wins the game at 5 step.
It's not necessary to continue to FINISH the whole permutation.
That is, for 14253dddd, the permutations of the 4 digits dddd is not
necessary. (Because we know who wins the game).

Maybe you mean the 14352, 24153, 24315,.....etc. 'x' wins the game with
the SAME board.
Well, it depends on the point of view. :)
paiyi

- Show quoted text -

Quote:
> >Of course, for some permutation, we may not play the game untill the
> >last step since the winner has appeared before it.
> This still applies.
> Stefan

Thu, 25 Sep 2003 04:26:10 GMT

 Page 1 of 1 [ 6 post ]

Relevant Pages