From 48b0ef1cf22ec37927116ac83ea7c7cfc1f9083e Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Thu, 25 Jun 2020 14:44:33 -0400 Subject: puzzles: resync with upstream This brings the upstream version to 9aa7b7c (with some of my changes as well). Change-Id: I5bf8a3e0b8672d82cb1bf34afc07adbe12a3ac53 --- apps/plugins/puzzles/README.rockbox | 4 + apps/plugins/puzzles/help/blackbox.c | 2 +- apps/plugins/puzzles/help/bridges.c | 2 +- apps/plugins/puzzles/help/cube.c | 2 +- apps/plugins/puzzles/help/dominosa.c | 2 +- apps/plugins/puzzles/help/fifteen.c | 2 +- apps/plugins/puzzles/help/filling.c | 2 +- apps/plugins/puzzles/help/flip.c | 2 +- apps/plugins/puzzles/help/flood.c | 2 +- apps/plugins/puzzles/help/galaxies.c | 2 +- apps/plugins/puzzles/help/guess.c | 2 +- apps/plugins/puzzles/help/inertia.c | 2 +- apps/plugins/puzzles/help/keen.c | 2 +- apps/plugins/puzzles/help/lightup.c | 2 +- apps/plugins/puzzles/help/loopy.c | 2 +- apps/plugins/puzzles/help/magnets.c | 2 +- apps/plugins/puzzles/help/map.c | 2 +- apps/plugins/puzzles/help/mines.c | 2 +- apps/plugins/puzzles/help/net.c | 2 +- apps/plugins/puzzles/help/netslide.c | 2 +- apps/plugins/puzzles/help/palisade.c | 2 +- apps/plugins/puzzles/help/pattern.c | 2 +- apps/plugins/puzzles/help/pearl.c | 2 +- apps/plugins/puzzles/help/pegs.c | 2 +- apps/plugins/puzzles/help/range.c | 2 +- apps/plugins/puzzles/help/rect.c | 2 +- apps/plugins/puzzles/help/samegame.c | 2 +- apps/plugins/puzzles/help/signpost.c | 2 +- apps/plugins/puzzles/help/singles.c | 2 +- apps/plugins/puzzles/help/sixteen.c | 2 +- apps/plugins/puzzles/help/slant.c | 2 +- apps/plugins/puzzles/help/solo.c | 2 +- apps/plugins/puzzles/help/tents.c | 2 +- apps/plugins/puzzles/help/towers.c | 2 +- apps/plugins/puzzles/help/tracks.c | 2 +- apps/plugins/puzzles/help/twiddle.c | 2 +- apps/plugins/puzzles/help/undead.c | 2 +- apps/plugins/puzzles/help/unequal.c | 2 +- apps/plugins/puzzles/help/unruly.c | 2 +- apps/plugins/puzzles/help/untangle.c | 2 +- apps/plugins/puzzles/src/LICENCE | 4 +- apps/plugins/puzzles/src/gamedesc.txt | 39 -- apps/plugins/puzzles/src/grid.c | 2 + apps/plugins/puzzles/src/gtk.c | 753 +++++++++++++++++++++++++--- apps/plugins/puzzles/src/keen.c | 88 +++- apps/plugins/puzzles/src/latin.c | 39 +- apps/plugins/puzzles/src/latin.h | 9 +- apps/plugins/puzzles/src/mines.c | 2 + apps/plugins/puzzles/src/pattern.c | 15 +- apps/plugins/puzzles/src/printing.c | 280 ++++++----- apps/plugins/puzzles/src/ps.c | 2 - apps/plugins/puzzles/src/puzzles.but | 3 +- apps/plugins/puzzles/src/puzzles.h | 7 +- apps/plugins/puzzles/src/towers.c | 34 +- apps/plugins/puzzles/src/tracks.R | 3 + apps/plugins/puzzles/src/tracks.c | 451 +++++++++++++++-- apps/plugins/puzzles/src/twiddle.c | 11 + apps/plugins/puzzles/src/unequal.c | 74 ++- apps/plugins/puzzles/src/unfinished/group.c | 226 ++++++++- apps/plugins/puzzles/src/unfinished/path.c | 97 ++++ 60 files changed, 1889 insertions(+), 332 deletions(-) delete mode 100644 apps/plugins/puzzles/src/gamedesc.txt (limited to 'apps/plugins') diff --git a/apps/plugins/puzzles/README.rockbox b/apps/plugins/puzzles/README.rockbox index 3adce72412..26e6bbb289 100644 --- a/apps/plugins/puzzles/README.rockbox +++ b/apps/plugins/puzzles/README.rockbox @@ -59,3 +59,7 @@ April 2018: Finished up the rest of the games. All work now! Surely there's still bugs to fix, so stay tuned... December 2018: Resync to 3ece3d6. Happy holidays! + +May 2019: Resync to e2135d5. + +June 2020: Resync to 9aa7b7c. diff --git a/apps/plugins/puzzles/help/blackbox.c b/apps/plugins/puzzles/help/blackbox.c index 938810a19f..659d26cd7a 100644 --- a/apps/plugins/puzzles/help/blackbox.c +++ b/apps/plugins/puzzles/help/blackbox.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/bridges.c b/apps/plugins/puzzles/help/bridges.c index ed901c1309..b0cdcedd34 100644 --- a/apps/plugins/puzzles/help/bridges.c +++ b/apps/plugins/puzzles/help/bridges.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/cube.c b/apps/plugins/puzzles/help/cube.c index f8026a5946..7939437658 100644 --- a/apps/plugins/puzzles/help/cube.c +++ b/apps/plugins/puzzles/help/cube.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/dominosa.c b/apps/plugins/puzzles/help/dominosa.c index f1c61620ee..20a2341c64 100644 --- a/apps/plugins/puzzles/help/dominosa.c +++ b/apps/plugins/puzzles/help/dominosa.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/fifteen.c b/apps/plugins/puzzles/help/fifteen.c index eb3f84ab26..dc3e5373e8 100644 --- a/apps/plugins/puzzles/help/fifteen.c +++ b/apps/plugins/puzzles/help/fifteen.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/filling.c b/apps/plugins/puzzles/help/filling.c index 15ba8cbe43..6602890bd8 100644 --- a/apps/plugins/puzzles/help/filling.c +++ b/apps/plugins/puzzles/help/filling.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/flip.c b/apps/plugins/puzzles/help/flip.c index c451e8c672..9553df8b77 100644 --- a/apps/plugins/puzzles/help/flip.c +++ b/apps/plugins/puzzles/help/flip.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/flood.c b/apps/plugins/puzzles/help/flood.c index 1bee956902..a800ca4444 100644 --- a/apps/plugins/puzzles/help/flood.c +++ b/apps/plugins/puzzles/help/flood.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/galaxies.c b/apps/plugins/puzzles/help/galaxies.c index eed08b8ac4..d6bbf9360c 100644 --- a/apps/plugins/puzzles/help/galaxies.c +++ b/apps/plugins/puzzles/help/galaxies.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/guess.c b/apps/plugins/puzzles/help/guess.c index 1fc4f0695f..8260b0c6f6 100644 --- a/apps/plugins/puzzles/help/guess.c +++ b/apps/plugins/puzzles/help/guess.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/inertia.c b/apps/plugins/puzzles/help/inertia.c index 8d7902dc54..184893af4a 100644 --- a/apps/plugins/puzzles/help/inertia.c +++ b/apps/plugins/puzzles/help/inertia.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/keen.c b/apps/plugins/puzzles/help/keen.c index 8f0374dcdd..4539df4625 100644 --- a/apps/plugins/puzzles/help/keen.c +++ b/apps/plugins/puzzles/help/keen.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/lightup.c b/apps/plugins/puzzles/help/lightup.c index 303aa45beb..1dca0363c4 100644 --- a/apps/plugins/puzzles/help/lightup.c +++ b/apps/plugins/puzzles/help/lightup.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/loopy.c b/apps/plugins/puzzles/help/loopy.c index eb4adedfc8..85ad8e27c4 100644 --- a/apps/plugins/puzzles/help/loopy.c +++ b/apps/plugins/puzzles/help/loopy.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/magnets.c b/apps/plugins/puzzles/help/magnets.c index becfe20902..2f18033675 100644 --- a/apps/plugins/puzzles/help/magnets.c +++ b/apps/plugins/puzzles/help/magnets.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/map.c b/apps/plugins/puzzles/help/map.c index 731b5f4745..5608eb7619 100644 --- a/apps/plugins/puzzles/help/map.c +++ b/apps/plugins/puzzles/help/map.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/mines.c b/apps/plugins/puzzles/help/mines.c index 317d626292..c37e9298ab 100644 --- a/apps/plugins/puzzles/help/mines.c +++ b/apps/plugins/puzzles/help/mines.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/net.c b/apps/plugins/puzzles/help/net.c index d83892c110..256012638e 100644 --- a/apps/plugins/puzzles/help/net.c +++ b/apps/plugins/puzzles/help/net.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/netslide.c b/apps/plugins/puzzles/help/netslide.c index dc6a0d65e1..5d6e282e04 100644 --- a/apps/plugins/puzzles/help/netslide.c +++ b/apps/plugins/puzzles/help/netslide.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/palisade.c b/apps/plugins/puzzles/help/palisade.c index 3de6c2d06d..c3e1de1b51 100644 --- a/apps/plugins/puzzles/help/palisade.c +++ b/apps/plugins/puzzles/help/palisade.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/pattern.c b/apps/plugins/puzzles/help/pattern.c index 3c51afd66c..83bfaeb5fe 100644 --- a/apps/plugins/puzzles/help/pattern.c +++ b/apps/plugins/puzzles/help/pattern.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/pearl.c b/apps/plugins/puzzles/help/pearl.c index 1c7a7ee3ab..fe3f3534fc 100644 --- a/apps/plugins/puzzles/help/pearl.c +++ b/apps/plugins/puzzles/help/pearl.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/pegs.c b/apps/plugins/puzzles/help/pegs.c index d64cbe8d56..24513761c8 100644 --- a/apps/plugins/puzzles/help/pegs.c +++ b/apps/plugins/puzzles/help/pegs.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/range.c b/apps/plugins/puzzles/help/range.c index 62c308778e..34ae51a512 100644 --- a/apps/plugins/puzzles/help/range.c +++ b/apps/plugins/puzzles/help/range.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/rect.c b/apps/plugins/puzzles/help/rect.c index 768bd1a4ce..196dc077d9 100644 --- a/apps/plugins/puzzles/help/rect.c +++ b/apps/plugins/puzzles/help/rect.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/samegame.c b/apps/plugins/puzzles/help/samegame.c index 2f8e8a3003..02fc670b80 100644 --- a/apps/plugins/puzzles/help/samegame.c +++ b/apps/plugins/puzzles/help/samegame.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/signpost.c b/apps/plugins/puzzles/help/signpost.c index ceafcfd056..c0e4c44e9f 100644 --- a/apps/plugins/puzzles/help/signpost.c +++ b/apps/plugins/puzzles/help/signpost.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/singles.c b/apps/plugins/puzzles/help/singles.c index dffc14b35b..606b4f7b41 100644 --- a/apps/plugins/puzzles/help/singles.c +++ b/apps/plugins/puzzles/help/singles.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/sixteen.c b/apps/plugins/puzzles/help/sixteen.c index eb8feed049..d72226f8a1 100644 --- a/apps/plugins/puzzles/help/sixteen.c +++ b/apps/plugins/puzzles/help/sixteen.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/slant.c b/apps/plugins/puzzles/help/slant.c index 873863757e..b78c7c694c 100644 --- a/apps/plugins/puzzles/help/slant.c +++ b/apps/plugins/puzzles/help/slant.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/solo.c b/apps/plugins/puzzles/help/solo.c index a02bb94c04..449a352fe2 100644 --- a/apps/plugins/puzzles/help/solo.c +++ b/apps/plugins/puzzles/help/solo.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/tents.c b/apps/plugins/puzzles/help/tents.c index e53f92b0f6..d26afead48 100644 --- a/apps/plugins/puzzles/help/tents.c +++ b/apps/plugins/puzzles/help/tents.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/towers.c b/apps/plugins/puzzles/help/towers.c index 62c08e011b..b062c4f350 100644 --- a/apps/plugins/puzzles/help/towers.c +++ b/apps/plugins/puzzles/help/towers.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/tracks.c b/apps/plugins/puzzles/help/tracks.c index d3bdc709be..6872ddbbab 100644 --- a/apps/plugins/puzzles/help/tracks.c +++ b/apps/plugins/puzzles/help/tracks.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/twiddle.c b/apps/plugins/puzzles/help/twiddle.c index 72495874b8..69ce44e9b0 100644 --- a/apps/plugins/puzzles/help/twiddle.c +++ b/apps/plugins/puzzles/help/twiddle.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/undead.c b/apps/plugins/puzzles/help/undead.c index 3af048a3b8..11fb57cf48 100644 --- a/apps/plugins/puzzles/help/undead.c +++ b/apps/plugins/puzzles/help/undead.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/unequal.c b/apps/plugins/puzzles/help/unequal.c index 8c5d2fa9b8..f7a612c01e 100644 --- a/apps/plugins/puzzles/help/unequal.c +++ b/apps/plugins/puzzles/help/unequal.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/unruly.c b/apps/plugins/puzzles/help/unruly.c index 55c4d5240f..88590aca32 100644 --- a/apps/plugins/puzzles/help/unruly.c +++ b/apps/plugins/puzzles/help/unruly.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ diff --git a/apps/plugins/puzzles/help/untangle.c b/apps/plugins/puzzles/help/untangle.c index 24f9d83986..6992d97e96 100644 --- a/apps/plugins/puzzles/help/untangle.c +++ b/apps/plugins/puzzles/help/untangle.c @@ -1,4 +1,4 @@ -/* auto-generated on Dec 21 2018 by genhelp.sh */ +/* auto-generated on Jun 25 2020 by genhelp.sh */ /* help text is compressed using LZ4; see compress.c for details */ /* DO NOT EDIT! */ 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. Portions copyright Richard Boulton, James Harvey, Mike Pinna, Jonas Kölker, Dariusz Olszewski, Michael Schierl, Lambros Lambrou, Bernd -Schmidt, Steffen Bauer, Lennard Sprong, Rogier Goossens and Michael -Quevillon. +Schmidt, Steffen Bauer, Lennard Sprong, Rogier Goossens, Michael +Quevillon and Asher Gordon. Permission is hereby granted, free of charge, to any person obtaining 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 @@ -blackbox:blackbox.exe:Black Box:Ball-finding puzzle:Find the hidden balls in the box by bouncing laser beams off them. -bridges:bridges.exe:Bridges:Bridge-placing puzzle:Connect all the islands with a network of bridges. -cube:cube.exe:Cube:Rolling cube puzzle:Pick up all the blue squares by rolling the cube over them. -dominosa:dominosa.exe:Dominosa:Domino tiling puzzle:Tile the rectangle with a full set of dominoes. -fifteen:fifteen.exe:Fifteen:Sliding block puzzle:Slide the tiles around to arrange them into order. -filling:filling.exe:Filling:Polyomino puzzle:Mark every square with the area of its containing region. -flip:flip.exe:Flip:Tile inversion puzzle:Flip groups of squares to light them all up at once. -flood:flood.exe:Flood:Flood-filling puzzle:Turn the grid the same colour in as few flood fills as possible. -galaxies:galaxies.exe:Galaxies:Symmetric polyomino puzzle:Divide the grid into rotationally symmetric regions each centred on a dot. -guess:guess.exe:Guess:Combination-guessing puzzle:Guess the hidden combination of colours. -inertia:inertia.exe:Inertia:Gem-collecting puzzle:Collect all the gems without running into any of the mines. -keen:keen.exe:Keen:Arithmetic Latin square puzzle:Complete the latin square in accordance with the arithmetic clues. -lightup:lightup.exe:Light Up:Light-bulb placing puzzle:Place bulbs to light up all the squares. -loopy:loopy.exe:Loopy:Loop-drawing puzzle:Draw a single closed loop, given clues about number of adjacent edges. -magnets:magnets.exe:Magnets:Magnet-placing puzzle:Place magnets to satisfy the clues and avoid like poles touching. -map:map.exe:Map:Map-colouring puzzle:Colour the map so that adjacent regions are never the same colour. -mines:mines.exe:Mines:Mine-finding puzzle:Find all the mines without treading on any of them. -net:netgame.exe:Net:Network jigsaw puzzle:Rotate each tile to reassemble the network. -netslide:netslide.exe:Netslide:Toroidal sliding network puzzle:Slide a row at a time to reassemble the network. -palisade:palisade.exe:Palisade:Grid-division puzzle:Divide the grid into equal-sized areas in accordance with the clues. -pattern:pattern.exe:Pattern:Pattern puzzle:Fill in the pattern in the grid, given only the lengths of runs of black squares. -pearl:pearl.exe:Pearl:Loop-drawing puzzle:Draw a single closed loop, given clues about corner and straight squares. -pegs:pegs.exe:Pegs:Peg solitaire puzzle:Jump pegs over each other to remove all but one. -range:range.exe:Range:Visible-distance puzzle:Place black squares to limit the visible distance from each numbered cell. -rect:rect.exe:Rectangles:Rectangles puzzle:Divide the grid into rectangles with areas equal to the numbers. -samegame:samegame.exe:Same Game:Block-clearing puzzle:Clear the grid by removing touching groups of the same colour squares. -signpost:signpost.exe:Signpost:Square-connecting puzzle:Connect the squares into a path following the arrows. -singles:singles.exe:Singles:Number-removing puzzle:Black out the right set of duplicate numbers. -sixteen:sixteen.exe:Sixteen:Toroidal sliding block puzzle:Slide a row at a time to arrange the tiles into order. -slant:slant.exe:Slant:Maze-drawing puzzle:Draw a maze of slanting lines that matches the clues. -solo:solo.exe:Solo:Number placement puzzle:Fill in the grid so that each row, column and square block contains one of every digit. -tents:tents.exe:Tents:Tent-placing puzzle:Place a tent next to each tree. -towers:towers.exe:Towers:Tower-placing Latin square puzzle:Complete the latin square of towers in accordance with the clues. -tracks:tracks.exe:Tracks:Path-finding railway track puzzle:Fill in the railway track according to the clues. -twiddle:twiddle.exe:Twiddle:Rotational sliding block puzzle:Rotate the tiles around themselves to arrange them into order. -undead:undead.exe:Undead:Monster-placing puzzle:Place ghosts, vampires and zombies so that the right numbers of them can be seen in mirrors. -unequal:unequal.exe:Unequal:Latin square puzzle:Complete the latin square in accordance with the > signs. -unruly:unruly.exe:Unruly:Black and white grid puzzle:Fill in the black and white grid to avoid runs of three. -untangle: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, *tilesize = FLORET_TILESIZE; *xextent = (6*px+3*qx)/2 * (width-1) + 4*qx + 2*px; *yextent = (5*qy-4*py) * (height-1) + 4*qy + 2*ry; + if (height == 1) + *yextent += (5*qy-4*py)/2; } static 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 @@ # endif #endif +#if defined USE_CAIRO && GTK_CHECK_VERSION(2,10,0) +/* We can only use printing if we are using Cairo for drawing and we + have a GTK version >= 2.10 (when GtkPrintOperation was added). */ +# define USE_PRINTING +# if GTK_CHECK_VERSION(2,18,0) +/* We can embed the page setup. Before 2.18, we needed to have a + separate page setup. */ +# define USE_EMBED_PAGE_SETUP +# endif +#endif + #if GTK_CHECK_VERSION(3,0,0) /* The old names are still more concise! */ #define gtk_hbox_new(x,y) gtk_box_new(GTK_ORIENTATION_HORIZONTAL,y) @@ -131,6 +142,18 @@ struct font { int size; }; +/* + * An internal API for functions which need to be different for + * printing and drawing. + */ +struct internal_drawing_api { + void (*set_colour)(frontend *fe, int colour); +#ifdef USE_CAIRO + void (*fill)(frontend *fe); + void (*fill_preserve)(frontend *fe); +#endif +}; + /* * This structure holds all the data relevant to a single window. * In principle this would allow us to open multiple independent @@ -180,7 +203,7 @@ struct frontend { GtkWidget *cfgbox; void *paste_data; int paste_data_len; - int pw, ph; /* pixmap size (w, h are area size) */ + int pw, ph, ps; /* pixmap size (w, h are area size, s is GDK scale) */ int ox, oy; /* offset of pixmap in drawing area */ #ifdef OLD_FILESEL char *filesel_name; @@ -225,6 +248,23 @@ struct frontend { */ bool awaiting_resize_ack; #endif +#ifdef USE_CAIRO + int printcount, printw, printh; + float printscale; + bool printsolns, printcolour; + int hatch; + float hatchthick, hatchspace; + drawing *print_dr; + document *doc; +#endif +#ifdef USE_PRINTING + GtkPrintOperation *printop; + GtkPrintContext *printcontext; + GtkSpinButton *printcount_spin_button, *printw_spin_button, + *printh_spin_button, *printscale_spin_button; + GtkCheckButton *soln_check_button, *colour_check_button; +#endif + const struct internal_drawing_api *dr_api; }; struct blitter { @@ -247,15 +287,19 @@ void get_random_seed(void **randseed, int *randseedsize) void frontend_default_colour(frontend *fe, float *output) { #if !GTK_CHECK_VERSION(3,0,0) - /* - * Use the widget style's default background colour as the - * background for the puzzle drawing area. - */ - GdkColor col = gtk_widget_get_style(fe->window)->bg[GTK_STATE_NORMAL]; - output[0] = col.red / 65535.0; - output[1] = col.green / 65535.0; - output[2] = col.blue / 65535.0; -#else + if (!fe->headless) { + /* + * If we have a widget and it has a style that specifies a + * default background colour, use that as the background for + * the puzzle drawing area. + */ + GdkColor col = gtk_widget_get_style(fe->window)->bg[GTK_STATE_NORMAL]; + output[0] = col.red / 65535.0; + output[1] = col.green / 65535.0; + output[2] = col.blue / 65535.0; + } +#endif + /* * GTK 3 has decided that there's no such thing as a 'default * background colour' any more, because widget styles might set @@ -263,9 +307,11 @@ void frontend_default_colour(frontend *fe, float *output) * image. We don't want to get into overlaying our entire puzzle * on an arbitrary background image, so we'll just make up a * reasonable shade of grey. + * + * This is also what we do on GTK 2 in headless mode, where we + * don't have a widget style to query. */ output[0] = output[1] = output[2] = 0.9F; -#endif } void gtk_status_bar(void *handle, const char *text) @@ -290,6 +336,7 @@ void gtk_status_bar(void *handle, const char *text) static void setup_drawing(frontend *fe) { fe->cr = cairo_create(fe->image); + cairo_scale(fe->cr, fe->ps, fe->ps); cairo_set_antialias(fe->cr, CAIRO_ANTIALIAS_GRAY); cairo_set_line_width(fe->cr, 1.0); cairo_set_line_cap(fe->cr, CAIRO_LINE_CAP_SQUARE); @@ -321,12 +368,23 @@ static void snaffle_colours(frontend *fe) fe->colours = midend_colours(fe->me, &fe->ncolours); } -static void set_colour(frontend *fe, int colour) +static void draw_set_colour(frontend *fe, int colour) { cairo_set_source_rgb(fe->cr, - fe->colours[3*colour + 0], - fe->colours[3*colour + 1], - fe->colours[3*colour + 2]); + fe->colours[3*colour + 0], + fe->colours[3*colour + 1], + fe->colours[3*colour + 2]); +} + +static void print_set_colour(frontend *fe, int colour) +{ + float r, g, b; + + print_get_colour(fe->print_dr, colour, fe->printcolour, + &(fe->hatch), &r, &g, &b); + + if (fe->hatch < 0) + cairo_set_source_rgb(fe->cr, r, g, b); } static void set_window_background(frontend *fe, int colour) @@ -395,6 +453,82 @@ static void save_screenshot_png(frontend *fe, const char *screenshot_file) cairo_surface_write_to_png(fe->image, screenshot_file); } +static void do_hatch(frontend *fe) +{ + double i, x, y, width, height, maxdim; + + /* Get the dimensions of the region to be hatched. */ + cairo_path_extents(fe->cr, &x, &y, &width, &height); + + maxdim = max(width, height); + + cairo_save(fe->cr); + + /* Set the line color and width. */ + cairo_set_source_rgb(fe->cr, 0, 0, 0); + cairo_set_line_width(fe->cr, fe->hatchthick); + /* Clip to the region. */ + cairo_clip(fe->cr); + /* Hatch the bounding area of the fill region. */ + if (fe->hatch == HATCH_VERT || fe->hatch == HATCH_PLUS) { + for (i = 0.0; i <= width; i += fe->hatchspace) { + cairo_move_to(fe->cr, i, 0); + cairo_rel_line_to(fe->cr, 0, height); + } + } + if (fe->hatch == HATCH_HORIZ || fe->hatch == HATCH_PLUS) { + for (i = 0.0; i <= height; i += fe->hatchspace) { + cairo_move_to(fe->cr, 0, i); + cairo_rel_line_to(fe->cr, width, 0); + } + } + if (fe->hatch == HATCH_SLASH || fe->hatch == HATCH_X) { + for (i = -height; i <= width; i += fe->hatchspace * ROOT2) { + cairo_move_to(fe->cr, i, 0); + cairo_rel_line_to(fe->cr, maxdim, maxdim); + } + } + if (fe->hatch == HATCH_BACKSLASH || fe->hatch == HATCH_X) { + for (i = 0.0; i <= width + height; i += fe->hatchspace * ROOT2) { + cairo_move_to(fe->cr, i, 0); + cairo_rel_line_to(fe->cr, -maxdim, maxdim); + } + } + cairo_stroke(fe->cr); + + cairo_restore(fe->cr); +} + +static void do_draw_fill(frontend *fe) +{ + cairo_fill(fe->cr); +} + +static void do_draw_fill_preserve(frontend *fe) +{ + cairo_fill_preserve(fe->cr); +} + +static void do_print_fill(frontend *fe) +{ + if (fe->hatch < 0) + cairo_fill(fe->cr); + else + do_hatch(fe); +} + +static void do_print_fill_preserve(frontend *fe) +{ + if (fe->hatch < 0) { + cairo_fill_preserve(fe->cr); + } else { + cairo_path_t *oldpath; + oldpath = cairo_copy_path(fe->cr); + do_hatch(fe); + cairo_append_path(fe->cr, oldpath); + } +} + static void do_clip(frontend *fe, int x, int y, int w, int h) { cairo_new_path(fe->cr); @@ -413,7 +547,7 @@ static void do_draw_rect(frontend *fe, int x, int y, int w, int h) cairo_new_path(fe->cr); cairo_set_antialias(fe->cr, CAIRO_ANTIALIAS_NONE); cairo_rectangle(fe->cr, x, y, w, h); - cairo_fill(fe->cr); + fe->dr_api->fill(fe); cairo_restore(fe->cr); } @@ -447,11 +581,11 @@ static void do_draw_poly(frontend *fe, int *coords, int npoints, cairo_line_to(fe->cr, coords[i*2] + 0.5, coords[i*2 + 1] + 0.5); cairo_close_path(fe->cr); if (fillcolour >= 0) { - set_colour(fe, fillcolour); - cairo_fill_preserve(fe->cr); + fe->dr_api->set_colour(fe, fillcolour); + fe->dr_api->fill_preserve(fe); } assert(outlinecolour >= 0); - set_colour(fe, outlinecolour); + fe->dr_api->set_colour(fe, outlinecolour); cairo_stroke(fe->cr); } @@ -462,11 +596,11 @@ static void do_draw_circle(frontend *fe, int cx, int cy, int radius, cairo_arc(fe->cr, cx + 0.5, cy + 0.5, radius, 0, 2*PI); cairo_close_path(fe->cr); /* Just in case... */ if (fillcolour >= 0) { - set_colour(fe, fillcolour); - cairo_fill_preserve(fe->cr); + fe->dr_api->set_colour(fe, fillcolour); + fe->dr_api->fill_preserve(fe); } assert(outlinecolour >= 0); - set_colour(fe, outlinecolour); + fe->dr_api->set_colour(fe, outlinecolour); cairo_stroke(fe->cr); } @@ -512,23 +646,24 @@ static void wipe_and_maybe_destroy_cairo(frontend *fe, cairo_t *cr, static void setup_backing_store(frontend *fe) { #ifndef USE_CAIRO_WITHOUT_PIXMAP - if (fe->headless) { - fprintf(stderr, "headless mode does not work with GDK pixmaps\n"); - exit(1); + if (!fe->headless) { + fe->pixmap = gdk_pixmap_new(gtk_widget_get_window(fe->area), + fe->pw*fe->ps, fe->ph*fe->ps, -1); + } else { + fe->pixmap = NULL; } - - fe->pixmap = gdk_pixmap_new(gtk_widget_get_window(fe->area), - fe->pw, fe->ph, -1); #endif + fe->image = cairo_image_surface_create(CAIRO_FORMAT_RGB24, - fe->pw, fe->ph); + fe->pw*fe->ps, fe->ph*fe->ps); wipe_and_maybe_destroy_cairo(fe, cairo_create(fe->image), true); #ifndef USE_CAIRO_WITHOUT_PIXMAP - wipe_and_maybe_destroy_cairo(fe, gdk_cairo_create(fe->pixmap), true); + if (!fe->headless) + wipe_and_maybe_destroy_cairo(fe, gdk_cairo_create(fe->pixmap), true); #endif -#if GTK_CHECK_VERSION(3,22,0) if (!fe->headless) { +#if GTK_CHECK_VERSION(3,22,0) GdkWindow *gdkwin; cairo_region_t *region; GdkDrawingContext *drawctx; @@ -541,11 +676,11 @@ static void setup_backing_store(frontend *fe) wipe_and_maybe_destroy_cairo(fe, cr, false); gdk_window_end_draw_frame(gdkwin, drawctx); cairo_region_destroy(region); - } #else - wipe_and_maybe_destroy_cairo( - fe, gdk_cairo_create(gtk_widget_get_window(fe->area)), true); + wipe_and_maybe_destroy_cairo( + fe, gdk_cairo_create(gtk_widget_get_window(fe->area)), true); #endif + } } static bool backing_store_ok(frontend *fe) @@ -616,7 +751,7 @@ static void set_window_background(frontend *fe, int colour) gdk_window_set_background(fe->window->window, &fe->colours[colour]); } -static void set_colour(frontend *fe, int colour) +static void draw_set_colour(frontend *fe, int colour) { gdk_gc_set_foreground(fe->gc, &fe->colours[colour]); } @@ -709,11 +844,11 @@ static void do_draw_poly(frontend *fe, int *coords, int npoints, } if (fillcolour >= 0) { - set_colour(fe, fillcolour); + fe->dr_api->set_colour(fe, fillcolour); gdk_draw_polygon(fe->pixmap, fe->gc, true, points, npoints); } assert(outlinecolour >= 0); - set_colour(fe, outlinecolour); + fe->dr_api->set_colour(fe, outlinecolour); /* * 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, int fillcolour, int outlinecolour) { if (fillcolour >= 0) { - set_colour(fe, fillcolour); + fe->dr_api->set_colour(fe, fillcolour); gdk_draw_arc(fe->pixmap, fe->gc, true, cx - radius, cy - radius, 2 * radius, 2 * radius, 0, 360 * 64); } assert(outlinecolour >= 0); - set_colour(fe, outlinecolour); + fe->dr_api->set_colour(fe, outlinecolour); gdk_draw_arc(fe->pixmap, fe->gc, false, cx - radius, cy - radius, 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, /* * Do the job. */ - set_colour(fe, colour); + fe->dr_api->set_colour(fe, colour); align_and_draw_text(fe, i, align, x, y, text); } void gtk_draw_rect(void *handle, int x, int y, int w, int h, int colour) { frontend *fe = (frontend *)handle; - set_colour(fe, colour); + fe->dr_api->set_colour(fe, colour); do_draw_rect(fe, x, y, w, h); } void gtk_draw_line(void *handle, int x1, int y1, int x2, int y2, int colour) { frontend *fe = (frontend *)handle; - set_colour(fe, colour); + fe->dr_api->set_colour(fe, colour); do_draw_line(fe, x1, y1, x2, y2); } @@ -1067,7 +1202,7 @@ void gtk_draw_thick_line(void *handle, float thickness, float x1, float y1, float x2, float y2, int colour) { frontend *fe = (frontend *)handle; - set_colour(fe, colour); + fe->dr_api->set_colour(fe, colour); do_draw_thick_line(fe, thickness, x1, y1, x2, y2); } @@ -1161,6 +1296,105 @@ char *gtk_text_fallback(void *handle, const char *const *strings, int nstrings) } #endif +#ifdef USE_PRINTING +void gtk_begin_doc(void *handle, int pages) +{ + frontend *fe = (frontend *)handle; + gtk_print_operation_set_n_pages(fe->printop, pages); +} + +void gtk_begin_page(void *handle, int number) +{ +} + +void gtk_begin_puzzle(void *handle, float xm, float xc, + float ym, float yc, int pw, int ph, float wmm) +{ + frontend *fe = (frontend *)handle; + double ppw, pph, pox, poy, dpmmx, dpmmy; + double scale; + + ppw = gtk_print_context_get_width(fe->printcontext); + pph = gtk_print_context_get_height(fe->printcontext); + dpmmx = gtk_print_context_get_dpi_x(fe->printcontext) / 25.4; + dpmmy = gtk_print_context_get_dpi_y(fe->printcontext) / 25.4; + + /* + * Compute the puzzle's position in pixels on the logical page. + */ + pox = xm * ppw + xc * dpmmx; + poy = ym * pph + yc * dpmmy; + + /* + * And determine the scale. + * + * I need a scale such that the maximum puzzle-coordinate + * extent of the rectangle (pw * scale) is equal to the pixel + * equivalent of the puzzle's millimetre width (wmm * dpmmx). + */ + scale = wmm * dpmmx / pw; + + /* + * Now instruct Cairo to transform points based on our calculated + * values (order here *is* important). + */ + cairo_save(fe->cr); + cairo_translate(fe->cr, pox, poy); + cairo_scale(fe->cr, scale, scale); + + fe->hatchthick = 0.2 * pw / wmm; + fe->hatchspace = 1.0 * pw / wmm; +} + +void gtk_end_puzzle(void *handle) +{ + frontend *fe = (frontend *)handle; + cairo_restore(fe->cr); +} + +void gtk_end_page(void *handle, int number) +{ +} + +void gtk_end_doc(void *handle) +{ +} + +void gtk_line_width(void *handle, float width) +{ + frontend *fe = (frontend *)handle; + cairo_set_line_width(fe->cr, width); +} + +void gtk_line_dotted(void *handle, bool dotted) +{ + frontend *fe = (frontend *)handle; + + if (dotted) { + const double dash = 35.0; + cairo_set_dash(fe->cr, &dash, 1, 0); + } else { + cairo_set_dash(fe->cr, NULL, 0, 0); + } +} +#endif /* USE_PRINTING */ + +const struct internal_drawing_api internal_drawing = { + draw_set_colour, +#ifdef USE_CAIRO + do_draw_fill, + do_draw_fill_preserve, +#endif +}; + +#ifdef USE_CAIRO +const struct internal_drawing_api internal_printing = { + print_set_colour, + do_print_fill, + do_print_fill_preserve, +}; +#endif + const struct drawing_api gtk_drawing = { gtk_draw_text, gtk_draw_rect, @@ -1177,8 +1411,19 @@ const struct drawing_api gtk_drawing = { gtk_blitter_free, gtk_blitter_save, gtk_blitter_load, +#ifdef USE_PRINTING + gtk_begin_doc, + gtk_begin_page, + gtk_begin_puzzle, + gtk_end_puzzle, + gtk_end_page, + gtk_end_doc, + gtk_line_width, + gtk_line_dotted, +#else NULL, NULL, NULL, NULL, NULL, NULL, /* {begin,end}_{doc,page,puzzle} */ NULL, NULL, /* line_width, line_dotted */ +#endif #ifdef USE_PANGO gtk_text_fallback, #else @@ -1340,12 +1585,22 @@ static gint draw_area(GtkWidget *widget, cairo_t *cr, gpointer data) frontend *fe = (frontend *)data; GdkRectangle dirtyrect; + cairo_surface_t *target_surface = cairo_get_target(cr); + cairo_matrix_t m; + cairo_get_matrix(cr, &m); + double orig_sx, orig_sy; + cairo_surface_get_device_scale(target_surface, &orig_sx, &orig_sy); + cairo_surface_set_device_scale(target_surface, 1.0, 1.0); + cairo_translate(cr, m.x0 * (orig_sx - 1.0), m.y0 * (orig_sy - 1.0)); + gdk_cairo_get_clip_rectangle(cr, &dirtyrect); cairo_set_source_surface(cr, fe->image, fe->ox, fe->oy); cairo_rectangle(cr, dirtyrect.x, dirtyrect.y, dirtyrect.width, dirtyrect.height); cairo_fill(cr); + cairo_surface_set_device_scale(target_surface, orig_sx, orig_sy); + return true; } #else @@ -1390,16 +1645,22 @@ static gint map_window(GtkWidget *widget, GdkEvent *event, static void resize_puzzle_to_area(frontend *fe, int x, int y) { int oldw = fe->w, oldpw = fe->pw, oldh = fe->h, oldph = fe->ph; + int oldps = fe->ps; fe->w = x; fe->h = y; midend_size(fe->me, &x, &y, true); fe->pw = x; fe->ph = y; +#if GTK_CHECK_VERSION(3,10,0) + fe->ps = gtk_widget_get_scale_factor(fe->area); +#else + fe->ps = 1; +#endif fe->ox = (fe->w - fe->pw) / 2; fe->oy = (fe->h - fe->ph) / 2; - if (oldw != fe->w || oldpw != fe->pw || + if (oldw != fe->w || oldpw != fe->pw || oldps != fe->ps || oldh != fe->h || oldph != fe->ph || !backing_store_ok(fe)) { if (backing_store_ok(fe)) teardown_backing_store(fe); @@ -1413,6 +1674,7 @@ static gint configure_area(GtkWidget *widget, GdkEventConfigure *event, gpointer data) { frontend *fe = (frontend *)data; + resize_puzzle_to_area(fe, event->width, event->height); #if GTK_CHECK_VERSION(3,0,0) fe->awaiting_resize_ack = false; @@ -2245,6 +2507,317 @@ static char *file_selector(frontend *fe, const char *title, bool save) #endif +#ifdef USE_PRINTING +GObject *create_print_widget(GtkPrintOperation *print, gpointer data) +{ + GtkLabel *count_label, *width_label, *height_label, + *scale_llabel, *scale_rlabel; + GtkBox *scale_hbox; + GtkWidget *grid; + frontend *fe = (frontend *)data; + + fe->printcount_spin_button = + GTK_SPIN_BUTTON(gtk_spin_button_new_with_range(1, 999, 1)); + gtk_spin_button_set_numeric(fe->printcount_spin_button, true); + gtk_spin_button_set_snap_to_ticks(fe->printcount_spin_button, true); + fe->printw_spin_button = + GTK_SPIN_BUTTON(gtk_spin_button_new_with_range(1, 99, 1)); + gtk_spin_button_set_numeric(fe->printw_spin_button, true); + gtk_spin_button_set_snap_to_ticks(fe->printw_spin_button, true); + fe->printh_spin_button = + GTK_SPIN_BUTTON(gtk_spin_button_new_with_range(1, 99, 1)); + gtk_spin_button_set_numeric(fe->printh_spin_button, true); + gtk_spin_button_set_snap_to_ticks(fe->printh_spin_button, true); + fe->printscale_spin_button = + GTK_SPIN_BUTTON(gtk_spin_button_new_with_range(1, 1000, 1)); + gtk_spin_button_set_digits(fe->printscale_spin_button, 1); + gtk_spin_button_set_numeric(fe->printscale_spin_button, true); + if (thegame.can_solve) { + fe->soln_check_button = + GTK_CHECK_BUTTON( + gtk_check_button_new_with_label("Print solutions")); + } + if (thegame.can_print_in_colour) { + fe->colour_check_button = + GTK_CHECK_BUTTON( + gtk_check_button_new_with_label("Print in color")); + } + + /* Set defaults to what was selected last time. */ + gtk_spin_button_set_value(fe->printcount_spin_button, + (gdouble)fe->printcount); + gtk_spin_button_set_value(fe->printw_spin_button, + (gdouble)fe->printw); + gtk_spin_button_set_value(fe->printh_spin_button, + (gdouble)fe->printh); + gtk_spin_button_set_value(fe->printscale_spin_button, + (gdouble)fe->printscale); + if (thegame.can_solve) { + gtk_toggle_button_set_active( + GTK_TOGGLE_BUTTON(fe->soln_check_button), fe->printsolns); + } + if (thegame.can_print_in_colour) { + gtk_toggle_button_set_active( + GTK_TOGGLE_BUTTON(fe->colour_check_button), fe->printcolour); + } + + count_label = GTK_LABEL(gtk_label_new("Puzzles to print:")); + width_label = GTK_LABEL(gtk_label_new("Puzzles across:")); + height_label = GTK_LABEL(gtk_label_new("Puzzles down:")); + scale_llabel = GTK_LABEL(gtk_label_new("Puzzle scale:")); + scale_rlabel = GTK_LABEL(gtk_label_new("%")); +#if GTK_CHECK_VERSION(3,0,0) + gtk_widget_set_halign(GTK_WIDGET(count_label), GTK_ALIGN_START); + gtk_widget_set_halign(GTK_WIDGET(width_label), GTK_ALIGN_START); + gtk_widget_set_halign(GTK_WIDGET(height_label), GTK_ALIGN_START); + gtk_widget_set_halign(GTK_WIDGET(scale_llabel), GTK_ALIGN_START); +#else + gtk_misc_set_alignment(GTK_MISC(count_label), 0, 0); + gtk_misc_set_alignment(GTK_MISC(width_label), 0, 0); + gtk_misc_set_alignment(GTK_MISC(height_label), 0, 0); + gtk_misc_set_alignment(GTK_MISC(scale_llabel), 0, 0); +#endif + + scale_hbox = GTK_BOX(gtk_hbox_new(false, 6)); + gtk_box_pack_start(scale_hbox, GTK_WIDGET(fe->printscale_spin_button), + false, false, 0); + gtk_box_pack_start(scale_hbox, GTK_WIDGET(scale_rlabel), + false, false, 0); + +#if GTK_CHECK_VERSION(3,0,0) + grid = gtk_grid_new(); + gtk_grid_set_column_spacing(GTK_GRID(grid), 18); + gtk_grid_set_row_spacing(GTK_GRID(grid), 18); + gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(count_label), 0, 0, 1, 1); + gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(width_label), 0, 1, 1, 1); + gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(height_label), 0, 2, 1, 1); + gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(scale_llabel), 0, 3, 1, 1); + gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(fe->printcount_spin_button), + 1, 0, 1, 1); + gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(fe->printw_spin_button), + 1, 1, 1, 1); + gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(fe->printh_spin_button), + 1, 2, 1, 1); + gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(scale_hbox), 1, 3, 1, 1); + if (thegame.can_solve) { + gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(fe->soln_check_button), + 0, 4, 1, 1); + } + if (thegame.can_print_in_colour) { + gtk_grid_attach(GTK_GRID(grid), GTK_WIDGET(fe->colour_check_button), + thegame.can_solve, 4, 1, 1); + } +#else + grid = gtk_table_new((thegame.can_solve || thegame.can_print_in_colour) ? + 5 : 4, 2, false); + gtk_table_set_col_spacings(GTK_TABLE(grid), 18); + gtk_table_set_row_spacings(GTK_TABLE(grid), 18); + gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(count_label), 0, 1, 0, 1, + GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0); + gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(width_label), 0, 1, 1, 2, + GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0); + gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(height_label), 0, 1, 2, 3, + GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0); + gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(scale_llabel), 0, 1, 3, 4, + GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0); + gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(fe->printcount_spin_button), + 1, 2, 0, 1, + GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0); + gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(fe->printw_spin_button), + 1, 2, 1, 2, + GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0); + gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(fe->printh_spin_button), + 1, 2, 2, 3, + GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0); + gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(scale_hbox), 1, 2, 3, 4, + GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0); + if (thegame.can_solve) { + gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(fe->soln_check_button), + 0, 1, 4, 5, + GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0); + } + if (thegame.can_print_in_colour) { + gtk_table_attach(GTK_TABLE(grid), GTK_WIDGET(fe->colour_check_button), + thegame.can_solve, thegame.can_solve + 1, 4, 5, + GTK_SHRINK | GTK_FILL, GTK_SHRINK | GTK_FILL, 0, 0); + } +#endif + gtk_container_set_border_width(GTK_CONTAINER(grid), 12); + + gtk_widget_show_all(grid); + + return G_OBJECT(grid); +} + +void apply_print_widget(GtkPrintOperation *print, + GtkWidget *widget, gpointer data) +{ + frontend *fe = (frontend *)data; + + /* We ignore `widget' because it is easier and faster to store the + widgets we need in `fe' then to get the children of `widget'. */ + fe->printcount = + gtk_spin_button_get_value_as_int(fe->printcount_spin_button); + fe->printw = gtk_spin_button_get_value_as_int(fe->printw_spin_button); + fe->printh = gtk_spin_button_get_value_as_int(fe->printh_spin_button); + fe->printscale = gtk_spin_button_get_value(fe->printscale_spin_button); + if (thegame.can_solve) { + fe->printsolns = + gtk_toggle_button_get_active( + GTK_TOGGLE_BUTTON(fe->soln_check_button)); + } + if (thegame.can_print_in_colour) { + fe->printcolour = + gtk_toggle_button_get_active( + GTK_TOGGLE_BUTTON(fe->colour_check_button)); + } +} + +void print_begin(GtkPrintOperation *printop, + GtkPrintContext *context, gpointer data) +{ + frontend *fe = (frontend *)data; + midend *nme = NULL; /* non-interactive midend for bulk puzzle generation */ + int i; + + fe->printcontext = context; + fe->cr = gtk_print_context_get_cairo_context(context); + + /* + * Create our document structure and fill it up with puzzles. + */ + fe->doc = document_new(fe->printw, fe->printh, fe->printscale / 100.0F); + + for (i = 0; i < fe->printcount; i++) { + const char *err; + + if (i == 0) { + err = midend_print_puzzle(fe->me, fe->doc, fe->printsolns); + } else { + if (!nme) { + game_params *params; + + nme = midend_new(NULL, &thegame, NULL, NULL); + + /* + * Set the non-interactive mid-end to have the same + * parameters as the standard one. + */ + params = midend_get_params(fe->me); + midend_set_params(nme, params); + thegame.free_params(params); + } + + midend_new_game(nme); + err = midend_print_puzzle(nme, fe->doc, fe->printsolns); + } + + if (err) { + error_box(fe->window, err); + return; + } + } + + if (nme) + midend_free(nme); + + /* Begin the document. */ + document_begin(fe->doc, fe->print_dr); +} + +void draw_page(GtkPrintOperation *printop, + GtkPrintContext *context, + gint page_nr, gpointer data) +{ + frontend *fe = (frontend *)data; + document_print_page(fe->doc, fe->print_dr, page_nr); +} + +void print_end(GtkPrintOperation *printop, + GtkPrintContext *context, gpointer data) +{ + frontend *fe = (frontend *)data; + + /* End and free the document. */ + document_end(fe->doc, fe->print_dr); + document_free(fe->doc); + fe->doc = NULL; +} + +static void print_dialog(frontend *fe) +{ + GError *error; + static GtkPrintSettings *settings = NULL; + static GtkPageSetup *page_setup = NULL; +#ifndef USE_EMBED_PAGE_SETUP + GtkPageSetup *new_page_setup; +#endif + + fe->printop = gtk_print_operation_new(); + gtk_print_operation_set_use_full_page(fe->printop, true); + gtk_print_operation_set_custom_tab_label(fe->printop, "Puzzle Settings"); + g_signal_connect(fe->printop, "create-custom-widget", + G_CALLBACK(create_print_widget), fe); + g_signal_connect(fe->printop, "custom-widget-apply", + G_CALLBACK(apply_print_widget), fe); + g_signal_connect(fe->printop, "begin-print", G_CALLBACK(print_begin), fe); + g_signal_connect(fe->printop, "draw-page", G_CALLBACK(draw_page), fe); + g_signal_connect(fe->printop, "end-print", G_CALLBACK(print_end), fe); +#ifdef USE_EMBED_PAGE_SETUP + gtk_print_operation_set_embed_page_setup(fe->printop, true); +#else + if (page_setup == NULL) { + page_setup = + g_object_ref( + gtk_print_operation_get_default_page_setup(fe->printop)); + } + if (settings == NULL) { + settings = + g_object_ref(gtk_print_operation_get_print_settings(fe->printop)); + } + new_page_setup = gtk_print_run_page_setup_dialog(GTK_WINDOW(fe->window), + page_setup, settings); + g_object_unref(page_setup); + page_setup = new_page_setup; + gtk_print_operation_set_default_page_setup(fe->printop, page_setup); +#endif + + if (settings != NULL) + gtk_print_operation_set_print_settings(fe->printop, settings); + if (page_setup != NULL) + gtk_print_operation_set_default_page_setup(fe->printop, page_setup); + + switch (gtk_print_operation_run(fe->printop, + GTK_PRINT_OPERATION_ACTION_PRINT_DIALOG, + GTK_WINDOW(fe->window), &error)) { + case GTK_PRINT_OPERATION_RESULT_ERROR: + error_box(fe->window, error->message); + g_error_free(error); + break; + case GTK_PRINT_OPERATION_RESULT_APPLY: + if (settings != NULL) + g_object_unref(settings); + settings = + g_object_ref(gtk_print_operation_get_print_settings(fe->printop)); +#ifdef USE_EMBED_PAGE_SETUP + if (page_setup != NULL) + g_object_unref(page_setup); + page_setup = + g_object_ref( + gtk_print_operation_get_default_page_setup(fe->printop)); +#endif + break; + default: + /* Don't error out on -Werror=switch. */ + break; + } + + g_object_unref(fe->printop); + fe->printop = NULL; + fe->printcontext = NULL; +} +#endif /* USE_PRINTING */ + struct savefile_write_ctx { FILE *fp; int error; @@ -2346,6 +2919,15 @@ static void menu_load_event(GtkMenuItem *menuitem, gpointer data) } } +#ifdef USE_PRINTING +static void menu_print_event(GtkMenuItem *menuitem, gpointer data) +{ + frontend *fe = (frontend *)data; + + print_dialog(fe); +} +#endif + static void menu_solve_event(GtkMenuItem *menuitem, gpointer data) { frontend *fe = (frontend *)data; @@ -2388,18 +2970,31 @@ static void menu_about_event(GtkMenuItem *menuitem, gpointer data) frontend *fe = (frontend *)data; #if GTK_CHECK_VERSION(3,0,0) +# define ABOUT_PARAMS \ + "program-name", thegame.name, \ + "version", ver, \ + "comments", "Part of Simon Tatham's Portable Puzzle Collection" + extern char *const *const xpm_icons[]; extern const int n_xpm_icons; - GdkPixbuf *icon = gdk_pixbuf_new_from_xpm_data - ((const gchar **)xpm_icons[n_xpm_icons-1]); - gtk_show_about_dialog - (GTK_WINDOW(fe->window), - "program-name", thegame.name, - "version", ver, - "comments", "Part of Simon Tatham's Portable Puzzle Collection", - "logo", icon, - (const gchar *)NULL); - g_object_unref(G_OBJECT(icon)); + + if (n_xpm_icons) { + GdkPixbuf *icon = gdk_pixbuf_new_from_xpm_data + ((const gchar **)xpm_icons[n_xpm_icons-1]); + + gtk_show_about_dialog + (GTK_WINDOW(fe->window), + ABOUT_PARAMS, + "logo", icon, + (const gchar *)NULL); + g_object_unref(G_OBJECT(icon)); + } + else { + gtk_show_about_dialog + (GTK_WINDOW(fe->window), + ABOUT_PARAMS, + (const gchar *)NULL); + } #else char titlebuf[256]; char textbuf[1024]; @@ -2489,6 +3084,9 @@ static frontend *new_window( char *arg, int argtype, char **error, bool headless) { frontend *fe; +#ifdef USE_PRINTING + frontend *print_fe = NULL; +#endif GtkBox *vbox, *hbox; GtkWidget *menu, *menuitem; GList *iconlist; @@ -2501,13 +3099,14 @@ static frontend *new_window( fe = snew(frontend); memset(fe, 0, sizeof(frontend)); -#if !GTK_CHECK_VERSION(3,0,0) +#ifndef USE_CAIRO if (headless) { - fprintf(stderr, "headless mode not supported below GTK 3\n"); + fprintf(stderr, "headless mode not supported for non-Cairo drawing\n"); exit(1); } #else fe->headless = headless; + fe->ps = 1; /* in headless mode, configure_area won't have set this */ #endif fe->timer_active = false; @@ -2515,6 +3114,32 @@ static frontend *new_window( fe->me = midend_new(fe, &thegame, >k_drawing, fe); + fe->dr_api = &internal_drawing; + +#ifdef USE_PRINTING + if (thegame.can_print) { + print_fe = snew(frontend); + memset(print_fe, 0, sizeof(frontend)); + + /* Defaults */ + print_fe->printcount = print_fe->printw = print_fe->printh = 1; + print_fe->printscale = 100; + print_fe->printsolns = false; + print_fe->printcolour = thegame.can_print_in_colour; + + /* + * We need to use the same midend as the main frontend because + * we need midend_print_puzzle() to be able to print the + * current puzzle. + */ + print_fe->me = fe->me; + + print_fe->print_dr = drawing_new(>k_drawing, print_fe->me, print_fe); + + print_fe->dr_api = &internal_printing; + } +#endif + if (arg) { const char *err; FILE *fp; @@ -2568,6 +3193,12 @@ static frontend *new_window( *error = dupstr(errbuf); midend_free(fe->me); sfree(fe); +#ifdef USE_PRINTING + if (thegame.can_print) { + drawing_free(print_fe->print_dr); + sfree(print_fe); + } +#endif return NULL; } @@ -2711,6 +3342,16 @@ static frontend *new_window( g_signal_connect(G_OBJECT(menuitem), "activate", G_CALLBACK(menu_save_event), fe); gtk_widget_show(menuitem); +#ifdef USE_PRINTING + if (thegame.can_print) { + add_menu_separator(GTK_CONTAINER(menu)); + menuitem = gtk_menu_item_new_with_label("Print..."); + gtk_container_add(GTK_CONTAINER(menu), menuitem); + g_signal_connect(G_OBJECT(menuitem), "activate", + G_CALLBACK(menu_print_event), print_fe); + gtk_widget_show(menuitem); + } +#endif #ifndef STYLUS_BASED add_menu_separator(GTK_CONTAINER(menu)); 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) #define SOLVER(upper,title,func,lower) func, static usersolver_t const keen_solvers[] = { DIFFLIST(SOLVER) }; +static int transpose(int index, int w) +{ + return (index % w) * w + (index / w); +} + +static bool keen_valid(struct latin_solver *solver, void *vctx) +{ + struct solver_ctx *ctx = (struct solver_ctx *)vctx; + int w = ctx->w; + int box, i; + + /* + * Iterate over each clue box and check it's satisfied. + */ + for (box = 0; box < ctx->nboxes; box++) { + int *sq = ctx->boxlist + ctx->boxes[box]; + int n = ctx->boxes[box+1] - ctx->boxes[box]; + long value = ctx->clues[box] & ~CMASK; + long op = ctx->clues[box] & CMASK; + bool fail = false; + + switch (op) { + case C_ADD: { + long sum = 0; + for (i = 0; i < n; i++) + sum += solver->grid[transpose(sq[i], w)]; + fail = (sum != value); + break; + } + + case C_MUL: { + long remaining = value; + for (i = 0; i < n; i++) { + if (remaining % solver->grid[transpose(sq[i], w)]) { + fail = true; + break; + } + remaining /= solver->grid[transpose(sq[i], w)]; + } + if (remaining != 1) + fail = true; + break; + } + + case C_SUB: + assert(n == 2); + if (value != labs(solver->grid[transpose(sq[0], w)] - + solver->grid[transpose(sq[1], w)])) + fail = true; + break; + + case C_DIV: { + int num, den; + assert(n == 2); + num = max(solver->grid[transpose(sq[0], w)], + solver->grid[transpose(sq[1], w)]); + den = min(solver->grid[transpose(sq[0], w)], + solver->grid[transpose(sq[1], w)]); + if (den * value != num) + fail = true; + break; + } + } + + if (fail) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*sclue at (%d,%d) is violated\n", + solver_recurse_depth*4, "", + sq[0]/w+1, sq[0]%w+1); + printf("%*s (%s clue with target %ld containing [", + solver_recurse_depth*4, "", + (op == C_ADD ? "addition" : op == C_SUB ? "subtraction": + op == C_MUL ? "multiplication" : "division"), value); + for (i = 0; i < n; i++) + printf(" %d", (int)solver->grid[transpose(sq[i], w)]); + printf(" ]\n"); + } +#endif + return false; + } + } + + return true; +} + static int solver(int w, int *dsf, long *clues, digit *soln, int maxdiff) { int a = w*w; @@ -638,7 +724,7 @@ static int solver(int w, int *dsf, long *clues, digit *soln, int maxdiff) ret = latin_solver(soln, w, maxdiff, DIFF_EASY, DIFF_HARD, DIFF_EXTREME, DIFF_EXTREME, DIFF_UNREASONABLE, - keen_solvers, &ctx, NULL, NULL); + keen_solvers, keen_valid, &ctx, NULL, NULL); sfree(ctx.dscratch); 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 @@ static int latin_solver_top(struct latin_solver *solver, int maxdiff, int diff_simple, int diff_set_0, int diff_set_1, int diff_forcing, int diff_recursive, - usersolver_t const *usersolvers, void *ctx, - ctxnew_t ctxnew, ctxfree_t ctxfree); + usersolver_t const *usersolvers, validator_t valid, + void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree); #ifdef STANDALONE_SOLVER int solver_show_working, solver_recurse_depth; @@ -711,7 +711,7 @@ int latin_solver_diff_set(struct latin_solver *solver, static int latin_solver_recurse (struct latin_solver *solver, int diff_simple, int diff_set_0, int diff_set_1, int diff_forcing, int diff_recursive, - usersolver_t const *usersolvers, void *ctx, + usersolver_t const *usersolvers, validator_t valid, void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree) { int best, bestcount; @@ -817,7 +817,8 @@ static int latin_solver_recurse ret = latin_solver_top(&subsolver, diff_recursive, diff_simple, diff_set_0, diff_set_1, diff_forcing, diff_recursive, - usersolvers, newctx, ctxnew, ctxfree); + usersolvers, valid, newctx, + ctxnew, ctxfree); latin_solver_free(&subsolver); if (ctxnew) ctxfree(newctx); @@ -879,8 +880,8 @@ static int latin_solver_recurse static int latin_solver_top(struct latin_solver *solver, int maxdiff, int diff_simple, int diff_set_0, int diff_set_1, int diff_forcing, int diff_recursive, - usersolver_t const *usersolvers, void *ctx, - ctxnew_t ctxnew, ctxfree_t ctxfree) + usersolver_t const *usersolvers, validator_t valid, + void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree) { struct latin_solver_scratch *scratch = latin_solver_new_scratch(solver); int ret, diff = diff_simple; @@ -941,7 +942,8 @@ static int latin_solver_top(struct latin_solver *solver, int maxdiff, int nsol = latin_solver_recurse(solver, diff_simple, diff_set_0, diff_set_1, diff_forcing, diff_recursive, - usersolvers, ctx, ctxnew, ctxfree); + usersolvers, valid, ctx, + ctxnew, ctxfree); if (nsol < 0) diff = diff_impossible; else if (nsol == 1) diff = diff_recursive; else if (nsol > 1) diff = diff_ambiguous; @@ -990,6 +992,17 @@ static int latin_solver_top(struct latin_solver *solver, int maxdiff, } #endif + if (diff != diff_impossible && diff != diff_unfinished && + diff != diff_ambiguous && valid && !valid(solver, ctx)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*ssolution failed final validation!\n", + solver_recurse_depth*4, ""); + } +#endif + diff = diff_impossible; + } + latin_solver_free_scratch(scratch); return diff; @@ -998,8 +1011,8 @@ static int latin_solver_top(struct latin_solver *solver, int maxdiff, int latin_solver_main(struct latin_solver *solver, int maxdiff, int diff_simple, int diff_set_0, int diff_set_1, int diff_forcing, int diff_recursive, - usersolver_t const *usersolvers, void *ctx, - ctxnew_t ctxnew, ctxfree_t ctxfree) + usersolver_t const *usersolvers, validator_t valid, + void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree) { int diff; #ifdef STANDALONE_SOLVER @@ -1027,7 +1040,7 @@ int latin_solver_main(struct latin_solver *solver, int maxdiff, diff = latin_solver_top(solver, maxdiff, diff_simple, diff_set_0, diff_set_1, diff_forcing, diff_recursive, - usersolvers, ctx, ctxnew, ctxfree); + usersolvers, valid, ctx, ctxnew, ctxfree); #ifdef STANDALONE_SOLVER sfree(names); @@ -1040,8 +1053,8 @@ int latin_solver_main(struct latin_solver *solver, int maxdiff, int latin_solver(digit *grid, int o, int maxdiff, int diff_simple, int diff_set_0, int diff_set_1, int diff_forcing, int diff_recursive, - usersolver_t const *usersolvers, void *ctx, - ctxnew_t ctxnew, ctxfree_t ctxfree) + usersolver_t const *usersolvers, validator_t valid, + void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree) { struct latin_solver solver; int diff; @@ -1050,7 +1063,7 @@ int latin_solver(digit *grid, int o, int maxdiff, diff = latin_solver_main(&solver, maxdiff, diff_simple, diff_set_0, diff_set_1, diff_forcing, diff_recursive, - usersolvers, ctx, ctxnew, ctxfree); + usersolvers, valid, ctx, ctxnew, ctxfree); latin_solver_free(&solver); return diff; } 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, bool extreme); typedef int (*usersolver_t)(struct latin_solver *solver, void *ctx); +typedef bool (*validator_t)(struct latin_solver *solver, void *ctx); typedef void *(*ctxnew_t)(void *ctx); typedef void (*ctxfree_t)(void *ctx); @@ -96,15 +97,15 @@ enum { diff_impossible = 10, diff_ambiguous, diff_unfinished }; int latin_solver(digit *grid, int o, int maxdiff, int diff_simple, int diff_set_0, int diff_set_1, int diff_forcing, int diff_recursive, - usersolver_t const *usersolvers, void *ctx, - ctxnew_t ctxnew, ctxfree_t ctxfree); + usersolver_t const *usersolvers, validator_t valid, + void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree); /* Version you can call if you want to alloc and free latin_solver yourself */ int latin_solver_main(struct latin_solver *solver, int maxdiff, int diff_simple, int diff_set_0, int diff_set_1, int diff_forcing, int diff_recursive, - usersolver_t const *usersolvers, void *ctx, - ctxnew_t ctxnew, ctxfree_t ctxfree); + usersolver_t const *usersolvers, validator_t valid, + void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree); void latin_solver_debug(unsigned char *cube, int o); 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) */ if (full && params->unique && (params->w <= 2 || params->h <= 2)) return "Width and height must both be greater than two"; + if (params->n < 0) + return "Mine count may not be negative"; if (params->n > params->w * params->h - 9) return "Too many mines for grid size"; 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 { COL_GRID, COL_CURSOR, COL_ERROR, + COL_CURSOR_GUIDE, NCOLOURS }; @@ -1660,11 +1661,12 @@ static float *game_colours(frontend *fe, int *ncolours) frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); for (i = 0; i < 3; i++) { - ret[COL_GRID * 3 + i] = 0.3F; - ret[COL_UNKNOWN * 3 + i] = 0.5F; - ret[COL_TEXT * 3 + i] = 0.0F; - ret[COL_FULL * 3 + i] = 0.0F; - ret[COL_EMPTY * 3 + i] = 1.0F; + ret[COL_GRID * 3 + i] = 0.3F; + ret[COL_UNKNOWN * 3 + i] = 0.5F; + ret[COL_TEXT * 3 + i] = 0.0F; + ret[COL_FULL * 3 + i] = 0.0F; + ret[COL_EMPTY * 3 + i] = 1.0F; + ret[COL_CURSOR_GUIDE * 3 + i] = 0.5F; } ret[COL_CURSOR * 3 + 0] = 1.0F; ret[COL_CURSOR * 3 + 1] = 0.25F; @@ -1891,6 +1893,9 @@ static void game_redraw(drawing *dr, game_drawstate *ds, */ for (i = 0; i < state->common->w + state->common->h; i++) { int colour = check_errors(state, i) ? COL_ERROR : COL_TEXT; + if (colour == COL_TEXT && ((cx >= 0 && i == cx) || (cy >= 0 && i == cy + ds->w))) { + colour = COL_CURSOR_GUIDE; + } if (ds->numcolours[i] != colour) { draw_numbers(dr, ds, state, i, true, colour); 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 @@ * setup and layout. */ +#include + #include "puzzles.h" struct puzzle { @@ -88,7 +90,7 @@ void document_add_puzzle(document *doc, const game *game, game_params *par, doc->got_solns = true; } -static void get_puzzle_size(document *doc, struct puzzle *pz, +static void get_puzzle_size(const document *doc, struct puzzle *pz, float *w, float *h, float *scale) { float ww, hh, ourscale; @@ -115,133 +117,177 @@ static void get_puzzle_size(document *doc, struct puzzle *pz, } /* - * Having accumulated a load of puzzles, actually do the printing. + * Calculate the the number of pages for a document. */ -void document_print(document *doc, drawing *dr) +int document_npages(const document *doc) { int ppp; /* puzzles per page */ int pages, passes; + + ppp = doc->pw * doc->ph; + pages = (doc->npuzzles + ppp - 1) / ppp; + passes = (doc->got_solns ? 2 : 1); + + return pages * passes; +} + +/* + * Begin a document. + */ +void document_begin(const document *doc, drawing *dr) +{ + print_begin_doc(dr, document_npages(doc)); +} + +/* + * End a document. + */ +void document_end(const document *doc, drawing *dr) +{ + print_end_doc(dr); +} + +/* + * Print a single page of a document. + */ +void document_print_page(const document *doc, drawing *dr, int page_nr) +{ + int ppp; /* puzzles per page */ + int pages; int page, pass; int pageno; + int i, n, offset; + float colsum, rowsum; ppp = doc->pw * doc->ph; pages = (doc->npuzzles + ppp - 1) / ppp; - passes = (doc->got_solns ? 2 : 1); - print_begin_doc(dr, pages * passes); - - pageno = 1; - for (pass = 0; pass < passes; pass++) { - for (page = 0; page < pages; page++) { - int i, n, offset; - float colsum, rowsum; - - print_begin_page(dr, pageno); - - offset = page * ppp; - n = min(ppp, doc->npuzzles - offset); - - for (i = 0; i < doc->pw; i++) - doc->colwid[i] = 0; - for (i = 0; i < doc->ph; i++) - doc->rowht[i] = 0; - - /* - * Lay the page out by computing all the puzzle sizes. - */ - for (i = 0; i < n; i++) { - struct puzzle *pz = doc->puzzles + offset + i; - int x = i % doc->pw, y = i / doc->pw; - float w, h, scale; - - get_puzzle_size(doc, pz, &w, &h, &scale); - - /* Update the maximum width/height of this column. */ - doc->colwid[x] = max(doc->colwid[x], w); - doc->rowht[y] = max(doc->rowht[y], h); - } - - /* - * Add up the maximum column/row widths to get the - * total amount of space used up by puzzles on the - * page. We will use this to compute gutter widths. - */ - colsum = 0.0; - for (i = 0; i < doc->pw; i++) - colsum += doc->colwid[i]; - rowsum = 0.0; - for (i = 0; i < doc->ph; i++) - rowsum += doc->rowht[i]; - - /* - * Now do the printing. - */ - for (i = 0; i < n; i++) { - struct puzzle *pz = doc->puzzles + offset + i; - int x = i % doc->pw, y = i / doc->pw, j; - float w, h, scale, xm, xc, ym, yc; - int pixw, pixh, tilesize; - - if (pass == 1 && !pz->st2) - continue; /* nothing to do */ - - /* - * The total amount of gutter space is the page - * width minus colsum. This is divided into pw+1 - * gutters, so the amount of horizontal gutter - * space appearing to the left of this puzzle - * column is - * - * (width-colsum) * (x+1)/(pw+1) - * = width * (x+1)/(pw+1) - (colsum * (x+1)/(pw+1)) - */ - xm = (float)(x+1) / (doc->pw + 1); - xc = -xm * colsum; - /* And similarly for y. */ - ym = (float)(y+1) / (doc->ph + 1); - yc = -ym * rowsum; - - /* - * However, the amount of space to the left of this - * puzzle isn't just gutter space: we must also - * count the widths of all the previous columns. - */ - for (j = 0; j < x; j++) - xc += doc->colwid[j]; - /* And similarly for rows. */ - for (j = 0; j < y; j++) - yc += doc->rowht[j]; - - /* - * Now we adjust for this _specific_ puzzle, which - * means centring it within the cell we've just - * computed. - */ - get_puzzle_size(doc, pz, &w, &h, &scale); - xc += (doc->colwid[x] - w) / 2; - yc += (doc->rowht[y] - h) / 2; - - /* - * And now we know where and how big we want to - * print the puzzle, just go ahead and do so. For - * the moment I'll pick a standard pixel tile size - * of 512. - * - * (FIXME: would it be better to pick this value - * with reference to the printer resolution? Or - * permit each game to choose its own?) - */ - tilesize = 512; - pz->game->compute_size(pz->par, tilesize, &pixw, &pixh); - print_begin_puzzle(dr, xm, xc, ym, yc, pixw, pixh, w, scale); - pz->game->print(dr, pass == 0 ? pz->st : pz->st2, tilesize); - print_end_puzzle(dr); - } - - print_end_page(dr, pageno); - pageno++; - } + /* Get the current page, pass, and pageno based on page_nr. */ + if (page_nr < pages) { + page = page_nr; + pass = 0; + } + else { + assert(doc->got_solns); + page = page_nr - pages; + pass = 1; + } + pageno = page_nr + 1; + + offset = page * ppp; + n = min(ppp, doc->npuzzles - offset); + + print_begin_page(dr, pageno); + + for (i = 0; i < doc->pw; i++) + doc->colwid[i] = 0; + for (i = 0; i < doc->ph; i++) + doc->rowht[i] = 0; + + /* + * Lay the page out by computing all the puzzle sizes. + */ + for (i = 0; i < n; i++) { + struct puzzle *pz = doc->puzzles + offset + i; + int x = i % doc->pw, y = i / doc->pw; + float w, h, scale; + + get_puzzle_size(doc, pz, &w, &h, &scale); + + /* Update the maximum width/height of this column. */ + doc->colwid[x] = max(doc->colwid[x], w); + doc->rowht[y] = max(doc->rowht[y], h); + } + + /* + * Add up the maximum column/row widths to get the + * total amount of space used up by puzzles on the + * page. We will use this to compute gutter widths. + */ + colsum = 0.0; + for (i = 0; i < doc->pw; i++) + colsum += doc->colwid[i]; + rowsum = 0.0; + for (i = 0; i < doc->ph; i++) + rowsum += doc->rowht[i]; + + /* + * Now do the printing. + */ + for (i = 0; i < n; i++) { + struct puzzle *pz = doc->puzzles + offset + i; + int x = i % doc->pw, y = i / doc->pw, j; + float w, h, scale, xm, xc, ym, yc; + int pixw, pixh, tilesize; + + if (pass == 1 && !pz->st2) + continue; /* nothing to do */ + + /* + * The total amount of gutter space is the page + * width minus colsum. This is divided into pw+1 + * gutters, so the amount of horizontal gutter + * space appearing to the left of this puzzle + * column is + * + * (width-colsum) * (x+1)/(pw+1) + * = width * (x+1)/(pw+1) - (colsum * (x+1)/(pw+1)) + */ + xm = (float)(x+1) / (doc->pw + 1); + xc = -xm * colsum; + /* And similarly for y. */ + ym = (float)(y+1) / (doc->ph + 1); + yc = -ym * rowsum; + + /* + * However, the amount of space to the left of this + * puzzle isn't just gutter space: we must also + * count the widths of all the previous columns. + */ + for (j = 0; j < x; j++) + xc += doc->colwid[j]; + /* And similarly for rows. */ + for (j = 0; j < y; j++) + yc += doc->rowht[j]; + + /* + * Now we adjust for this _specific_ puzzle, which + * means centring it within the cell we've just + * computed. + */ + get_puzzle_size(doc, pz, &w, &h, &scale); + xc += (doc->colwid[x] - w) / 2; + yc += (doc->rowht[y] - h) / 2; + + /* + * And now we know where and how big we want to + * print the puzzle, just go ahead and do so. For + * the moment I'll pick a standard pixel tile size + * of 512. + * + * (FIXME: would it be better to pick this value + * with reference to the printer resolution? Or + * permit each game to choose its own?) + */ + tilesize = 512; + pz->game->compute_size(pz->par, tilesize, &pixw, &pixh); + print_begin_puzzle(dr, xm, xc, ym, yc, pixw, pixh, w, scale); + pz->game->print(dr, pass == 0 ? pz->st : pz->st2, tilesize); + print_end_puzzle(dr); } + print_end_page(dr, pageno); +} + +/* + * Having accumulated a load of puzzles, actually do the printing. + */ +void document_print(const document *doc, drawing *dr) +{ + int page, pages; + pages = document_npages(doc); + print_begin_doc(dr, pages); + for (page = 0; page < pages; page++) + document_print_page(doc, dr, page); print_end_doc(dr); } 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 @@ #include "puzzles.h" -#define ROOT2 1.414213562 - struct psdata { FILE *fp; 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. Portions copyright Richard Boulton, James Harvey, Mike Pinna, Jonas K\u00F6{oe}lker, Dariusz Olszewski, Michael Schierl, Lambros Lambrou, -Bernd Schmidt, Steffen Bauer, Lennard Sprong and Rogier Goossens. +Bernd Schmidt, Steffen Bauer, Lennard Sprong, Rogier Goossens, Michael +Quevillon and Asher Gordon. Permission is hereby granted, free of charge, to any person obtaining 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 @@ #include #define PI 3.141592653589793238462643383279502884197169399 +#define ROOT2 1.414213562373095048801688724209698078569672 #define lenof(array) ( sizeof(array) / sizeof(*(array)) ) @@ -530,7 +531,11 @@ document *document_new(int pw, int ph, float userscale); void document_free(document *doc); void document_add_puzzle(document *doc, const game *game, game_params *par, game_state *st, game_state *st2); -void document_print(document *doc, drawing *dr); +int document_npages(const document *doc); +void document_begin(const document *doc, drawing *dr); +void document_end(const document *doc, drawing *dr); +void document_print_page(const document *doc, drawing *dr, int page_nr); +void document_print(const document *doc, drawing *dr); /* * 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) #define SOLVER(upper,title,func,lower) func, static usersolver_t const towers_solvers[] = { DIFFLIST(SOLVER) }; +static bool towers_valid(struct latin_solver *solver, void *vctx) +{ + struct solver_ctx *ctx = (struct solver_ctx *)vctx; + int w = ctx->w; + int c, i, n, best, clue, start, step; + for (c = 0; c < 4*w; c++) { + clue = ctx->clues[c]; + if (!clue) + continue; + + STARTSTEP(start, step, c, w); + n = best = 0; + for (i = 0; i < w; i++) { + if (solver->grid[start+i*step] > best) { + best = solver->grid[start+i*step]; + n++; + } + } + + if (n != clue) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("%*sclue %s %d is violated\n", + solver_recurse_depth*4, "", + cluepos[c/w], c%w+1); +#endif + return false; + } + } + return true; +} + static int solver(int w, int *clues, digit *soln, int maxdiff) { int ret; @@ -589,7 +621,7 @@ static int solver(int w, int *clues, digit *soln, int maxdiff) ret = latin_solver(soln, w, maxdiff, DIFF_EASY, DIFF_HARD, DIFF_EXTREME, DIFF_EXTREME, DIFF_UNREASONABLE, - towers_solvers, &ctx, NULL, NULL); + towers_solvers, towers_valid, &ctx, NULL, NULL); sfree(ctx.iscratch); 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 ALL += tracks[COMBINED] TRACKS_EXTRA +trackssolver : [U] tracks[STANDALONE_SOLVER] TRACKS_EXTRA STANDALONE +trackssolver : [C] tracks[STANDALONE_SOLVER] TRACKS_EXTRA STANDALONE + !begin am gtk GAMES += tracks !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 @@ * #113 8x8:gCx5xAf,1,S4,2,5,4,6,2,3,4,2,5,2,S4,4,5,1 * #114 8x8:p5fAzkAb,1,6,3,3,3,S6,2,3,5,4,S3,3,5,1,5,1 * #115 8x8:zi9d5tAb,1,3,4,5,3,S4,2,4,2,6,2,3,6,S3,3,1 + * #942 8x8:n5iCfAzAe,2,2,S5,5,3,5,4,5,4,5,2,S5,3,4,5,3 */ #include @@ -29,9 +30,11 @@ * Difficulty levels. I do some macro ickery here to ensure that my * enum and the various forms of my name list always match up. */ -#define DIFFLIST(A) \ - A(EASY,Easy,e) \ - A(TRICKY,Tricky,t) +#define DIFFLIST(A) \ + A(EASY,Easy,e) \ + A(TRICKY,Tricky,t) \ + A(HARD,Hard,h) \ + /* end of list */ #define ENUM(upper,title,lower) DIFF_ ## upper, #define TITLE(upper,title,lower) #title, @@ -65,10 +68,12 @@ static const struct game_params tracks_presets[] = { {10, 8, DIFF_TRICKY, 1 }, {10, 10, DIFF_EASY, 1}, {10, 10, DIFF_TRICKY, 1}, + {10, 10, DIFF_HARD, 1}, {15, 10, DIFF_EASY, 1}, {15, 10, DIFF_TRICKY, 1}, {15, 15, DIFF_EASY, 1}, {15, 15, DIFF_TRICKY, 1}, + {15, 15, DIFF_HARD, 1}, }; static bool game_fetch_preset(int i, char **name, game_params **params) @@ -452,7 +457,7 @@ start: state->numbers->col_s = px; } -static int tracks_solve(game_state *state, int diff); +static int tracks_solve(game_state *state, int diff, int *max_diff_out); static void debug_state(game_state *state, const char *what); /* Clue-setting algorithm: @@ -533,6 +538,26 @@ static game_state *copy_and_strip(const game_state *state, game_state *ret, int return ret; } +#ifdef STANDALONE_SOLVER +#include +static FILE *solver_diagnostics_fp = NULL; +static void solver_diagnostic(const char *fmt, ...) +{ + va_list ap; + va_start(ap, fmt); + vfprintf(solver_diagnostics_fp, fmt, ap); + va_end(ap); + fputc('\n', solver_diagnostics_fp); +} +#define solverdebug(printf_params) do { \ + if (solver_diagnostics_fp) { \ + solver_diagnostic printf_params; \ + } \ + } while (0) +#else +#define solverdebug(printf_params) ((void)0) +#endif + static int solve_progress(const game_state *state) { int i, w = state->p.w, h = state->p.h, progress = 0; @@ -575,6 +600,7 @@ static int add_clues(game_state *state, random_state *rs, int diff) int *positions = snewn(w*h, int), npositions = 0; int *nedges_previous_solve = snewn(w*h, int); game_state *scratch = dup_game(state); + int diff_used; debug_state(state, "gen: Initial board"); @@ -591,17 +617,13 @@ static int add_clues(game_state *state, random_state *rs, int diff) /* First, check whether the puzzle is already either too easy, or just right */ scratch = copy_and_strip(state, scratch, -1); - if (diff > 0) { - sr = tracks_solve(scratch, diff-1); - if (sr < 0) - assert(!"Generator should not have created impossible puzzle"); - if (sr > 0) { - ret = -1; /* already too easy, even without adding clues. */ - debug(("gen: ...already too easy, need new board.")); - goto done; - } + sr = tracks_solve(scratch, diff, &diff_used); + if (diff_used < diff) { + ret = -1; /* already too easy, even without adding clues. */ + debug(("gen: ...already too easy, need new board.")); + goto done; } - sr = tracks_solve(scratch, diff); + if (sr < 0) assert(!"Generator should not have created impossible puzzle"); if (sr > 0) { @@ -629,12 +651,10 @@ static int add_clues(game_state *state, random_state *rs, int diff) if (check_phantom_moves(scratch)) continue; /* adding a clue here would add phantom track */ - if (diff > 0) { - if (tracks_solve(scratch, diff-1) > 0) { + if (tracks_solve(scratch, diff, &diff_used) > 0) { + if (diff_used < diff) { continue; /* adding a clue here makes it too easy */ } - } - if (tracks_solve(scratch, diff) > 0) { /* we're now soluble (and we weren't before): add this clue, and then start stripping clues */ debug(("gen: ...adding clue at (%d,%d), now soluble", i%w, i/w)); @@ -676,7 +696,7 @@ strip_clues: if (check_phantom_moves(scratch)) continue; /* removing a clue here would add phantom track */ - if (tracks_solve(scratch, diff) > 0) { + if (tracks_solve(scratch, diff, NULL) > 0) { debug(("gen: ... removing clue at (%d,%d), still soluble without it", i%w, i/w)); state->sflags[i] &= ~S_CLUE; /* still soluble without this clue. */ } @@ -686,6 +706,7 @@ strip_clues: done: sfree(positions); + sfree(nedges_previous_solve); free_game(scratch); return ret; } @@ -780,7 +801,7 @@ newpath: } *p++ = '\0'; - ret = tracks_solve(state, DIFFCOUNT); + ret = tracks_solve(state, DIFFCOUNT, NULL); assert(ret >= 0); free_game(state); @@ -882,6 +903,10 @@ static game_state *new_game(midend *me, const game_params *params, const char *d return state; } +struct solver_scratch { + int *dsf; +}; + static int solve_set_sflag(game_state *state, int x, int y, unsigned int f, const char *why) { @@ -889,10 +914,10 @@ static int solve_set_sflag(game_state *state, int x, int y, if (state->sflags[i] & f) return 0; - debug(("solve: square (%d,%d) -> %s: %s", + solverdebug(("square (%d,%d) -> %s: %s", x, y, (f == S_TRACK ? "TRACK" : "NOTRACK"), why)); if (state->sflags[i] & (f == S_TRACK ? S_NOTRACK : S_TRACK)) { - debug(("solve: opposite flag already set there, marking IMPOSSIBLE")); + solverdebug(("opposite flag already set there, marking IMPOSSIBLE")); state->impossible = true; } state->sflags[i] |= f; @@ -906,11 +931,11 @@ static int solve_set_eflag(game_state *state, int x, int y, int d, if (sf & f) return 0; - debug(("solve: edge (%d,%d)/%c -> %s: %s", x, y, + solverdebug(("edge (%d,%d)/%c -> %s: %s", x, y, (d == U) ? 'U' : (d == D) ? 'D' : (d == L) ? 'L' : 'R', (f == S_TRACK ? "TRACK" : "NOTRACK"), why)); if (sf & (f == E_TRACK ? E_NOTRACK : E_TRACK)) { - debug(("solve: opposite flag already set there, marking IMPOSSIBLE")); + solverdebug(("opposite flag already set there, marking IMPOSSIBLE")); state->impossible = true; } 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, if (ctrack != (target-1)) return 0; if (nperp > 0 || n1edge != 1) return 0; - debug(("check_single from (%d,%d): 1 match from (%d,%d)", + solverdebug(("check_single from (%d,%d): 1 match from (%d,%d)", si%w, si/w, i1edge%w, i1edge/w)); /* 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, } if (nloose > (target - e2count)) { - debug(("check %s from (%d,%d): more loose (%d) than empty (%d), IMPOSSIBLE", + solverdebug(("check %s from (%d,%d): more loose (%d) than empty (%d), IMPOSSIBLE", what, si%w, si/w, nloose, target-e2count)); state->impossible = true; } if (nloose > 0 && nloose == (target - e2count)) { - debug(("check %s from (%d,%d): nloose = empty (%d), forcing loners out.", + solverdebug(("check %s from (%d,%d): nloose = empty (%d), forcing loners out.", what, si%w, si/w, nloose)); for (j = 0, i = si; j < n; j++, i += id) { 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, } } if (nloose == 1 && (target - e2count) == 2 && nperp == 0) { - debug(("check %s from (%d,%d): 1 loose end, 2 empty squares, forcing parallel", + solverdebug(("check %s from (%d,%d): 1 loose end, 2 empty squares, forcing parallel", what, si%w, si/w)); for (j = 0, i = si; j < n; j++, i += id) { if (!(state->sflags[i] & S_MARK)) @@ -1176,6 +1201,110 @@ static int solve_check_loose_ends(game_state *state) return did; } +static void solve_check_neighbours_count( + game_state *state, int start, int step, int n, int clueindex, + bool *onefill, bool *oneempty) +{ + int to_fill = state->numbers->numbers[clueindex]; + int to_empty = n - to_fill; + int i; + for (i = 0; i < n; i++) { + int p = start + i*step; + if (state->sflags[p] & S_TRACK) + to_fill--; + if (state->sflags[p] & S_NOTRACK) + to_empty--; + } + *onefill = (to_fill == 1); + *oneempty = (to_empty == 1); +} + +static int solve_check_neighbours_try(game_state *state, int x, int y, + int X, int Y, bool onefill, + bool oneempty, unsigned dir, + const char *what) +{ + int w = state->p.w, p = y*w+x, P = Y*w+X; + + /* + * We're given a neighbouring pair of squares p,P, with 'dir' + * being the direction from the former to the latter. We aim to + * spot situations in which, if p is a track square, then P must + * also be one (because p doesn't have enough free exits to avoid + * using the one that goes towards P). + * + * Then, if the target number of track squares on their shared + * row/column says that there's only one track square left to + * place, it can't be p, because P would have to be one too, + * violating the clue. So in that situation we can mark p as + * unfilled. Conversely, if there's only one _non_-track square + * left to place, it can't be P, so we can mark P as filled. + */ + + if ((state->sflags[p] | state->sflags[P]) & (S_TRACK | S_NOTRACK)) + return 0; /* no need: we already know something about these squares */ + + int possible_exits_except_dir = nbits[ + ALLDIR & ~dir & ~S_E_DIRS(state, x, y, E_NOTRACK)]; + if (possible_exits_except_dir >= 2) + return 0; /* square p need not connect to P, even if it is filled */ + + /* OK, now we know that if p is filled, P must be filled too. */ + + int did = 0; + if (onefill) { + /* But at most one of them can be filled, so it can't be p. */ + state->sflags[p] |= S_NOTRACK; + solverdebug(("square (%d,%d) -> NOTRACK: otherwise, that and (%d,%d) " + "would make too many TRACK in %s", x, y, X, Y, what)); + did++; + } + if (oneempty) { + /* Alternatively, at least one of them _must_ be filled, so P + * must be. */ + state->sflags[P] |= S_TRACK; + solverdebug(("square (%d,%d) -> TRACK: otherwise, that and (%d,%d) " + "would make too many NOTRACK in %s", X, Y, x, y, what)); + did++; + } + return did; +} + +static int solve_check_neighbours(game_state *state, bool both_ways) +{ + int w = state->p.w, h = state->p.h, x, y, did = 0; + bool onefill, oneempty; + + for (x = 0; x < w; x++) { + solve_check_neighbours_count(state, x, w, h, x, &onefill, &oneempty); + if (!both_ways) + oneempty = false; /* disable the harder version of the deduction */ + if (!onefill && !oneempty) + continue; + for (y = 0; y+1 < h; y++) { + did += solve_check_neighbours_try(state, x, y, x, y+1, + onefill, oneempty, D, "column"); + did += solve_check_neighbours_try(state, x, y+1, x, y, + onefill, oneempty, U, "column"); + } + } + for (y = 0; y < h; y++) { + solve_check_neighbours_count(state, y*w, 1, w, w+y, + &onefill, &oneempty); + if (!both_ways) + oneempty = false; /* disable the harder version of the deduction */ + if (!onefill && !oneempty) + continue; + for (x = 0; x+1 < w; x++) { + did += solve_check_neighbours_try(state, x, y, x+1, y, + onefill, oneempty, R, "row"); + did += solve_check_neighbours_try(state, x+1, y, x, y, + onefill, oneempty, L, "row"); + } + } + return did; +} + static int solve_check_loop_sub(game_state *state, int x, int y, int dir, int *dsf, int startc, int endc) { @@ -1195,7 +1324,7 @@ static int solve_check_loop_sub(game_state *state, int x, int y, int dir, return solve_set_eflag(state, x, y, dir, E_NOTRACK, "would close loop"); } if ((ic == startc && jc == endc) || (ic == endc && jc == startc)) { - debug(("Adding link at (%d,%d) would join start to end", x, y)); + solverdebug(("Adding link at (%d,%d) would join start to end", x, y)); /* We mustn't join the start to the end if: - there are other bits of track that aren't attached to either end - 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) solve_set_eflag(state, x, y, d, E_NOTRACK, "outer edge"); } -static int tracks_solve(game_state *state, int diff) +static int solve_bridge_sub(game_state *state, int x, int y, int d, + struct solver_scratch *sc) +{ + /* + * Imagine a graph on the squares of the grid, with an edge + * connecting neighbouring squares only if it's not yet known + * whether there's a track between them. + * + * This function is called if the edge between x,y and X,Y is a + * bridge in that graph: that is, it's not part of any loop in the + * graph, or equivalently, removing it would increase the number + * of connected components in the graph. + * + * In that situation, we can fill in the edge by a parity + * argument. Construct a closed loop of edges in the grid, all of + * whose states are known except this one. The track starts and + * ends outside this loop, so it must cross the boundary of the + * loop an even number of times. So if we count up how many times + * the track is known to cross the edges of our loop, then we can + * fill in the last edge in whichever way makes that number even. + * + * In fact, there's not even any need to go to the effort of + * constructing a _single_ closed loop. The simplest thing is to + * delete the bridge edge from the graph, find a connected + * component of the reduced graph whose boundary includes that + * edge, and take every edge separating that component from + * another. This may not lead to _exactly one_ cycle - the + * component could be non-simply connected and have a hole in the + * middle - but that doesn't matter, because the same parity + * constraint applies just as well with more than one disjoint + * loop. + */ + int w = state->p.w, h = state->p.h, wh = w*h; + int X = x + DX(d), Y = y + DY(d); + int xi, yi, di; + + assert(d == D || d == R); + + if (!sc->dsf) + sc->dsf = snew_dsf(wh); + dsf_init(sc->dsf, wh); + + for (xi = 0; xi < w; xi++) { + for (yi = 0; yi < h; yi++) { + /* We expect to have been called with X,Y either to the + * right of x,y or below it, not the other way round. If + * that were not true, the tests in this loop to exclude + * the bridge edge would have to be twice as annoying. */ + + if (yi+1 < h && !S_E_FLAGS(state, xi, yi, D) && + !(xi == x && yi == y && xi == X && yi+1 == Y)) + dsf_merge(sc->dsf, yi*w+xi, (yi+1)*w+xi); + + if (xi+1 < w && !S_E_FLAGS(state, xi, yi, R) && + !(xi == x && yi == y && xi+1 == X && yi == Y)) + dsf_merge(sc->dsf, yi*w+xi, yi*w+(xi+1)); + } + } + + int component = dsf_canonify(sc->dsf, y*w+x); + int parity = 0; + for (xi = 0; xi < w; xi++) { + for (yi = 0; yi < h; yi++) { + if (dsf_canonify(sc->dsf, yi*w+xi) != component) + continue; + for (di = 1; di < 16; di *= 2) { + int Xi = xi + DX(di), Yi = yi + DY(di); + if ((Xi < 0 || Xi >= w || Yi < 0 || Yi >= h || + dsf_canonify(sc->dsf, Yi*w+Xi) != component) && + (S_E_DIRS(state, xi, yi, E_TRACK) & di)) + parity ^= 1; + } + } + } + + solve_set_eflag(state, x, y, d, parity ? E_TRACK : E_NOTRACK, "parity"); + return 1; +} + +struct solve_bridge_neighbour_ctx { + game_state *state; + int x, y, dirs; +}; +static int solve_bridge_neighbour(int vertex, void *vctx) +{ + struct solve_bridge_neighbour_ctx *ctx = + (struct solve_bridge_neighbour_ctx *)vctx; + int w = ctx->state->p.w; + + if (vertex >= 0) { + ctx->x = vertex % w; + ctx->y = vertex / w; + ctx->dirs = ALLDIR + & ~S_E_DIRS(ctx->state, ctx->x, ctx->y, E_TRACK) + & ~S_E_DIRS(ctx->state, ctx->x, ctx->y, E_NOTRACK); + } + unsigned dir = ctx->dirs & -ctx->dirs; /* isolate lowest set bit */ + if (!dir) + return -1; + ctx->dirs &= ~dir; + int xr = ctx->x + DX(dir), yr = ctx->y + DY(dir); + assert(0 <= xr && xr < w); + assert(0 <= yr && yr < ctx->state->p.h); + return yr * w + xr; +} + +static int solve_check_bridge_parity(game_state *state, + struct solver_scratch *sc) +{ + int w = state->p.w, h = state->p.h, wh = w*h; + struct findloopstate *fls; + struct solve_bridge_neighbour_ctx ctx[1]; + int x, y, did = 0; + + ctx->state = state; + fls = findloop_new_state(wh); + findloop_run(fls, wh, solve_bridge_neighbour, ctx); + + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + if (y+1 < h && !findloop_is_loop_edge(fls, y*w+x, (y+1)*w+x)) + did += solve_bridge_sub(state, x, y, D, sc); + if (x+1 < w && !findloop_is_loop_edge(fls, y*w+x, y*w+(x+1))) + did += solve_bridge_sub(state, x, y, R, sc); + } + } + + findloop_free_state(fls); + + return did; +} + +static int tracks_solve(game_state *state, int diff, int *max_diff_out) { int x, y, w = state->p.w, h = state->p.h; - bool didsth; + struct solver_scratch sc[1]; + int max_diff = DIFF_EASY; + + sc->dsf = NULL; debug(("solve...")); state->impossible = false; @@ -1305,21 +1569,37 @@ static int tracks_solve(game_state *state, int diff) solve_discount_edge(state, w-1, y, R); } - while (1) { - didsth = false; + while (!state->impossible) { - didsth |= solve_update_flags(state); - didsth |= solve_count_clues(state); - didsth |= solve_check_loop(state); +/* Can't use do ... while (0) because we need a 'continue' in this macro */ +#define TRY(curr_diff, funcall) \ + if (diff >= (curr_diff) && (funcall)) { \ + if (max_diff < curr_diff) \ + max_diff = curr_diff; \ + continue; \ + } else ((void)0) - if (diff >= DIFF_TRICKY) { - didsth |= solve_check_single(state); - didsth |= solve_check_loose_ends(state); - } + TRY(DIFF_EASY, solve_update_flags(state)); + TRY(DIFF_EASY, solve_count_clues(state)); + TRY(DIFF_EASY, solve_check_loop(state)); - if (!didsth || state->impossible) break; + TRY(DIFF_TRICKY, solve_check_single(state)); + TRY(DIFF_TRICKY, solve_check_loose_ends(state)); + TRY(DIFF_TRICKY, solve_check_neighbours(state, false)); + + TRY(DIFF_HARD, solve_check_neighbours(state, true)); + TRY(DIFF_HARD, solve_check_bridge_parity(state, sc)); + +#undef TRY + + break; } + sfree(sc->dsf); + + if (max_diff_out) + *max_diff_out = max_diff; + return state->impossible ? -1 : check_completion(state, false) ? 1 : 0; } @@ -1379,11 +1659,11 @@ static char *solve_game(const game_state *state, const game_state *currstate, char *move; solved = dup_game(currstate); - ret = tracks_solve(solved, DIFFCOUNT); + ret = tracks_solve(solved, DIFFCOUNT, NULL); if (ret < 1) { free_game(solved); solved = dup_game(state); - ret = tracks_solve(solved, DIFFCOUNT); + ret = tracks_solve(solved, DIFFCOUNT, NULL); } if (ret < 1) { @@ -2094,7 +2374,7 @@ static game_state *execute_move(const game_state *state, const char *move) goto badmove; move += n; } else if (c == 'H') { - tracks_solve(ret, DIFFCOUNT); + tracks_solve(ret, DIFFCOUNT, NULL); move++; } else { goto badmove; @@ -2675,4 +2955,87 @@ const struct game thegame = { 0, /* flags */ }; +#ifdef STANDALONE_SOLVER + +int main(int argc, char **argv) +{ + game_params *p; + game_state *s; + char *id = NULL, *desc; + int maxdiff = DIFFCOUNT, diff_used; + const char *err; + bool diagnostics = false, grade = false; + int retd; + + while (--argc > 0) { + char *p = *++argv; + if (!strcmp(p, "-v")) { + diagnostics = true; + } else if (!strcmp(p, "-g")) { + grade = true; + } else if (!strncmp(p, "-d", 2) && p[2] && !p[3]) { + int i; + bool bad = true; + for (i = 0; i < lenof(tracks_diffchars); i++) + if (tracks_diffchars[i] == p[2]) { + bad = false; + maxdiff = i; + break; + } + if (bad) { + fprintf(stderr, "%s: unrecognised difficulty `%c'\n", + argv[0], p[2]); + return 1; + } + } else if (*p == '-') { + fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); + return 1; + } else { + id = p; + } + } + + if (!id) { + fprintf(stderr, "usage: %s [-v | -g] \n", argv[0]); + return 1; + } + + desc = strchr(id, ':'); + if (!desc) { + fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); + return 1; + } + *desc++ = '\0'; + + p = default_params(); + decode_params(p, id); + err = validate_desc(p, desc); + if (err) { + fprintf(stderr, "%s: %s\n", argv[0], err); + return 1; + } + s = new_game(NULL, p, desc); + + solver_diagnostics_fp = (diagnostics ? stdout : NULL); + retd = tracks_solve(s, maxdiff, &diff_used); + if (retd < 0) { + printf("Puzzle is inconsistent\n"); + } else if (grade) { + printf("Difficulty rating: %s\n", + (retd == 0 ? "Ambiguous" : tracks_diffnames[diff_used])); + } else { + char *text = game_text_format(s); + fputs(text, stdout); + sfree(text); + if (retd == 0) + printf("Could not deduce a unique solution\n"); + } + free_game(s); + free_params(p); + + return 0; +} + +#endif + /* 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) int i, x, y, col, maxlen; bool o = state->orientable; + /* Pedantic check: ensure buf is large enough to format an int in + * decimal, using the bound log10(2) < 1/3. (Obviously in practice + * int is not going to be larger than even 32 bits any time soon, + * but.) */ + assert(sizeof(buf) >= 1 + sizeof(int) * CHAR_BIT/3); + /* * First work out how many characters we need to display each * number. We're pretty flexible on grid contents here, so we @@ -563,6 +569,11 @@ static char *game_text_format(const game_state *state) if (col < x) col = x; } + /* Reassure sprintf-checking compilers like gcc that the field + * width we've just computed is not now excessive */ + if (col >= sizeof(buf)) + col = sizeof(buf)-1; + /* * Now we know the exact total size of the grid we're going to * 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) #define SOLVER(upper,title,func,lower) func, static usersolver_t const unequal_solvers[] = { DIFFLIST(SOLVER) }; +static bool unequal_valid(struct latin_solver *solver, void *vctx) +{ + struct solver_ctx *ctx = (struct solver_ctx *)vctx; + if (ctx->state->mode == MODE_ADJACENT) { + int o = solver->o; + int x, y, nx, ny, v, nv, i; + + for (x = 0; x+1 < o; x++) { + for (y = 0; y+1 < o; y++) { + v = grid(x, y); + for (i = 0; i < 4; i++) { + bool is_adj, should_be_adj; + + should_be_adj = + (GRID(ctx->state, flags, x, y) & adjthan[i].f); + + nx = x + adjthan[i].dx, ny = y + adjthan[i].dy; + if (nx < 0 || ny < 0 || nx >= o || ny >= o) + continue; + + nv = grid(nx, ny); + is_adj = (labs(v - nv) == 1); + + if (is_adj && !should_be_adj) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("%*s(%d,%d):%d and (%d,%d):%d have " + "adjacent values, but should not\n", + solver_recurse_depth*4, "", + x+1, y+1, v, nx+1, ny+1, nv); +#endif + return false; + } + + if (!is_adj && should_be_adj) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("%*s(%d,%d):%d and (%d,%d):%d do not have " + "adjacent values, but should\n", + solver_recurse_depth*4, "", + x+1, y+1, v, nx+1, ny+1, nv); +#endif + return false; + } + } + } + } + } else { + int i; + for (i = 0; i < ctx->nlinks; i++) { + struct solver_link *link = &ctx->links[i]; + int gv = grid(link->gx, link->gy); + int lv = grid(link->lx, link->ly); + if (gv <= lv) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("%*s(%d,%d):%d should be greater than (%d,%d):%d, " + "but is not\n", solver_recurse_depth*4, "", + link->gx+1, link->gy+1, gv, + link->lx+1, link->ly+1, lv); +#endif + return false; + } + } + } + return true; +} + static int solver_state(game_state *state, int maxdiff) { struct solver_ctx *ctx = new_ctx(state); @@ -827,7 +895,8 @@ static int solver_state(game_state *state, int maxdiff) diff = latin_solver_main(&solver, maxdiff, DIFF_LATIN, DIFF_SET, DIFF_EXTREME, DIFF_EXTREME, DIFF_RECURSIVE, - unequal_solvers, ctx, clone_ctx, free_ctx); + unequal_solvers, unequal_valid, ctx, + clone_ctx, free_ctx); memcpy(state->hints, solver.cube, state->order*state->order*state->order); @@ -2155,7 +2224,8 @@ static int solve(game_params *p, char *desc, int debug) diff = latin_solver_main(&solver, DIFF_RECURSIVE, DIFF_LATIN, DIFF_SET, DIFF_EXTREME, DIFF_EXTREME, DIFF_RECURSIVE, - unequal_solvers, ctx, clone_ctx, free_ctx); + unequal_solvers, unequal_valid, ctx, + clone_ctx, free_ctx); free_ctx(ctx); 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 @@ #define DIFFLIST(A) \ A(TRIVIAL,Trivial,NULL,t) \ A(NORMAL,Normal,solver_normal,n) \ - A(HARD,Hard,NULL,h) \ + A(HARD,Hard,solver_hard,h) \ A(EXTREME,Extreme,NULL,x) \ A(UNREASONABLE,Unreasonable,NULL,u) #define ENUM(upper,title,func,lower) DIFF_ ## upper, @@ -280,6 +280,23 @@ static const char *validate_params(const game_params *params, bool full) * Solver. */ +static int find_identity(struct latin_solver *solver) +{ + int w = solver->o; + digit *grid = solver->grid; + int i, j; + + for (i = 0; i < w; i++) + for (j = 0; j < w; j++) { + if (grid[i*w+j] == i+1) + return j+1; + if (grid[i*w+j] == j+1) + return i+1; + } + + return 0; +} + static int solver_normal(struct latin_solver *solver, void *vctx) { int w = solver->o; @@ -295,9 +312,9 @@ static int solver_normal(struct latin_solver *solver, void *vctx) * So we pick any a,b,c we like; then if we know ab, bc, and * (ab)c we can fill in a(bc). */ - for (i = 1; i < w; i++) - for (j = 1; j < w; j++) - for (k = 1; k < w; k++) { + for (i = 0; i < w; i++) + for (j = 0; j < w; j++) + for (k = 0; k < w; k++) { if (!grid[i*w+j] || !grid[j*w+k]) continue; if (grid[(grid[i*w+j]-1)*w+k] && @@ -358,12 +375,206 @@ static int solver_normal(struct latin_solver *solver, void *vctx) } } + /* + * Fill in the row and column for the group identity, if it's not + * already known and if we've just found out what it is. + */ + i = find_identity(solver); + if (i) { + bool done_something = false; + for (j = 1; j <= w; j++) { + if (!grid[(i-1)*w+(j-1)] || !grid[(j-1)*w+(i-1)]) { + done_something = true; + } + } + if (done_something) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*s%s is the group identity\n", + solver_recurse_depth*4, "", names[i-1]); + } +#endif + for (j = 1; j <= w; j++) { + if (!grid[(j-1)*w+(i-1)]) { + if (!cube(i-1, j-1, j)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*s but %s cannot go at (%d,%d) - " + "contradiction!\n", + solver_recurse_depth*4, "", + names[j-1], i, j); + } +#endif + return -1; + } +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*s placing %s at (%d,%d)\n", + solver_recurse_depth*4, "", + names[j-1], i, j); + } +#endif + latin_solver_place(solver, i-1, j-1, j); + } + if (!grid[(i-1)*w+(j-1)]) { + if (!cube(j-1, i-1, j)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*s but %s cannot go at (%d,%d) - " + "contradiction!\n", + solver_recurse_depth*4, "", + names[j-1], j, i); + } +#endif + return -1; + } +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*s placing %s at (%d,%d)\n", + solver_recurse_depth*4, "", + names[j-1], j, i); + } +#endif + latin_solver_place(solver, j-1, i-1, j); + } + } + return 1; + } + } + return 0; } +static int solver_hard(struct latin_solver *solver, void *vctx) +{ + bool done_something = false; + int w = solver->o; +#ifdef STANDALONE_SOLVER + char **names = solver->names; +#endif + int i, j; + + /* + * In identity-hidden mode, systematically rule out possibilities + * for the group identity. + * + * In solver_normal, we used the fact that any filled square in + * the grid whose contents _does_ match one of the elements it's + * the product of - that is, ab=a or ab=b - tells you immediately + * that the other element is the identity. + * + * Here, we use the flip side of that: any filled square in the + * grid whose contents does _not_ match either its row or column - + * that is, if ab is neither a nor b - tells you immediately that + * _neither_ of those elements is the identity. And if that's + * true, then we can also immediately rule out the possibility + * that it acts as the identity on any element at all. + */ + for (i = 0; i < w; i++) { + bool i_can_be_id = true; +#ifdef STANDALONE_SOLVER + char title[80]; +#endif + + for (j = 0; j < w; j++) { + if (grid(i,j) && grid(i,j) != j+1) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + sprintf(title, "%s cannot be the identity: " + "%s%s = %s =/= %s", names[i], names[i], names[j], + names[grid(i,j)-1], names[j]); +#endif + i_can_be_id = false; + break; + } + if (grid(j,i) && grid(j,i) != j+1) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + sprintf(title, "%s cannot be the identity: " + "%s%s = %s =/= %s", names[i], names[j], names[i], + names[grid(j,i)-1], names[j]); +#endif + i_can_be_id = false; + break; + } + } + + if (!i_can_be_id) { + /* Now rule out ij=j or ji=j for all j. */ + for (j = 0; j < w; j++) { + if (cube(i, j, j+1)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + if (title[0]) { + printf("%*s%s\n", solver_recurse_depth*4, "", + title); + title[0] = '\0'; + } + printf("%*s ruling out %s at (%d,%d)\n", + solver_recurse_depth*4, "", names[j], i, j); + } +#endif + cube(i, j, j+1) = false; + } + if (cube(j, i, j+1)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + if (title[0]) { + printf("%*s%s\n", solver_recurse_depth*4, "", + title); + title[0] = '\0'; + } + printf("%*s ruling out %s at (%d,%d)\n", + solver_recurse_depth*4, "", names[j], j, i); + } +#endif + cube(j, i, j+1) = false; + } + } + } + } + + return done_something; +} + #define SOLVER(upper,title,func,lower) func, static usersolver_t const group_solvers[] = { DIFFLIST(SOLVER) }; +static bool group_valid(struct latin_solver *solver, void *ctx) +{ + int w = solver->o; +#ifdef STANDALONE_SOLVER + char **names = solver->names; +#endif + int i, j, k; + + for (i = 0; i < w; i++) + for (j = 0; j < w; j++) + for (k = 0; k < w; k++) { + int ij = grid(i, j) - 1; + int jk = grid(j, k) - 1; + int ij_k = grid(ij, k) - 1; + int i_jk = grid(i, jk) - 1; + if (ij_k != i_jk) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*sfailure of associativity: " + "(%s%s)%s = %s%s = %s but " + "%s(%s%s) = %s%s = %s\n", + solver_recurse_depth*4, "", + names[i], names[j], names[k], + names[ij], names[k], names[ij_k], + names[i], names[j], names[k], + names[i], names[jk], names[i_jk]); + } +#endif + return false; + } + } + + return true; +} + static int solver(const game_params *params, digit *grid, int maxdiff) { int w = params->w; @@ -387,7 +598,7 @@ static int solver(const game_params *params, digit *grid, int maxdiff) ret = latin_solver_main(&solver, maxdiff, DIFF_TRIVIAL, DIFF_HARD, DIFF_EXTREME, DIFF_EXTREME, DIFF_UNREASONABLE, - group_solvers, NULL, NULL, NULL); + group_solvers, group_valid, NULL, NULL, NULL); latin_solver_free(&solver); @@ -2183,6 +2394,11 @@ int main(int argc, char **argv) } if (diff == DIFFCOUNT) { + if (really_show_working) { + solver_show_working = true; + memcpy(grid, s->grid, p->w * p->w); + ret = solver(&s->par, grid, DIFFCOUNT - 1); + } if (grade) printf("Difficulty rating: ambiguous\n"); 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 @@ -68,6 +68,103 @@ * has precisely the set of link changes to cause that effect). */ +/* + * 2020-05-11: some thoughts on a solver. + * + * Consider this example puzzle, from Wikipedia: + * + * ---4--- + * -3--25- + * ---31-- + * ---5--- + * ------- + * --1---- + * 2---4-- + * + * The kind of deduction that a human wants to make here is: which way + * does the path between the 4s go? In particular, does it go round + * the left of the W-shaped cluster of endpoints, or round the right + * of it? It's clear at a glance that it must go to the right, because + * _any_ path between the 4s that goes to the left of that cluster, no + * matter what detailed direction it takes, will disconnect the + * remaining grid squares into two components, with the two 2s not in + * the same component. So we immediately know that the path between + * the 4s _must_ go round the right-hand side of the grid. + * + * How do you model that global and topological reasoning in a + * computer? + * + * The most plausible idea I've seen so far is to use fundamental + * groups. The fundamental group of loops based at a given point in a + * space is a free group, under loop concatenation and up to homotopy, + * generated by the loops that go in each direction around each hole + * in the space. In this case, the 'holes' are clues, or connected + * groups of clues. + * + * So you might be able to enumerate all the homotopy classes of paths + * between (say) the two 4s as follows. Start with any old path + * between them (say, find the first one that breadth-first search + * will give you). Choose one of the 4s to regard as the base point + * (arbitrarily). Then breadth-first search among the space of _paths_ + * by the following procedure. Given a candidate path, append to it + * each of the possible loops that starts from the base point, + * circumnavigates one clue cluster, and returns to the base point. + * The result will typically be a path that retraces its steps and + * self-intersects. Now adjust it homotopically so that it doesn't. If + * that can't be done, then we haven't generated a fresh candidate + * path; if it can, then we've got a new path that is not homotopic to + * any path we already had, so add it to our list and queue it up to + * become the starting point of this search later. + * + * The idea is that this should exhaustively enumerate, up to + * homotopy, the different ways in which the two 4s can connect to + * each other within the constraint that you have to actually fit the + * path non-self-intersectingly into this grid. Then you can keep a + * list of those homotopy classes in mind, and start ruling them out + * by techniques like the connectivity approach described above. + * Hopefully you end up narrowing down to few enough homotopy classes + * that you can deduce something concrete about actual squares of the + * grid - for example, here, that if the path between 4s has to go + * round the right, then we know some specific squares it must go + * through, so we can fill those in. And then, having filled in a + * piece of the middle of a path, you can now regard connecting the + * ultimate endpoints to that mid-section as two separate subproblems, + * so you've reduced to a simpler instance of the same puzzle. + * + * But I don't know whether all of this actually works. I more or less + * believe the process for enumerating elements of the free group; but + * I'm not as confident that when you find a group element that won't + * fit in the grid, you'll never have to consider its descendants in + * the BFS either. And I'm assuming that 'unwind the self-intersection + * homotopically' is a thing that can actually be turned into a + * sensible algorithm. + * + * -------- + * + * Another thing that might be needed is to characterise _which_ + * homotopy class a given path is in. + * + * For this I think it's sufficient to choose a collection of paths + * along the _edges_ of the square grid, each of which connects two of + * the holes in the grid (including the grid exterior, which counts as + * a huge hole), such that they form a spanning tree between the + * holes. Then assign each of those paths an orientation, so that + * crossing it in one direction counts as 'positive' and the other + * 'negative'. Now analyse a candidate path from one square to another + * by following it and noting down which of those paths it crosses in + * which direction, then simplifying the result like a free group word + * (i.e. adjacent + and - crossings of the same path cancel out). + * + * -------- + * + * If we choose those paths to be of minimal length, then we can get + * an upper bound on the number of homotopy classes by observing that + * you can't traverse any of those barriers more times than will fit + * non-self-intersectingly in the grid. That might be an alternative + * method of bounding the search through the fundamental group to only + * finitely many possibilities. + */ + /* * Standard notation for directions. */ -- cgit v1.2.3