[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionHere’s a first attempt at documenting the thought processes involved in creating a program to solve a puzzle problem, a Mensa Calendar puzzle in this case. Here’s the puzzle:
From the October 7, 2016 Mensa Puzzle calendar: “Place stars in six cells of the grid so that every row, every column, and every outlined region contains exactly one star. Stars must never be located in adjacent cells, not even diagonally.“
Background & TechniquesGetting Started: First order of business is to study the puzzle and guess how it might be solved. If you remember learning about the "Scientific Method" from High School, this is the "Data Collection" phase. For me, this usually means searching my internal experience "data bank" and the web. “Trial and error” comes to mind here as a likely approach for this puzzle, since no shortcut way is obvious. A more technical name for “Trial and Error” is “Depth First Search with Backtracking” In this case the method would require us to start placing stars, one per figure, in some systematic manner until we get stuck and then backtracking to the previous star and trying the next , againlocation backing up star by star far as necessary and going forward at each step until the solution is found. Computers are much better at this approach than humans. I know how to code “recursive” functions that implement this technique by calling themselves, so we don’t need separate code for each figure. We'll call our function "PlaceNext" (Star). "PlaceNext" Recursive Function: Within the “PlaceNext” function we’ll try placing a star each cell within a given figure (passed to the function as a parameter) in some systematic way that does not violate any of the rules: i.e. no other star in the candidate column or row or adjacent diagonal cells that are in a different figure. We won’t need to check diagonals in the current figure because we are only trying them one star at a time. If this placement is OK, place the star temporarily (in such a way that we can remove it later) and call PlaceNext with the next figure number. Set the return function to the return value of the PlaceNext call. If the return value is False, remove the star and place it in the next untried location. If all locations have been tried without success, set return value to False, and exit. If we enter PlaceNext with the 7th star position, we're done so we just set the Result value to True and exit. That’s it. This code should be able to step through all possible arrangements of six stars in all valid positions. If the very first call returns true , we have a solution. Since there are 9, 8, 5, 5, 3, and 5 cells in the six figures, the product of these numbers (27,000) represents the maximum of trial star sets to check if there is no solution. From past experience, I predict that it will only take a few milliseconds at most to find the solution, even if we keep searching after the first solution is found to prove that the solution is unique. Problem solved – in theory - just the details to fill in now. Divide and ConquerI always try the “Divide and Conquer” technique from here on. Break the large problem into smaller easier-to-solve problems. The sub-problems I see for now (with likely solution concepts) are:
Time to start coding.
Program Version 1I decided to tackle tasks 1 and 2 initially as a warm-up. They have to be done anyway and it will be the best way to check program results visually. The data structure I chose to represent the grid data is a 6x6 array of integers. It looks like this:
DefVal:array[0..5,0..5] of integer = Each line represents the figure numbers of the six cells on that row. The grid cells are strings, not integer data, but string constants require ‘quote’ marks, so I use integers and let the computer do the formatting. The index range is set as 0 to 5 rather than 1 to 6 because grid cells are indexed from zero. The Grid1DrawCell exit works by drawing heavy blue cell top and/or left boundary lines when either the cell is in column zero or row zero, or if the number in the cell above or to the left of this cell doesn’t match this cell. The right-most column and bottom row cells always add the right and bottom boundary lines. Here’s a condensed copy of the actual code: {Comments are in red} {*********** GridDrawCell **************} procedure TForm1.Grid1DrawCell(Sender: TObject; ACol, ARow: Integer; Rect: TRect; State: TGridDrawState); begin
with grid1, canvas, rect do {allows
shortcut names below for fieldsfrom these objects;
e.g.
{Heavy
left side line? Yes, if 1st column or left cell doesn't match}
{Heavy
top line?}
{Last column? Draw heavy right side line}
{Last row?
Graw
heavy bottom line}
{Display the figure number for
checking} end; end;
Here’s a screen shot of the resulting grid:
Program Version 2So now we have the grid built, it’s time to add the fun part – placing the stars. Two new data types were added to help model the data required to solve the puzzle. Grid1 is simply a 6x6 array of integers representing the current state of the board. By assigning it as a data type (TGridRec), we can pass the grid status of the board along to the Placenext function call for each new figure we are solving. The other new data type for this version is TFigLocs, an array of the column and row points for each of the 6 figures on the board. This greatly simplifies the search as we try placing a star at each location within the current figure because we can just step though the points array to get the nexxt location to test. So the Placenext function definition looks like this: Function Placenext(StarNbr:integer; NextGrid:TGridDef):boolean; Pseudo-code for the function looks like this: All six stars set? Yes: We have a solution! Display it. No: For all cell locations in this figure (StarNbr) using the FigLocs array for this figure, Can a star be validly placed here? (call IsValidLoc function which checks that there is no other star already in this row or column and no star from another figure adjacent to any of the 4 corners). Yes: Place the star in NextGrid and call Result:=Placenext(StarNbr+1, Nextgrid). This is the recursion part! If Result is true the exit Otherwise remove the star placed in NextGrid and continue trying locations. No: Check next location;
Notes: This version does not update the displayed grid, just reports success or failure. Success is checked by stopping the program to debug the grid using the Watch list. Program Version 3Almost there – just need to update the displayed grid . This is the stage when extra unanticipated features start rearing their pretty little heads to add to the fun. Here’s the list of "unplanned" features added in this case::
A final note – I intended to post the final version as “StarsInAGrid” but discovered that I had posted program with that name (and solving a similar puzzle), a few years ago. The approach then seems quite different that the current study, thankfully. One advantage of growing old is the ability to re-solve a problem as if for the first time! I'll post this one in our Delphi Techniques section as GridSubdivisionsV3). Running/Exploring the Program
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |