Paletto Puzzle

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

 

Search

Search WWW

Search DelphiForFun.org

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.

Contact

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

Search DelphiForFun.org only

 

 

Problem Description

This program implements a board game called Paletto and a puzzle derived from it.

Background & Techniques

Paletto is a game for 2 to 4 players designed by Dieter Stein and described on his website http://spielstein.com/games/paletto. The rules are simple and play is easy but some strategic thinking is required to win. The physical game is manufactured and marketed by Clemens Gerhards on eBay and, along with many other attractive games, on his website http://www.spiel-und-design.eu/en. The games look to be of excellent construction and reasonably priced at around $25. Unfortunately, shipping to the US adds $48 to that price making unlikely that I will ever own one! 

Partial game: The 3 Purple tiles might be a good choice for Player 1 

The Game

The physical game is played on a 6x6 board and has 6 balls of 6 different colors, 36 in all.  A game starts with all of the balls randomly placed on the board. In serious competition, a third party would have to load the board since it would be easy for a knowledgeable player to  "stack the deck".  Players take turns removing eligible balls of a single color.  The game is won by the player who either takes all pieces of any color or whoever takes the last piece from the board. Players take turns. In each turn a player chooses a color, then removes any number of same-colored pieces (not necessarily all) from the board by clicking on them.

A piece may be removed from the board if:

  • There are two or more open sides (board edges or touching an empty cell) and
  • All remaining pieces after the move are still  "orthogonally connected", that is, one could travel from any occupied cell to any other occupied cell by making horizontal and vertical moves.

The puzzle described below requires an 8x8 board so and 8x8 version of the game has also been implemented.,

First 3 rows while solving

The Puzzle

I became aware of the game because a long time viewer and fellow Delphian residing in Germany owns the game and had developed a puzzle idea based on it but wasn't sure that it was solvable. After a few iterations, we proved that it is solvable and is included here as "Puzzle 2", both as a user playable version and the solution search that proved it could be done.   For the puzzle, we are required to fill an 8x8 board with 64 balls or tiles, 8 balls in each of 8 colors following 2 rules.

  • Each tile and its the vertical and horizontal neighbors, if any,  must be of different colors (requiring 5 colors  for interiors tiles).
  • Each corner of the board must be of a different color.

Users play using "click-drag" operations.  Click a tile from the 8 tile "piles" which pick it up, move to the target cell and click again to drop it.  A "beep" indicates that the attempted placement is invalid.  Tiles in place may be clicked and returned to the available stack or dropped on any other empty cell on the board.

Random program search solution

The programmed  search to fill the board performs a trial and error search to find a tile which can be placed without violating the rules, If none can be found, the program "backtracks" to the previously placed tile and tries to find another valid choice. Options allow the board to display color numbers (1 through 8) or colored tile in either the order that they were defined or in random order.  There is a "Show progress" box to watch the backtracking process.  For random board solution, the amount of backtracking required depends on how the early tiles got placed.  Typically between 4,000 and 4,000,000 tile placements are required before a solution is found.  

 

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:

Program logic is a quite straightforward implementation of the rules.  However there are a few interesting techniques used (or reused) here:

  • "Click dragging", dragging without holding a button down:  Especially when using a touchpad to drag across a grid, it is easy to accidentally drop the object in the wrong place.  A simple solution is to define a flag to indicate when dragging is taking place.  Here we use an integer variable, DragColor, to indicate both that a tile is being dragged (DragColor>0) and the color index of the tile color being dragged.  A second MouseUp on at an eligible location when Dragcolor >0 marks the "drop" operation.    
  • Creating a colored square as a "drag" cursor for each color during manual play of the puzzle: The process is straightforward using the TIconInfo data structure to hold the bitmap (a colored square in this case) and the CreateIconIndirect  Windows API call to assign the cursor to the array of Screen cursors.  This is done in the FormActivate procedure for all 8 colors.    
  • To recognize where a mouse click is made on a string grid: The MouseToCell method of TStringGrid handles this nicely.  The OnMouseUp event exit will return the X and Y mouse coordinates more readily than using the OnClick exit.  
  • Moving the mouse cursor to a specific grid cell:   This inverse problem occurs here when the user is dropping a tile back onto  the tile stock pile grid  when manually solving the puzzle.   Dragcolor is the color number of the tile being dropped with values 1 through 8, corresponding to columns 0 through 7 and we want to recognize any click on the stock pile grid while dragging as a signal to drop the tile on the cell from whence it came.  Here's the code:
    •   acol:=dragcolor-1;
        r:=StockPileGrid.CellRect(acol,1); {the rectangle containing the color}
        {move the mouse cursor to the center of this rectangle}
        with r do mouse.cursorpos:=ClientToScreen(point((left+right) div 2, (top+bottom) div 2));  
  • Shuffling the color array to control the order of trying colors for random solutions:  Procedure Shuffle randomly rearranges any array of integers by swapping each number location, starting at the high end of the array, with a random location less than or equal to the current one.
  • Manual vs. program checking in solving the puzzle: There are two sets of offsets; the programmed search proceeds from left to right and top to bottom and therefore only needs the verify that the tile being placed does not match either of the two preceding neighbors to the left of or the two above the current location (4 tests in all).  The human player however may place tiles in any order  and therefore we must check 2 neighbors in each orthogonal  direction as well as the 4 diagonals,  12 tests in all to ensure that the tile may be safely placed.       
  • Recursive Placepiece function places pieces and retracts and tries a different color for the previous move when no valid color exists for the cell being filled:  Long time DFF followers will recognize the "recursive search with backtracking"   exhaustive search technique used in many programs here for puzzles which  require no more than a few million trials. When the "Show progress" box is unchecked, the search process about 1,000,000 locations per second and solves most cases in a few seconds.  Watching the progress slows the process down significantly.

Addendum February 4, 2013:  I received a note today from Paletto's author, Dieter Stein.  He likes the program but pointed that the initial board for the game must not share a side with another token of the same color which I did not realize.  This restriction prevents the person placing the tokens initially from "stacking the deck" as I had initially mentioned.  Version 2.1 posted today corrects the problem by generating random boards until a valid one is found.  About 1,000,000 boards per second can be created and tested.  Making new 8x8 boards may take a few seconds (up to 5,000,000, tries) but 6x6 boards require only a few hundred thousand trial boards, so appear almost instantly.  

  

Running/Exploring the Program 

  • Download  executable
  • Download source  (Note: the DFFUtils unit which contains the "AdjustGridSize" procedure resides in our library zip file of commonly used units.  Library file DFFVLIB13 or later is required to recompile this program )
  • Download current library file (DFFLibV14_12Nov2016) required to recompile Paletto Puzzle.

Suggestions for Further Explorations

Teach the program to play the game against a human opponent,
   
Original:  January 17, 2013

Modified:  February 18, 2016

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