TriSolve Source Code

Contents

• Introduction
• About the Code
• The Source Modules
• Potential Features
• Copyright and License
• The TriSolve Source Files

Introduction

TriSolve solves polyiamond puzzles. A polyiamond is a puzzle piece made of equilateral triangles. Here are some polyiamonds:

About the Code

Microsoft's Windows documentation and code samples and textbooks for Windows are fraught with global variables and local static variables. Such objects prevent the use of multiple threads or even multiple windows in a class that uses static variables to record context. TriSolve contains no variables that prevent multithreading or multiple windows. TriSolve contains no global variables, and it contains no static variables except read-only constants and a few process-wide constants that are initialized once. One such constant is used to access thread-local storage and is necessitated by Windows' failure to pass any context to a print abort procedure. As a result, each Window and each operation in TriSolve supports multiple instances. For example, several print operations can be in progress at once, if the user can send print commands quickly enough. Also, printing is done in a background thread, leaving the main application free for user interaction during printing. The Solver engine also supports multiple threads, although the main window only executes one at a time.

The solution-finding algorithm is extremely primitive and was not redesigned for TriSolve since the purpose of the exercise was to learn Windows programming.

The Source Modules

TriSolve.cpp contains WinMain and the code for the main window, of the TriSolve class. This window manages two small windows displaying the pieces and the goal; one large exhibit window showing the pieces, the goal, or the solutions, as selected; and one status/dialog window. The TriSolve window also manages much of the user interface, including menu commands and some navigation keys; manages the open pieces and goal; and starts the Solver engine.

TriDisplay.cpp contains the code for the TriDisplay window class and support routines. The TriDisplay windows paint polyiamond shapes, manage scrolling and scaling, and provide rudimentary editing capabilities.

Status.cpp contains the code for the status/dialog box. This dialog displays the Solver status, provides controls for the user to select views of the Solver progress, and provides controls to navigate through the found solutions. It also contains a graphic image of an on/off switch to start and stop the Solver.

Dialogs.cpp contains the code for small dialogs such as selecting application options, setting a view zoom percentage, and so on.

Shapes.cpp is a library of routines for operating on polyiamond shapes. This includes routines to read shapes from and write shapes to files, to find geometric transforms of shapes, to release the memory of shape structures, and so on. Not all of the information about shape structures is contained in this module, as TriDisplay.cpp also uses knowledge about the shapes to paint them in the display.

Solver.cpp contains the actual problem solving code. As noted above, the Solver engine is very primitive. It is run in a separate thread with a lower priority, so the solution search runs in the background and other work can continue in the application and in other processes in the system.

Print.cpp contains all the code for printing shapes in the background except the actual drawing routine, which is in TriDisplay.cpp. This includes prompting the user for print parameters, creating a thread to print in the background, the print abort procedure and abort dialog, and the print job code.

Utilities.cpp contains general subroutines, currently just routines to display error messages.

Sobol.cpp contains a routine from Numerical Recipes that prepares a list of color values intended to maximally separate the colors in the color space.

Potential Features

• Manage the pieces: Allow the user to select piece colors, remember the piece colors when saving and opening files, grab and drag pieces when editing, and edit with additional tools such as draw and erase tools instead of just a toggle tool.
• Allow the user to carve up a shape (some goal) to make pieces out of it.
• Generate all pieces up to a given size (in number of triangles). Let user take whole set or select pieces from it, including multiple copies.
• Provide a keyboard interface for editing: Let arrow keys move a cursor and space or enter keys activate a tool. (Scrolling would have to be moved to control-arrow keys.)
• For monochrome printing, color the shape interiors opposite to the perimeter line, giving white-on-black or black-on-white instead of grey against black.
• Enhance printing with labels and multiple displays per page.
• Evaluate changing perimeter pen thickness to logical units so it scales with shape and so that printed output looks more like the display.
• Rotate the display 90 degrees to orient the triangles as left-right pointing instead of up-down pointing, for aesthetically better display of shapes with lines intended to be vertical.
• Save and load solutions.
• Accept a goal file name or a goal file name and a pieces file name from the command line.
• Accept dropped files.
• The array index arithmetic in the Solver can be eliminated by converting the two-dimensional Point structures to one-dimensional address offsets prior to starting the Solver. This will speed up the Solver by about 8%. It may also be advantageous to separate the pieces and their transforms into two lists by parity to the first point, so the Solver can search only the list it needs at the moment.
• The on/off switch ought to be a button control instead of a static control, so that it would participate in the focus and tab selection.
• Count solutions without recording them (and consuming memory), and keep counting solutions after memory runs out.
• Perform simple checks before solving, such as counting the numbers of triangles.
• Write an advanced solving algorithm. Once the goal shape is disconnected, it may be good to pursue solutions within the smallest component before proceeding to the rest of the goal. It may also be possible to exclude impossible positions by checking whether the remaining pieces can be partitioned into the remaining components in ways that match the numbers of triangles. (Mathematically, the question here is whether a list of numbers of triangles in pieces can be partitioned to match the numbers of triangles in goal components. A list of potential sums of each subset of pieces prepared before starting to solve might be useful.) Some strategy to cut the goal into components might be useful.
• Identify symmetries in the goal shape and eliminate them by restricting transformations of one or more of the pieces.
• The preview and status windows are a bit of a hack, being fixed in place. The code as it is is quite capable of letting these windows move around, but there are issues to consider in how the interface appears to the user and how to manage size changes of the main window.
• Remove the two-pixel margin when drawing for the printer.
• Internal code improvements: Separate the scaling and scrolling structures and code in TriDisplay.cpp, so that the printing code does not incur the overhead of calculating scrolling.
• A technical note about the status box: It currently appears without a caption. Removing the control style from the dialog box will allow the caption to appear, but the edit control then misbehaves because it no longer has the notification style that causes it to inform the dialog window when it receives a mouse click. This might be corrected by changing the edit control to have the notification style after it is created or some hack, or it might be possible to give the window a caption by enclosing it in a window of another style. This requires determining the dialog's window size to use in sizing the enclosing window.

Copyright and License

The source code is published on the web for educational and demonstration purposes.

• Potential employers may copy the source code for the purpose of evaluating my skills.
• Natural persons other than employees of Microsoft may copy the source code for personal study.
• Corporations, government agencies, and other entities except those above are not granted any permission.

The TriSolve Source Files

© Copyright 2002 by Eric Postpischil.