From 1507058f4e2f6d72ffbf3b342d280f8702b1cfb6 Mon Sep 17 00:00:00 2001
From: simon <simon@cda61777-01e9-0310-a592-d414129be87e>
Date: Sat, 28 May 2005 08:04:29 +0000
Subject: [PATCH] Add the ability to use the Rectangles solver for actually
 solving puzzles, rather than just doing its nondeterministic number placement
 thing. This enables the use of the `Solve' menu option on externally entered
 game IDs, provided of course that they aren't _too_ difficult.

git-svn-id: svn://svn.tartarus.org/sgt/puzzles@5852 cda61777-01e9-0310-a592-d414129be87e
---
 rect.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 64 insertions(+), 6 deletions(-)

diff --git a/rect.c b/rect.c
index 76abeed..12d14b9 100644
--- a/rect.c
+++ b/rect.c
@@ -321,7 +321,7 @@ static void remove_number_placement(int w, int h, struct numberdata *number,
 }
 
 static int rect_solver(int w, int h, int nrects, struct numberdata *numbers,
-                       random_state *rs)
+                       game_state *result, random_state *rs)
 {
     struct rectlist *rectpositions;
     int *overlaps, *rectbyplace, *workspace;
@@ -739,7 +739,7 @@ static int rect_solver(int w, int h, int nrects, struct numberdata *numbers,
          * rectangle) which overlaps a candidate placement of the
          * number for some other rectangle.
          */
-        {
+        if (rs) {
             struct rpn {
                 int rect;
                 int placement;
@@ -844,8 +844,28 @@ static int rect_solver(int w, int h, int nrects, struct numberdata *numbers,
                i, rectpositions[i].n);
 #endif
         assert(rectpositions[i].n > 0);
-        if (rectpositions[i].n > 1)
+        if (rectpositions[i].n > 1) {
             ret = FALSE;
+	} else if (result) {
+	    /*
+	     * Place the rectangle in its only possible position.
+	     */
+	    int x, y;
+	    struct rect *r = &rectpositions[i].rects[0];
+
+	    for (y = 0; y < r->h; y++) {
+		if (r->x > 0)
+		    vedge(result, r->x, r->y+y) = 1;
+		if (r->x+r->w < result->w)
+		    vedge(result, r->x+r->w, r->y+y) = 1;
+	    }
+	    for (x = 0; x < r->w; x++) {
+		if (r->y > 0)
+		    hedge(result, r->x+x, r->y) = 1;
+		if (r->y+r->h < result->h)
+		    hedge(result, r->x+x, r->y+r->h) = 1;
+	    }
+	}
     }
 
     /*
@@ -1523,7 +1543,8 @@ static char *new_game_desc(game_params *params, random_state *rs,
             }
 
 	    if (params->unique)
-		ret = rect_solver(params->w, params->h, nnumbers, nd, rs);
+		ret = rect_solver(params->w, params->h, nnumbers, nd,
+				  NULL, rs);
 	    else
 		ret = TRUE;	       /* allow any number placement at all */
 
@@ -1748,8 +1769,45 @@ static game_state *solve_game(game_state *state, game_aux_info *ai,
     game_state *ret;
 
     if (!ai) {
-	*error = "Solution not known for this puzzle";
-	return NULL;
+	int i, j, n;
+	struct numberdata *nd;
+
+	/*
+	 * Attempt the in-built solver.
+	 */
+
+	/* Set up each number's (very short) candidate position list. */
+	for (i = n = 0; i < state->h * state->w; i++)
+	    if (state->grid[i])
+		n++;
+
+	nd = snewn(n, struct numberdata);
+
+	for (i = j = 0; i < state->h * state->w; i++)
+	    if (state->grid[i]) {
+		nd[j].area = state->grid[i];
+		nd[j].npoints = 1;
+		nd[j].points = snewn(1, struct point);
+		nd[j].points[0].x = i % state->w;
+		nd[j].points[0].y = i / state->w;
+		j++;
+	    }
+
+	assert(j == n);
+
+	ret = dup_game(state);
+	ret->cheated = TRUE;
+
+	rect_solver(state->w, state->h, n, nd, ret, NULL);
+
+	/*
+	 * Clean up.
+	 */
+	for (i = 0; i < n; i++)
+	    sfree(nd[i].points);
+	sfree(nd);
+
+	return ret;
     }
 
     assert(state->w == ai->w);
-- 
2.11.0