If you shop at Amazon anyway, consider using
this link. We receive a few cents from each purchase.
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.
e-mail with your comments about this program (or anything else).
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
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
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
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
- 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
- Pawn next to King of the same
- 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
- 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
- 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
- Shuffle the input order.
- Display the moves tried in finding the
- 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
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
- 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
February 18, 2016