Chess Logic Puzzle

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

 

Search

 

Search DelphiForFun.org only

Support DFF

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

In Association with Amazon.com

 

Support DFF

 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

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: 

    bulletRandom Move Order randomizes the order in which pieces are placed  Some sequences will take many more trials moves before a solution is found.
    bulletAnimate Moves checkbox moves the visual images on the board as move are applied and retracted.  
    bulletShow 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
    bulletThe 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.
    bullet 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:
    bulletHow to tell when to stop. 
    bulletHow to tell is a move is valid - further divided into sub-problems:
    bulletFind an empty cell
    bulletNo more than 3 pieces in a row or column
    bulletPawn next to King of the same color
    bulletNo two of the same piece type in the same row or column
    bullet No two of the same piece on the same diagonal.   
    Version 1 : Add text display  in a StringGrid
    bulletInitialize the grid with fixed pieces
    bulletDisplay and clear grid display as pieces are placed and removes  (Use OnDrawCell TStringGrid).
    Version 2: Add images
    bulletFind the images (a Chess Piece TrueType font on the web.
    bulletGet the images available as 12 individual images
    bulletModify TPiece record to hold the image of that piece as well ans it current location.
    bulletReplace 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
    bulletImplement drag/drop for the piece images.
    bulletConvert mouse X,Y coordinates to board column and row coordinates.
    bulletModify the drag cursor in an OnDragOver exit to indicate when the piece may be dropped. 
    bulletDon't let the user drag the fixed piece images!
    bulletDesign 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.
    bulletAnimate the moving of pieces while PlacePiece function is searching. Solved in AnimatePiece procedure - trickier than i would have thought. 
    Version 4: Add  additional options,
    bulletMake animation an option. 
    bulletKeep piece image on top of other images while moving.
    bulletShuffle the input order.
    bulletDisplay the moves tried in finding the solution.
    bulletDisplay 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 

    bullet Download source
    bullet Download  executable

    Suggestions for Further Explorations

    bulletWhen 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.
    bulletValidity 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 18, 2009

  •  

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