Dotnet Turkey

A Little Puzzle Called Jeu de Taquin

It's now time to program a game. Well, more like a puzzle. This particular puzzle was invented in the 1870s, probably by the famous American puzzle-maker Sam Loyd (1841-1911). For a while, this puzzle was all the rage, particularly in Europe, and was known under various names, including the 15-puzzle, the 14-15 puzzle, and (in France) Jeu de Taquin, the "teasing game."

In its classic form, the puzzle consists of 15 square blocks numbered 1 through 15. The squares are arranged in a 4-by-4 grid, leaving one blank space. You can move the squares around the grid by shifting a square horizontally or vertically into the blank space, which in turn opens a different blank space.

As Sam Loyd presented it, the numbered squares were arranged in consecutive order except with the 14 and 15 reversed. He offered $1000 to anyone who could find a way to shift the squares around to correct the order of the 14 and 15. No one collected the reward because, from that starting point, the puzzle is insolvable.141

In computer form, this puzzle was one of the first game programs created for the Apple Macintosh, where it was called PUZZLE. It also appeared in early versions of the Microsoft Windows Software Development Kit (SDK) under the name MUZZLE, where it was the only sample program in the SDK coded in Microsoft Pascal rather than C. Both these programs initially displayed the 15 squares in consecutive order and presented a menu option to scramble the squares. You then attempted to restore the order of the squares or put them into different orders, such as going down the columns rather than across the rows. Because we haven't covered menus yet, my version of the program scrambles the squares when it first starts up. (That's where the timer comes into play.)

The tiles are child windows, but they set their Enabled property to false to let the parent process all keyboard and mouse input. Normally, controls indicate that they're disabled by graying their text, but they don't have to use this approach. In this case, they don't. The OnPaint method uses normal control colors to draw a 3D-like edge.

JeuDeTaquinTile.cs

// JeuDeTaquinTile.cs ® 2001 by Charles Petzold //----------------------------------------------

using System;

using System.Drawing;

using System.Windows.Forms;

