This post is about just one interesting thing that I did in the last week. Some days ago, I had posted about quzzle (for some strange reason I called it Quazzle in that post). On of my colleague (hes a real brain.. THE best programmer I personally know) wrote a program to solve it in just an hour. That inspired me to give it a try. It took me almost three days to get it right. But atlast here it is. It was fun. I had to solve many problems in doing that. It was cool and kept me busy for some days. And in the end its VERY VERY satisfying. :). It also reminded me that I have a looong way to go before I call myself a good programmer. I am sure this one is also not very optimized.
Heres the thing: (If you are a programmer, please review and suggest improvements)
#include
#define TRUE 0
#define FALSE 1
#define UP 1
#define DOWN 2
#define RIGHT 3
#define LEFT 4
#define MAXDEPTH 116
typedef int state[10];
struct moves {
int block;
int direction;
};
struct old_states {
state saved_state;
int depth;
struct old_states *next_state;
};
struct old_states *states = NULL;
int depth = 0;
void free_old_states()
{
struct old_states *tmp_st, *new_st;
if(!states)
return;
if(!states->next_state){
free(states);
return;
}
for(tmp_st = states, new_st = states->next_state; tmp_st;
new_st = tmp_st->next_state, tmp_st = new_st){
free(tmp_st);
}
return;
}
int get_valid_moves(state st, struct moves *move)
{
int i, move_count = 0;
for(i = 0; i <= 8; i++){
if(((((st[i] | st[i] >> 4) ^ st[i]) & st[9]) ==
((st[i] | st[i] >> 4) ^ st[i])) && !(st[i] & 0xf)){
move[move_count].block = i;
move[move_count].direction = UP;
move_count++;
}
if(((((st[i] | st[i] << 4) ^ st[i]) & st[9]) ==
((st[i] | st[i] << 4) ^ st[i])) && !(st[i] & 0xf0000)){
move[move_count].block = i;
move[move_count].direction = DOWN;
move_count++;
}
if(((((st[i] | st[i] >> 1) ^ st[i]) & st[9]) ==
((st[i] | st[i] >> 1) ^ st[i])) && !(st[i] & 0x11111)){
move[move_count].block = i;
move[move_count].direction = RIGHT;
move_count++;
}
if(((((st[i] | st[i] << 1) ^ st[i]) & st[9]) ==
((st[i] | st[i] << 1) ^ st[i])) && !(st[i] & 0x88888)){
move[move_count].block = i;
move[move_count].direction = LEFT;
move_count++;
}
}
return move_count;
}
void add_state(state st)
{
struct old_states *new_st;
new_st = (struct old_states *)malloc(sizeof(struct old_states));
new_st->next_state = states;
new_st->depth = depth;
memcpy(&new_st->saved_state, st, sizeof(state));
states = new_st;
}
int is_old_state(state st)
{
struct old_states *tmp_st, *new_st;
for(tmp_st = states; tmp_st; tmp_st = tmp_st->next_state){
if(memcmp(&tmp_st->saved_state, st, sizeof(state)) == 0){
if(tmp_st->depth <= depth){
return TRUE;
} else {
tmp_st->depth = depth;
return FALSE;
}
}
}
add_state(st);
return FALSE;
}
void make_move(state st, struct moves *move, state *new_state)
{
int new_bits, old_bits;
int i = move->block;
memcpy(*new_state, st, sizeof(state));
switch(move->direction){
case UP:
new_bits = (st[i] | st[i] >> 4) ^ st[i];
old_bits = (st[i] | st[i] >> 4) ^ (st[i] >> 4);
(*new_state)[i] = (*new_state)[i] >> 4;
break;
case DOWN:
new_bits =(st[i] | st[i] << 4) ^ st[i];
old_bits = (st[i] | st[i] << 4) ^ (st[i] << 4);
(*new_state)[i] = (*new_state)[i] << 4;
break;
case LEFT:
new_bits =(st[i] | st[i] << 1) ^ st[i];
old_bits = (st[i] | st[i] << 1) ^ (st[i] << 1);
(*new_state)[i] = (*new_state)[i] << 1;
break;
case RIGHT:
new_bits =(st[i] | st[i] >> 1) ^ st[i];
old_bits = (st[i] | st[i] >> 1) ^ (st[i] >> 1);
(*new_state)[i] = (*new_state)[i] >> 1;
break;
}
(*new_state)[9] ^= new_bits;
(*new_state)[9] |= old_bits;
return;
}
int is_final(state st)
{
if(st[0] == 0x00033)
return TRUE;
return FALSE;
}
void print_move(struct moves *move)
{
printf("%d)move is %d to ", depth, move->block, move->direction);
switch(move->direction){
case UP: printf("UP\n"); break;
case DOWN: printf("DOWN\n"); break;
case LEFT: printf("LEFT\n"); break;
case RIGHT: printf("RIGHT\n"); break;
}
}
int solve(state st)
{
state new_state;
int moves, i;
struct moves move[36];
if(is_final(st) == TRUE){
return TRUE;
}
depth++;
if(depth >= MAXDEPTH){
depth--;
return FALSE;
}
if(is_old_state(st) == TRUE){
depth--;
return FALSE;
}
moves = get_valid_moves(st, &move[0]);
for(i = 0; i < moves; i ++){
make_move(st, &move[i], &new_state);
if(solve(new_state) == TRUE){
print_move(&move[i]);
depth--;
return TRUE;
}
}
depth--;
return FALSE;
}
int main()
{
state init_state;
init_state[0] = 0x000cc;
init_state[1] = 0x00003;
init_state[2] = 0x00220;
init_state[3] = 0x00110;
init_state[4] = 0x88000;
init_state[5] = 0x06000;
init_state[6] = 0x01000;
init_state[7] = 0x60000;
init_state[8] = 0x10000;
init_state[9] = 0x00c00;
if(solve(&init_state[0]) == TRUE)
printf("solved\n");
free_old_states();
return 0;
}
Yours Sinerely,
