/************************************************************ bridgen.c Generate a random hashi puzzle of specified size. */ #include #include #include #include #define MAX_ROW 100 #define MAX_COL 100 #define MAX_HUB 500 #define MAX_BRIDGE 1000 #define NONE -1 #define HORIZONTAL 0 #define VERTICAL 1 #define FALSE 0 #define TRUE 1 #define EAST 0 #define NORTH 1 #define WEST 2 #define SOUTH 3 //#define SPROUT #define SPARSE //#define TREE /************************************************************ Print the input map in character format. */ void print_map( int nrow, int ncol, int map[MAX_ROW][MAX_COL] ) { int r,c; for( r=0; r < nrow; r++ ) { for( c=0; c < ncol; c++ ) { if( map[r][c] > 0 ) { if( map[r][c] > 9 ) { putchar( map[r][c] + 'a' - 10 ); } else { putchar( '0' + map[r][c] ); } } else { putchar('.'); } } putchar('\n'); } } /************************************************************ Return TRUE if location (r,c) is next to an existing island. */ int island_neighbor( int r, int c, int nrow, int ncol, int map[MAX_ROW][MAX_COL] ) { if( ( c < ncol-1 && map[r][c+1] > 0 ) ||( r > 0 && map[r-1][c] > 0 ) ||( c > 0 && map[r][c-1] > 0 ) ||( r < nrow-1 && map[r+1][c] > 0 )) { return( TRUE ); } else { return( FALSE ); } } /************************************************************ Find a random start and end location and add a new bridge. */ int add_bridge( int map_empty, int nrow, int ncol, int max_plank, int map[MAX_ROW][MAX_COL], int dirn[MAX_ROW][MAX_COL], int nplank[MAX_ROW][MAX_COL] ) { int num_plank; int r0,c0,r1,c1; int r,c; if( map_empty == TRUE ) { // this will be the first bridge r = random() % nrow; c = random() % ncol; } else { // look for an existing island or bridge which can // be used as the starting point for a new bridge do { r = random() % nrow; c = random() % ncol; #ifdef SPROUT } while( map[r][c] == 0 ); #else } while( dirn[r][c] == NONE && map[r][c] == 0 ); #endif if( island_neighbor(r,c,nrow,ncol,map)) { return( FALSE ); } } // choose number of planks num_plank = 1 + ( random() % max_plank ); // choose direction and end location for new bridge switch( random() % 4 ) { case EAST: c0 = c; r0 = r1 = r; c = c0+1; while( c < ncol-1 && dirn[r][c] == NONE && map[r][c] == 0 ) { c++; } #ifdef SPARSE if( dirn[r][c] != NONE ) { c--; } #else #ifdef TREE c--; #endif #endif if( c < c0+2 ) { // too short return( FALSE ); } c1 = c0 + 2 + (random() % ( c - c0 - 1 )); if( island_neighbor(r1,c1,nrow,ncol,map)) { return( FALSE ); } for( c = c0+1; c < c1; c++ ) { dirn[r][c] = HORIZONTAL; nplank[r][c] = num_plank; } break; case NORTH: c0 = c1 = c; r1 = r; r = r1-1; while( r > 0 && dirn[r][c] == NONE && map[r][c] == 0 ) { r--; } #ifdef SPARSE if( dirn[r][c] != NONE ) { r++; } #else #ifdef TREE r++; #endif #endif if( r > r1-2 ) { return( FALSE ); } r0 = r1 - 2 - (random() % ( r1 - r - 1 )); if( island_neighbor(r0,c0,nrow,ncol,map)) { return( FALSE ); } for( r = r0+1; r < r1; r++ ) { dirn[r][c] = VERTICAL; nplank[r][c] = num_plank; } break; case WEST: c1 = c; r0 = r1 = r; c = c1-1; while( c > 0 && dirn[r][c] == NONE && map[r][c] == 0 ) { c--; } #ifdef SPARSE if( dirn[r][c] != NONE ) { c++; } #else #ifdef TREE c++; #endif #endif if( c > c1-2 ) { return( FALSE ); } c0 = c1 - 2 - (random() % ( c1 - c - 1 )); if( island_neighbor(r0,c0,nrow,ncol,map)) { return( FALSE ); } for( c = c0+1; c < c1; c++ ) { dirn[r][c] = HORIZONTAL; nplank[r][c] = num_plank; } break; case SOUTH: c0 = c1 = c; r0 = r; r = r0+1; while( r < nrow-1 && dirn[r][c] == NONE && map[r][c] == 0 ) { r++; } #ifdef SPARSE if( dirn[r][c] != NONE ) { r--; } #else #ifdef TREE r--; #endif #endif if( r < r0+2 ) { return( FALSE ); } r1 = r0 + 2 + (random() % ( r - r0 - 1 )); if( island_neighbor(r1,c1,nrow,ncol,map)) { return( FALSE ); } for( r = r0+1; r < r1; r++ ) { dirn[r][c] = VERTICAL; nplank[r][c] = num_plank; } break; } // re-compute number of planks at start of new bridge nplank[r0][c0] = 0; map[r0][c0] = 0; if( c0 < ncol-1 && dirn[r0][c0+1] == HORIZONTAL ) map[r0][c0] += nplank[r0][c0+1]; if( r0 > 0 && dirn[r0-1][c0] == VERTICAL ) map[r0][c0] += nplank[r0-1][c0]; if( c0 > 0 && dirn[r0][c0-1] == HORIZONTAL ) map[r0][c0] += nplank[r0][c0-1]; if( r0 < nrow-1 && dirn[r0+1][c0] == VERTICAL ) map[r0][c0] += nplank[r0+1][c0]; // re-compute number of planks at end of new bridge nplank[r1][c1] = 0; map[r1][c1] = 0; if( c1 < ncol-1 && dirn[r1][c1+1] == HORIZONTAL ) map[r1][c1] += nplank[r1][c1+1]; if( r1 > 0 && dirn[r1-1][c1] == VERTICAL ) map[r1][c1] += nplank[r1-1][c1]; if( c1 > 0 && dirn[r1][c1-1] == HORIZONTAL ) map[r1][c1] += nplank[r1][c1-1]; if( r1 < nrow-1 && dirn[r1+1][c1] == VERTICAL ) map[r1][c1] += nplank[r1+1][c1]; return( TRUE ); } int main( int argc, char *argv[] ) { int map[MAX_ROW][MAX_COL]; // islands int dirn[MAX_ROW][MAX_COL]; // NONE, HORIZONTAL or VERTICAL int nplank[MAX_ROW][MAX_COL]; int max_plank = 3; int nrow, ncol; int nfail; int r,c; if( argc < 2 || !isdigit(argv[1][0])) { printf("Usage: %s [ncol]\n",argv[0]); printf("Generate a random Hashi puzzle of size nrow x ncol;\n"); printf("can be run repeatedly, producing different puzzles each time;\n"); printf("ncol defaults to nrow.\n"); return 0; } else { nrow = atoi(argv[1]); } if( nrow < 3 ) { nrow = 3; } if( nrow > MAX_ROW ) { nrow = MAX_ROW; } if( argc < 3 ) { ncol = nrow; } else { ncol = atoi(argv[2]); } if( ncol < 3 ) { ncol = 3; } if( ncol > MAX_COL ) { ncol = MAX_COL; } srandom(time(NULL)); for( r=0; r < nrow; r++ ) { for( c=0; c < ncol; c++ ) { map[r][c] = 0; nplank[r][c] = 0; dirn[r][c] = NONE; } } // add the first bridge while( !add_bridge( TRUE, nrow, ncol, max_plank, map, dirn, nplank )) ; // keep adding bridges until it becomes too difficult nfail = 0; while( nfail < 200 ) { nfail=0; while( nfail < 200 && !add_bridge( FALSE, nrow, ncol, max_plank, map, dirn, nplank )) { nfail++; } } print_map( nrow, ncol, map ); return 0; }