class JeuDeTaquinTile: {

int iNum;

UserControl public JeuDeTaquinTile(int iNum) {

this.iNum = iNum; Enabled = false;

protected override void OnPaint(PaintEventArgs pea) {

Graphics grfx = pea.Graphies;

grfx.Clear(SystemColors.Control);

int wx = Systemlnformation.FrameBorderSize.Width; int wy = Systemlnformation.FrameBorderSize.Height;

grfx.FillPolygon(SystemBrushes.ControlLightLight, new Point[] {new Point( 0, cy), new Point(0, 0), new Point(cx, 0), new Point(cx - wx, wy) new Point(wx, wy), new Point(wx, cy - wy)

grfx.FillPolygon(SystemBrushes.ControlDark, new Point[] { new Point(cx, 0), new Point(cx, cy), new Point(0, cy), new Point(wx, cy - wy), new Point(cx - wx, cy - wy), new Point(cx - wx, wy)});

StringFormat strfmt = new StringFormat();

strfmt.Alignment = strfmt.LineAlignment = StringAlignment.Center;

grfx.DrawString(iNum.ToString(), font, SystemBrushes.ControlText,

ClientRectangle, strfmt);

The program that creates these tiles and moves them around the grid is a bit more complicated. It creates the tile controls (and sizes the client area based on those controls) in an override of the OnLoad method implemented in the Form class. The OnLoad method is called soon before the form is first displayed; my experience indicates that obtaining Graphics objects and setting the size of a client area usually works better when done during OnLoad rather than during the constructor.

OnLoad processing concludes with a call to the protected method Randomize, which uses a timer to scramble the tiles.

JeuDeTaquin.cs

// JeuDeTaquin.cs ® 2001 by Charles Petzold //------------------------------------------

using System;

using System.Drawing;

using System.Windows.Forms;

class JeuDeTaquin: Form {

const int nRows = 4;

const int nCols = 4;

Size sizeTile;

JeuDeTaquinTile[,] atile = new JeuDeTaquinTile[nRows, nCols];

Random rand;

Point ptBlank;

int iTimerCountdown;

public static void Main() {

Application.Run(new JeuDeTaquin());

public JeuDeTaquin() {

BorderStyle = FormBorderStyle.Fixed3D;

protected override void OnLoad(EventArgs ea) {

// Calculate the size of the tiles and the form.

Graphies grfx = CreateGraphies();

ClientSize = new Size(nCols * sizeTile.Width, nRows * sizeTile.Height);

grfx.Dispose();

// Create the tiles.

0; iRow < nRows; iRow++) 0; iCol < nCols; iCol++)

JeuDeTaquinTile tile = new JeuDeTaquinTile(iNum); tile.Parent = this;

tile.Location = new Point(iCol * sizeTile.Width, iRow * sizeTile.Height);

tile.Size = sizeTile; atile[iRow, iCol] = tile;

ptBlank = new Point(nCols - 1, nRows - 1); Randomize();

protected void Randomize() {

iTimerCountdown = 64 * nRows * nCols; Timer timer = new Timer();

timer.Tick += new EventHandler(TimerOnTick); timer.Interval = 1; timer.Enabled = true;

void TimerOnTick(object obj, EventArgs ea) {

case	0:	x++ ;	break;
case	1:	x-- ;	break;
case	2:	y++;	break;
case	3:	y-- ;	break;

if (x >= 0 && x < nCols && y >= 0 && y < nRows) MoveTile(x, y);

((Timer)obj).Tick -= new EventHandler(TimerOnTick);

protected override void OnKeyDown(KeyEventArgs kea) {

if (kea.KeyCode == Keys.Left && ptBlank.X < nCols - 1) MoveTile(ptBlank.X + 1, ptBlank.Y);

else if (kea.KeyCode == Keys.Right && ptBlank.X > 0) MoveTile(ptBlank.X - 1, ptBlank.Y);

else if (kea.KeyCode == Keys.Up && ptBlank.Y < nRows - 1) MoveTile(ptBlank.X, ptBlank.Y + 1);

else if (kea.KeyCode == Keys.Down && ptBlank.Y > 0) MoveTile(ptBlank.X, ptBlank.Y - 1);

kea.Handled = true;

protected override void OnMouseDown(MouseEventArgs mea) {

int x = mea.X / sizeTile.Width; int y = mea.Y / sizeTile.Height;

for (int y2 = ptBlank.Y - 1; y2 >= y; y2--) MoveTile(x, y2);

for (int y2 = ptBlank.Y + 1; y2 <= y; y2++) MoveTile(x, y2);

for (int x2 = ptBlank.X - 1; x2 >= x; x2--) MoveTile(x2, y);

for (int x2 = ptBlank.X + 1; x2 <= x; x2++) MoveTile(x2, y);

atile[y, x].Loeation = new Point(ptBlank.X * sizeTile.Width, ptBlank.Y * sizeTile.Height);

atile[ptBlank.Y, ptBlank.X] = atile[y, x]; atile[y, x] = null; ptBlank = new Point(x, y);

Everything else in the program just involves processing keyboard and mouse input leading up to a call to the MoveTile method at the bottom of the listing.

The two-dimensional atile array stores the tile objects. For example, the tile object stored at atile[3,1] is the tile currently in the fourth row and second column of the grid. One element of the atile array is always null. That null element corresponds to the coordinate currently not occupied by any tile. The ptBlank field also stores that coordinate. The blank—as I'll call it—governs the user interface; likewise, ptBlank plays a major role in the user interface code. Any tile that the program moves must be adjacent to the blank, and it must move into the blank.

When you use the mouse, you don't have to click a tile adjacent to the blank, however. If you click a tile in the same row or column as the blank, the program moves multiple tiles with one shot, which means it makes multiple calls to MoveTile. The MoveTile method both physically moves the tile (by setting the Location property of the tile being moved to the location of the blank) and adjusts the atile and ptBlank fields accordingly.

The keyboard interface involves the arrow keys. If you think about it, pressing any of the four arrow keys has an unambiguous meaning. For example, pressing the down key always moves the tile immediately above the blank (if any) into the location of the blank.

Here's a sample view of the program as I'm about halfway through solving it:

This is now the third program in this book in which creating a custom control has been found useful. As you undoubtedly know, Windows and the Windows Forms .NET Framework implement a multitude of ready-made controls in the form of buttons, labels, text-entry fields, list boxes, scroll bars, and much more. We'll begin exploring that world in Chapter 12.

141 A mathematical analysis of the 14-15 puzzle first appeared in an 1879 article in the American Journal of Mathematics. The underlying math is summarized in James R. Newman, The World of Mathematics (New York: Simon and Schuster, 1956), 4: 2429-2432. The four-volume World of Mathematics was republished in 1988 by Tempus Books (a defunct imprint of Microsoft Press) and in 2000 by Dover Books. The section on the 14-15 puzzle appears on pages 2405 to 2408 in the Tempus edition.

0 0