Search
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).
|
| |
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:
May 15, 2018
|
|
