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
We are given a 4x4 board with 6 of the 12
uniquely identifiable chess pieces in place. Place the other 6 on the
board in such a way that these constraints are met:
Two men of opposite colors may not occupy the
same row, column, or diagonal
Each Pawn must be adjacent to the King
of the same color.
There are no
more than 3 men per row or column.
Background & Techniques
This puzzle was adapted from the January 31 page of the Mensa 2009
Page-A-Day Puzzle calendar.
On startup or when the Reset button is clicked, the initial 6
pieces are placed in fixed positions on the board.
The user may drag and drop the other pieces to solve the problem. When all
12 pieces are on the board, they will be checked against conditions specified
above.
The Solve button resets the board and solves the puzzle using a
depth-first search with backtracking. There are checkboxes to set
options which apply while solving:
 | Random Move Order randomizes the order in which pieces
are placed Some sequences will take many more trials moves
before a solution is found. |
| Animate Moves checkbox moves the visual images on the
board as move are applied and retracted. |
| Show Steps display a text description of each trial move
made and retracted as the search progresses. |
A depth-first search with backtracking is a powerful but
fairly straightforward technique for searching a "space" of potential
move sequences We try the pieces in
order starting with the first piece in the list. When a valid position
for a piece is found, we
place it and move on to fit the next piece. This continues until all pieces are placed
or, more likely, we reach dead-end where no valid move exists for a piece.
When this happens, we remove the last move for the previous piece and look
for
another valid move location. If found, we move forward again, if not found, we back up another
piece a try to place it in a different position, etc until all six pieces
have been placed (success), or there are no more possible arrangements to try
(failure).
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to download
executable version of the program.
Notes for Programmers
Every problem, in programming or life, is most
likely to be successfully resolved if approached systematically.
There are books dedicated to describing problem solving techniques, but
the most basic in my opinion is "Divide and Conquer"; break every
big problem into lots of smaller problems. This seemingly simple
puzzle has a number of smaller ones. I decided to see how many i
could recall and then list them here:
Version 0: The basic problem
| The data structure - how to represent the
problem in data with arrays, objects, lists, records is one that
must be solved first. In this case i decided on an array of 12
TPiece records. Each record holds information about
each part: its name, location, and whether it was fixed or movable
were basic. |
| The backtracking search problem was
solved first, probably because it is the most fun, and you then know
the answer even if you have to use a watch to view it in memory.
It involve subproblems like:
 | How to tell when to stop.
|
| How to tell is a move is valid -
further divided into sub-problems:
 | Find an empty cell |
| No more than 3 pieces in a row or
column |
| Pawn next to King of the same
color |
| No two of the same piece type in
the same row or column |
| No two of the same piece on
the same diagonal. |
|
|
Version 1 : Add text display in a
StringGrid
| Initialize the grid with fixed pieces |
| Display and clear grid display as pieces are placed and removes
(Use OnDrawCell TStringGrid). |
Version 2: Add images
| Find the images (a Chess Piece TrueType font on the web. |
| Get the images available as 12 individual images |
| Modify TPiece record to hold the image of that piece as
well ans it current location. |
| Replace the TStringGrid with Canvas drawing lines for the
board. (Images only display on their parent control, we but we need
to display them on the form and on the board.) |
Version 3: Add user play and animation
| Implement drag/drop for the piece images.
| Convert mouse X,Y coordinates to board column and row
coordinates. |
| Modify the drag cursor in an OnDragOver exit to
indicate when the piece may be dropped. |
|
| Don't let the user drag the fixed piece images! |
| Design decision was made to defer checking validity of the
solution until all six pieces had been placed by the user.
Requires counting of pieces placed so far. If a user moves a
piece after the board is diagnosed as not a solution, do not count
that drop as an additional piece. |
| Animate the moving of pieces while PlacePiece function is
searching. Solved in AnimatePiece procedure - trickier than i
would have thought. |
Version 4: Add additional options,
| Make animation an option.
|
| Keep piece image on top of other images
while moving. |
| Shuffle the input order. |
| Display the moves tried in finding the
solution. |
| Display the move that failed when a move
must be withdrawn (much harder!). |
Each of these 20 or so could be (and was)
subdivided into 4 or 5 more sub-problems, so there may have been 100
problems solved in the course of writing the program. Divide and
conquer!
Running/Exploring the Program
Suggestions for Further Explorations
| When the user is solving, there is
currently no way to remove a piece that has been dropped on the
board, it can be shuffled around to empty spaces on the board, but
"un-moving" it might be more convenient when debugging a proposed
solution. |
| Validity checking when the user drops a
piece on the board could be an added option, although the
current method (checking after all pieces have been placed)
encourages more forethought placement. |
|
Original Date: February 3, 2009 |
Modified:
May 15, 2018 |
|
|
