Chess Logic Puzzle

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



Search WWW


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.


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

Search only



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: February 18, 2016


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