shithub: puzzles

Info  •  Files  •  Log  •  Branches

Dominosa: move set analysis with doubles into Extreme.

This change doesn't alter the overall power of the Dominosa solver; it
just moves the boundary between Hard and Extreme so that fewer puzzles
count as Hard, and more as Extreme. Specifically, either of the two
cases of set analysis potentially involving a double domino with both
squares in the set is now classed as Extreme.

The effects on difficulty are that Hard is now easier, and Extreme is
at least easier _on average_. But the main purpose is the effect on
generation time: before this change, Dominosa Extreme was the slowest
puzzle present to generate in the whole collection, by a factor of
more than three. I think the forcing-chain deductions just didn't make
very many additional grids soluble, so that the generator had to try a
lot of candidates before finding one that could be solved using
forcing chains but not with all the other techniques put together.

--- a/dominosa.c

+++ b/dominosa.c

@@ -1013,7 +1013,7 @@

  * is small enough to let us rule out placements of those dominoes

  * elsewhere.

  */

-static bool deduce_set_simple(struct solver_scratch *sc)

+static bool deduce_set(struct solver_scratch *sc, bool doubles)

 {

     struct solver_square **sqs, **sqp, **sqe;

     int num, nsq, i, j;

@@ -1195,6 +1195,9 @@

                 rule_out_text = "all of them elsewhere";

 #endif

             } else {

+                if (!doubles)

+                    continue;          /* not at this difficulty level */

+

                 /*

                  * But in Dominosa, there's a special case if _two_

                  * squares in this set can possibly both be covered by

@@ -1761,7 +1764,7 @@

         if (max_diff_allowed <= DIFF_BASIC)

             continue;

-        if (deduce_set_simple(sc))

+        if (deduce_set(sc, false))

             done_something = true;

         if (done_something) {

             sc->max_diff_used = max(sc->max_diff_used, DIFF_HARD);

@@ -1770,6 +1773,13 @@

         if (max_diff_allowed <= DIFF_HARD)

             continue;

+

+        if (deduce_set(sc, true))

+            done_something = true;

+        if (done_something) {

+            sc->max_diff_used = max(sc->max_diff_used, DIFF_EXTREME);

+            continue;

+        }

         if (deduce_forcing_chain(sc))

             done_something = true;