[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
This program implements creating, solving and allowing users to solve a puzzle type defined as follows::
Given a square N x N grid divided into N sections, place a star in each section with no two stars in the same column or row, and no two stars diagonally adjacent to each other. .
Background & Techniques
Here's a program twist on the classic Eight Queens problem which required
Users can solve a problem manually by right clicking on grid cells which will add a star if the cell does not have one or remove it if it does. Users can also create or modify puzzles using the "Number of stars" field to change grid size if desired, and then choosing a color from the color column at the right side of the form and then left clicking the grid to apply the color to cells.
Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.
The program grew to 750 lines of code by the time the four main task areas were implemented:
Data Structure: Saving & Restoring Cases
Deciding on data structures to represent the puzzle and and the solutions is always the first problem. I decided to fill the string grid, StringGrid2, with letters, a different letter for each section. Each star on the grid would be identified by asterisk following the letter for that cell. Cases will be saved as sections (Casename) in a TIniFile ("StarsInGrid.ini"), with 3 fields for each section: a Title string, an integer , StarCount, representing the number of rows, columns, and sections of the grid, and stars to be placed. The third field is Cells, a string of NxN letters representing the letters in each row within each column of the grid. Solution star positions are not saved since there may be many of them and they can be quickly regenerated by the program. The SaveBtn button solicits Case name and Title strings to add to (or replace) a section in the init file. Initially and after each update of the init file, the dropdown list of a TComboBox, CaseInBox, is reloaded with the Case names using the Tinifile ReadSections method.
A revision after version 1 of the program enhances the display by replacing the letters with colored rectangles and '*' characters with star images. A template of 10 different colors is assigned in an array of 10 TColors, Colors, indexed by letters 'A' to 'J', is defined in the constants area. The TImage, StarImage, is an image from the web reduced to 32x32 pixels and with it's Transparent property set to True to implement masking. This allows the Canvas area of cells with the asterisk to be drawn with StarImage after it is filled with it's color. The color displays in the transparent spaces between the star points.
Program Case Solving
The heart of the solver is based on the Wirth algorithm with the "no two queens on the same diagonal" test changed to "no two stars diagonally adjacent" plus and additional test to ensure that each color has exactly one star. Allowing user editing of a string grid requires some user training to work smoothly. so the final result uses letters internally to define the sections, but assigns unique colors to each letter and uses the "OnDrawCell" event exit to color the grid cell as they are drawn.
Allow User Creation/Modifiying
A 1x10 TDrawGrid, ColorGrid, is used to display color choices which users can select by clicking. The 10 rows of ColorGrid are mapped to the 10 colors of the Colors array by the row number. An OnDrawCell exit fills the cell with the appropriate color. To limit the users access to colors, only the first N cells of ColorGrid are displayed when N stars are specified as the grid size. When a user selects a color, the OnClick exit sets a square TShape, CurrentColor to the color of the cell clicked and sets its Tag property to the row number that was clicked. Setting the CurrentColor color gives a visual reminder of the currently selected color to and the Tag property is the position of the color name in the Colors. Left clicking on a cell of the board, Stringgrid2, sets the appropriate letter in the cell clicked based on the CurrentColor Tag value and the Stringgrid2DrawCel exit takes care of coloring the cell.
The TSpinEdiit, StarCountSpin, is set when a case is loaded but can be changed by the user. Changing the value resets any existing stars and solutions. If changed downward, rightmost columns and bottom most columns are removed. If value is increased, right and bottom column are filled with the colors corresponding to the new column and row numbers.
Allow User Play
Briefly, right clicking on a cell of StringGrid2 triggers a MouseUp event exit which adds an asterisk to the letter in the cell if it does not exist and removes the asterisk if it is present. Again, StringGrid2DrawCell takes care adding the star to the cell image if requested. After each Star change, is added a IsSolved function is called which checks to see if the solution conditions are met, i.e. one star per row, one star per column, one star per color, and no diagonally adjacent stars. Error or congratulation messages are displayed in the TStaticText, MsgBar areas at the bottom of the screen.
Whew! As my daughter says when I mention the current state of the sex life of Mom and I: "TMI Dad, TMI!". ( I now know that TMI is slang for "Too much information!".)
Actually the above description is a simplified version of things which must exist in the code to make the program work reasonably well. That, plus improvements and redesigns conceived during testing, are the reasons that my programs take several tines longer to complete than I anticipate. I enjoy most every minute of it but there is always room for improvement so feedback regarding bugs or improvements is always welcome.
Addendum September 4, 2017: A new puzzle of this type showed up
in our September 1st
Mensa 365 Puzzlers Calendar. It sounded familiar, but
took a while to locate the program so I decided to review and repost it along
with the new puzzle. I cleaned up a few typos and other minor errors and
added a "Shift-Click" option to the "Right-Click" method for adding stars to the
grid during user play. Right clicking on my laptop's touchpad
is a little fussy sometimes. This puzzle is near the bottom of the
list of sample puzzles named "Mensa_9-1-17".
Suggestions for Further Explorations
Copyright © 2000-2018, Gary Darby All rights reserved.