From 918a098aae4994b52ceda1bc1c3a7113271705e2 Mon Sep 17 00:00:00 2001 From: simon Date: Thu, 24 Feb 2011 19:06:49 +0000 Subject: [PATCH] Another patch from Chris Moore implementing two more grid types, both involving dodecagons. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@9109 cda61777-01e9-0310-a592-d414129be87e --- grid.c | 173 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ grid.h | 4 +- loopy.c | 31 +++++++++--- 3 files changed, 199 insertions(+), 9 deletions(-) diff --git a/grid.c b/grid.c index 5d59150..1e5fe6f 100644 --- a/grid.c +++ b/grid.c @@ -1381,4 +1381,177 @@ grid *grid_new_floret(int width, int height) return g; } +grid *grid_new_dodecagonal(int width, int height) +{ + int x, y; + /* Vector for side of triangle - ratio is close to sqrt(3) */ + int a = 15; + int b = 26; + + /* Upper bounds - don't have to be exact */ + int max_faces = 3 * width * height; + int max_dots = 14 * width * height; + + tree234 *points; + + grid *g = grid_new(); + g->tilesize = b; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* centre of dodecagon */ + int px = (4*a + 2*b) * x; + int py = (3*a + 2*b) * y; + if (y % 2) + px += 2*a + b; + + /* dodecagon */ + grid_face_add_new(g, 12); + d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5); + d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6); + d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7); + d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8); + d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9); + d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10); + d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11); + + /* triangle below dodecagon */ + if ((y < height - 1 && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2)))) { + grid_face_add_new(g, 3); + d = grid_get_dot(g, points, px + a, py + (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px , py + (2*a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - a, py + (2*a + b)); grid_face_set_dot(g, d, 2); + } + + /* triangle above dodecagon */ + if ((y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2)))) { + grid_face_add_new(g, 3); + d = grid_get_dot(g, points, px - a, py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px , py - (2*a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + a, py - (2*a + b)); grid_face_set_dot(g, d, 2); + } + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +grid *grid_new_greatdodecagonal(int width, int height) +{ + int x, y; + /* Vector for side of triangle - ratio is close to sqrt(3) */ + int a = 15; + int b = 26; + + /* Upper bounds - don't have to be exact */ + int max_faces = 30 * width * height; + int max_dots = 200 * width * height; + + tree234 *points; + + grid *g = grid_new(); + g->tilesize = b; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* centre of dodecagon */ + int px = (6*a + 2*b) * x; + int py = (3*a + 3*b) * y; + if (y % 2) + px += 3*a + b; + + /* dodecagon */ + grid_face_add_new(g, 12); + d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5); + d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6); + d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7); + d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8); + d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9); + d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10); + d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11); + + /* hexagon below dodecagon */ + if (y < height - 1 && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) { + grid_face_add_new(g, 6); + d = grid_get_dot(g, points, px + a, py + (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + 2*a, py + (2*a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + a, py + (2*a + 3*b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - a, py + (2*a + 3*b)); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px - 2*a, py + (2*a + 2*b)); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px - a, py + (2*a + b)); grid_face_set_dot(g, d, 5); + } + + /* hexagon above dodecagon */ + if (y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) { + grid_face_add_new(g, 6); + d = grid_get_dot(g, points, px - a, py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px - 2*a, py - (2*a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - a, py - (2*a + 3*b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + a, py - (2*a + 3*b)); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + 2*a, py - (2*a + 2*b)); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px + a, py - (2*a + b)); grid_face_set_dot(g, d, 5); + } + + /* square on right of dodecagon */ + if (x < width - 1) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px + 2*a + b, py - a); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + 4*a + b, py - a); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + 4*a + b, py + a); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + 2*a + b, py + a); grid_face_set_dot(g, d, 3); + } + + /* square on top right of dodecagon */ + if (y && (x < width - 1 || !(y % 2))) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + (2*a ), py - (2*a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (2*a + b), py - ( a + 2*b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 3); + } + + /* square on top left of dodecagon */ + if (y && (x || (y % 2))) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px - (2*a + b), py - ( a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - (2*a ), py - (2*a + 2*b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 3); + } + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + /* ----------- End of grid generators ------------- */ diff --git a/grid.h b/grid.h index 00bc7b4..9adf3a9 100644 --- a/grid.h +++ b/grid.h @@ -80,8 +80,10 @@ grid *grid_new_snubsquare(int width, int height); grid *grid_new_cairo(int width, int height); grid *grid_new_greathexagonal(int width, int height); grid *grid_new_octagonal(int width, int height); -grid *grid_new_floret(int width, int height); grid *grid_new_kites(int width, int height); +grid *grid_new_floret(int width, int height); +grid *grid_new_dodecagonal(int width, int height); +grid *grid_new_greatdodecagonal(int width, int height); void grid_free(grid *g); diff --git a/loopy.c b/loopy.c index 07f17a9..0a03cf4 100644 --- a/loopy.c +++ b/loopy.c @@ -254,7 +254,9 @@ static void check_caches(const solver_state* sstate); A(Great-Hexagonal,grid_new_greathexagonal,3,3) \ A(Octagonal,grid_new_octagonal,3,3) \ A(Kites,grid_new_kites,3,3) \ - A(Floret,grid_new_floret,1,2) + A(Floret,grid_new_floret,1,2) \ + A(Dodecagonal,grid_new_dodecagonal,2,2) \ + A(Great-Dodecagonal,grid_new_greatdodecagonal,2,2) #define GRID_NAME(title,fn,amin,omin) #title, #define GRID_CONFIG(title,fn,amin,omin) ":" #title @@ -301,7 +303,7 @@ static void params_generate_grid(game_params *params) ((field) &= ~(1<<(bit)), TRUE) : FALSE) #define CLUE2CHAR(c) \ - ((c < 0) ? ' ' : c + '0') + ((c < 0) ? ' ' : c < 10 ? c + '0' : c - 10 + 'A') /* ---------------------------------------------------------------------- * General struct manipulation and other straightforward code @@ -506,6 +508,8 @@ static const game_params presets[] = { { 5, 5, DIFF_HARD, 6, NULL }, { 5, 5, DIFF_HARD, 7, NULL }, { 3, 3, DIFF_HARD, 8, NULL }, + { 3, 3, DIFF_HARD, 9, NULL }, + { 3, 3, DIFF_HARD, 10, NULL }, #else { 7, 7, DIFF_EASY, 0, NULL }, { 10, 10, DIFF_EASY, 0, NULL }, @@ -521,6 +525,8 @@ static const game_params presets[] = { { 7, 7, DIFF_HARD, 6, NULL }, { 5, 5, DIFF_HARD, 7, NULL }, { 5, 5, DIFF_HARD, 8, NULL }, + { 5, 4, DIFF_HARD, 9, NULL }, + { 5, 4, DIFF_HARD, 10, NULL }, #endif }; @@ -705,7 +711,7 @@ static char *validate_desc(game_params *params, char *desc) g = params->game_grid; for (; *desc; ++desc) { - if (*desc >= '0' && *desc <= '9') { + if ((*desc >= '0' && *desc <= '9') || (*desc >= 'A' && *desc <= 'Z')) { count++; continue; } @@ -1822,6 +1828,7 @@ static char *new_game_desc(game_params *params, random_state *rs, grid *g; game_state *state = snew(game_state); game_state *state_new; + int count = 0; params_generate_grid(params); state->game_grid = g = params->game_grid; g->refcount++; @@ -1843,6 +1850,7 @@ static char *new_game_desc(game_params *params, random_state *rs, * preventing games smaller than 4x4 seems to stop this happening */ do { add_full_clues(state, rs); + if (++count%100 == 0) printf("tried %d times to make a unique board\n", count); } while (!game_has_unique_soln(state, params->diff)); state_new = remove_clues(state, rs, params->diff); @@ -1871,7 +1879,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) int i; game_state *state = snew(game_state); int empties_to_make = 0; - int n; + int n,n2; const char *dp = desc; grid *g; int num_faces, num_edges; @@ -1899,8 +1907,11 @@ static game_state *new_game(midend *me, game_params *params, char *desc) assert(*dp); n = *dp - '0'; + n2 = *dp - 'A' + 10; if (n >= 0 && n < 10) { state->clues[i] = n; + } else if (n2 >= 10 && n2 < 36) { + state->clues[i] = n2; } else { n = *dp - 'a' + 1; assert(n > 0); @@ -2534,7 +2545,7 @@ static int dline_deductions(solver_state *sstate) * on that. We check this with an assertion, in case someone decides to * make a grid which has larger faces than this. Note, this algorithm * could get quite expensive if there are many large faces. */ -#define MAX_FACE_SIZE 8 +#define MAX_FACE_SIZE 12 for (i = 0; i < g->num_faces; i++) { int maxs[MAX_FACE_SIZE][MAX_FACE_SIZE]; @@ -3356,10 +3367,14 @@ static void game_redraw_clue(drawing *dr, game_drawstate *ds, grid *g = state->game_grid; grid_face *f = g->faces + i; int x, y; - char c[2]; + char c[3]; - c[0] = CLUE2CHAR(state->clues[i]); - c[1] = '\0'; + if (state->clues[i] < 10) { + c[0] = CLUE2CHAR(state->clues[i]); + c[1] = '\0'; + } else { + sprintf(c, "%d", state->clues[i]); + } face_text_pos(ds, g, f, &x, &y); draw_text(dr, x, y, -- 2.11.0