Dynamic Programming for board game in C

board_game.c

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

//#define DEBUGVV
//#define DEBUGV
//#define DEBUG
#define WAIT 500000

typedef struct {
	unsigned int seqs;
	unsigned int seq[32];
} memo_t;

memo_t* memo;
unsigned int memos = 0;
unsigned int hits = 0;

void print(int cols, char board[][256]){
	int i,j;
	for(i=0;i<cols;i++){
		for(j=0;j<cols;j++){
			printf("%c ",board[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	usleep(WAIT);
}

void make_hole(int cols, int holes, int* hole_idx){
	int i=0, j, h, flag;
	while(i<holes){
		flag = 0;
		h = rand()%(cols*cols);
		for(j=0;j<i;j++){
			if(*(hole_idx+j) == h){
				flag = 1;
				break;
			}
		}
		if(flag){
				continue;
		}
		*(hole_idx+i) = h;
		i++;
	}
}

void make_hole_manual(int cols, int holes, int* hole_idx, char* argv[]){
	int i;
	for(i=0;i<holes;i++){
		*(hole_idx+1) = atoi(argv[i]);
	}
}

void init_board(int cols, char board[][256]){
	int i,j;
	for(i=0;i<cols;i++){
		for(j=0;j<cols;j++){
			board[i][j] = '_';
		}
	}
}

void build_hole(int cols, int holes, int* hole_idx, char board[][256]){
	int i,h,x,y;
	for(i=0;i<holes;i++){
		h = *(hole_idx+i);
		x = h/cols;
		y = h%cols;
		board[x][y] = '+';
	}
}

void make_board(int cols, int holes, char board[][256],int* hole_idx){
	int i,j,h,x,y;

	init_board(cols,board);
	build_hole(cols,holes,hole_idx,board);
	print(cols,board);
}

void make_memo_entry(int cols, char board[][256], memo_t* entry){
	int i,j;
	unsigned int n = 0;
	entry->seqs = 0;
	char flag = 'N'; // Null, Occupy, Empty
	for(i=0;i<cols;i++){
		for(j=0;j<cols;j++){
			if( board[i][j]=='<' ||
				board[i][j]=='>' ||
				board[i][j]=='^' ||
				board[i][j]=='v' )
			{
				if(flag == 'E'){
					entry->seq[(entry->seqs)++] = n;
					n = 0;
				}
				flag = 'O';
				n++;
			}else if( board[i][j]=='+' ){
				n++;
			}else{
				if(flag == 'O'){
					entry->seq[(entry->seqs)++] = n;
					n = 0;
				}
				flag = 'E';
				n++;
			}
		}
	}
}

void print_memo_entry(int cols, memo_t* entry){
	int f,i,j,k;
	k=0;
	f=1;
	for(i=0;i<entry->seqs;i++){
		for(j=0;j<entry->seq[i];j++){
			if(k%cols==0)
				printf("\n");
			k++;
			if(f==1){
				printf("X ");
			}else{
				printf("_ ");
			}
		}
		if(f==0){
			f=1;
		}else{
			f=0;
		}
	}
	printf("\n\n");
}

int check_memo(int cols, char board[][256]){
	int m,i,f;
	if(memos==0)
		return 0;

	memo_t* entry = (memo_t*)malloc(sizeof(memo_t));
	make_memo_entry(cols,board,entry);

#ifdef DEBUGVV
	printf("====================\n");
	printf("Current board.\n");
	print_memo_entry(cols,entry);
#endif

	for(m=0;m<memos;m++){

#ifdef DEBUGVV
		printf("Memo board %d.\n",m);
		print_memo_entry(cols,memo+m);
#endif

		if((memo+m)->seqs != entry->seqs){
			continue;
		}else{
			f=0;
			for(i=0;i<entry->seqs;i++){
				if( (memo+m)->seq[i] != entry->seq[i] ){
					f=1;
					break;
				}
			}
			if(f==0)
				return 1;
		}
	}
#ifdef DEBUGVV
	printf("====================\n");
#endif
	return 0;
}

void append_entry(int cols, memo_t* entry){
#ifdef DEBUGV
	print_memo_entry(cols, entry);
#endif
	memcpy(memo+memos,entry,sizeof(memo_t));
	memos++;
}

int check_redundancy(memo_t* entry){
	int i,j,f;
	for(i=0;i<memos;i++){
		if((memo+i)->seqs!=entry->seqs)
			continue;

		f=0;
		for(j=0;j<(memo+i)->seqs;j++){
			if(entry->seq[j]!=(memo+i)->seq[j]){
				f=1;
				break;
			}
		}
		if(f)
			continue;

		return 1;
	}
	return 0;
}

void make_memo(int cols, char board[][256]){
	int i,j,n,k;
	n=k=0;
	memo_t* entry = (memo_t*)malloc(sizeof(memo_t));
	make_memo_entry(cols, board, entry);
	if(!check_redundancy(entry))
		append_entry(cols,entry);
}

int complete(int cols, char board[][256]){
	int i,j;
	for(i=0;i<cols;i++){
		for(j=0;j<cols;j++){
			if(board[i][j]=='_'){
				return 0;
			}
		}
	}
	return 1;
}

void print_memo(){
	int m,i;
	if(memos==0){
		printf("No memo.\n");
		return;
	}
	for(m=0;m<memos;m++){
		for(i=0;i<(memo+m)->seqs;i++){
			printf("%d ",(memo+m)->seq[i]);
		}
		printf("\n");
	}
}

int domino(int i, int j, int cols, char board[][256], int cnt){
	if(check_memo(cols,board)){
#ifdef DEBUG
		printf("Hit memo.\n\n");
#endif
		hits++;
		return 0;
	}

	if(cols<=j){
		j=0;
		i++;
	}
	if(cols<=i){
		return complete(cols,board);
	}

	if(board[i][j]=='_'){

#ifdef DEBUG
		print(cols,board);
#endif

		if(i+1<cols && board[i+1][j]=='_'){
			board[i][j] = '^';
			board[i+1][j] = 'v';
			if(domino(i,j+1,cols,board,cnt+1)){
				return 1;
			}else{
				make_memo(cols,board);
				board[i][j] = '_';
				board[i+1][j] = '_';
			}
		}

		if(j+1<cols && board[i][j+1]=='_'){
			board[i][j] = '<';
			board[i][j+1] = '>';
			if(domino(i,j+2,cols,board,cnt+1)){
				return 1;
			}else{
				make_memo(cols,board);
				board[i][j] = '_';
				board[i][j+1] = '_';
			}
		}

		return 0;
	}

	return domino(i,j+1,cols,board,cnt+1);
}

int main(int argc, char* argv[]){
	srand((unsigned)time(NULL));

	int cols = atoi(argv[1]);

	char board[256][256] = {0};
	int holes = (rand()%((cols*cols/2)/2)+1)*2;

	int* hole_idx = malloc(sizeof(int)*holes);
	if(argc > 2){
		int holes = atoi(argv[2]);
		make_hole_manual(cols,holes,hole_idx,(argv+2));
	}else{
		make_hole(cols,holes,hole_idx);
	}

	printf("%d x %d : # of holes(+) = %d\n",cols,cols,holes);
	memo = (memo_t*)malloc(sizeof(memo_t)*cols*cols);
	make_board(cols,holes,board,hole_idx);

	if(domino(0,0,cols,board,1)){
		printf("Completed. (# of hits = %d)\n",hits);
		print(cols,board);
	}else{
		printf("Not completed... (# of hits = %d)\n\n",hits);
	}

	return 0;

}