Music Box Puzzle

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

Contact

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

Search DelphiForFun.org only

 

 

 

Problem Description

Fill this 5x5 grid box with the letters M, U, S, I, C.  The constraint is that the same letter may not appear more than once in any column, row or diagonal.   A few initial letters are placed to get you started. 

Background & Techniques

This was the May 1, 2011  puzzle in my favorite source for program ideas: the Mensa 365 Brain Puzzlers Calendar.   The  4 letters placed initially make it feasible to solve the puzzle  without additional hints; at each step there is a least one cell that has only one valid letter choice available.  For the puzzle novice, I added two hint levels: one to show the number of valid letter choices for each cell, and one which shows the letter choices for each cell.  The second level makes the puzzle almost too easy, the "number of choices" level just makes it easier to spot the cells with only one valid letter.

Play is simple;  use the mouse or arrow keys to select a cell, then press one of the "MUSIC" keys to enter a letter.  Choices which do not violate the constraint will be entered, other keys will reward you with a beep.  Double click an occupied cell to clear it.  Your reward for completing the puzzle is a "Congratulations" message.

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:

I started coding with the intent of writing code to solve the puzzle, thinking that it would be more difficult to solve than it is.  The original data structure included provision to sort the cells by the number letters which might fit there so that the search could resolve the shortest paths (the cells with fewest choices) first.  Then I realized that a simpler unsorted structure would work, I made a "Valids" array of strings with 25 entries, one for each cell with the string containing the current valid choices for that cell.  Cells are mapped to array locations by the expression  5r+c, where r is the row and c is the column of interest, indexed relative to 0, i.e. rows and columns numbered 0 to 4.   

Whether the user or the program makes the guesses about placing letters, we need code to evaluate if the letter can be placed in the selected location, and if so, to evaluate the effect on letters which can be placed in other cells (i.e. the Valids array strings).  The letters which may be placed might also be changed when an existing letter is deleted.  The checking logic is contained in these routines:.

  • Function AddChar handles letter additions.  It ensures that the letter to be added is in the Valids string for that cell and, if OK, adds it and then calls ReDoValidLetters telling it the cell and letter where it was added.
  • ReDoValidLetters removes (or adds) the  letter that was added (or removed) from the passed location in the Valids array for all cells in-line with that location. A character parameter, AddSub,  says whether the letter is to be added ('+') or removed ('-') from the Valids array.  It is called from AddChar when a letter has been added to the grid (must be removed from the in-line Valids strings).  It is called from GridDblClick when a letter has been removed (and is possibly to be added back to the in-line Valids strings).  RedoValidLetters scans and calls Updatevalids for each cell on  the row, column, and both diagonals of the passed cell location.
  • Updatevalids is the procedure which performs the actual Valids update adding or subtracting the passed letter as directed.    It is called from ReDoValidLetters for each cell to be checked.  Before a letter can be added back to any Valids, an additional check must be made of its row, column, and diagonal cells to make sure that the letter does not already exist there.  Local function CanAddLetter within UpdateValids does this check.

The other big job for user play is to respond to user inputs;  The string grid event exit methods for this are:

  • GridMouseMove: Cells in a string grid are identified by values of the Col and Row properties.  These are set typically set by user mouse clicks on a cell but can also be set by using arrow keys to move the cursor once the grid has the focus.  I decided to also allow cells to be automatically selected by the mouse position as it moves around the grid. 
  • GridKeypress;  Called when the user presses the key.  All we have to do here is make  sure that the key is uppercase and is one of the letters in "MUSIC".  If it is, pass it and the cell location along to AddChar to finish the task of adding the letter and updating the grid.   
  • GridDblClick: Tells the program to remove the letter in the clicked cell from the grid.  The exit then calls RedoValidLetters to update the Valids array to reflect the change; the removed letter may now be allowed in other cells in the same row, column or diagonals as this cell.
  • GridDrawCell: Finally, the draw cell exit gets to update the grid visual image after each change.  it draws the in-place letters in a large font and for the empty cells, either leaves them blank, displays the number of letters that might fit there, or displays the letter choices themselves, depending on the hint level selected.

 

Running/Exploring the Program 

Suggestions for Further Explorations

Starting with fewer than 4 letters in place would make the puzzle much harder to solve and justify adding  solution search code to the program.
There is likely a body of literature about these kinds of problems but I haven't searched yet.  We now know that it's possible to fill a 5x5 array with 5 symbols.  Is it possible to fill an N x N grid with N distinct symbols?  The 8 Queens puzzle requires placing a single symbol so that no two are aligned, How many more chess piece types could be added meeting the same constraint?
 
   
   

 

Original:  May 3, 2011

Modified:  February 18, 2016

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