The Solitaire Board Game (solitaire)
The Solitaire Board Game is most commonly played on a 33 point board in a cross shape with 32 pegs, marbles or pieces (see Figure 1), other shapes are common too.
All Posts
In this blog, I will add a new post all 3-5 days. Each post contains a complete (optimization) problem, many of them are puzzles. Each problem consists of a comprehensive description of the problem, a description of the modeling (translation from spoken language to mathematical language), a mathematical formulation, an implementation in the LPL modeling language, and a link to solve the problem directly through the Internet. A full document is also downloadable as a PDF.
I start with easy puzzle problems, but later on, more complicated problems will be presented. Enjoy!
Snakes Problem (snake1)
This is another board game similar to the problem described in snake. Given 50 pellets each colored with one of five colors. 10 pellets at a time have the same color. The problem is to place all pellets on a board consisting of 50 notches layouted on a 10 × 5 grid points in such a way that all pellets with the same color must have at least one neighbor and build a sequence without braching. Two pellets are neighbors if they are immediate horizontal or vertical neighbors on the grid. The game begins after 5 pellets – all of different colors – have been placed on arbitary grid points (notches).
6-Snakes Problem (snake)
The 6-snakes problem is a board game for one person. The board is a hexagon with 72 notches where the 72 pellets must be placed (see Figure 1). The pellets are divided into 6 groups of 12 pellets. In each group the pellets have the same color – hence there are 6 colors.
The 6-Magic Star (mstar)
A 6-pointed magic star is a star polygon in which numbers are placed at each of the 6 vertices and 6 intersections, such that the four numbers on each line sum to the same magic constant (see Figure 1).
Who Went Hiking Alone? (hikers)
A group of 17 persons, named A, B, …, Q went hiking. The next day, they came together with their friend James who was not on the hike. They told him that soon after the start they split into 4 groups and each group went on its own continuing hiking. Each person gave James four names with whom he was not in the same group. This information is displayed in Table 1. He was also told that one person went alone and there was a group of three persons. James then immediately told them who was the person that went alone. How did he find out?
Coloring a Map (coloring2)
Color the map in Figure 1 with the smallest possible number of colors in such a way that two fields, numbered from 1 to 110, having a common border (that is, they touch each other) do not have the same color. This problem is from [1], page 127.
Shoe Lacing Problem (lacing)
Proper shoe lacing is important and there are various ways of lacing passing through the eyelets. The problem can be described as follows. Let {1,…,m} be a straight line of m ≥ 1 eyelets on a shoe and let {m + 1,…, 2m} another parallel line of m eyelets. A feasible lacing is a “circuit” from eyelet 1 to eyelet m + 1 and back to 1 passing through each eyelets exactly once, choosing eyelets on both lines alternatively and closing the circuit by moving from eyelet m + 1 to 1. Figure 3 shows three common methods of lacing a shoe (see [2]).
Hamiltonian Circuit (cross92)
This problem is another example for tour finding in a graph (see icosian). Given a graph as in Figure ?? find a tour in the graph, if it exists.
Hamiltonian’s Game (icosian)
The Icosian game, also called the Hamiltonian game, is a mathematical game invented in 1857 by William Rowan Hamilton. The game’s object is finding a path along the edges of a dodecahedron such that every vertex is visited exactly once, and the ending point is the same as the starting point.
Moving Coins (triangle)
Figure 1 displays 10 coins arranged in a triangle pointing to the top. Arrange the coins in a triangle such that it is pointing down by moving as few coins as possible.