From 93b955d5ee3d2ba7f36b1b6f7c17d06f1d7497a4 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Thu, 19 May 2005 16:17:03 +0000 Subject: Cunning way to ensure unique solutions in generated Rectangles puzzles. I generate the grid of rectangles as normal, but before I place the numbers I run it through a non-deterministic solver algorithm which tries to do as much as it can with as little information about where the numbers are going to be. The solver itself narrows down the number placement when it runs out of steam, but does so as little as possible. Once it reaches a state where it has ensured solubility, and then the generation algorithm chooses random number placement from whatever's left. Occasionally it paints itself into a corner and can't ensure a unique solution no matter what happens; in that situation we just have to give up, generate a fresh grid, and try again. [originally from svn r5809] --- puzzles.but | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'puzzles.but') diff --git a/puzzles.but b/puzzles.but index fb61a82..44bdb25 100644 --- a/puzzles.but +++ b/puzzles.but @@ -578,13 +578,13 @@ numbered square, and (b) the area of each rectangle is equal to the number written in its numbered square. Credit for this game goes to the Japanese puzzle magazine \i{Nikoli} -\k{nikoli-rect}; I've also seen a Palm implementation at \i{Puzzle Palace} -\k{puzzle-palace-rect}. Unlike Puzzle Palace's implementation, my version -automatically generates random grids of any size you like. The quality -of puzzle design is therefore not quite as good as hand-crafted -puzzles would be (in particular, a unique solution cannot be -guaranteed), but on the plus side you get an inexhaustible supply of -puzzles tailored to your own specification. +\k{nikoli-rect}; I've also seen a Palm implementation at \i{Puzzle +Palace} \k{puzzle-palace-rect}. Unlike Puzzle Palace's +implementation, my version automatically generates random grids of +any size you like. The quality of puzzle design is therefore not +quite as good as hand-crafted puzzles would be, but on the plus side +you get an inexhaustible supply of puzzles tailored to your own +specification. \B{nikoli-rect} \W{http://www.nikoli.co.jp/puzzles/7/index_text-e.htm}\cw{http://www.nikoli.co.jp/puzzles/7/index_text-e.htm} -- cgit v1.1