Stars On A Grid

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

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 placing
eight queens on a standard 8x8 chessboard with no queen threatening another.
Queens can move many spaces in a vertical, horizontal, or diagonal direction.

This program uses the same efficient algorithm discovered by Niklaus Wirth which
finds solutions very rapidly. (Niklaus Wirth, Algorithms and Data Structures, 1978,
1986). In this version, we need to place N "Stars" in an NxN grid which has been
divided into N sections in such a way that there is exactly 1 star in each section. No
two stars can reside in the same row or column, nor is any star diagonally adjacent
to another star.

The default case was derived from the June 3rd page of the 2014 Mensa Puzzle Calendar. I represent the sections by assigning unique colors to the cells of each section. Feel free to design your own sectioned grid of any size from 2x2 up to 10x10 by selecting N different colors from the template provided.  (I am quite sure that 5 x5 is the smallest grid that can have a solution.)  . The "Find all solutions"  button will look for solutions. There may be zero, one, or many solutions. A single solution is the preferred arrangement.    The program includes a number of predefined sample grids to play with.  

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.

Programmer's Notes:

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.      

 Summary

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".  
 

Running/Exploring the Program 

bulletDownload  executable
bulletDownload source  (Note: the DFFUtils unit which resides in our library zip file of commonly used units.  Library file DFFVLIB13 or later is required to recompile this program )
bulletDownload current library file (DFFLibV15).

 

Suggestions for Further Explorations

Program currently insures that each definition has N sections as defined by colors, but it does not that the cells of a particular color are contiguous.  A future version should probably correct this.. 
.

 

Original:  July 13, 2014

Modified:  May 15, 2018

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby    All rights reserved.