summaryrefslogtreecommitdiff
path: root/apps/plugins/puzzles/src
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/puzzles/src')
-rw-r--r--apps/plugins/puzzles/src/LICENCE4
-rw-r--r--apps/plugins/puzzles/src/gamedesc.txt39
-rw-r--r--apps/plugins/puzzles/src/grid.c2
-rw-r--r--apps/plugins/puzzles/src/gtk.c753
-rw-r--r--apps/plugins/puzzles/src/keen.c88
-rw-r--r--apps/plugins/puzzles/src/latin.c39
-rw-r--r--apps/plugins/puzzles/src/latin.h9
-rw-r--r--apps/plugins/puzzles/src/mines.c2
-rw-r--r--apps/plugins/puzzles/src/pattern.c15
-rw-r--r--apps/plugins/puzzles/src/printing.c280
-rw-r--r--apps/plugins/puzzles/src/ps.c2
-rw-r--r--apps/plugins/puzzles/src/puzzles.but3
-rw-r--r--apps/plugins/puzzles/src/puzzles.h7
-rw-r--r--apps/plugins/puzzles/src/towers.c34
-rw-r--r--apps/plugins/puzzles/src/tracks.R3
-rw-r--r--apps/plugins/puzzles/src/tracks.c451
-rw-r--r--apps/plugins/puzzles/src/twiddle.c11
-rw-r--r--apps/plugins/puzzles/src/unequal.c74
-rw-r--r--apps/plugins/puzzles/src/unfinished/group.c226
-rw-r--r--apps/plugins/puzzles/src/unfinished/path.c97
20 files changed, 1846 insertions, 293 deletions
diff --git a/apps/plugins/puzzles/src/LICENCE b/apps/plugins/puzzles/src/LICENCE
index ce0418e6cc..85f67ba795 100644
--- a/apps/plugins/puzzles/src/LICENCE
+++ b/apps/plugins/puzzles/src/LICENCE
@@ -2,8 +2,8 @@ This software is copyright (c) 2004-2014 Simon Tatham.
2 2
3Portions copyright Richard Boulton, James Harvey, Mike Pinna, Jonas 3Portions copyright Richard Boulton, James Harvey, Mike Pinna, Jonas
4Kölker, Dariusz Olszewski, Michael Schierl, Lambros Lambrou, Bernd 4Kölker, Dariusz Olszewski, Michael Schierl, Lambros Lambrou, Bernd
5Schmidt, Steffen Bauer, Lennard Sprong, Rogier Goossens and Michael 5Schmidt, Steffen Bauer, Lennard Sprong, Rogier Goossens, Michael
6Quevillon. 6Quevillon and Asher Gordon.
7 7
8Permission is hereby granted, free of charge, to any person 8Permission is hereby granted, free of charge, to any person
9obtaining a copy of this software and associated documentation files 9obtaining a copy of this software and associated documentation files
diff --git a/apps/plugins/puzzles/src/gamedesc.txt b/apps/plugins/puzzles/src/gamedesc.txt
deleted file mode 100644
index db0d9cbd01..0000000000
--- a/apps/plugins/puzzles/src/gamedesc.txt
+++ /dev/null
@@ -1,39 +0,0 @@
1blackbox:blackbox.exe:Black Box:Ball-finding puzzle:Find the hidden balls in the box by bouncing laser beams off them.
2bridges:bridges.exe:Bridges:Bridge-placing puzzle:Connect all the islands with a network of bridges.
3cube:cube.exe:Cube:Rolling cube puzzle:Pick up all the blue squares by rolling the cube over them.
4dominosa:dominosa.exe:Dominosa:Domino tiling puzzle:Tile the rectangle with a full set of dominoes.
5fifteen:fifteen.exe:Fifteen:Sliding block puzzle:Slide the tiles around to arrange them into order.
6filling:filling.exe:Filling:Polyomino puzzle:Mark every square with the area of its containing region.
7flip:flip.exe:Flip:Tile inversion puzzle:Flip groups of squares to light them all up at once.
8flood:flood.exe:Flood:Flood-filling puzzle:Turn the grid the same colour in as few flood fills as possible.
9galaxies:galaxies.exe:Galaxies:Symmetric polyomino puzzle:Divide the grid into rotationally symmetric regions each centred on a dot.
10guess:guess.exe:Guess:Combination-guessing puzzle:Guess the hidden combination of colours.
11inertia:inertia.exe:Inertia:Gem-collecting puzzle:Collect all the gems without running into any of the mines.
12keen:keen.exe:Keen:Arithmetic Latin square puzzle:Complete the latin square in accordance with the arithmetic clues.
13lightup:lightup.exe:Light Up:Light-bulb placing puzzle:Place bulbs to light up all the squares.
14loopy:loopy.exe:Loopy:Loop-drawing puzzle:Draw a single closed loop, given clues about number of adjacent edges.
15magnets:magnets.exe:Magnets:Magnet-placing puzzle:Place magnets to satisfy the clues and avoid like poles touching.
16map:map.exe:Map:Map-colouring puzzle:Colour the map so that adjacent regions are never the same colour.
17mines:mines.exe:Mines:Mine-finding puzzle:Find all the mines without treading on any of them.
18net:netgame.exe:Net:Network jigsaw puzzle:Rotate each tile to reassemble the network.
19netslide:netslide.exe:Netslide:Toroidal sliding network puzzle:Slide a row at a time to reassemble the network.
20palisade:palisade.exe:Palisade:Grid-division puzzle:Divide the grid into equal-sized areas in accordance with the clues.
21pattern:pattern.exe:Pattern:Pattern puzzle:Fill in the pattern in the grid, given only the lengths of runs of black squares.
22pearl:pearl.exe:Pearl:Loop-drawing puzzle:Draw a single closed loop, given clues about corner and straight squares.
23pegs:pegs.exe:Pegs:Peg solitaire puzzle:Jump pegs over each other to remove all but one.
24range:range.exe:Range:Visible-distance puzzle:Place black squares to limit the visible distance from each numbered cell.
25rect:rect.exe:Rectangles:Rectangles puzzle:Divide the grid into rectangles with areas equal to the numbers.
26samegame:samegame.exe:Same Game:Block-clearing puzzle:Clear the grid by removing touching groups of the same colour squares.
27signpost:signpost.exe:Signpost:Square-connecting puzzle:Connect the squares into a path following the arrows.
28singles:singles.exe:Singles:Number-removing puzzle:Black out the right set of duplicate numbers.
29sixteen:sixteen.exe:Sixteen:Toroidal sliding block puzzle:Slide a row at a time to arrange the tiles into order.
30slant:slant.exe:Slant:Maze-drawing puzzle:Draw a maze of slanting lines that matches the clues.
31solo:solo.exe:Solo:Number placement puzzle:Fill in the grid so that each row, column and square block contains one of every digit.
32tents:tents.exe:Tents:Tent-placing puzzle:Place a tent next to each tree.
33towers:towers.exe:Towers:Tower-placing Latin square puzzle:Complete the latin square of towers in accordance with the clues.
34tracks:tracks.exe:Tracks:Path-finding railway track puzzle:Fill in the railway track according to the clues.
35twiddle:twiddle.exe:Twiddle:Rotational sliding block puzzle:Rotate the tiles around themselves to arrange them into order.
36undead:undead.exe:Undead:Monster-placing puzzle:Place ghosts, vampires and zombies so that the right numbers of them can be seen in mirrors.
37unequal:unequal.exe:Unequal:Latin square puzzle:Complete the latin square in accordance with the > signs.
38unruly:unruly.exe:Unruly:Black and white grid puzzle:Fill in the black and white grid to avoid runs of three.
39untangle:untangle.exe:Untangle:Planar graph layout puzzle:Reposition the points so that the lines do not cross.
diff --git a/apps/plugins/puzzles/src/grid.c b/apps/plugins/puzzles/src/grid.c
index 89bde187be..5ea37439d4 100644
--- a/apps/plugins/puzzles/src/grid.c
+++ b/apps/plugins/puzzles/src/grid.c
@@ -2378,6 +2378,8 @@ static void grid_size_floret(int width, int height,
2378 *tilesize = FLORET_TILESIZE; 2378 *tilesize = FLORET_TILESIZE;
2379 *xextent = (6*px+3*qx)/2 * (width-1) + 4*qx + 2*px; 2379 *xextent = (6*px+3*qx)/2 * (width-1) + 4*qx + 2*px;
2380 *yextent = (5*qy-4*py) * (height-1) + 4*qy + 2*ry; 2380 *yextent = (5*qy-4*py) * (height-1) + 4*qy + 2*ry;
2381 if (height == 1)
2382 *yextent += (5*qy-4*py)/2;
2381} 2383}
2382 2384
2383static grid *grid_new_floret(int width, int height, const char *desc) 2385static grid *grid_new_floret(int width, int height, const char *desc)
diff --git a/apps/plugins/puzzles/src/gtk.c b/apps/plugins/puzzles/src/gtk.c
index d41f8677b9..7588ee0dc6 100644
--- a/apps/plugins/puzzles/src/gtk.c
+++ b/apps/plugins/puzzles/src/gtk.c
@@ -44,6 +44,17 @@
44# endif 44# endif
45#endif 45#endif
46 46
47#if defined USE_CAIRO && GTK_CHECK_VERSION(2,10,0)
48/* We can only use printing if we are using Cairo for drawing and we
49 have a GTK version >= 2.10 (when GtkPrintOperation was added). */
50# define USE_PRINTING
51# if GTK_CHECK_VERSION(2,18,0)
52/* We can embed the page setup. Before 2.18, we needed to have a
53 separate page setup. */
54# define USE_EMBED_PAGE_SETUP
55# endif
56#endif
57
47#if GTK_CHECK_VERSION(3,0,0) 58#if GTK_CHECK_VERSION(3,0,0)
48/* The old names are still more concise! */ 59/* The old names are still more concise! */
49#define gtk_hbox_new(x,y) gtk_box_new(GTK_ORIENTATION_HORIZONTAL,y) 60#define gtk_hbox_new(x,y) gtk_box_new(GTK_ORIENTATION_HORIZONTAL,y)
@@ -132,6 +143,18 @@ struct font {
132}; 143};
133 144
134/* 145/*
146 * An internal API for functions which need to be different for
147 * printing and drawing.
148 */
149struct internal_drawing_api {
150 void (*set_colour)(frontend *fe, int colour);
151#ifdef USE_CAIRO
152 void (*fill)(frontend *fe);
153 void (*fill_preserve)(frontend *fe);
154#endif
155};
156
157/*
135 * This structure holds all the data relevant to a single window. 158 * This structure holds all the data relevant to a single window.
136 * In principle this would allow us to open multiple independent 159 * In principle this would allow us to open multiple independent
137 * puzzle windows, although I can't currently see any real point in 160 * puzzle windows, although I can't currently see any real point in
@@ -180,7 +203,7 @@ struct frontend {
180 GtkWidget *cfgbox; 203 GtkWidget *cfgbox;
181 void *paste_data; 204 void *paste_data;
182 int paste_data_len; 205 int paste_data_len;
183 int pw, ph; /* pixmap size (w, h are area size) */ 206 int pw, ph, ps; /* pixmap size (w, h are area size, s is GDK scale) */
184 int ox, oy; /* offset of pixmap in drawing area */ 207 int ox, oy; /* offset of pixmap in drawing area */
185#ifdef OLD_FILESEL 208#ifdef OLD_FILESEL
186 char *filesel_name; 209 char *filesel_name;
@@ -225,6 +248,23 @@ struct frontend {
225 */ 248 */
226 bool awaiting_resize_ack; 249 bool awaiting_resize_ack;
227#endif 250#endif
251#ifdef USE_CAIRO
252 int printcount, printw, printh;
253 float printscale;
254 bool printsolns, printcolour;
255 int hatch;
256 float hatchthick, hatchspace;
257 drawing *print_dr;
258 document *doc;
259#endif
260#ifdef USE_PRINTING
261 GtkPrintOperation *printop;
262 GtkPrintContext *printcontext;
263 GtkSpinButton *printcount_spin_button, *printw_spin_button,
264 *printh_spin_button, *printscale_spin_button;
265 GtkCheckButton *soln_check_button, *colour_check_button;
266#endif
267 const struct internal_drawing_api *dr_api;
228}; 268};
229 269
230struct blitter { 270struct blitter {
@@ -247,15 +287,19 @@ void get_random_seed(void **randseed, int *randseedsize)
247void frontend_default_colour(frontend *fe, float *output) 287void frontend_default_colour(frontend *fe, float *output)
248{ 288{
249#if !GTK_CHECK_VERSION(3,0,0) 289#if !GTK_CHECK_VERSION(3,0,0)
250 /* 290 if (!fe->headless) {
251 * Use the widget style's default background colour as the 291 /*
252 * background for the puzzle drawing area. 292 * If we have a widget and it has a style that specifies a
253 */ 293 * default background colour, use that as the background for
254 GdkColor col = gtk_widget_get_style(fe->window)->bg[GTK_STATE_NORMAL]; 294 * the puzzle drawing area.
255 output[0] = col.red / 65535.0; 295 */
256 output[1] = col.green / 65535.0; 296 GdkColor col = gtk_widget_get_style(fe->window)->bg[GTK_STATE_NORMAL];
257 output[2] = col.blue / 65535.0; 297 output[0] = col.red / 65535.0;
258#else 298 output[1] = col.green / 65535.0;
299 output[2] = col.blue / 65535.0;
300 }
301#endif
302
259 /* 303 /*
260 * GTK 3 has decided that there's no such thing as a 'default 304 * GTK 3 has decided that there's no such thing as a 'default
261 * background colour' any more, because widget styles might set 305 * background colour' any more, because widget styles might set
@@ -263,9 +307,11 @@ void frontend_default_colour(frontend *fe, float *output)
263 * image. We don't want to get into overlaying our entire puzzle 307 * image. We don't want to get into overlaying our entire puzzle
264 * on an arbitrary background image, so we'll just make up a 308 * on an arbitrary background image, so we'll just make up a
265 * reasonable shade of grey. 309 * reasonable shade of grey.
310 *
311 * This is also what we do on GTK 2 in headless mode, where we
312 * don't have a widget style to query.
266 */ 313 */
267 output[0] = output[1] = output[2] = 0.9F; 314 output[0] = output[1] = output[2] = 0.9F;
268#endif
269} 315}
270 316
271void gtk_status_bar(void *handle, const char *text) 317void gtk_status_bar(void *handle, const char *text)
@@ -290,6 +336,7 @@ void gtk_status_bar(void *handle, const char *text)
290static void setup_drawing(frontend *fe) 336static void setup_drawing(frontend *fe)
291{ 337{
292 fe->cr = cairo_create(fe->image); 338 fe->cr = cairo_create(fe->image);
339 cairo_scale(fe->cr, fe->ps, fe->ps);
293 cairo_set_antialias(fe->cr, CAIRO_ANTIALIAS_GRAY); 340 cairo_set_antialias(fe->cr, CAIRO_ANTIALIAS_GRAY);
294 cairo_set_line_width(fe->cr, 1.0); 341 cairo_set_line_width(fe->cr, 1.0);
295 cairo_set_line_cap(fe->cr, CAIRO_LINE_CAP_SQUARE); 342 cairo_set_line_cap(fe->cr, CAIRO_LINE_CAP_SQUARE);
@@ -321,12 +368,23 @@ static void snaffle_colours(frontend *fe)
321 fe->colours = midend_colours(fe->me, &fe->ncolours); 368 fe->colours = midend_colours(fe->me, &fe->ncolours);
322} 369}
323 370
324static void set_colour(frontend *fe, int colour) 371static void draw_set_colour(frontend *fe, int colour)
325{ 372{
326 cairo_set_source_rgb(fe->cr, 373 cairo_set_source_rgb(fe->cr,
327 fe->colours[3*colour + 0], 374 fe->colours[3*colour + 0],
328 fe->colours[3*colour + 1], 375 fe->colours[3*colour + 1],
329 fe->colours[3*colour + 2]); 376 fe->colours[3*colour + 2]);
377}
378
379static void print_set_colour(frontend *fe, int colour)
380{
381 float r, g, b;
382
383 print_get_colour(fe->print_dr, colour, fe->printcolour,
384 &(fe->hatch), &r, &g, &b);
385
386 if (fe->hatch < 0)
387 cairo_set_source_rgb(fe->cr, r, g, b);
330} 388}
331 389
332static void set_window_background(frontend *fe, int colour) 390static void set_window_background(frontend *fe, int colour)
@@ -395,6 +453,82 @@ static void save_screenshot_png(frontend *fe, const char *screenshot_file)
395 cairo_surface_write_to_png(fe->image, screenshot_file); 453 cairo_surface_write_to_png(fe->image, screenshot_file);
396} 454}
397 455
456static void do_hatch(frontend *fe)
457{
458 double i, x, y, width, height, maxdim;
459
460 /* Get the dimensions of the region to be hatched. */
461 cairo_path_extents(fe->cr, &x, &y, &width, &height);
462
463 maxdim = max(width, height);
464
465 cairo_save(fe->cr);
466
467 /* Set the line color and width. */
468 cairo_set_source_rgb(fe->cr, 0, 0, 0);
469 cairo_set_line_width(fe->cr, fe->hatchthick);
470 /* Clip to the region. */
471 cairo_clip(fe->cr);
472 /* Hatch the bounding area of the fill region. */
473 if (fe->hatch == HATCH_VERT || fe->hatch == HATCH_PLUS) {
474 for (i = 0.0; i <= width; i += fe->hatchspace) {
475 cairo_move_to(fe->cr, i, 0);
476 cairo_rel_line_to(fe->cr, 0, height);
477 }
478 }
479 if (fe->hatch == HATCH_HORIZ || fe->hatch == HATCH_PLUS) {
480 for (i = 0.0; i <= height; i += fe->hatchspace) {
481 cairo_move_to(fe->cr, 0, i);
482 cairo_rel_line_to(fe->cr, width, 0);
483 }
484 }
485 if (fe->hatch == HATCH_SLASH || fe->hatch == HATCH_X) {
486 for (i = -height; i <= width; i += fe->hatchspace * ROOT2) {
487 cairo_move_to(fe->cr, i, 0);
488 cairo_rel_line_to(fe->cr, maxdim, maxdim);
489 }
490 }
491 if (fe->hatch == HATCH_BACKSLASH || fe->hatch == HATCH_X) {
492 for (i = 0.0; i <= width + height; i += fe->hatchspace * ROOT2) {
493 cairo_move_to(fe->cr, i, 0);
494 cairo_rel_line_to(fe->cr, -maxdim, maxdim);
495 }
496 }
497 cairo_stroke(fe->cr);
498
499 cairo_restore(fe->cr);
500}
501
502static void do_draw_fill(frontend *fe)
503{
504 cairo_fill(fe->cr);
505}
506
507static void do_draw_fill_preserve(frontend *fe)
508{
509 cairo_fill_preserve(fe->cr);
510}
511
512static void do_print_fill(frontend *fe)
513{
514 if (fe->hatch < 0)
515 cairo_fill(fe->cr);
516 else
517 do_hatch(fe);
518}
519
520static void do_print_fill_preserve(frontend *fe)
521{
522 if (fe->hatch < 0) {
523 cairo_fill_preserve(fe->cr);
524 } else {
525 cairo_path_t *oldpath;
526 oldpath = cairo_copy_path(fe->cr);
527 do_hatch(fe);
528 cairo_append_path(fe->cr, oldpath);
529 }
530}
531
398static void do_clip(frontend *fe, int x, int y, int w, int h) 532static void do_clip(frontend *fe, int x, int y, int w, int h)
399{ 533{
400 cairo_new_path(fe->cr); 534 cairo_new_path(fe->cr);
@@ -413,7 +547,7 @@ static void do_draw_rect(frontend *fe, int x, int y, int w, int h)
413 cairo_new_path(fe->cr); 547 cairo_new_path(fe->cr);
414 cairo_set_antialias(fe->cr, CAIRO_ANTIALIAS_NONE); 548 cairo_set_antialias(fe->cr, CAIRO_ANTIALIAS_NONE);
415 cairo_rectangle(fe->cr, x, y, w, h); 549 cairo_rectangle(fe->cr, x, y, w, h);
416 cairo_fill(fe->cr); 550 fe->dr_api->fill(fe);
417 cairo_restore(fe->cr); 551 cairo_restore(fe->cr);
418} 552}
419 553
@@ -447,11 +581,11 @@ static void do_draw_poly(frontend *fe, int *coords, int npoints,
447 cairo_line_to(fe->cr, coords[i*2] + 0.5, coords[i*2 + 1] + 0.5); 581 cairo_line_to(fe->cr, coords[i*2] + 0.5, coords[i*2 + 1] + 0.5);
448 cairo_close_path(fe->cr); 582 cairo_close_path(fe->cr);
449 if (fillcolour >= 0) { 583 if (fillcolour >= 0) {
450 set_colour(fe, fillcolour); 584 fe->dr_api->set_colour(fe, fillcolour);
451 cairo_fill_preserve(fe->cr); 585 fe->dr_api->fill_preserve(fe);
452 } 586 }
453 assert(outlinecolour >= 0); 587 assert(outlinecolour >= 0);
454 set_colour(fe, outlinecolour); 588 fe->dr_api->set_colour(fe, outlinecolour);
455 cairo_stroke(fe->cr); 589 cairo_stroke(fe->cr);
456} 590}
457 591
@@ -462,11 +596,11 @@ static void do_draw_circle(frontend *fe, int cx, int cy, int radius,
462 cairo_arc(fe->cr, cx + 0.5, cy + 0.5, radius, 0, 2*PI); 596 cairo_arc(fe->cr, cx + 0.5, cy + 0.5, radius, 0, 2*PI);
463 cairo_close_path(fe->cr); /* Just in case... */ 597 cairo_close_path(fe->cr); /* Just in case... */
464 if (fillcolour >= 0) { 598 if (fillcolour >= 0) {
465 set_colour(fe, fillcolour); 599 fe->dr_api->set_colour(fe, fillcolour);
466 cairo_fill_preserve(fe->cr); 600 fe->dr_api->fill_preserve(fe);
467 } 601 }
468 assert(outlinecolour >= 0); 602 assert(outlinecolour >= 0);
469 set_colour(fe, outlinecolour); 603 fe->dr_api->set_colour(fe, outlinecolour);
470 cairo_stroke(fe->cr); 604 cairo_stroke(fe->cr);
471} 605}
472 606
@@ -512,23 +646,24 @@ static void wipe_and_maybe_destroy_cairo(frontend *fe, cairo_t *cr,
512static void setup_backing_store(frontend *fe) 646static void setup_backing_store(frontend *fe)
513{ 647{
514#ifndef USE_CAIRO_WITHOUT_PIXMAP 648#ifndef USE_CAIRO_WITHOUT_PIXMAP
515 if (fe->headless) { 649 if (!fe->headless) {
516 fprintf(stderr, "headless mode does not work with GDK pixmaps\n"); 650 fe->pixmap = gdk_pixmap_new(gtk_widget_get_window(fe->area),
517 exit(1); 651 fe->pw*fe->ps, fe->ph*fe->ps, -1);
652 } else {
653 fe->pixmap = NULL;
518 } 654 }
519
520 fe->pixmap = gdk_pixmap_new(gtk_widget_get_window(fe->area),
521 fe->pw, fe->ph, -1);
522#endif 655#endif
656
523 fe->image = cairo_image_surface_create(CAIRO_FORMAT_RGB24, 657 fe->image = cairo_image_surface_create(CAIRO_FORMAT_RGB24,
524 fe->pw, fe->ph); 658 fe->pw*fe->ps, fe->ph*fe->ps);
525 659
526 wipe_and_maybe_destroy_cairo(fe, cairo_create(fe->image), true); 660 wipe_and_maybe_destroy_cairo(fe, cairo_create(fe->image), true);
527#ifndef USE_CAIRO_WITHOUT_PIXMAP 661#ifndef USE_CAIRO_WITHOUT_PIXMAP
528 wipe_and_maybe_destroy_cairo(fe, gdk_cairo_create(fe->pixmap), true); 662 if (!fe->headless)
663 wipe_and_maybe_destroy_cairo(fe, gdk_cairo_create(fe->pixmap), true);
529#endif 664#endif
530#if GTK_CHECK_VERSION(3,22,0)
531 if (!fe->headless) { 665 if (!fe->headless) {
666#if GTK_CHECK_VERSION(3,22,0)
532 GdkWindow *gdkwin; 667 GdkWindow *gdkwin;
533 cairo_region_t *region; 668 cairo_region_t *region;
534 GdkDrawingContext *drawctx; 669 GdkDrawingContext *drawctx;
@@ -541,11 +676,11 @@ static void setup_backing_store(frontend *fe)
541 wipe_and_maybe_destroy_cairo(fe, cr, false); 676 wipe_and_maybe_destroy_cairo(fe, cr, false);
542 gdk_window_end_draw_frame(gdkwin, drawctx); 677 gdk_window_end_draw_frame(gdkwin, drawctx);
543 cairo_region_destroy(region); 678 cairo_region_destroy(region);
544 }
545#else 679#else
546 wipe_and_maybe_destroy_cairo( 680 wipe_and_maybe_destroy_cairo(
547 fe, gdk_cairo_create(gtk_widget_get_window(fe->area)), true); 681 fe, gdk_cairo_create(gtk_widget_get_window(fe->area)), true);
548#endif 682#endif
683 }
549} 684}
550 685
551static bool backing_store_ok(frontend *fe) 686static bool backing_store_ok(frontend *fe)
@@ -616,7 +751,7 @@ static void set_window_background(frontend *fe, int colour)
616 gdk_window_set_background(fe->window->window, &fe->colours[colour]); 751 gdk_window_set_background(fe->window->window, &fe->colours[colour]);
617} 752}
618 753
619static void set_colour(frontend *fe, int colour) 754static void draw_set_colour(frontend *fe, int colour)
620{ 755{
621 gdk_gc_set_foreground(fe->gc, &fe->colours[colour]); 756 gdk_gc_set_foreground(fe->gc, &fe->colours[colour]);
622} 757}
@@ -709,11 +844,11 @@ static void do_draw_poly(frontend *fe, int *coords, int npoints,
709 } 844 }
710 845
711 if (fillcolour >= 0) { 846 if (fillcolour >= 0) {
712 set_colour(fe, fillcolour); 847 fe->dr_api->set_colour(fe, fillcolour);
713 gdk_draw_polygon(fe->pixmap, fe->gc, true, points, npoints); 848 gdk_draw_polygon(fe->pixmap, fe->gc, true, points, npoints);
714 } 849 }
715 assert(outlinecolour >= 0); 850 assert(outlinecolour >= 0);
716 set_colour(fe, outlinecolour); 851 fe->dr_api->set_colour(fe, outlinecolour);
717 852
718 /* 853 /*
719 * In principle we ought to be able to use gdk_draw_polygon for 854 * In principle we ought to be able to use gdk_draw_polygon for
@@ -733,14 +868,14 @@ static void do_draw_circle(frontend *fe, int cx, int cy, int radius,
733 int fillcolour, int outlinecolour) 868 int fillcolour, int outlinecolour)
734{ 869{
735 if (fillcolour >= 0) { 870 if (fillcolour >= 0) {
736 set_colour(fe, fillcolour); 871 fe->dr_api->set_colour(fe, fillcolour);
737 gdk_draw_arc(fe->pixmap, fe->gc, true, 872 gdk_draw_arc(fe->pixmap, fe->gc, true,
738 cx - radius, cy - radius, 873 cx - radius, cy - radius,
739 2 * radius, 2 * radius, 0, 360 * 64); 874 2 * radius, 2 * radius, 0, 360 * 64);
740 } 875 }
741 876
742 assert(outlinecolour >= 0); 877 assert(outlinecolour >= 0);
743 set_colour(fe, outlinecolour); 878 fe->dr_api->set_colour(fe, outlinecolour);
744 gdk_draw_arc(fe->pixmap, fe->gc, false, 879 gdk_draw_arc(fe->pixmap, fe->gc, false,
745 cx - radius, cy - radius, 880 cx - radius, cy - radius,
746 2 * radius, 2 * radius, 0, 360 * 64); 881 2 * radius, 2 * radius, 0, 360 * 64);
@@ -1045,21 +1180,21 @@ void gtk_draw_text(void *handle, int x, int y, int fonttype, int fontsize,
1045 /* 1180 /*
1046 * Do the job. 1181 * Do the job.
1047 */ 1182 */
1048 set_colour(fe, colour); 1183 fe->dr_api->set_colour(fe, colour);
1049 align_and_draw_text(fe, i, align, x, y, text); 1184 align_and_draw_text(fe, i, align, x, y, text);
1050} 1185}
1051 1186
1052void gtk_draw_rect(void *handle, int x, int y, int w, int h, int colour) 1187void gtk_draw_rect(void *handle, int x, int y, int w, int h, int colour)
1053{ 1188{
1054 frontend *fe = (frontend *)handle; 1189 frontend *fe = (frontend *)handle;
1055 set_colour(fe, colour); 1190 fe->dr_api->set_colour(fe, colour);
1056 do_draw_rect(fe, x, y, w, h); 1191 do_draw_rect(fe, x, y, w, h);
1057} 1192}
1058 1193
1059void gtk_draw_line(void *handle, int x1, int y1, int x2, int y2, int colour) 1194void gtk_draw_line(void *handle, int x1, int y1, int x2, int y2, int colour)
1060{ 1195{
1061 frontend *fe = (frontend *)handle; 1196 frontend *fe = (frontend *)handle;
1062 set_colour(fe, colour); 1197 fe->dr_api->set_colour(fe, colour);
1063 do_draw_line(fe, x1, y1, x2, y2); 1198 do_draw_line(fe, x1, y1, x2, y2);
1064} 1199}
1065 1200
@@ -1067,7 +1202,7 @@ void gtk_draw_thick_line(void *handle, float thickness,
1067 float x1, float y1, float x2, float y2, int colour) 1202 float x1, float y1, float x2, float y2, int colour)
1068{ 1203{
1069 frontend *fe = (frontend *)handle; 1204 frontend *fe = (frontend *)handle;
1070 set_colour(fe, colour); 1205 fe->dr_api->set_colour(fe, colour);
1071 do_draw_thick_line(fe, thickness, x1, y1, x2, y2); 1206 do_draw_thick_line(fe, thickness, x1, y1, x2, y2);
1072} 1207}
1073 1208
@@ -1161,6 +1296,105 @@ char *gtk_text_fallback(void *handle, const char *const *strings, int nstrings)
1161} 1296}
1162#endif 1297#endif
1163 1298
1299#ifdef USE_PRINTING
1300void gtk_begin_doc(void *handle, int pages)
1301{
1302 frontend *fe = (frontend *)handle;
1303 gtk_print_operation_set_n_pages(fe->printop, pages);
1304}
1305
1306void gtk_begin_page(void *handle, int number)
1307{
1308}
1309
1310void gtk_begin_puzzle(void *handle, float xm, float xc,
1311 float ym, float yc, int pw, int ph, float wmm)
1312{
1313 frontend *fe = (frontend *)handle;
1314 double ppw, pph, pox, poy, dpmmx, dpmmy;
1315 double scale;
1316
1317 ppw = gtk_print_context_get_width(fe->printcontext);
1318 pph = gtk_print_context_get_height(fe->printcontext);
1319 dpmmx = gtk_print_context_get_dpi_x(fe->printcontext) / 25.4;
1320 dpmmy = gtk_print_context_get_dpi_y(fe->printcontext) / 25.4;
1321
1322 /*
1323 * Compute the puzzle's position in pixels on the logical page.
1324 */
1325 pox = xm * ppw + xc * dpmmx;
1326 poy = ym * pph + yc * dpmmy;
1327
1328 /*
1329 * And determine the scale.
1330 *
1331 * I need a scale such that the maximum puzzle-coordinate
1332 * extent of the rectangle (pw * scale) is equal to the pixel
1333 * equivalent of the puzzle's millimetre width (wmm * dpmmx).
1334 */
1335 scale = wmm * dpmmx / pw;
1336
1337 /*
1338 * Now instruct Cairo to transform points based on our calculated
1339 * values (order here *is* important).
1340 */
1341 cairo_save(fe->cr);
1342 cairo_translate(fe->cr, pox, poy);
1343 cairo_scale(fe->cr, scale, scale);
1344
1345 fe->hatchthick = 0.2 * pw / wmm;
1346 fe->hatchspace = 1.0 * pw / wmm;
1347}
1348
1349void gtk_end_puzzle(void *handle)
1350{
1351 frontend *fe = (frontend *)handle;
1352 cairo_restore(fe->cr);
1353}
1354
1355void gtk_end_page(void *handle, int number)
1356{
1357}
1358
1359void gtk_end_doc(void *handle)
1360{
1361}
1362
1363void gtk_line_width(void *handle, float width)
1364{
1365 frontend *fe = (frontend *)handle;
1366 cairo_set_line_width(fe->cr, width);
1367}
1368
1369void gtk_line_dotted(void *handle, bool dotted)
1370{
1371 frontend *fe = (frontend *)handle;
1372
1373 if (dotted) {
1374 const double dash = 35.0;
1375 cairo_set_dash(fe->cr, &dash, 1, 0);
1376 } else {
1377 cairo_set_dash(fe->cr, NULL, 0, 0);
1378 }
1379}
1380#endif /* USE_PRINTING */
1381
1382const struct internal_drawing_api internal_drawing = {
1383 draw_set_colour,
1384#ifdef USE_CAIRO
1385 do_draw_fill,
1386 do_draw_fill_preserve,
1387#endif
1388};
1389
1390#ifdef USE_CAIRO
1391const struct internal_drawing_api internal_printing = {
1392 print_set_colour,
1393 do_print_fill,
1394 do_print_fill_preserve,
1395};
1396#endif
1397
1164const struct drawing_api gtk_drawing = { 1398const struct drawing_api gtk_drawing = {
1165 gtk_draw_text, 1399 gtk_draw_text,
1166 gtk_draw_rect, 1400 gtk_draw_rect,
@@ -1177,8 +1411,19 @@ const struct drawing_api gtk_drawing = {
1177 gtk_blitter_free, 1411 gtk_blitter_free,
1178 gtk_blitter_save, 1412 gtk_blitter_save,
1179 gtk_blitter_load, 1413 gtk_blitter_load,
1414#ifdef USE_PRINTING
1415 gtk_begin_doc,
1416 gtk_begin_page,
1417 gtk_begin_puzzle,
1418 gtk_end_puzzle,
1419 gtk_end_page,
1420 gtk_end_doc,
1421 gtk_line_width,
1422 gtk_line_dotted,
1423#else
1180 NULL, NULL, NULL, NULL, NULL, NULL, /* {begin,end}_{doc,page,puzzle} */ 1424 NULL, NULL, NULL, NULL, NULL, NULL, /* {begin,end}_{doc,page,puzzle} */
1181 NULL, NULL, /* line_width, line_dotted */ 1425 NULL, NULL, /* line_width, line_dotted */
1426#endif
1182#ifdef USE_PANGO 1427#ifdef USE_PANGO
1183 gtk_text_fallback, 1428 gtk_text_fallback,
1184#else 1429#else
@@ -1340,12 +1585,22 @@ static gint draw_area(GtkWidget *widget, cairo_t *cr, gpointer data)
1340 frontend *fe = (frontend *)data; 1585 frontend *fe = (frontend *)data;
1341 GdkRectangle dirtyrect; 1586 GdkRectangle dirtyrect;
1342 1587
1588 cairo_surface_t *target_surface = cairo_get_target(cr);
1589 cairo_matrix_t m;
1590 cairo_get_matrix(cr, &m);
1591 double orig_sx, orig_sy;
1592 cairo_surface_get_device_scale(target_surface, &orig_sx, &orig_sy);
1593 cairo_surface_set_device_scale(target_surface, 1.0, 1.0);
1594 cairo_translate(cr, m.x0 * (orig_sx - 1.0), m.y0 * (orig_sy - 1.0));
1595
1343 gdk_cairo_get_clip_rectangle(cr, &dirtyrect); 1596 gdk_cairo_get_clip_rectangle(cr, &dirtyrect);
1344 cairo_set_source_surface(cr, fe->image, fe->ox, fe->oy); 1597 cairo_set_source_surface(cr, fe->image, fe->ox, fe->oy);
1345 cairo_rectangle(cr, dirtyrect.x, dirtyrect.y, 1598 cairo_rectangle(cr, dirtyrect.x, dirtyrect.y,
1346 dirtyrect.width, dirtyrect.height); 1599 dirtyrect.width, dirtyrect.height);
1347 cairo_fill(cr); 1600 cairo_fill(cr);
1348 1601
1602 cairo_surface_set_device_scale(target_surface, orig_sx, orig_sy);
1603
1349 return true; 1604 return true;
1350} 1605}
1351#else 1606#else
@@ -1390,16 +1645,22 @@ static gint map_window(GtkWidget *widget, GdkEvent *event,
1390static void resize_puzzle_to_area(frontend *fe, int x, int y) 1645static void resize_puzzle_to_area(frontend *fe, int x, int y)
1391{ 1646{
1392 int oldw = fe->w, oldpw = fe->pw, oldh = fe->h, oldph = fe->ph; 1647 int oldw = fe->w, oldpw = fe->pw, oldh = fe->h, oldph = fe->ph;
1648 int oldps = fe->ps;
1393 1649
1394 fe->w = x; 1650 fe->w = x;
1395 fe->h = y; 1651 fe->h = y;
1396 midend_size(fe->me, &x, &y, true); 1652 midend_size(fe->me, &x, &y, true);
1397 fe->pw = x; 1653 fe->pw = x;
1398 fe->ph = y; 1654 fe->ph = y;
1655#if GTK_CHECK_VERSION(3,10,0)
1656 fe->ps = gtk_widget_get_scale_factor(fe->area);
1657#else
1658 fe->ps = 1;
1659#endif
1399 fe->ox = (fe->w - fe->pw) / 2; 1660 fe->ox = (fe->w - fe->pw) / 2;
1400 fe->oy = (fe->h - fe->ph) / 2; 1661 fe->oy = (fe->h - fe->ph) / 2;
1401 1662
1402 if (oldw != fe->w || oldpw != fe->pw || 1663 if (oldw != fe->w || oldpw != fe->pw || oldps != fe->ps ||
1403 oldh != fe->h || oldph != fe->ph || !backing_store_ok(fe)) { 1664 oldh != fe->h || oldph != fe->ph || !backing_store_ok(fe)) {
1404 if (backing_store_ok(fe)) 1665 if (backing_store_ok(fe))
1405 teardown_backing_store(fe); 1666 teardown_backing_store(fe);
@@ -1413,6 +1674,7 @@ static gint configure_area(GtkWidget *widget,
1413 GdkEventConfigure *event, gpointer data) 1674 GdkEventConfigure *event, gpointer data)
1414{ 1675{
1415 frontend *fe = (frontend *)data; 1676 frontend *fe = (frontend *)data;
1677
1416 resize_puzzle_to_area(fe, event->width, event->height); 1678 resize_puzzle_to_area(fe, event->width, event->height);
1417#if GTK_CHECK_VERSION(3,0,0) 1679#if GTK_CHECK_VERSION(3,0,0)
1418 fe->awaiting_resize_ack = false; 1680 fe->awaiting_resize_ack = false;
@@ -2245,6 +2507,317 @@ static char *file_selector(frontend *fe, const char *title, bool save)
2245 2507
2246#endif 2508#endif
2247 2509
2510#ifdef USE_PRINTING
2511GObject *create_print_widget(GtkPrintOperation *print, gpointer data)
2512{
2513 GtkLabel *count_label, *width_label, *height_label,
2514 *scale_llabel, *scale_rlabel;
2515 GtkBox *scale_hbox;
2516 GtkWidget *grid;
2517 frontend *fe = (frontend *)data;
2518
2519 fe->printcount_spin_button =
2520 GTK_SPIN_BUTTON(gtk_spin_button_new_with_range(1, 999, 1));
2521 gtk_spin_button_set_numeric(fe->printcount_spin_button, true);
2522 gtk_spin_button_set_snap_to_ticks(fe->printcount_spin_button, true);
2523 fe->printw_spin_button =
2524 GTK_SPIN_BUTTON(gtk_spin_button_new_with_range(1, 99, 1));
2525 gtk_spin_button_set_numeric(fe->printw_spin_button, true);
2526 gtk_spin_button_set_snap_to_ticks(fe->printw_spin_button, true);
2527 fe->printh_spin_button =
2528 GTK_SPIN_BUTTON(gtk_spin_button_new_with_range(1, 99, 1));
2529 gtk_spin_button_set_numeric(fe->printh_spin_button, true);
2530 gtk_spin_button_set_snap_to_ticks(fe->printh_spin_button, true);
2531 fe->printscale_spin_button =
2532 GTK_SPIN_BUTTON(gtk_spin_button_new_with_range(1, 1000, 1));
2533 gtk_spin_button_set_digits(fe->printscale_spin_button, 1);
2534 gtk_spin_button_set_numeric(fe->printscale_spin_button, true);
2535 if (thegame.can_solve) {
2536 fe->soln_check_button =
2537 GTK_CHECK_BUTTON(
2538 gtk_check_button_new_with_label("Print solutions"));
2539 }
2540 if (thegame.can_print_in_colour) {
2541 fe->colour_check_button =
2542 GTK_CHECK_BUTTON(
2543 gtk_check_button_new_with_label("Print in color"));
2544 }
2545
2546 /* Set defaults to what was selected last time. */
2547 gtk_spin_button_set_value(fe->printcount_spin_button,
2548 (gdouble)fe->printcount);
2549 gtk_spin_button_set_value(fe->printw_spin_button,
2550 (gdouble)fe->printw);
2551 gtk_spin_button_set_value(fe->printh_spin_button,
2552 (gdouble)fe->printh);
2553 gtk_spin_button_set_value(fe->printscale_spin_button,
2554 (gdouble)fe->printscale);
2555 if (thegame.can_solve) {
2556 gtk_toggle_button_set_active(
2557 GTK_TOGGLE_BUTTON(fe->soln_check_button), fe->printsolns);
2558 }
2559 if (thegame.can_print_in_colour) {
2560 gtk_toggle_button_set_active(
2561 GTK_TOGGLE_BUTTON(fe->colour_check_button), fe->printcolour);
2562 }
2563
2564 count_label = GTK_LABEL(gtk_label_new("Puzzles to print:"));
2565 width_label = GTK_LABEL(gtk_label_new("Puzzles across:"));
2566 height_label = GTK_LABEL(gtk_label_new("Puzzles down:"));
2567 scale_llabel = GTK_LABEL(gtk_label_new("Puzzle scale:"));
2568 scale_rlabel = GTK_LABEL(gtk_label_new("%"));
2569#if GTK_CHECK_VERSION(3,0,0)
2570 gtk_widget_set_halign(GTK_WIDGET(count_label), GTK_ALIGN_START);
2571 gtk_widget_set_halign(GTK_WIDGET(width_label), GTK_ALIGN_START);
2572 gtk_widget_set_halign(GTK_WIDGET(height_label), GTK_ALIGN_START);
2573 gtk_widget_set_halign(GTK_WIDGET(scale_llabel), GTK_ALIGN_START);
2574#else
2575 gtk_misc_set_alignment(GTK_MISC(count_label), 0, 0);
2576 gtk_misc_set_alignment(GTK_MISC(width_label), 0, 0);
2577 gtk_misc_set_alignment(GTK_MISC(height_label), 0, 0);
2578 gtk_misc_set_alignment(GTK_MISC(scale_llabel), 0, 0);
2579#endif
2580
2581 scale_hbox = GTK_BOX(gtk_hbox_new(false, 6));
2582 gtk_box_pack_start(scale_hbox, GTK_WIDGET(fe->printscale_spin_button),
2583 false, false, 0);
2584 gtk_box_pack_start(scale_hbox, GTK_WIDGET(scale_rlabel),
2585 false, false, 0);
2586
2587#if GTK_CHECK_VERSION(3,0,0)
2588 grid = gtk_grid_new();
2589 gtk_grid_set_column_spacing(GTK_GRID(grid), 18);
2590 gtk_grid_set_row_spacing(GTK_GRID(grid), 18);
2591 gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(count_label), 0, 0, 1, 1);
2592 gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(width_label), 0, 1, 1, 1);
2593 gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(height_label), 0, 2, 1, 1);
2594 gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(scale_llabel), 0, 3, 1, 1);
2595 gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(fe->printcount_spin_button),
2596 1, 0, 1, 1);
2597 gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(fe->printw_spin_button),
2598 1, 1, 1, 1);
2599 gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(fe->printh_spin_button),
2600 1, 2, 1, 1);
2601 gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(scale_hbox), 1, 3, 1, 1);
2602 if (thegame.can_solve) {
2603 gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(fe->soln_check_button),
2604 0, 4, 1, 1);
2605 }
2606 if (thegame.can_print_in_colour) {
2607 gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(fe->colour_check_button),
2608 thegame.can_solve, 4, 1, 1);
2609 }
2610#else
2611 grid = gtk_table_new((thegame.can_solve || thegame.can_print_in_colour) ?
2612 5 : 4, 2, false);
2613 gtk_table_set_col_spacings(GTK_TABLE(grid), 18);
2614 gtk_table_set_row_spacings(GTK_TABLE(grid), 18);
2615 gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(count_label), 0, 1, 0, 1,
2616 GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0);
2617 gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(width_label), 0, 1, 1, 2,
2618 GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0);
2619 gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(height_label), 0, 1, 2, 3,
2620 GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0);
2621 gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(scale_llabel), 0, 1, 3, 4,
2622 GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0);
2623 gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(fe->printcount_spin_button),
2624 1, 2, 0, 1,
2625 GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0);
2626 gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(fe->printw_spin_button),
2627 1, 2, 1, 2,
2628 GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0);
2629 gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(fe->printh_spin_button),
2630 1, 2, 2, 3,
2631 GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0);
2632 gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(scale_hbox), 1, 2, 3, 4,
2633 GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0);
2634 if (thegame.can_solve) {
2635 gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(fe->soln_check_button),
2636 0, 1, 4, 5,
2637 GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0);
2638 }
2639 if (thegame.can_print_in_colour) {
2640 gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(fe->colour_check_button),
2641 thegame.can_solve, thegame.can_solve + 1, 4, 5,
2642 GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0);
2643 }
2644#endif
2645 gtk_container_set_border_width(GTK_CONTAINER(grid), 12);
2646
2647 gtk_widget_show_all(grid);
2648
2649 return G_OBJECT(grid);
2650}
2651
2652void apply_print_widget(GtkPrintOperation *print,
2653 GtkWidget *widget, gpointer data)
2654{
2655 frontend *fe = (frontend *)data;
2656
2657 /* We ignore `widget' because it is easier and faster to store the
2658 widgets we need in `fe' then to get the children of `widget'. */
2659 fe->printcount =
2660 gtk_spin_button_get_value_as_int(fe->printcount_spin_button);
2661 fe->printw = gtk_spin_button_get_value_as_int(fe->printw_spin_button);
2662 fe->printh = gtk_spin_button_get_value_as_int(fe->printh_spin_button);
2663 fe->printscale = gtk_spin_button_get_value(fe->printscale_spin_button);
2664 if (thegame.can_solve) {
2665 fe->printsolns =
2666 gtk_toggle_button_get_active(
2667 GTK_TOGGLE_BUTTON(fe->soln_check_button));
2668 }
2669 if (thegame.can_print_in_colour) {
2670 fe->printcolour =
2671 gtk_toggle_button_get_active(
2672 GTK_TOGGLE_BUTTON(fe->colour_check_button));
2673 }
2674}
2675
2676void print_begin(GtkPrintOperation *printop,
2677 GtkPrintContext *context, gpointer data)
2678{
2679 frontend *fe = (frontend *)data;
2680 midend *nme = NULL; /* non-interactive midend for bulk puzzle generation */
2681 int i;
2682
2683 fe->printcontext = context;
2684 fe->cr = gtk_print_context_get_cairo_context(context);
2685
2686 /*
2687 * Create our document structure and fill it up with puzzles.
2688 */
2689 fe->doc = document_new(fe->printw, fe->printh, fe->printscale / 100.0F);
2690
2691 for (i = 0; i < fe->printcount; i++) {
2692 const char *err;
2693
2694 if (i == 0) {
2695 err = midend_print_puzzle(fe->me, fe->doc, fe->printsolns);
2696 } else {
2697 if (!nme) {
2698 game_params *params;
2699
2700 nme = midend_new(NULL, &thegame, NULL, NULL);
2701
2702 /*
2703 * Set the non-interactive mid-end to have the same
2704 * parameters as the standard one.
2705 */
2706 params = midend_get_params(fe->me);
2707 midend_set_params(nme, params);
2708 thegame.free_params(params);
2709 }
2710
2711 midend_new_game(nme);
2712 err = midend_print_puzzle(nme, fe->doc, fe->printsolns);
2713 }
2714
2715 if (err) {
2716 error_box(fe->window, err);
2717 return;
2718 }
2719 }
2720
2721 if (nme)
2722 midend_free(nme);
2723
2724 /* Begin the document. */
2725 document_begin(fe->doc, fe->print_dr);
2726}
2727
2728void draw_page(GtkPrintOperation *printop,
2729 GtkPrintContext *context,
2730 gint page_nr, gpointer data)
2731{
2732 frontend *fe = (frontend *)data;
2733 document_print_page(fe->doc, fe->print_dr, page_nr);
2734}
2735
2736void print_end(GtkPrintOperation *printop,
2737 GtkPrintContext *context, gpointer data)
2738{
2739 frontend *fe = (frontend *)data;
2740
2741 /* End and free the document. */
2742 document_end(fe->doc, fe->print_dr);
2743 document_free(fe->doc);
2744 fe->doc = NULL;
2745}
2746
2747static void print_dialog(frontend *fe)
2748{
2749 GError *error;
2750 static GtkPrintSettings *settings = NULL;
2751 static GtkPageSetup *page_setup = NULL;
2752#ifndef USE_EMBED_PAGE_SETUP
2753 GtkPageSetup *new_page_setup;
2754#endif
2755
2756 fe->printop = gtk_print_operation_new();
2757 gtk_print_operation_set_use_full_page(fe->printop, true);
2758 gtk_print_operation_set_custom_tab_label(fe->printop, "Puzzle Settings");
2759 g_signal_connect(fe->printop, "create-custom-widget",
2760 G_CALLBACK(create_print_widget), fe);
2761 g_signal_connect(fe->printop, "custom-widget-apply",
2762 G_CALLBACK(apply_print_widget), fe);
2763 g_signal_connect(fe->printop, "begin-print", G_CALLBACK(print_begin), fe);
2764 g_signal_connect(fe->printop, "draw-page", G_CALLBACK(draw_page), fe);
2765 g_signal_connect(fe->printop, "end-print", G_CALLBACK(print_end), fe);
2766#ifdef USE_EMBED_PAGE_SETUP
2767 gtk_print_operation_set_embed_page_setup(fe->printop, true);
2768#else
2769 if (page_setup == NULL) {
2770 page_setup =
2771 g_object_ref(
2772 gtk_print_operation_get_default_page_setup(fe->printop));
2773 }
2774 if (settings == NULL) {
2775 settings =
2776 g_object_ref(gtk_print_operation_get_print_settings(fe->printop));
2777 }
2778 new_page_setup = gtk_print_run_page_setup_dialog(GTK_WINDOW(fe->window),
2779 page_setup, settings);
2780 g_object_unref(page_setup);
2781 page_setup = new_page_setup;
2782 gtk_print_operation_set_default_page_setup(fe->printop, page_setup);
2783#endif
2784
2785 if (settings != NULL)
2786 gtk_print_operation_set_print_settings(fe->printop, settings);
2787 if (page_setup != NULL)
2788 gtk_print_operation_set_default_page_setup(fe->printop, page_setup);
2789
2790 switch (gtk_print_operation_run(fe->printop,
2791 GTK_PRINT_OPERATION_ACTION_PRINT_DIALOG,
2792 GTK_WINDOW(fe->window), &error)) {
2793 case GTK_PRINT_OPERATION_RESULT_ERROR:
2794 error_box(fe->window, error->message);
2795 g_error_free(error);
2796 break;
2797 case GTK_PRINT_OPERATION_RESULT_APPLY:
2798 if (settings != NULL)
2799 g_object_unref(settings);
2800 settings =
2801 g_object_ref(gtk_print_operation_get_print_settings(fe->printop));
2802#ifdef USE_EMBED_PAGE_SETUP
2803 if (page_setup != NULL)
2804 g_object_unref(page_setup);
2805 page_setup =
2806 g_object_ref(
2807 gtk_print_operation_get_default_page_setup(fe->printop));
2808#endif
2809 break;
2810 default:
2811 /* Don't error out on -Werror=switch. */
2812 break;
2813 }
2814
2815 g_object_unref(fe->printop);
2816 fe->printop = NULL;
2817 fe->printcontext = NULL;
2818}
2819#endif /* USE_PRINTING */
2820
2248struct savefile_write_ctx { 2821struct savefile_write_ctx {
2249 FILE *fp; 2822 FILE *fp;
2250 int error; 2823 int error;
@@ -2346,6 +2919,15 @@ static void menu_load_event(GtkMenuItem *menuitem, gpointer data)
2346 } 2919 }
2347} 2920}
2348 2921
2922#ifdef USE_PRINTING
2923static void menu_print_event(GtkMenuItem *menuitem, gpointer data)
2924{
2925 frontend *fe = (frontend *)data;
2926
2927 print_dialog(fe);
2928}
2929#endif
2930
2349static void menu_solve_event(GtkMenuItem *menuitem, gpointer data) 2931static void menu_solve_event(GtkMenuItem *menuitem, gpointer data)
2350{ 2932{
2351 frontend *fe = (frontend *)data; 2933 frontend *fe = (frontend *)data;
@@ -2388,18 +2970,31 @@ static void menu_about_event(GtkMenuItem *menuitem, gpointer data)
2388 frontend *fe = (frontend *)data; 2970 frontend *fe = (frontend *)data;
2389 2971
2390#if GTK_CHECK_VERSION(3,0,0) 2972#if GTK_CHECK_VERSION(3,0,0)
2973# define ABOUT_PARAMS \
2974 "program-name", thegame.name, \
2975 "version", ver, \
2976 "comments", "Part of Simon Tatham's Portable Puzzle Collection"
2977
2391 extern char *const *const xpm_icons[]; 2978 extern char *const *const xpm_icons[];
2392 extern const int n_xpm_icons; 2979 extern const int n_xpm_icons;
2393 GdkPixbuf *icon = gdk_pixbuf_new_from_xpm_data 2980
2394 ((const gchar **)xpm_icons[n_xpm_icons-1]); 2981 if (n_xpm_icons) {
2395 gtk_show_about_dialog 2982 GdkPixbuf *icon = gdk_pixbuf_new_from_xpm_data
2396 (GTK_WINDOW(fe->window), 2983 ((const gchar **)xpm_icons[n_xpm_icons-1]);
2397 "program-name", thegame.name, 2984
2398 "version", ver, 2985 gtk_show_about_dialog
2399 "comments", "Part of Simon Tatham's Portable Puzzle Collection", 2986 (GTK_WINDOW(fe->window),
2400 "logo", icon, 2987 ABOUT_PARAMS,
2401 (const gchar *)NULL); 2988 "logo", icon,
2402 g_object_unref(G_OBJECT(icon)); 2989 (const gchar *)NULL);
2990 g_object_unref(G_OBJECT(icon));
2991 }
2992 else {
2993 gtk_show_about_dialog
2994 (GTK_WINDOW(fe->window),
2995 ABOUT_PARAMS,
2996 (const gchar *)NULL);
2997 }
2403#else 2998#else
2404 char titlebuf[256]; 2999 char titlebuf[256];
2405 char textbuf[1024]; 3000 char textbuf[1024];
@@ -2489,6 +3084,9 @@ static frontend *new_window(
2489 char *arg, int argtype, char **error, bool headless) 3084 char *arg, int argtype, char **error, bool headless)
2490{ 3085{
2491 frontend *fe; 3086 frontend *fe;
3087#ifdef USE_PRINTING
3088 frontend *print_fe = NULL;
3089#endif
2492 GtkBox *vbox, *hbox; 3090 GtkBox *vbox, *hbox;
2493 GtkWidget *menu, *menuitem; 3091 GtkWidget *menu, *menuitem;
2494 GList *iconlist; 3092 GList *iconlist;
@@ -2501,13 +3099,14 @@ static frontend *new_window(
2501 fe = snew(frontend); 3099 fe = snew(frontend);
2502 memset(fe, 0, sizeof(frontend)); 3100 memset(fe, 0, sizeof(frontend));
2503 3101
2504#if !GTK_CHECK_VERSION(3,0,0) 3102#ifndef USE_CAIRO
2505 if (headless) { 3103 if (headless) {
2506 fprintf(stderr, "headless mode not supported below GTK 3\n"); 3104 fprintf(stderr, "headless mode not supported for non-Cairo drawing\n");
2507 exit(1); 3105 exit(1);
2508 } 3106 }
2509#else 3107#else
2510 fe->headless = headless; 3108 fe->headless = headless;
3109 fe->ps = 1; /* in headless mode, configure_area won't have set this */
2511#endif 3110#endif
2512 3111
2513 fe->timer_active = false; 3112 fe->timer_active = false;
@@ -2515,6 +3114,32 @@ static frontend *new_window(
2515 3114
2516 fe->me = midend_new(fe, &thegame, &gtk_drawing, fe); 3115 fe->me = midend_new(fe, &thegame, &gtk_drawing, fe);
2517 3116
3117 fe->dr_api = &internal_drawing;
3118
3119#ifdef USE_PRINTING
3120 if (thegame.can_print) {
3121 print_fe = snew(frontend);
3122 memset(print_fe, 0, sizeof(frontend));
3123
3124 /* Defaults */
3125 print_fe->printcount = print_fe->printw = print_fe->printh = 1;
3126 print_fe->printscale = 100;
3127 print_fe->printsolns = false;
3128 print_fe->printcolour = thegame.can_print_in_colour;
3129
3130 /*
3131 * We need to use the same midend as the main frontend because
3132 * we need midend_print_puzzle() to be able to print the
3133 * current puzzle.
3134 */
3135 print_fe->me = fe->me;
3136
3137 print_fe->print_dr = drawing_new(&gtk_drawing, print_fe->me, print_fe);
3138
3139 print_fe->dr_api = &internal_printing;
3140 }
3141#endif
3142
2518 if (arg) { 3143 if (arg) {
2519 const char *err; 3144 const char *err;
2520 FILE *fp; 3145 FILE *fp;
@@ -2568,6 +3193,12 @@ static frontend *new_window(
2568 *error = dupstr(errbuf); 3193 *error = dupstr(errbuf);
2569 midend_free(fe->me); 3194 midend_free(fe->me);
2570 sfree(fe); 3195 sfree(fe);
3196#ifdef USE_PRINTING
3197 if (thegame.can_print) {
3198 drawing_free(print_fe->print_dr);
3199 sfree(print_fe);
3200 }
3201#endif
2571 return NULL; 3202 return NULL;
2572 } 3203 }
2573 3204
@@ -2711,6 +3342,16 @@ static frontend *new_window(
2711 g_signal_connect(G_OBJECT(menuitem), "activate", 3342 g_signal_connect(G_OBJECT(menuitem), "activate",
2712 G_CALLBACK(menu_save_event), fe); 3343 G_CALLBACK(menu_save_event), fe);
2713 gtk_widget_show(menuitem); 3344 gtk_widget_show(menuitem);
3345#ifdef USE_PRINTING
3346 if (thegame.can_print) {
3347 add_menu_separator(GTK_CONTAINER(menu));
3348 menuitem = gtk_menu_item_new_with_label("Print...");
3349 gtk_container_add(GTK_CONTAINER(menu), menuitem);
3350 g_signal_connect(G_OBJECT(menuitem), "activate",
3351 G_CALLBACK(menu_print_event), print_fe);
3352 gtk_widget_show(menuitem);
3353 }
3354#endif
2714#ifndef STYLUS_BASED 3355#ifndef STYLUS_BASED
2715 add_menu_separator(GTK_CONTAINER(menu)); 3356 add_menu_separator(GTK_CONTAINER(menu));
2716 add_menu_ui_item(fe, GTK_CONTAINER(menu), "Undo", UI_UNDO, 'u', 0); 3357 add_menu_ui_item(fe, GTK_CONTAINER(menu), "Undo", UI_UNDO, 'u', 0);
diff --git a/apps/plugins/puzzles/src/keen.c b/apps/plugins/puzzles/src/keen.c
index baa1d81802..70e3e5432c 100644
--- a/apps/plugins/puzzles/src/keen.c
+++ b/apps/plugins/puzzles/src/keen.c
@@ -591,6 +591,92 @@ static int solver_hard(struct latin_solver *solver, void *vctx)
591#define SOLVER(upper,title,func,lower) func, 591#define SOLVER(upper,title,func,lower) func,
592static usersolver_t const keen_solvers[] = { DIFFLIST(SOLVER) }; 592static usersolver_t const keen_solvers[] = { DIFFLIST(SOLVER) };
593 593
594static int transpose(int index, int w)
595{
596 return (index % w) * w + (index / w);
597}
598
599static bool keen_valid(struct latin_solver *solver, void *vctx)
600{
601 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
602 int w = ctx->w;
603 int box, i;
604
605 /*
606 * Iterate over each clue box and check it's satisfied.
607 */
608 for (box = 0; box < ctx->nboxes; box++) {
609 int *sq = ctx->boxlist + ctx->boxes[box];
610 int n = ctx->boxes[box+1] - ctx->boxes[box];
611 long value = ctx->clues[box] & ~CMASK;
612 long op = ctx->clues[box] & CMASK;
613 bool fail = false;
614
615 switch (op) {
616 case C_ADD: {
617 long sum = 0;
618 for (i = 0; i < n; i++)
619 sum += solver->grid[transpose(sq[i], w)];
620 fail = (sum != value);
621 break;
622 }
623
624 case C_MUL: {
625 long remaining = value;
626 for (i = 0; i < n; i++) {
627 if (remaining % solver->grid[transpose(sq[i], w)]) {
628 fail = true;
629 break;
630 }
631 remaining /= solver->grid[transpose(sq[i], w)];
632 }
633 if (remaining != 1)
634 fail = true;
635 break;
636 }
637
638 case C_SUB:
639 assert(n == 2);
640 if (value != labs(solver->grid[transpose(sq[0], w)] -
641 solver->grid[transpose(sq[1], w)]))
642 fail = true;
643 break;
644
645 case C_DIV: {
646 int num, den;
647 assert(n == 2);
648 num = max(solver->grid[transpose(sq[0], w)],
649 solver->grid[transpose(sq[1], w)]);
650 den = min(solver->grid[transpose(sq[0], w)],
651 solver->grid[transpose(sq[1], w)]);
652 if (den * value != num)
653 fail = true;
654 break;
655 }
656 }
657
658 if (fail) {
659#ifdef STANDALONE_SOLVER
660 if (solver_show_working) {
661 printf("%*sclue at (%d,%d) is violated\n",
662 solver_recurse_depth*4, "",
663 sq[0]/w+1, sq[0]%w+1);
664 printf("%*s (%s clue with target %ld containing [",
665 solver_recurse_depth*4, "",
666 (op == C_ADD ? "addition" : op == C_SUB ? "subtraction":
667 op == C_MUL ? "multiplication" : "division"), value);
668 for (i = 0; i < n; i++)
669 printf(" %d", (int)solver->grid[transpose(sq[i], w)]);
670 printf(" ]\n");
671 }
672#endif
673 return false;
674 }
675 }
676
677 return true;
678}
679
594static int solver(int w, int *dsf, long *clues, digit *soln, int maxdiff) 680static int solver(int w, int *dsf, long *clues, digit *soln, int maxdiff)
595{ 681{
596 int a = w*w; 682 int a = w*w;
@@ -638,7 +724,7 @@ static int solver(int w, int *dsf, long *clues, digit *soln, int maxdiff)
638 ret = latin_solver(soln, w, maxdiff, 724 ret = latin_solver(soln, w, maxdiff,
639 DIFF_EASY, DIFF_HARD, DIFF_EXTREME, 725 DIFF_EASY, DIFF_HARD, DIFF_EXTREME,
640 DIFF_EXTREME, DIFF_UNREASONABLE, 726 DIFF_EXTREME, DIFF_UNREASONABLE,
641 keen_solvers, &ctx, NULL, NULL); 727 keen_solvers, keen_valid, &ctx, NULL, NULL);
642 728
643 sfree(ctx.dscratch); 729 sfree(ctx.dscratch);
644 sfree(ctx.iscratch); 730 sfree(ctx.iscratch);
diff --git a/apps/plugins/puzzles/src/latin.c b/apps/plugins/puzzles/src/latin.c
index 9d06ccd938..39930166e7 100644
--- a/apps/plugins/puzzles/src/latin.c
+++ b/apps/plugins/puzzles/src/latin.c
@@ -19,8 +19,8 @@
19static int latin_solver_top(struct latin_solver *solver, int maxdiff, 19static int latin_solver_top(struct latin_solver *solver, int maxdiff,
20 int diff_simple, int diff_set_0, int diff_set_1, 20 int diff_simple, int diff_set_0, int diff_set_1,
21 int diff_forcing, int diff_recursive, 21 int diff_forcing, int diff_recursive,
22 usersolver_t const *usersolvers, void *ctx, 22 usersolver_t const *usersolvers, validator_t valid,
23 ctxnew_t ctxnew, ctxfree_t ctxfree); 23 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree);
24 24
25#ifdef STANDALONE_SOLVER 25#ifdef STANDALONE_SOLVER
26int solver_show_working, solver_recurse_depth; 26int solver_show_working, solver_recurse_depth;
@@ -711,7 +711,7 @@ int latin_solver_diff_set(struct latin_solver *solver,
711static int latin_solver_recurse 711static int latin_solver_recurse
712 (struct latin_solver *solver, int diff_simple, int diff_set_0, 712 (struct latin_solver *solver, int diff_simple, int diff_set_0,
713 int diff_set_1, int diff_forcing, int diff_recursive, 713 int diff_set_1, int diff_forcing, int diff_recursive,
714 usersolver_t const *usersolvers, void *ctx, 714 usersolver_t const *usersolvers, validator_t valid, void *ctx,
715 ctxnew_t ctxnew, ctxfree_t ctxfree) 715 ctxnew_t ctxnew, ctxfree_t ctxfree)
716{ 716{
717 int best, bestcount; 717 int best, bestcount;
@@ -817,7 +817,8 @@ static int latin_solver_recurse
817 ret = latin_solver_top(&subsolver, diff_recursive, 817 ret = latin_solver_top(&subsolver, diff_recursive,
818 diff_simple, diff_set_0, diff_set_1, 818 diff_simple, diff_set_0, diff_set_1,
819 diff_forcing, diff_recursive, 819 diff_forcing, diff_recursive,
820 usersolvers, newctx, ctxnew, ctxfree); 820 usersolvers, valid, newctx,
821 ctxnew, ctxfree);
821 latin_solver_free(&subsolver); 822 latin_solver_free(&subsolver);
822 if (ctxnew) 823 if (ctxnew)
823 ctxfree(newctx); 824 ctxfree(newctx);
@@ -879,8 +880,8 @@ static int latin_solver_recurse
879static int latin_solver_top(struct latin_solver *solver, int maxdiff, 880static int latin_solver_top(struct latin_solver *solver, int maxdiff,
880 int diff_simple, int diff_set_0, int diff_set_1, 881 int diff_simple, int diff_set_0, int diff_set_1,
881 int diff_forcing, int diff_recursive, 882 int diff_forcing, int diff_recursive,
882 usersolver_t const *usersolvers, void *ctx, 883 usersolver_t const *usersolvers, validator_t valid,
883 ctxnew_t ctxnew, ctxfree_t ctxfree) 884 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree)
884{ 885{
885 struct latin_solver_scratch *scratch = latin_solver_new_scratch(solver); 886 struct latin_solver_scratch *scratch = latin_solver_new_scratch(solver);
886 int ret, diff = diff_simple; 887 int ret, diff = diff_simple;
@@ -941,7 +942,8 @@ static int latin_solver_top(struct latin_solver *solver, int maxdiff,
941 int nsol = latin_solver_recurse(solver, 942 int nsol = latin_solver_recurse(solver,
942 diff_simple, diff_set_0, diff_set_1, 943 diff_simple, diff_set_0, diff_set_1,
943 diff_forcing, diff_recursive, 944 diff_forcing, diff_recursive,
944 usersolvers, ctx, ctxnew, ctxfree); 945 usersolvers, valid, ctx,
946 ctxnew, ctxfree);
945 if (nsol < 0) diff = diff_impossible; 947 if (nsol < 0) diff = diff_impossible;
946 else if (nsol == 1) diff = diff_recursive; 948 else if (nsol == 1) diff = diff_recursive;
947 else if (nsol > 1) diff = diff_ambiguous; 949 else if (nsol > 1) diff = diff_ambiguous;
@@ -990,6 +992,17 @@ static int latin_solver_top(struct latin_solver *solver, int maxdiff,
990 } 992 }
991#endif 993#endif
992 994
995 if (diff != diff_impossible && diff != diff_unfinished &&
996 diff != diff_ambiguous && valid && !valid(solver, ctx)) {
997#ifdef STANDALONE_SOLVER
998 if (solver_show_working) {
999 printf("%*ssolution failed final validation!\n",
1000 solver_recurse_depth*4, "");
1001 }
1002#endif
1003 diff = diff_impossible;
1004 }
1005
993 latin_solver_free_scratch(scratch); 1006 latin_solver_free_scratch(scratch);
994 1007
995 return diff; 1008 return diff;
@@ -998,8 +1011,8 @@ static int latin_solver_top(struct latin_solver *solver, int maxdiff,
998int latin_solver_main(struct latin_solver *solver, int maxdiff, 1011int latin_solver_main(struct latin_solver *solver, int maxdiff,
999 int diff_simple, int diff_set_0, int diff_set_1, 1012 int diff_simple, int diff_set_0, int diff_set_1,
1000 int diff_forcing, int diff_recursive, 1013 int diff_forcing, int diff_recursive,
1001 usersolver_t const *usersolvers, void *ctx, 1014 usersolver_t const *usersolvers, validator_t valid,
1002 ctxnew_t ctxnew, ctxfree_t ctxfree) 1015 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree)
1003{ 1016{
1004 int diff; 1017 int diff;
1005#ifdef STANDALONE_SOLVER 1018#ifdef STANDALONE_SOLVER
@@ -1027,7 +1040,7 @@ int latin_solver_main(struct latin_solver *solver, int maxdiff,
1027 diff = latin_solver_top(solver, maxdiff, 1040 diff = latin_solver_top(solver, maxdiff,
1028 diff_simple, diff_set_0, diff_set_1, 1041 diff_simple, diff_set_0, diff_set_1,
1029 diff_forcing, diff_recursive, 1042 diff_forcing, diff_recursive,
1030 usersolvers, ctx, ctxnew, ctxfree); 1043 usersolvers, valid, ctx, ctxnew, ctxfree);
1031 1044
1032#ifdef STANDALONE_SOLVER 1045#ifdef STANDALONE_SOLVER
1033 sfree(names); 1046 sfree(names);
@@ -1040,8 +1053,8 @@ int latin_solver_main(struct latin_solver *solver, int maxdiff,
1040int latin_solver(digit *grid, int o, int maxdiff, 1053int latin_solver(digit *grid, int o, int maxdiff,
1041 int diff_simple, int diff_set_0, int diff_set_1, 1054 int diff_simple, int diff_set_0, int diff_set_1,
1042 int diff_forcing, int diff_recursive, 1055 int diff_forcing, int diff_recursive,
1043 usersolver_t const *usersolvers, void *ctx, 1056 usersolver_t const *usersolvers, validator_t valid,
1044 ctxnew_t ctxnew, ctxfree_t ctxfree) 1057 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree)
1045{ 1058{
1046 struct latin_solver solver; 1059 struct latin_solver solver;
1047 int diff; 1060 int diff;
@@ -1050,7 +1063,7 @@ int latin_solver(digit *grid, int o, int maxdiff,
1050 diff = latin_solver_main(&solver, maxdiff, 1063 diff = latin_solver_main(&solver, maxdiff,
1051 diff_simple, diff_set_0, diff_set_1, 1064 diff_simple, diff_set_0, diff_set_1,
1052 diff_forcing, diff_recursive, 1065 diff_forcing, diff_recursive,
1053 usersolvers, ctx, ctxnew, ctxfree); 1066 usersolvers, valid, ctx, ctxnew, ctxfree);
1054 latin_solver_free(&solver); 1067 latin_solver_free(&solver);
1055 return diff; 1068 return diff;
1056} 1069}
diff --git a/apps/plugins/puzzles/src/latin.h b/apps/plugins/puzzles/src/latin.h
index ff6f07c922..bb172ec3c7 100644
--- a/apps/plugins/puzzles/src/latin.h
+++ b/apps/plugins/puzzles/src/latin.h
@@ -85,6 +85,7 @@ int latin_solver_diff_set(struct latin_solver *solver,
85 bool extreme); 85 bool extreme);
86 86
87typedef int (*usersolver_t)(struct latin_solver *solver, void *ctx); 87typedef int (*usersolver_t)(struct latin_solver *solver, void *ctx);
88typedef bool (*validator_t)(struct latin_solver *solver, void *ctx);
88typedef void *(*ctxnew_t)(void *ctx); 89typedef void *(*ctxnew_t)(void *ctx);
89typedef void (*ctxfree_t)(void *ctx); 90typedef void (*ctxfree_t)(void *ctx);
90 91
@@ -96,15 +97,15 @@ enum { diff_impossible = 10, diff_ambiguous, diff_unfinished };
96int latin_solver(digit *grid, int o, int maxdiff, 97int latin_solver(digit *grid, int o, int maxdiff,
97 int diff_simple, int diff_set_0, int diff_set_1, 98 int diff_simple, int diff_set_0, int diff_set_1,
98 int diff_forcing, int diff_recursive, 99 int diff_forcing, int diff_recursive,
99 usersolver_t const *usersolvers, void *ctx, 100 usersolver_t const *usersolvers, validator_t valid,
100 ctxnew_t ctxnew, ctxfree_t ctxfree); 101 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree);
101 102
102/* Version you can call if you want to alloc and free latin_solver yourself */ 103/* Version you can call if you want to alloc and free latin_solver yourself */
103int latin_solver_main(struct latin_solver *solver, int maxdiff, 104int latin_solver_main(struct latin_solver *solver, int maxdiff,
104 int diff_simple, int diff_set_0, int diff_set_1, 105 int diff_simple, int diff_set_0, int diff_set_1,
105 int diff_forcing, int diff_recursive, 106 int diff_forcing, int diff_recursive,
106 usersolver_t const *usersolvers, void *ctx, 107 usersolver_t const *usersolvers, validator_t valid,
107 ctxnew_t ctxnew, ctxfree_t ctxfree); 108 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree);
108 109
109void latin_solver_debug(unsigned char *cube, int o); 110void latin_solver_debug(unsigned char *cube, int o);
110 111
diff --git a/apps/plugins/puzzles/src/mines.c b/apps/plugins/puzzles/src/mines.c
index c9d9852573..ae717d3f37 100644
--- a/apps/plugins/puzzles/src/mines.c
+++ b/apps/plugins/puzzles/src/mines.c
@@ -258,6 +258,8 @@ static const char *validate_params(const game_params *params, bool full)
258 */ 258 */
259 if (full && params->unique && (params->w <= 2 || params->h <= 2)) 259 if (full && params->unique && (params->w <= 2 || params->h <= 2))
260 return "Width and height must both be greater than two"; 260 return "Width and height must both be greater than two";
261 if (params->n < 0)
262 return "Mine count may not be negative";
261 if (params->n > params->w * params->h - 9) 263 if (params->n > params->w * params->h - 9)
262 return "Too many mines for grid size"; 264 return "Too many mines for grid size";
263 if (params->n < 1) 265 if (params->n < 1)
diff --git a/apps/plugins/puzzles/src/pattern.c b/apps/plugins/puzzles/src/pattern.c
index 42f3fc55ce..a43982f452 100644
--- a/apps/plugins/puzzles/src/pattern.c
+++ b/apps/plugins/puzzles/src/pattern.c
@@ -20,6 +20,7 @@ enum {
20 COL_GRID, 20 COL_GRID,
21 COL_CURSOR, 21 COL_CURSOR,
22 COL_ERROR, 22 COL_ERROR,
23 COL_CURSOR_GUIDE,
23 NCOLOURS 24 NCOLOURS
24}; 25};
25 26
@@ -1660,11 +1661,12 @@ static float *game_colours(frontend *fe, int *ncolours)
1660 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); 1661 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1661 1662
1662 for (i = 0; i < 3; i++) { 1663 for (i = 0; i < 3; i++) {
1663 ret[COL_GRID * 3 + i] = 0.3F; 1664 ret[COL_GRID * 3 + i] = 0.3F;
1664 ret[COL_UNKNOWN * 3 + i] = 0.5F; 1665 ret[COL_UNKNOWN * 3 + i] = 0.5F;
1665 ret[COL_TEXT * 3 + i] = 0.0F; 1666 ret[COL_TEXT * 3 + i] = 0.0F;
1666 ret[COL_FULL * 3 + i] = 0.0F; 1667 ret[COL_FULL * 3 + i] = 0.0F;
1667 ret[COL_EMPTY * 3 + i] = 1.0F; 1668 ret[COL_EMPTY * 3 + i] = 1.0F;
1669 ret[COL_CURSOR_GUIDE * 3 + i] = 0.5F;
1668 } 1670 }
1669 ret[COL_CURSOR * 3 + 0] = 1.0F; 1671 ret[COL_CURSOR * 3 + 0] = 1.0F;
1670 ret[COL_CURSOR * 3 + 1] = 0.25F; 1672 ret[COL_CURSOR * 3 + 1] = 0.25F;
@@ -1891,6 +1893,9 @@ static void game_redraw(drawing *dr, game_drawstate *ds,
1891 */ 1893 */
1892 for (i = 0; i < state->common->w + state->common->h; i++) { 1894 for (i = 0; i < state->common->w + state->common->h; i++) {
1893 int colour = check_errors(state, i) ? COL_ERROR : COL_TEXT; 1895 int colour = check_errors(state, i) ? COL_ERROR : COL_TEXT;
1896 if (colour == COL_TEXT && ((cx >= 0 && i == cx) || (cy >= 0 && i == cy + ds->w))) {
1897 colour = COL_CURSOR_GUIDE;
1898 }
1894 if (ds->numcolours[i] != colour) { 1899 if (ds->numcolours[i] != colour) {
1895 draw_numbers(dr, ds, state, i, true, colour); 1900 draw_numbers(dr, ds, state, i, true, colour);
1896 ds->numcolours[i] = colour; 1901 ds->numcolours[i] = colour;
diff --git a/apps/plugins/puzzles/src/printing.c b/apps/plugins/puzzles/src/printing.c
index 98fdd841d3..d1a3badaaa 100644
--- a/apps/plugins/puzzles/src/printing.c
+++ b/apps/plugins/puzzles/src/printing.c
@@ -3,6 +3,8 @@
3 * setup and layout. 3 * setup and layout.
4 */ 4 */
5 5
6#include <assert.h>
7
6#include "puzzles.h" 8#include "puzzles.h"
7 9
8struct puzzle { 10struct puzzle {
@@ -88,7 +90,7 @@ void document_add_puzzle(document *doc, const game *game, game_params *par,
88 doc->got_solns = true; 90 doc->got_solns = true;
89} 91}
90 92
91static void get_puzzle_size(document *doc, struct puzzle *pz, 93static void get_puzzle_size(const document *doc, struct puzzle *pz,
92 float *w, float *h, float *scale) 94 float *w, float *h, float *scale)
93{ 95{
94 float ww, hh, ourscale; 96 float ww, hh, ourscale;
@@ -115,133 +117,177 @@ static void get_puzzle_size(document *doc, struct puzzle *pz,
115} 117}
116 118
117/* 119/*
118 * Having accumulated a load of puzzles, actually do the printing. 120 * Calculate the the number of pages for a document.
119 */ 121 */
120void document_print(document *doc, drawing *dr) 122int document_npages(const document *doc)
121{ 123{
122 int ppp; /* puzzles per page */ 124 int ppp; /* puzzles per page */
123 int pages, passes; 125 int pages, passes;
126
127 ppp = doc->pw * doc->ph;
128 pages = (doc->npuzzles + ppp - 1) / ppp;
129 passes = (doc->got_solns ? 2 : 1);
130
131 return pages * passes;
132}
133
134/*
135 * Begin a document.
136 */
137void document_begin(const document *doc, drawing *dr)
138{
139 print_begin_doc(dr, document_npages(doc));
140}
141
142/*
143 * End a document.
144 */
145void document_end(const document *doc, drawing *dr)
146{
147 print_end_doc(dr);
148}
149
150/*
151 * Print a single page of a document.
152 */
153void document_print_page(const document *doc, drawing *dr, int page_nr)
154{
155 int ppp; /* puzzles per page */
156 int pages;
124 int page, pass; 157 int page, pass;
125 int pageno; 158 int pageno;
159 int i, n, offset;
160 float colsum, rowsum;
126 161
127 ppp = doc->pw * doc->ph; 162 ppp = doc->pw * doc->ph;
128 pages = (doc->npuzzles + ppp - 1) / ppp; 163 pages = (doc->npuzzles + ppp - 1) / ppp;
129 passes = (doc->got_solns ? 2 : 1);
130 164
131 print_begin_doc(dr, pages * passes); 165 /* Get the current page, pass, and pageno based on page_nr. */
132 166 if (page_nr < pages) {
133 pageno = 1; 167 page = page_nr;
134 for (pass = 0; pass < passes; pass++) { 168 pass = 0;
135 for (page = 0; page < pages; page++) { 169 }
136 int i, n, offset; 170 else {
137 float colsum, rowsum; 171 assert(doc->got_solns);
138 172 page = page_nr - pages;
139 print_begin_page(dr, pageno); 173 pass = 1;
140 174 }
141 offset = page * ppp; 175 pageno = page_nr + 1;
142 n = min(ppp, doc->npuzzles - offset); 176
143 177 offset = page * ppp;
144 for (i = 0; i < doc->pw; i++) 178 n = min(ppp, doc->npuzzles - offset);
145 doc->colwid[i] = 0; 179
146 for (i = 0; i < doc->ph; i++) 180 print_begin_page(dr, pageno);
147 doc->rowht[i] = 0; 181
148 182 for (i = 0; i < doc->pw; i++)
149 /* 183 doc->colwid[i] = 0;
150 * Lay the page out by computing all the puzzle sizes. 184 for (i = 0; i < doc->ph; i++)
151 */ 185 doc->rowht[i] = 0;
152 for (i = 0; i < n; i++) { 186
153 struct puzzle *pz = doc->puzzles + offset + i; 187 /*
154 int x = i % doc->pw, y = i / doc->pw; 188 * Lay the page out by computing all the puzzle sizes.
155 float w, h, scale; 189 */
156 190 for (i = 0; i < n; i++) {
157 get_puzzle_size(doc, pz, &w, &h, &scale); 191 struct puzzle *pz = doc->puzzles + offset + i;
158 192 int x = i % doc->pw, y = i / doc->pw;
159 /* Update the maximum width/height of this column. */ 193 float w, h, scale;
160 doc->colwid[x] = max(doc->colwid[x], w); 194
161 doc->rowht[y] = max(doc->rowht[y], h); 195 get_puzzle_size(doc, pz, &w, &h, &scale);
162 } 196
163 197 /* Update the maximum width/height of this column. */
164 /* 198 doc->colwid[x] = max(doc->colwid[x], w);
165 * Add up the maximum column/row widths to get the 199 doc->rowht[y] = max(doc->rowht[y], h);
166 * total amount of space used up by puzzles on the 200 }
167 * page. We will use this to compute gutter widths. 201
168 */ 202 /*
169 colsum = 0.0; 203 * Add up the maximum column/row widths to get the
170 for (i = 0; i < doc->pw; i++) 204 * total amount of space used up by puzzles on the
171 colsum += doc->colwid[i]; 205 * page. We will use this to compute gutter widths.
172 rowsum = 0.0; 206 */
173 for (i = 0; i < doc->ph; i++) 207 colsum = 0.0;
174 rowsum += doc->rowht[i]; 208 for (i = 0; i < doc->pw; i++)
175 209 colsum += doc->colwid[i];
176 /* 210 rowsum = 0.0;
177 * Now do the printing. 211 for (i = 0; i < doc->ph; i++)
178 */ 212 rowsum += doc->rowht[i];
179 for (i = 0; i < n; i++) { 213
180 struct puzzle *pz = doc->puzzles + offset + i; 214 /*
181 int x = i % doc->pw, y = i / doc->pw, j; 215 * Now do the printing.
182 float w, h, scale, xm, xc, ym, yc; 216 */
183 int pixw, pixh, tilesize; 217 for (i = 0; i < n; i++) {
184 218 struct puzzle *pz = doc->puzzles + offset + i;
185 if (pass == 1 && !pz->st2) 219 int x = i % doc->pw, y = i / doc->pw, j;
186 continue; /* nothing to do */ 220 float w, h, scale, xm, xc, ym, yc;
187 221 int pixw, pixh, tilesize;
188 /* 222
189 * The total amount of gutter space is the page 223 if (pass == 1 && !pz->st2)
190 * width minus colsum. This is divided into pw+1 224 continue; /* nothing to do */
191 * gutters, so the amount of horizontal gutter 225
192 * space appearing to the left of this puzzle 226 /*
193 * column is 227 * The total amount of gutter space is the page
194 * 228 * width minus colsum. This is divided into pw+1
195 * (width-colsum) * (x+1)/(pw+1) 229 * gutters, so the amount of horizontal gutter
196 * = width * (x+1)/(pw+1) - (colsum * (x+1)/(pw+1)) 230 * space appearing to the left of this puzzle
197 */ 231 * column is
198 xm = (float)(x+1) / (doc->pw + 1); 232 *
199 xc = -xm * colsum; 233 * (width-colsum) * (x+1)/(pw+1)
200 /* And similarly for y. */ 234 * = width * (x+1)/(pw+1) - (colsum * (x+1)/(pw+1))
201 ym = (float)(y+1) / (doc->ph + 1); 235 */
202 yc = -ym * rowsum; 236 xm = (float)(x+1) / (doc->pw + 1);
203 237 xc = -xm * colsum;
204 /* 238 /* And similarly for y. */
205 * However, the amount of space to the left of this 239 ym = (float)(y+1) / (doc->ph + 1);
206 * puzzle isn't just gutter space: we must also 240 yc = -ym * rowsum;
207 * count the widths of all the previous columns. 241
208 */ 242 /*
209 for (j = 0; j < x; j++) 243 * However, the amount of space to the left of this
210 xc += doc->colwid[j]; 244 * puzzle isn't just gutter space: we must also
211 /* And similarly for rows. */ 245 * count the widths of all the previous columns.
212 for (j = 0; j < y; j++) 246 */
213 yc += doc->rowht[j]; 247 for (j = 0; j < x; j++)
214 248 xc += doc->colwid[j];
215 /* 249 /* And similarly for rows. */
216 * Now we adjust for this _specific_ puzzle, which 250 for (j = 0; j < y; j++)
217 * means centring it within the cell we've just 251 yc += doc->rowht[j];
218 * computed. 252
219 */ 253 /*
220 get_puzzle_size(doc, pz, &w, &h, &scale); 254 * Now we adjust for this _specific_ puzzle, which
221 xc += (doc->colwid[x] - w) / 2; 255 * means centring it within the cell we've just
222 yc += (doc->rowht[y] - h) / 2; 256 * computed.
223 257 */
224 /* 258 get_puzzle_size(doc, pz, &w, &h, &scale);
225 * And now we know where and how big we want to 259 xc += (doc->colwid[x] - w) / 2;
226 * print the puzzle, just go ahead and do so. For 260 yc += (doc->rowht[y] - h) / 2;
227 * the moment I'll pick a standard pixel tile size 261
228 * of 512. 262 /*
229 * 263 * And now we know where and how big we want to
230 * (FIXME: would it be better to pick this value 264 * print the puzzle, just go ahead and do so. For
231 * with reference to the printer resolution? Or 265 * the moment I'll pick a standard pixel tile size
232 * permit each game to choose its own?) 266 * of 512.
233 */ 267 *
234 tilesize = 512; 268 * (FIXME: would it be better to pick this value
235 pz->game->compute_size(pz->par, tilesize, &pixw, &pixh); 269 * with reference to the printer resolution? Or
236 print_begin_puzzle(dr, xm, xc, ym, yc, pixw, pixh, w, scale); 270 * permit each game to choose its own?)
237 pz->game->print(dr, pass == 0 ? pz->st : pz->st2, tilesize); 271 */
238 print_end_puzzle(dr); 272 tilesize = 512;
239 } 273 pz->game->compute_size(pz->par, tilesize, &pixw, &pixh);
240 274 print_begin_puzzle(dr, xm, xc, ym, yc, pixw, pixh, w, scale);
241 print_end_page(dr, pageno); 275 pz->game->print(dr, pass == 0 ? pz->st : pz->st2, tilesize);
242 pageno++; 276 print_end_puzzle(dr);
243 }
244 } 277 }
245 278
279 print_end_page(dr, pageno);
280}
281
282/*
283 * Having accumulated a load of puzzles, actually do the printing.
284 */
285void document_print(const document *doc, drawing *dr)
286{
287 int page, pages;
288 pages = document_npages(doc);
289 print_begin_doc(dr, pages);
290 for (page = 0; page < pages; page++)
291 document_print_page(doc, dr, page);
246 print_end_doc(dr); 292 print_end_doc(dr);
247} 293}
diff --git a/apps/plugins/puzzles/src/ps.c b/apps/plugins/puzzles/src/ps.c
index 94a708648a..ab8a1589f4 100644
--- a/apps/plugins/puzzles/src/ps.c
+++ b/apps/plugins/puzzles/src/ps.c
@@ -9,8 +9,6 @@
9 9
10#include "puzzles.h" 10#include "puzzles.h"
11 11
12#define ROOT2 1.414213562
13
14struct psdata { 12struct psdata {
15 FILE *fp; 13 FILE *fp;
16 bool colour; 14 bool colour;
diff --git a/apps/plugins/puzzles/src/puzzles.but b/apps/plugins/puzzles/src/puzzles.but
index e22e63d544..ee519b8aa1 100644
--- a/apps/plugins/puzzles/src/puzzles.but
+++ b/apps/plugins/puzzles/src/puzzles.but
@@ -3360,7 +3360,8 @@ This software is \i{copyright} 2004-2014 Simon Tatham.
3360 3360
3361Portions copyright Richard Boulton, James Harvey, Mike Pinna, Jonas 3361Portions copyright Richard Boulton, James Harvey, Mike Pinna, Jonas
3362K\u00F6{oe}lker, Dariusz Olszewski, Michael Schierl, Lambros Lambrou, 3362K\u00F6{oe}lker, Dariusz Olszewski, Michael Schierl, Lambros Lambrou,
3363Bernd Schmidt, Steffen Bauer, Lennard Sprong and Rogier Goossens. 3363Bernd Schmidt, Steffen Bauer, Lennard Sprong, Rogier Goossens, Michael
3364Quevillon and Asher Gordon.
3364 3365
3365Permission is hereby granted, free of charge, to any person 3366Permission is hereby granted, free of charge, to any person
3366obtaining a copy of this software and associated documentation files 3367obtaining a copy of this software and associated documentation files
diff --git a/apps/plugins/puzzles/src/puzzles.h b/apps/plugins/puzzles/src/puzzles.h
index 1732abe3e9..45ae321cc6 100644
--- a/apps/plugins/puzzles/src/puzzles.h
+++ b/apps/plugins/puzzles/src/puzzles.h
@@ -11,6 +11,7 @@
11#include <stdbool.h> 11#include <stdbool.h>
12 12
13#define PI 3.141592653589793238462643383279502884197169399 13#define PI 3.141592653589793238462643383279502884197169399
14#define ROOT2 1.414213562373095048801688724209698078569672
14 15
15#define lenof(array) ( sizeof(array) / sizeof(*(array)) ) 16#define lenof(array) ( sizeof(array) / sizeof(*(array)) )
16 17
@@ -530,7 +531,11 @@ document *document_new(int pw, int ph, float userscale);
530void document_free(document *doc); 531void document_free(document *doc);
531void document_add_puzzle(document *doc, const game *game, game_params *par, 532void document_add_puzzle(document *doc, const game *game, game_params *par,
532 game_state *st, game_state *st2); 533 game_state *st, game_state *st2);
533void document_print(document *doc, drawing *dr); 534int document_npages(const document *doc);
535void document_begin(const document *doc, drawing *dr);
536void document_end(const document *doc, drawing *dr);
537void document_print_page(const document *doc, drawing *dr, int page_nr);
538void document_print(const document *doc, drawing *dr);
534 539
535/* 540/*
536 * ps.c 541 * ps.c
diff --git a/apps/plugins/puzzles/src/towers.c b/apps/plugins/puzzles/src/towers.c
index a72cae680d..aee088fb54 100644
--- a/apps/plugins/puzzles/src/towers.c
+++ b/apps/plugins/puzzles/src/towers.c
@@ -574,6 +574,38 @@ static int solver_hard(struct latin_solver *solver, void *vctx)
574#define SOLVER(upper,title,func,lower) func, 574#define SOLVER(upper,title,func,lower) func,
575static usersolver_t const towers_solvers[] = { DIFFLIST(SOLVER) }; 575static usersolver_t const towers_solvers[] = { DIFFLIST(SOLVER) };
576 576
577static bool towers_valid(struct latin_solver *solver, void *vctx)
578{
579 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
580 int w = ctx->w;
581 int c, i, n, best, clue, start, step;
582 for (c = 0; c < 4*w; c++) {
583 clue = ctx->clues[c];
584 if (!clue)
585 continue;
586
587 STARTSTEP(start, step, c, w);
588 n = best = 0;
589 for (i = 0; i < w; i++) {
590 if (solver->grid[start+i*step] > best) {
591 best = solver->grid[start+i*step];
592 n++;
593 }
594 }
595
596 if (n != clue) {
597#ifdef STANDALONE_SOLVER
598 if (solver_show_working)
599 printf("%*sclue %s %d is violated\n",
600 solver_recurse_depth*4, "",
601 cluepos[c/w], c%w+1);
602#endif
603 return false;
604 }
605 }
606 return true;
607}
608
577static int solver(int w, int *clues, digit *soln, int maxdiff) 609static int solver(int w, int *clues, digit *soln, int maxdiff)
578{ 610{
579 int ret; 611 int ret;
@@ -589,7 +621,7 @@ static int solver(int w, int *clues, digit *soln, int maxdiff)
589 ret = latin_solver(soln, w, maxdiff, 621 ret = latin_solver(soln, w, maxdiff,
590 DIFF_EASY, DIFF_HARD, DIFF_EXTREME, 622 DIFF_EASY, DIFF_HARD, DIFF_EXTREME,
591 DIFF_EXTREME, DIFF_UNREASONABLE, 623 DIFF_EXTREME, DIFF_UNREASONABLE,
592 towers_solvers, &ctx, NULL, NULL); 624 towers_solvers, towers_valid, &ctx, NULL, NULL);
593 625
594 sfree(ctx.iscratch); 626 sfree(ctx.iscratch);
595 sfree(ctx.dscratch); 627 sfree(ctx.dscratch);
diff --git a/apps/plugins/puzzles/src/tracks.R b/apps/plugins/puzzles/src/tracks.R
index f88dfb03eb..8b0ac97e0f 100644
--- a/apps/plugins/puzzles/src/tracks.R
+++ b/apps/plugins/puzzles/src/tracks.R
@@ -8,6 +8,9 @@ tracks : [G] WINDOWS COMMON tracks TRACKS_EXTRA tracks.res|noicon.res
8 8
9ALL += tracks[COMBINED] TRACKS_EXTRA 9ALL += tracks[COMBINED] TRACKS_EXTRA
10 10
11trackssolver : [U] tracks[STANDALONE_SOLVER] TRACKS_EXTRA STANDALONE
12trackssolver : [C] tracks[STANDALONE_SOLVER] TRACKS_EXTRA STANDALONE
13
11!begin am gtk 14!begin am gtk
12GAMES += tracks 15GAMES += tracks
13!end 16!end
diff --git a/apps/plugins/puzzles/src/tracks.c b/apps/plugins/puzzles/src/tracks.c
index 8f29faa0fd..924836afa9 100644
--- a/apps/plugins/puzzles/src/tracks.c
+++ b/apps/plugins/puzzles/src/tracks.c
@@ -12,6 +12,7 @@
12 * #113 8x8:gCx5xAf,1,S4,2,5,4,6,2,3,4,2,5,2,S4,4,5,1 12 * #113 8x8:gCx5xAf,1,S4,2,5,4,6,2,3,4,2,5,2,S4,4,5,1
13 * #114 8x8:p5fAzkAb,1,6,3,3,3,S6,2,3,5,4,S3,3,5,1,5,1 13 * #114 8x8:p5fAzkAb,1,6,3,3,3,S6,2,3,5,4,S3,3,5,1,5,1
14 * #115 8x8:zi9d5tAb,1,3,4,5,3,S4,2,4,2,6,2,3,6,S3,3,1 14 * #115 8x8:zi9d5tAb,1,3,4,5,3,S4,2,4,2,6,2,3,6,S3,3,1
15 * #942 8x8:n5iCfAzAe,2,2,S5,5,3,5,4,5,4,5,2,S5,3,4,5,3
15 */ 16 */
16 17
17#include <stdio.h> 18#include <stdio.h>
@@ -29,9 +30,11 @@
29 * Difficulty levels. I do some macro ickery here to ensure that my 30 * Difficulty levels. I do some macro ickery here to ensure that my
30 * enum and the various forms of my name list always match up. 31 * enum and the various forms of my name list always match up.
31 */ 32 */
32#define DIFFLIST(A) \ 33#define DIFFLIST(A) \
33 A(EASY,Easy,e) \ 34 A(EASY,Easy,e) \
34 A(TRICKY,Tricky,t) 35 A(TRICKY,Tricky,t) \
36 A(HARD,Hard,h) \
37 /* end of list */
35 38
36#define ENUM(upper,title,lower) DIFF_ ## upper, 39#define ENUM(upper,title,lower) DIFF_ ## upper,
37#define TITLE(upper,title,lower) #title, 40#define TITLE(upper,title,lower) #title,
@@ -65,10 +68,12 @@ static const struct game_params tracks_presets[] = {
65 {10, 8, DIFF_TRICKY, 1 }, 68 {10, 8, DIFF_TRICKY, 1 },
66 {10, 10, DIFF_EASY, 1}, 69 {10, 10, DIFF_EASY, 1},
67 {10, 10, DIFF_TRICKY, 1}, 70 {10, 10, DIFF_TRICKY, 1},
71 {10, 10, DIFF_HARD, 1},
68 {15, 10, DIFF_EASY, 1}, 72 {15, 10, DIFF_EASY, 1},
69 {15, 10, DIFF_TRICKY, 1}, 73 {15, 10, DIFF_TRICKY, 1},
70 {15, 15, DIFF_EASY, 1}, 74 {15, 15, DIFF_EASY, 1},
71 {15, 15, DIFF_TRICKY, 1}, 75 {15, 15, DIFF_TRICKY, 1},
76 {15, 15, DIFF_HARD, 1},
72}; 77};
73 78
74static bool game_fetch_preset(int i, char **name, game_params **params) 79static bool game_fetch_preset(int i, char **name, game_params **params)
@@ -452,7 +457,7 @@ start:
452 state->numbers->col_s = px; 457 state->numbers->col_s = px;
453} 458}
454 459
455static int tracks_solve(game_state *state, int diff); 460static int tracks_solve(game_state *state, int diff, int *max_diff_out);
456static void debug_state(game_state *state, const char *what); 461static void debug_state(game_state *state, const char *what);
457 462
458/* Clue-setting algorithm: 463/* Clue-setting algorithm:
@@ -533,6 +538,26 @@ static game_state *copy_and_strip(const game_state *state, game_state *ret, int
533 return ret; 538 return ret;
534} 539}
535 540
541#ifdef STANDALONE_SOLVER
542#include <stdarg.h>
543static FILE *solver_diagnostics_fp = NULL;
544static void solver_diagnostic(const char *fmt, ...)
545{
546 va_list ap;
547 va_start(ap, fmt);
548 vfprintf(solver_diagnostics_fp, fmt, ap);
549 va_end(ap);
550 fputc('\n', solver_diagnostics_fp);
551}
552#define solverdebug(printf_params) do { \
553 if (solver_diagnostics_fp) { \
554 solver_diagnostic printf_params; \
555 } \
556 } while (0)
557#else
558#define solverdebug(printf_params) ((void)0)
559#endif
560
536static int solve_progress(const game_state *state) { 561static int solve_progress(const game_state *state) {
537 int i, w = state->p.w, h = state->p.h, progress = 0; 562 int i, w = state->p.w, h = state->p.h, progress = 0;
538 563
@@ -575,6 +600,7 @@ static int add_clues(game_state *state, random_state *rs, int diff)
575 int *positions = snewn(w*h, int), npositions = 0; 600 int *positions = snewn(w*h, int), npositions = 0;
576 int *nedges_previous_solve = snewn(w*h, int); 601 int *nedges_previous_solve = snewn(w*h, int);
577 game_state *scratch = dup_game(state); 602 game_state *scratch = dup_game(state);
603 int diff_used;
578 604
579 debug_state(state, "gen: Initial board"); 605 debug_state(state, "gen: Initial board");
580 606
@@ -591,17 +617,13 @@ static int add_clues(game_state *state, random_state *rs, int diff)
591 617
592 /* First, check whether the puzzle is already either too easy, or just right */ 618 /* First, check whether the puzzle is already either too easy, or just right */
593 scratch = copy_and_strip(state, scratch, -1); 619 scratch = copy_and_strip(state, scratch, -1);
594 if (diff > 0) { 620 sr = tracks_solve(scratch, diff, &diff_used);
595 sr = tracks_solve(scratch, diff-1); 621 if (diff_used < diff) {
596 if (sr < 0) 622 ret = -1; /* already too easy, even without adding clues. */
597 assert(!"Generator should not have created impossible puzzle"); 623 debug(("gen: ...already too easy, need new board."));
598 if (sr > 0) { 624 goto done;
599 ret = -1; /* already too easy, even without adding clues. */
600 debug(("gen: ...already too easy, need new board."));
601 goto done;
602 }
603 } 625 }
604 sr = tracks_solve(scratch, diff); 626
605 if (sr < 0) 627 if (sr < 0)
606 assert(!"Generator should not have created impossible puzzle"); 628 assert(!"Generator should not have created impossible puzzle");
607 if (sr > 0) { 629 if (sr > 0) {
@@ -629,12 +651,10 @@ static int add_clues(game_state *state, random_state *rs, int diff)
629 if (check_phantom_moves(scratch)) 651 if (check_phantom_moves(scratch))
630 continue; /* adding a clue here would add phantom track */ 652 continue; /* adding a clue here would add phantom track */
631 653
632 if (diff > 0) { 654 if (tracks_solve(scratch, diff, &diff_used) > 0) {
633 if (tracks_solve(scratch, diff-1) > 0) { 655 if (diff_used < diff) {
634 continue; /* adding a clue here makes it too easy */ 656 continue; /* adding a clue here makes it too easy */
635 } 657 }
636 }
637 if (tracks_solve(scratch, diff) > 0) {
638 /* we're now soluble (and we weren't before): add this clue, and then 658 /* we're now soluble (and we weren't before): add this clue, and then
639 start stripping clues */ 659 start stripping clues */
640 debug(("gen: ...adding clue at (%d,%d), now soluble", i%w, i/w)); 660 debug(("gen: ...adding clue at (%d,%d), now soluble", i%w, i/w));
@@ -676,7 +696,7 @@ strip_clues:
676 if (check_phantom_moves(scratch)) 696 if (check_phantom_moves(scratch))
677 continue; /* removing a clue here would add phantom track */ 697 continue; /* removing a clue here would add phantom track */
678 698
679 if (tracks_solve(scratch, diff) > 0) { 699 if (tracks_solve(scratch, diff, NULL) > 0) {
680 debug(("gen: ... removing clue at (%d,%d), still soluble without it", i%w, i/w)); 700 debug(("gen: ... removing clue at (%d,%d), still soluble without it", i%w, i/w));
681 state->sflags[i] &= ~S_CLUE; /* still soluble without this clue. */ 701 state->sflags[i] &= ~S_CLUE; /* still soluble without this clue. */
682 } 702 }
@@ -686,6 +706,7 @@ strip_clues:
686 706
687done: 707done:
688 sfree(positions); 708 sfree(positions);
709 sfree(nedges_previous_solve);
689 free_game(scratch); 710 free_game(scratch);
690 return ret; 711 return ret;
691} 712}
@@ -780,7 +801,7 @@ newpath:
780 } 801 }
781 *p++ = '\0'; 802 *p++ = '\0';
782 803
783 ret = tracks_solve(state, DIFFCOUNT); 804 ret = tracks_solve(state, DIFFCOUNT, NULL);
784 assert(ret >= 0); 805 assert(ret >= 0);
785 free_game(state); 806 free_game(state);
786 807
@@ -882,6 +903,10 @@ static game_state *new_game(midend *me, const game_params *params, const char *d
882 return state; 903 return state;
883} 904}
884 905
906struct solver_scratch {
907 int *dsf;
908};
909
885static int solve_set_sflag(game_state *state, int x, int y, 910static int solve_set_sflag(game_state *state, int x, int y,
886 unsigned int f, const char *why) 911 unsigned int f, const char *why)
887{ 912{
@@ -889,10 +914,10 @@ static int solve_set_sflag(game_state *state, int x, int y,
889 914
890 if (state->sflags[i] & f) 915 if (state->sflags[i] & f)
891 return 0; 916 return 0;
892 debug(("solve: square (%d,%d) -> %s: %s", 917 solverdebug(("square (%d,%d) -> %s: %s",
893 x, y, (f == S_TRACK ? "TRACK" : "NOTRACK"), why)); 918 x, y, (f == S_TRACK ? "TRACK" : "NOTRACK"), why));
894 if (state->sflags[i] & (f == S_TRACK ? S_NOTRACK : S_TRACK)) { 919 if (state->sflags[i] & (f == S_TRACK ? S_NOTRACK : S_TRACK)) {
895 debug(("solve: opposite flag already set there, marking IMPOSSIBLE")); 920 solverdebug(("opposite flag already set there, marking IMPOSSIBLE"));
896 state->impossible = true; 921 state->impossible = true;
897 } 922 }
898 state->sflags[i] |= f; 923 state->sflags[i] |= f;
@@ -906,11 +931,11 @@ static int solve_set_eflag(game_state *state, int x, int y, int d,
906 931
907 if (sf & f) 932 if (sf & f)
908 return 0; 933 return 0;
909 debug(("solve: edge (%d,%d)/%c -> %s: %s", x, y, 934 solverdebug(("edge (%d,%d)/%c -> %s: %s", x, y,
910 (d == U) ? 'U' : (d == D) ? 'D' : (d == L) ? 'L' : 'R', 935 (d == U) ? 'U' : (d == D) ? 'D' : (d == L) ? 'L' : 'R',
911 (f == S_TRACK ? "TRACK" : "NOTRACK"), why)); 936 (f == S_TRACK ? "TRACK" : "NOTRACK"), why));
912 if (sf & (f == E_TRACK ? E_NOTRACK : E_TRACK)) { 937 if (sf & (f == E_TRACK ? E_NOTRACK : E_TRACK)) {
913 debug(("solve: opposite flag already set there, marking IMPOSSIBLE")); 938 solverdebug(("opposite flag already set there, marking IMPOSSIBLE"));
914 state->impossible = true; 939 state->impossible = true;
915 } 940 }
916 S_E_SET(state, x, y, d, f); 941 S_E_SET(state, x, y, d, f);
@@ -1063,7 +1088,7 @@ static int solve_check_single_sub(game_state *state, int si, int id, int n,
1063 if (ctrack != (target-1)) return 0; 1088 if (ctrack != (target-1)) return 0;
1064 if (nperp > 0 || n1edge != 1) return 0; 1089 if (nperp > 0 || n1edge != 1) return 0;
1065 1090
1066 debug(("check_single from (%d,%d): 1 match from (%d,%d)", 1091 solverdebug(("check_single from (%d,%d): 1 match from (%d,%d)",
1067 si%w, si/w, i1edge%w, i1edge/w)); 1092 si%w, si/w, i1edge%w, i1edge/w));
1068 1093
1069 /* We have a match: anything that's more than 1 away from this square 1094 /* We have a match: anything that's more than 1 away from this square
@@ -1120,12 +1145,12 @@ static int solve_check_loose_sub(game_state *state, int si, int id, int n,
1120 } 1145 }
1121 1146
1122 if (nloose > (target - e2count)) { 1147 if (nloose > (target - e2count)) {
1123 debug(("check %s from (%d,%d): more loose (%d) than empty (%d), IMPOSSIBLE", 1148 solverdebug(("check %s from (%d,%d): more loose (%d) than empty (%d), IMPOSSIBLE",
1124 what, si%w, si/w, nloose, target-e2count)); 1149 what, si%w, si/w, nloose, target-e2count));
1125 state->impossible = true; 1150 state->impossible = true;
1126 } 1151 }
1127 if (nloose > 0 && nloose == (target - e2count)) { 1152 if (nloose > 0 && nloose == (target - e2count)) {
1128 debug(("check %s from (%d,%d): nloose = empty (%d), forcing loners out.", 1153 solverdebug(("check %s from (%d,%d): nloose = empty (%d), forcing loners out.",
1129 what, si%w, si/w, nloose)); 1154 what, si%w, si/w, nloose));
1130 for (j = 0, i = si; j < n; j++, i += id) { 1155 for (j = 0, i = si; j < n; j++, i += id) {
1131 if (!(state->sflags[i] & S_MARK)) 1156 if (!(state->sflags[i] & S_MARK))
@@ -1146,7 +1171,7 @@ static int solve_check_loose_sub(game_state *state, int si, int id, int n,
1146 } 1171 }
1147 } 1172 }
1148 if (nloose == 1 && (target - e2count) == 2 && nperp == 0) { 1173 if (nloose == 1 && (target - e2count) == 2 && nperp == 0) {
1149 debug(("check %s from (%d,%d): 1 loose end, 2 empty squares, forcing parallel", 1174 solverdebug(("check %s from (%d,%d): 1 loose end, 2 empty squares, forcing parallel",
1150 what, si%w, si/w)); 1175 what, si%w, si/w));
1151 for (j = 0, i = si; j < n; j++, i += id) { 1176 for (j = 0, i = si; j < n; j++, i += id) {
1152 if (!(state->sflags[i] & S_MARK)) 1177 if (!(state->sflags[i] & S_MARK))
@@ -1176,6 +1201,110 @@ static int solve_check_loose_ends(game_state *state)
1176 return did; 1201 return did;
1177} 1202}
1178 1203
1204static void solve_check_neighbours_count(
1205 game_state *state, int start, int step, int n, int clueindex,
1206 bool *onefill, bool *oneempty)
1207{
1208 int to_fill = state->numbers->numbers[clueindex];
1209 int to_empty = n - to_fill;
1210 int i;
1211 for (i = 0; i < n; i++) {
1212 int p = start + i*step;
1213 if (state->sflags[p] & S_TRACK)
1214 to_fill--;
1215 if (state->sflags[p] & S_NOTRACK)
1216 to_empty--;
1217 }
1218 *onefill = (to_fill == 1);
1219 *oneempty = (to_empty == 1);
1220}
1221
1222static int solve_check_neighbours_try(game_state *state, int x, int y,
1223 int X, int Y, bool onefill,
1224 bool oneempty, unsigned dir,
1225 const char *what)
1226{
1227 int w = state->p.w, p = y*w+x, P = Y*w+X;
1228
1229 /*
1230 * We're given a neighbouring pair of squares p,P, with 'dir'
1231 * being the direction from the former to the latter. We aim to
1232 * spot situations in which, if p is a track square, then P must
1233 * also be one (because p doesn't have enough free exits to avoid
1234 * using the one that goes towards P).
1235 *
1236 * Then, if the target number of track squares on their shared
1237 * row/column says that there's only one track square left to
1238 * place, it can't be p, because P would have to be one too,
1239 * violating the clue. So in that situation we can mark p as
1240 * unfilled. Conversely, if there's only one _non_-track square
1241 * left to place, it can't be P, so we can mark P as filled.
1242 */
1243
1244 if ((state->sflags[p] | state->sflags[P]) & (S_TRACK | S_NOTRACK))
1245 return 0; /* no need: we already know something about these squares */
1246
1247 int possible_exits_except_dir = nbits[
1248 ALLDIR & ~dir & ~S_E_DIRS(state, x, y, E_NOTRACK)];
1249 if (possible_exits_except_dir >= 2)
1250 return 0; /* square p need not connect to P, even if it is filled */
1251
1252 /* OK, now we know that if p is filled, P must be filled too. */
1253
1254 int did = 0;
1255 if (onefill) {
1256 /* But at most one of them can be filled, so it can't be p. */
1257 state->sflags[p] |= S_NOTRACK;
1258 solverdebug(("square (%d,%d) -> NOTRACK: otherwise, that and (%d,%d) "
1259 "would make too many TRACK in %s", x, y, X, Y, what));
1260 did++;
1261 }
1262 if (oneempty) {
1263 /* Alternatively, at least one of them _must_ be filled, so P
1264 * must be. */
1265 state->sflags[P] |= S_TRACK;
1266 solverdebug(("square (%d,%d) -> TRACK: otherwise, that and (%d,%d) "
1267 "would make too many NOTRACK in %s", X, Y, x, y, what));
1268 did++;
1269 }
1270 return did;
1271}
1272
1273static int solve_check_neighbours(game_state *state, bool both_ways)
1274{
1275 int w = state->p.w, h = state->p.h, x, y, did = 0;
1276 bool onefill, oneempty;
1277
1278 for (x = 0; x < w; x++) {
1279 solve_check_neighbours_count(state, x, w, h, x, &onefill, &oneempty);
1280 if (!both_ways)
1281 oneempty = false; /* disable the harder version of the deduction */
1282 if (!onefill && !oneempty)
1283 continue;
1284 for (y = 0; y+1 < h; y++) {
1285 did += solve_check_neighbours_try(state, x, y, x, y+1,
1286 onefill, oneempty, D, "column");
1287 did += solve_check_neighbours_try(state, x, y+1, x, y,
1288 onefill, oneempty, U, "column");
1289 }
1290 }
1291 for (y = 0; y < h; y++) {
1292 solve_check_neighbours_count(state, y*w, 1, w, w+y,
1293 &onefill, &oneempty);
1294 if (!both_ways)
1295 oneempty = false; /* disable the harder version of the deduction */
1296 if (!onefill && !oneempty)
1297 continue;
1298 for (x = 0; x+1 < w; x++) {
1299 did += solve_check_neighbours_try(state, x, y, x+1, y,
1300 onefill, oneempty, R, "row");
1301 did += solve_check_neighbours_try(state, x+1, y, x, y,
1302 onefill, oneempty, L, "row");
1303 }
1304 }
1305 return did;
1306}
1307
1179static int solve_check_loop_sub(game_state *state, int x, int y, int dir, 1308static int solve_check_loop_sub(game_state *state, int x, int y, int dir,
1180 int *dsf, int startc, int endc) 1309 int *dsf, int startc, int endc)
1181{ 1310{
@@ -1195,7 +1324,7 @@ static int solve_check_loop_sub(game_state *state, int x, int y, int dir,
1195 return solve_set_eflag(state, x, y, dir, E_NOTRACK, "would close loop"); 1324 return solve_set_eflag(state, x, y, dir, E_NOTRACK, "would close loop");
1196 } 1325 }
1197 if ((ic == startc && jc == endc) || (ic == endc && jc == startc)) { 1326 if ((ic == startc && jc == endc) || (ic == endc && jc == startc)) {
1198 debug(("Adding link at (%d,%d) would join start to end", x, y)); 1327 solverdebug(("Adding link at (%d,%d) would join start to end", x, y));
1199 /* We mustn't join the start to the end if: 1328 /* We mustn't join the start to the end if:
1200 - there are other bits of track that aren't attached to either end 1329 - there are other bits of track that aren't attached to either end
1201 - the clues are not fully satisfied yet 1330 - the clues are not fully satisfied yet
@@ -1287,10 +1416,145 @@ static void solve_discount_edge(game_state *state, int x, int y, int d)
1287 solve_set_eflag(state, x, y, d, E_NOTRACK, "outer edge"); 1416 solve_set_eflag(state, x, y, d, E_NOTRACK, "outer edge");
1288} 1417}
1289 1418
1290static int tracks_solve(game_state *state, int diff) 1419static int solve_bridge_sub(game_state *state, int x, int y, int d,
1420 struct solver_scratch *sc)
1421{
1422 /*
1423 * Imagine a graph on the squares of the grid, with an edge
1424 * connecting neighbouring squares only if it's not yet known
1425 * whether there's a track between them.
1426 *
1427 * This function is called if the edge between x,y and X,Y is a
1428 * bridge in that graph: that is, it's not part of any loop in the
1429 * graph, or equivalently, removing it would increase the number
1430 * of connected components in the graph.
1431 *
1432 * In that situation, we can fill in the edge by a parity
1433 * argument. Construct a closed loop of edges in the grid, all of
1434 * whose states are known except this one. The track starts and
1435 * ends outside this loop, so it must cross the boundary of the
1436 * loop an even number of times. So if we count up how many times
1437 * the track is known to cross the edges of our loop, then we can
1438 * fill in the last edge in whichever way makes that number even.
1439 *
1440 * In fact, there's not even any need to go to the effort of
1441 * constructing a _single_ closed loop. The simplest thing is to
1442 * delete the bridge edge from the graph, find a connected
1443 * component of the reduced graph whose boundary includes that
1444 * edge, and take every edge separating that component from
1445 * another. This may not lead to _exactly one_ cycle - the
1446 * component could be non-simply connected and have a hole in the
1447 * middle - but that doesn't matter, because the same parity
1448 * constraint applies just as well with more than one disjoint
1449 * loop.
1450 */
1451 int w = state->p.w, h = state->p.h, wh = w*h;
1452 int X = x + DX(d), Y = y + DY(d);
1453 int xi, yi, di;
1454
1455 assert(d == D || d == R);
1456
1457 if (!sc->dsf)
1458 sc->dsf = snew_dsf(wh);
1459 dsf_init(sc->dsf, wh);
1460
1461 for (xi = 0; xi < w; xi++) {
1462 for (yi = 0; yi < h; yi++) {
1463 /* We expect to have been called with X,Y either to the
1464 * right of x,y or below it, not the other way round. If
1465 * that were not true, the tests in this loop to exclude
1466 * the bridge edge would have to be twice as annoying. */
1467
1468 if (yi+1 < h && !S_E_FLAGS(state, xi, yi, D) &&
1469 !(xi == x && yi == y && xi == X && yi+1 == Y))
1470 dsf_merge(sc->dsf, yi*w+xi, (yi+1)*w+xi);
1471
1472 if (xi+1 < w && !S_E_FLAGS(state, xi, yi, R) &&
1473 !(xi == x && yi == y && xi+1 == X && yi == Y))
1474 dsf_merge(sc->dsf, yi*w+xi, yi*w+(xi+1));
1475 }
1476 }
1477
1478 int component = dsf_canonify(sc->dsf, y*w+x);
1479 int parity = 0;
1480 for (xi = 0; xi < w; xi++) {
1481 for (yi = 0; yi < h; yi++) {
1482 if (dsf_canonify(sc->dsf, yi*w+xi) != component)
1483 continue;
1484 for (di = 1; di < 16; di *= 2) {
1485 int Xi = xi + DX(di), Yi = yi + DY(di);
1486 if ((Xi < 0 || Xi >= w || Yi < 0 || Yi >= h ||
1487 dsf_canonify(sc->dsf, Yi*w+Xi) != component) &&
1488 (S_E_DIRS(state, xi, yi, E_TRACK) & di))
1489 parity ^= 1;
1490 }
1491 }
1492 }
1493
1494 solve_set_eflag(state, x, y, d, parity ? E_TRACK : E_NOTRACK, "parity");
1495 return 1;
1496}
1497
1498struct solve_bridge_neighbour_ctx {
1499 game_state *state;
1500 int x, y, dirs;
1501};
1502static int solve_bridge_neighbour(int vertex, void *vctx)
1503{
1504 struct solve_bridge_neighbour_ctx *ctx =
1505 (struct solve_bridge_neighbour_ctx *)vctx;
1506 int w = ctx->state->p.w;
1507
1508 if (vertex >= 0) {
1509 ctx->x = vertex % w;
1510 ctx->y = vertex / w;
1511 ctx->dirs = ALLDIR
1512 & ~S_E_DIRS(ctx->state, ctx->x, ctx->y, E_TRACK)
1513 & ~S_E_DIRS(ctx->state, ctx->x, ctx->y, E_NOTRACK);
1514 }
1515 unsigned dir = ctx->dirs & -ctx->dirs; /* isolate lowest set bit */
1516 if (!dir)
1517 return -1;
1518 ctx->dirs &= ~dir;
1519 int xr = ctx->x + DX(dir), yr = ctx->y + DY(dir);
1520 assert(0 <= xr && xr < w);
1521 assert(0 <= yr && yr < ctx->state->p.h);
1522 return yr * w + xr;
1523}
1524
1525static int solve_check_bridge_parity(game_state *state,
1526 struct solver_scratch *sc)
1527{
1528 int w = state->p.w, h = state->p.h, wh = w*h;
1529 struct findloopstate *fls;
1530 struct solve_bridge_neighbour_ctx ctx[1];
1531 int x, y, did = 0;
1532
1533 ctx->state = state;
1534 fls = findloop_new_state(wh);
1535 findloop_run(fls, wh, solve_bridge_neighbour, ctx);
1536
1537 for (x = 0; x < w; x++) {
1538 for (y = 0; y < h; y++) {
1539 if (y+1 < h && !findloop_is_loop_edge(fls, y*w+x, (y+1)*w+x))
1540 did += solve_bridge_sub(state, x, y, D, sc);
1541 if (x+1 < w && !findloop_is_loop_edge(fls, y*w+x, y*w+(x+1)))
1542 did += solve_bridge_sub(state, x, y, R, sc);
1543 }
1544 }
1545
1546 findloop_free_state(fls);
1547
1548 return did;
1549}
1550
1551static int tracks_solve(game_state *state, int diff, int *max_diff_out)
1291{ 1552{
1292 int x, y, w = state->p.w, h = state->p.h; 1553 int x, y, w = state->p.w, h = state->p.h;
1293 bool didsth; 1554 struct solver_scratch sc[1];
1555 int max_diff = DIFF_EASY;
1556
1557 sc->dsf = NULL;
1294 1558
1295 debug(("solve...")); 1559 debug(("solve..."));
1296 state->impossible = false; 1560 state->impossible = false;
@@ -1305,21 +1569,37 @@ static int tracks_solve(game_state *state, int diff)
1305 solve_discount_edge(state, w-1, y, R); 1569 solve_discount_edge(state, w-1, y, R);
1306 } 1570 }
1307 1571
1308 while (1) { 1572 while (!state->impossible) {
1309 didsth = false;
1310 1573
1311 didsth |= solve_update_flags(state); 1574/* Can't use do ... while (0) because we need a 'continue' in this macro */
1312 didsth |= solve_count_clues(state); 1575#define TRY(curr_diff, funcall) \
1313 didsth |= solve_check_loop(state); 1576 if (diff >= (curr_diff) && (funcall)) { \
1577 if (max_diff < curr_diff) \
1578 max_diff = curr_diff; \
1579 continue; \
1580 } else ((void)0)
1314 1581
1315 if (diff >= DIFF_TRICKY) { 1582 TRY(DIFF_EASY, solve_update_flags(state));
1316 didsth |= solve_check_single(state); 1583 TRY(DIFF_EASY, solve_count_clues(state));
1317 didsth |= solve_check_loose_ends(state); 1584 TRY(DIFF_EASY, solve_check_loop(state));
1318 }
1319 1585
1320 if (!didsth || state->impossible) break; 1586 TRY(DIFF_TRICKY, solve_check_single(state));
1587 TRY(DIFF_TRICKY, solve_check_loose_ends(state));
1588 TRY(DIFF_TRICKY, solve_check_neighbours(state, false));
1589
1590 TRY(DIFF_HARD, solve_check_neighbours(state, true));
1591 TRY(DIFF_HARD, solve_check_bridge_parity(state, sc));
1592
1593#undef TRY
1594
1595 break;
1321 } 1596 }
1322 1597
1598 sfree(sc->dsf);
1599
1600 if (max_diff_out)
1601 *max_diff_out = max_diff;
1602
1323 return state->impossible ? -1 : check_completion(state, false) ? 1 : 0; 1603 return state->impossible ? -1 : check_completion(state, false) ? 1 : 0;
1324} 1604}
1325 1605
@@ -1379,11 +1659,11 @@ static char *solve_game(const game_state *state, const game_state *currstate,
1379 char *move; 1659 char *move;
1380 1660
1381 solved = dup_game(currstate); 1661 solved = dup_game(currstate);
1382 ret = tracks_solve(solved, DIFFCOUNT); 1662 ret = tracks_solve(solved, DIFFCOUNT, NULL);
1383 if (ret < 1) { 1663 if (ret < 1) {
1384 free_game(solved); 1664 free_game(solved);
1385 solved = dup_game(state); 1665 solved = dup_game(state);
1386 ret = tracks_solve(solved, DIFFCOUNT); 1666 ret = tracks_solve(solved, DIFFCOUNT, NULL);
1387 } 1667 }
1388 1668
1389 if (ret < 1) { 1669 if (ret < 1) {
@@ -2094,7 +2374,7 @@ static game_state *execute_move(const game_state *state, const char *move)
2094 goto badmove; 2374 goto badmove;
2095 move += n; 2375 move += n;
2096 } else if (c == 'H') { 2376 } else if (c == 'H') {
2097 tracks_solve(ret, DIFFCOUNT); 2377 tracks_solve(ret, DIFFCOUNT, NULL);
2098 move++; 2378 move++;
2099 } else { 2379 } else {
2100 goto badmove; 2380 goto badmove;
@@ -2675,4 +2955,87 @@ const struct game thegame = {
2675 0, /* flags */ 2955 0, /* flags */
2676}; 2956};
2677 2957
2958#ifdef STANDALONE_SOLVER
2959
2960int main(int argc, char **argv)
2961{
2962 game_params *p;
2963 game_state *s;
2964 char *id = NULL, *desc;
2965 int maxdiff = DIFFCOUNT, diff_used;
2966 const char *err;
2967 bool diagnostics = false, grade = false;
2968 int retd;
2969
2970 while (--argc > 0) {
2971 char *p = *++argv;
2972 if (!strcmp(p, "-v")) {
2973 diagnostics = true;
2974 } else if (!strcmp(p, "-g")) {
2975 grade = true;
2976 } else if (!strncmp(p, "-d", 2) && p[2] && !p[3]) {
2977 int i;
2978 bool bad = true;
2979 for (i = 0; i < lenof(tracks_diffchars); i++)
2980 if (tracks_diffchars[i] == p[2]) {
2981 bad = false;
2982 maxdiff = i;
2983 break;
2984 }
2985 if (bad) {
2986 fprintf(stderr, "%s: unrecognised difficulty `%c'\n",
2987 argv[0], p[2]);
2988 return 1;
2989 }
2990 } else if (*p == '-') {
2991 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2992 return 1;
2993 } else {
2994 id = p;
2995 }
2996 }
2997
2998 if (!id) {
2999 fprintf(stderr, "usage: %s [-v | -g] <game_id>\n", argv[0]);
3000 return 1;
3001 }
3002
3003 desc = strchr(id, ':');
3004 if (!desc) {
3005 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
3006 return 1;
3007 }
3008 *desc++ = '\0';
3009
3010 p = default_params();
3011 decode_params(p, id);
3012 err = validate_desc(p, desc);
3013 if (err) {
3014 fprintf(stderr, "%s: %s\n", argv[0], err);
3015 return 1;
3016 }
3017 s = new_game(NULL, p, desc);
3018
3019 solver_diagnostics_fp = (diagnostics ? stdout : NULL);
3020 retd = tracks_solve(s, maxdiff, &diff_used);
3021 if (retd < 0) {
3022 printf("Puzzle is inconsistent\n");
3023 } else if (grade) {
3024 printf("Difficulty rating: %s\n",
3025 (retd == 0 ? "Ambiguous" : tracks_diffnames[diff_used]));
3026 } else {
3027 char *text = game_text_format(s);
3028 fputs(text, stdout);
3029 sfree(text);
3030 if (retd == 0)
3031 printf("Could not deduce a unique solution\n");
3032 }
3033 free_game(s);
3034 free_params(p);
3035
3036 return 0;
3037}
3038
3039#endif
3040
2678/* vim: set shiftwidth=4 tabstop=8: */ 3041/* vim: set shiftwidth=4 tabstop=8: */
diff --git a/apps/plugins/puzzles/src/twiddle.c b/apps/plugins/puzzles/src/twiddle.c
index 1d91559e37..5f2ea02e6f 100644
--- a/apps/plugins/puzzles/src/twiddle.c
+++ b/apps/plugins/puzzles/src/twiddle.c
@@ -552,6 +552,12 @@ static char *game_text_format(const game_state *state)
552 int i, x, y, col, maxlen; 552 int i, x, y, col, maxlen;
553 bool o = state->orientable; 553 bool o = state->orientable;
554 554
555 /* Pedantic check: ensure buf is large enough to format an int in
556 * decimal, using the bound log10(2) < 1/3. (Obviously in practice
557 * int is not going to be larger than even 32 bits any time soon,
558 * but.) */
559 assert(sizeof(buf) >= 1 + sizeof(int) * CHAR_BIT/3);
560
555 /* 561 /*
556 * First work out how many characters we need to display each 562 * First work out how many characters we need to display each
557 * number. We're pretty flexible on grid contents here, so we 563 * number. We're pretty flexible on grid contents here, so we
@@ -563,6 +569,11 @@ static char *game_text_format(const game_state *state)
563 if (col < x) col = x; 569 if (col < x) col = x;
564 } 570 }
565 571
572 /* Reassure sprintf-checking compilers like gcc that the field
573 * width we've just computed is not now excessive */
574 if (col >= sizeof(buf))
575 col = sizeof(buf)-1;
576
566 /* 577 /*
567 * Now we know the exact total size of the grid we're going to 578 * Now we know the exact total size of the grid we're going to
568 * produce: it's got h rows, each containing w lots of col+o, 579 * produce: it's got h rows, each containing w lots of col+o,
diff --git a/apps/plugins/puzzles/src/unequal.c b/apps/plugins/puzzles/src/unequal.c
index 951e9ac80f..556cf01c45 100644
--- a/apps/plugins/puzzles/src/unequal.c
+++ b/apps/plugins/puzzles/src/unequal.c
@@ -816,6 +816,74 @@ static int solver_set(struct latin_solver *solver, void *vctx)
816#define SOLVER(upper,title,func,lower) func, 816#define SOLVER(upper,title,func,lower) func,
817static usersolver_t const unequal_solvers[] = { DIFFLIST(SOLVER) }; 817static usersolver_t const unequal_solvers[] = { DIFFLIST(SOLVER) };
818 818
819static bool unequal_valid(struct latin_solver *solver, void *vctx)
820{
821 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
822 if (ctx->state->mode == MODE_ADJACENT) {
823 int o = solver->o;
824 int x, y, nx, ny, v, nv, i;
825
826 for (x = 0; x+1 < o; x++) {
827 for (y = 0; y+1 < o; y++) {
828 v = grid(x, y);
829 for (i = 0; i < 4; i++) {
830 bool is_adj, should_be_adj;
831
832 should_be_adj =
833 (GRID(ctx->state, flags, x, y) & adjthan[i].f);
834
835 nx = x + adjthan[i].dx, ny = y + adjthan[i].dy;
836 if (nx < 0 || ny < 0 || nx >= o || ny >= o)
837 continue;
838
839 nv = grid(nx, ny);
840 is_adj = (labs(v - nv) == 1);
841
842 if (is_adj && !should_be_adj) {
843#ifdef STANDALONE_SOLVER
844 if (solver_show_working)
845 printf("%*s(%d,%d):%d and (%d,%d):%d have "
846 "adjacent values, but should not\n",
847 solver_recurse_depth*4, "",
848 x+1, y+1, v, nx+1, ny+1, nv);
849#endif
850 return false;
851 }
852
853 if (!is_adj && should_be_adj) {
854#ifdef STANDALONE_SOLVER
855 if (solver_show_working)
856 printf("%*s(%d,%d):%d and (%d,%d):%d do not have "
857 "adjacent values, but should\n",
858 solver_recurse_depth*4, "",
859 x+1, y+1, v, nx+1, ny+1, nv);
860#endif
861 return false;
862 }
863 }
864 }
865 }
866 } else {
867 int i;
868 for (i = 0; i < ctx->nlinks; i++) {
869 struct solver_link *link = &ctx->links[i];
870 int gv = grid(link->gx, link->gy);
871 int lv = grid(link->lx, link->ly);
872 if (gv <= lv) {
873#ifdef STANDALONE_SOLVER
874 if (solver_show_working)
875 printf("%*s(%d,%d):%d should be greater than (%d,%d):%d, "
876 "but is not\n", solver_recurse_depth*4, "",
877 link->gx+1, link->gy+1, gv,
878 link->lx+1, link->ly+1, lv);
879#endif
880 return false;
881 }
882 }
883 }
884 return true;
885}
886
819static int solver_state(game_state *state, int maxdiff) 887static int solver_state(game_state *state, int maxdiff)
820{ 888{
821 struct solver_ctx *ctx = new_ctx(state); 889 struct solver_ctx *ctx = new_ctx(state);
@@ -827,7 +895,8 @@ static int solver_state(game_state *state, int maxdiff)
827 diff = latin_solver_main(&solver, maxdiff, 895 diff = latin_solver_main(&solver, maxdiff,
828 DIFF_LATIN, DIFF_SET, DIFF_EXTREME, 896 DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
829 DIFF_EXTREME, DIFF_RECURSIVE, 897 DIFF_EXTREME, DIFF_RECURSIVE,
830 unequal_solvers, ctx, clone_ctx, free_ctx); 898 unequal_solvers, unequal_valid, ctx,
899 clone_ctx, free_ctx);
831 900
832 memcpy(state->hints, solver.cube, state->order*state->order*state->order); 901 memcpy(state->hints, solver.cube, state->order*state->order*state->order);
833 902
@@ -2155,7 +2224,8 @@ static int solve(game_params *p, char *desc, int debug)
2155 diff = latin_solver_main(&solver, DIFF_RECURSIVE, 2224 diff = latin_solver_main(&solver, DIFF_RECURSIVE,
2156 DIFF_LATIN, DIFF_SET, DIFF_EXTREME, 2225 DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
2157 DIFF_EXTREME, DIFF_RECURSIVE, 2226 DIFF_EXTREME, DIFF_RECURSIVE,
2158 unequal_solvers, ctx, clone_ctx, free_ctx); 2227 unequal_solvers, unequal_valid, ctx,
2228 clone_ctx, free_ctx);
2159 2229
2160 free_ctx(ctx); 2230 free_ctx(ctx);
2161 2231
diff --git a/apps/plugins/puzzles/src/unfinished/group.c b/apps/plugins/puzzles/src/unfinished/group.c
index ef7ffba349..006a9e0ee6 100644
--- a/apps/plugins/puzzles/src/unfinished/group.c
+++ b/apps/plugins/puzzles/src/unfinished/group.c
@@ -43,7 +43,7 @@
43#define DIFFLIST(A) \ 43#define DIFFLIST(A) \
44 A(TRIVIAL,Trivial,NULL,t) \ 44 A(TRIVIAL,Trivial,NULL,t) \
45 A(NORMAL,Normal,solver_normal,n) \ 45 A(NORMAL,Normal,solver_normal,n) \
46 A(HARD,Hard,NULL,h) \ 46 A(HARD,Hard,solver_hard,h) \
47 A(EXTREME,Extreme,NULL,x) \ 47 A(EXTREME,Extreme,NULL,x) \
48 A(UNREASONABLE,Unreasonable,NULL,u) 48 A(UNREASONABLE,Unreasonable,NULL,u)
49#define ENUM(upper,title,func,lower) DIFF_ ## upper, 49#define ENUM(upper,title,func,lower) DIFF_ ## upper,
@@ -280,6 +280,23 @@ static const char *validate_params(const game_params *params, bool full)
280 * Solver. 280 * Solver.
281 */ 281 */
282 282
283static int find_identity(struct latin_solver *solver)
284{
285 int w = solver->o;
286 digit *grid = solver->grid;
287 int i, j;
288
289 for (i = 0; i < w; i++)
290 for (j = 0; j < w; j++) {
291 if (grid[i*w+j] == i+1)
292 return j+1;
293 if (grid[i*w+j] == j+1)
294 return i+1;
295 }
296
297 return 0;
298}
299
283static int solver_normal(struct latin_solver *solver, void *vctx) 300static int solver_normal(struct latin_solver *solver, void *vctx)
284{ 301{
285 int w = solver->o; 302 int w = solver->o;
@@ -295,9 +312,9 @@ static int solver_normal(struct latin_solver *solver, void *vctx)
295 * So we pick any a,b,c we like; then if we know ab, bc, and 312 * So we pick any a,b,c we like; then if we know ab, bc, and
296 * (ab)c we can fill in a(bc). 313 * (ab)c we can fill in a(bc).
297 */ 314 */
298 for (i = 1; i < w; i++) 315 for (i = 0; i < w; i++)
299 for (j = 1; j < w; j++) 316 for (j = 0; j < w; j++)
300 for (k = 1; k < w; k++) { 317 for (k = 0; k < w; k++) {
301 if (!grid[i*w+j] || !grid[j*w+k]) 318 if (!grid[i*w+j] || !grid[j*w+k])
302 continue; 319 continue;
303 if (grid[(grid[i*w+j]-1)*w+k] && 320 if (grid[(grid[i*w+j]-1)*w+k] &&
@@ -358,12 +375,206 @@ static int solver_normal(struct latin_solver *solver, void *vctx)
358 } 375 }
359 } 376 }
360 377
378 /*
379 * Fill in the row and column for the group identity, if it's not
380 * already known and if we've just found out what it is.
381 */
382 i = find_identity(solver);
383 if (i) {
384 bool done_something = false;
385 for (j = 1; j <= w; j++) {
386 if (!grid[(i-1)*w+(j-1)] || !grid[(j-1)*w+(i-1)]) {
387 done_something = true;
388 }
389 }
390 if (done_something) {
391#ifdef STANDALONE_SOLVER
392 if (solver_show_working) {
393 printf("%*s%s is the group identity\n",
394 solver_recurse_depth*4, "", names[i-1]);
395 }
396#endif
397 for (j = 1; j <= w; j++) {
398 if (!grid[(j-1)*w+(i-1)]) {
399 if (!cube(i-1, j-1, j)) {
400#ifdef STANDALONE_SOLVER
401 if (solver_show_working) {
402 printf("%*s but %s cannot go at (%d,%d) - "
403 "contradiction!\n",
404 solver_recurse_depth*4, "",
405 names[j-1], i, j);
406 }
407#endif
408 return -1;
409 }
410#ifdef STANDALONE_SOLVER
411 if (solver_show_working) {
412 printf("%*s placing %s at (%d,%d)\n",
413 solver_recurse_depth*4, "",
414 names[j-1], i, j);
415 }
416#endif
417 latin_solver_place(solver, i-1, j-1, j);
418 }
419 if (!grid[(i-1)*w+(j-1)]) {
420 if (!cube(j-1, i-1, j)) {
421#ifdef STANDALONE_SOLVER
422 if (solver_show_working) {
423 printf("%*s but %s cannot go at (%d,%d) - "
424 "contradiction!\n",
425 solver_recurse_depth*4, "",
426 names[j-1], j, i);
427 }
428#endif
429 return -1;
430 }
431#ifdef STANDALONE_SOLVER
432 if (solver_show_working) {
433 printf("%*s placing %s at (%d,%d)\n",
434 solver_recurse_depth*4, "",
435 names[j-1], j, i);
436 }
437#endif
438 latin_solver_place(solver, j-1, i-1, j);
439 }
440 }
441 return 1;
442 }
443 }
444
361 return 0; 445 return 0;
362} 446}
363 447
448static int solver_hard(struct latin_solver *solver, void *vctx)
449{
450 bool done_something = false;
451 int w = solver->o;
452#ifdef STANDALONE_SOLVER
453 char **names = solver->names;
454#endif
455 int i, j;
456
457 /*
458 * In identity-hidden mode, systematically rule out possibilities
459 * for the group identity.
460 *
461 * In solver_normal, we used the fact that any filled square in
462 * the grid whose contents _does_ match one of the elements it's
463 * the product of - that is, ab=a or ab=b - tells you immediately
464 * that the other element is the identity.
465 *
466 * Here, we use the flip side of that: any filled square in the
467 * grid whose contents does _not_ match either its row or column -
468 * that is, if ab is neither a nor b - tells you immediately that
469 * _neither_ of those elements is the identity. And if that's
470 * true, then we can also immediately rule out the possibility
471 * that it acts as the identity on any element at all.
472 */
473 for (i = 0; i < w; i++) {
474 bool i_can_be_id = true;
475#ifdef STANDALONE_SOLVER
476 char title[80];
477#endif
478
479 for (j = 0; j < w; j++) {
480 if (grid(i,j) && grid(i,j) != j+1) {
481#ifdef STANDALONE_SOLVER
482 if (solver_show_working)
483 sprintf(title, "%s cannot be the identity: "
484 "%s%s = %s =/= %s", names[i], names[i], names[j],
485 names[grid(i,j)-1], names[j]);
486#endif
487 i_can_be_id = false;
488 break;
489 }
490 if (grid(j,i) && grid(j,i) != j+1) {
491#ifdef STANDALONE_SOLVER
492 if (solver_show_working)
493 sprintf(title, "%s cannot be the identity: "
494 "%s%s = %s =/= %s", names[i], names[j], names[i],
495 names[grid(j,i)-1], names[j]);
496#endif
497 i_can_be_id = false;
498 break;
499 }
500 }
501
502 if (!i_can_be_id) {
503 /* Now rule out ij=j or ji=j for all j. */
504 for (j = 0; j < w; j++) {
505 if (cube(i, j, j+1)) {
506#ifdef STANDALONE_SOLVER
507 if (solver_show_working) {
508 if (title[0]) {
509 printf("%*s%s\n", solver_recurse_depth*4, "",
510 title);
511 title[0] = '\0';
512 }
513 printf("%*s ruling out %s at (%d,%d)\n",
514 solver_recurse_depth*4, "", names[j], i, j);
515 }
516#endif
517 cube(i, j, j+1) = false;
518 }
519 if (cube(j, i, j+1)) {
520#ifdef STANDALONE_SOLVER
521 if (solver_show_working) {
522 if (title[0]) {
523 printf("%*s%s\n", solver_recurse_depth*4, "",
524 title);
525 title[0] = '\0';
526 }
527 printf("%*s ruling out %s at (%d,%d)\n",
528 solver_recurse_depth*4, "", names[j], j, i);
529 }
530#endif
531 cube(j, i, j+1) = false;
532 }
533 }
534 }
535 }
536
537 return done_something;
538}
539
364#define SOLVER(upper,title,func,lower) func, 540#define SOLVER(upper,title,func,lower) func,
365static usersolver_t const group_solvers[] = { DIFFLIST(SOLVER) }; 541static usersolver_t const group_solvers[] = { DIFFLIST(SOLVER) };
366 542
543static bool group_valid(struct latin_solver *solver, void *ctx)
544{
545 int w = solver->o;
546#ifdef STANDALONE_SOLVER
547 char **names = solver->names;
548#endif
549 int i, j, k;
550
551 for (i = 0; i < w; i++)
552 for (j = 0; j < w; j++)
553 for (k = 0; k < w; k++) {
554 int ij = grid(i, j) - 1;
555 int jk = grid(j, k) - 1;
556 int ij_k = grid(ij, k) - 1;
557 int i_jk = grid(i, jk) - 1;
558 if (ij_k != i_jk) {
559#ifdef STANDALONE_SOLVER
560 if (solver_show_working) {
561 printf("%*sfailure of associativity: "
562 "(%s%s)%s = %s%s = %s but "
563 "%s(%s%s) = %s%s = %s\n",
564 solver_recurse_depth*4, "",
565 names[i], names[j], names[k],
566 names[ij], names[k], names[ij_k],
567 names[i], names[j], names[k],
568 names[i], names[jk], names[i_jk]);
569 }
570#endif
571 return false;
572 }
573 }
574
575 return true;
576}
577
367static int solver(const game_params *params, digit *grid, int maxdiff) 578static int solver(const game_params *params, digit *grid, int maxdiff)
368{ 579{
369 int w = params->w; 580 int w = params->w;
@@ -387,7 +598,7 @@ static int solver(const game_params *params, digit *grid, int maxdiff)
387 ret = latin_solver_main(&solver, maxdiff, 598 ret = latin_solver_main(&solver, maxdiff,
388 DIFF_TRIVIAL, DIFF_HARD, DIFF_EXTREME, 599 DIFF_TRIVIAL, DIFF_HARD, DIFF_EXTREME,
389 DIFF_EXTREME, DIFF_UNREASONABLE, 600 DIFF_EXTREME, DIFF_UNREASONABLE,
390 group_solvers, NULL, NULL, NULL); 601 group_solvers, group_valid, NULL, NULL, NULL);
391 602
392 latin_solver_free(&solver); 603 latin_solver_free(&solver);
393 604
@@ -2183,6 +2394,11 @@ int main(int argc, char **argv)
2183 } 2394 }
2184 2395
2185 if (diff == DIFFCOUNT) { 2396 if (diff == DIFFCOUNT) {
2397 if (really_show_working) {
2398 solver_show_working = true;
2399 memcpy(grid, s->grid, p->w * p->w);
2400 ret = solver(&s->par, grid, DIFFCOUNT - 1);
2401 }
2186 if (grade) 2402 if (grade)
2187 printf("Difficulty rating: ambiguous\n"); 2403 printf("Difficulty rating: ambiguous\n");
2188 else 2404 else
diff --git a/apps/plugins/puzzles/src/unfinished/path.c b/apps/plugins/puzzles/src/unfinished/path.c
index 829fbc6c75..fe5a47fd2a 100644
--- a/apps/plugins/puzzles/src/unfinished/path.c
+++ b/apps/plugins/puzzles/src/unfinished/path.c
@@ -69,6 +69,103 @@
69 */ 69 */
70 70
71/* 71/*
72 * 2020-05-11: some thoughts on a solver.
73 *
74 * Consider this example puzzle, from Wikipedia:
75 *
76 * ---4---
77 * -3--25-
78 * ---31--
79 * ---5---
80 * -------
81 * --1----
82 * 2---4--
83 *
84 * The kind of deduction that a human wants to make here is: which way
85 * does the path between the 4s go? In particular, does it go round
86 * the left of the W-shaped cluster of endpoints, or round the right
87 * of it? It's clear at a glance that it must go to the right, because
88 * _any_ path between the 4s that goes to the left of that cluster, no
89 * matter what detailed direction it takes, will disconnect the
90 * remaining grid squares into two components, with the two 2s not in
91 * the same component. So we immediately know that the path between
92 * the 4s _must_ go round the right-hand side of the grid.
93 *
94 * How do you model that global and topological reasoning in a
95 * computer?
96 *
97 * The most plausible idea I've seen so far is to use fundamental
98 * groups. The fundamental group of loops based at a given point in a
99 * space is a free group, under loop concatenation and up to homotopy,
100 * generated by the loops that go in each direction around each hole
101 * in the space. In this case, the 'holes' are clues, or connected
102 * groups of clues.
103 *
104 * So you might be able to enumerate all the homotopy classes of paths
105 * between (say) the two 4s as follows. Start with any old path
106 * between them (say, find the first one that breadth-first search
107 * will give you). Choose one of the 4s to regard as the base point
108 * (arbitrarily). Then breadth-first search among the space of _paths_
109 * by the following procedure. Given a candidate path, append to it
110 * each of the possible loops that starts from the base point,
111 * circumnavigates one clue cluster, and returns to the base point.
112 * The result will typically be a path that retraces its steps and
113 * self-intersects. Now adjust it homotopically so that it doesn't. If
114 * that can't be done, then we haven't generated a fresh candidate
115 * path; if it can, then we've got a new path that is not homotopic to
116 * any path we already had, so add it to our list and queue it up to
117 * become the starting point of this search later.
118 *
119 * The idea is that this should exhaustively enumerate, up to
120 * homotopy, the different ways in which the two 4s can connect to
121 * each other within the constraint that you have to actually fit the
122 * path non-self-intersectingly into this grid. Then you can keep a
123 * list of those homotopy classes in mind, and start ruling them out
124 * by techniques like the connectivity approach described above.
125 * Hopefully you end up narrowing down to few enough homotopy classes
126 * that you can deduce something concrete about actual squares of the
127 * grid - for example, here, that if the path between 4s has to go
128 * round the right, then we know some specific squares it must go
129 * through, so we can fill those in. And then, having filled in a
130 * piece of the middle of a path, you can now regard connecting the
131 * ultimate endpoints to that mid-section as two separate subproblems,
132 * so you've reduced to a simpler instance of the same puzzle.
133 *
134 * But I don't know whether all of this actually works. I more or less
135 * believe the process for enumerating elements of the free group; but
136 * I'm not as confident that when you find a group element that won't
137 * fit in the grid, you'll never have to consider its descendants in
138 * the BFS either. And I'm assuming that 'unwind the self-intersection
139 * homotopically' is a thing that can actually be turned into a
140 * sensible algorithm.
141 *
142 * --------
143 *
144 * Another thing that might be needed is to characterise _which_
145 * homotopy class a given path is in.
146 *
147 * For this I think it's sufficient to choose a collection of paths
148 * along the _edges_ of the square grid, each of which connects two of
149 * the holes in the grid (including the grid exterior, which counts as
150 * a huge hole), such that they form a spanning tree between the
151 * holes. Then assign each of those paths an orientation, so that
152 * crossing it in one direction counts as 'positive' and the other
153 * 'negative'. Now analyse a candidate path from one square to another
154 * by following it and noting down which of those paths it crosses in
155 * which direction, then simplifying the result like a free group word
156 * (i.e. adjacent + and - crossings of the same path cancel out).
157 *
158 * --------
159 *
160 * If we choose those paths to be of minimal length, then we can get
161 * an upper bound on the number of homotopy classes by observing that
162 * you can't traverse any of those barriers more times than will fit
163 * non-self-intersectingly in the grid. That might be an alternative
164 * method of bounding the search through the fundamental group to only
165 * finitely many possibilities.
166 */
167
168/*
72 * Standard notation for directions. 169 * Standard notation for directions.
73 */ 170 */
74#define L 0 171#define L 0
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-22 20:36:53 +0000