Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 14, 2026

Available Issues

April 10, 2013 - May 14, 2026

Puzzle—A Mathematical Programming Approach for Mongolia’s “The Four Strongest” Puzzle

Published Online:29 Nov 2024https://doi.org/10.1287/ited.2024.0112

Abstract

We describe a mathematical programming approach to solve a recently proposed puzzle from Mongolia. This puzzle involves physically laying out toys of four legendary Mongolian animals in different orientations and positions within a box such that they fit. The author of the puzzle finds a solution by an exhaustive enumeration of the exponentially many possibilities and by employing a series of axiomatic assumptions. In the absence of the physical toys (and, thus, their true measurements), could we use operations research to help us? We present one such approach and several exercises that could be tasked in an introductory course on mathematical optimization. Classroom activities provide us a diverse set of solutions for some of these exercises.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/ited.2024.0112.

1. Introduction

Introductory courses on mathematical optimization and operations research (OR) across universities worldwide teach two key skills. The first skill is formulation: taking a layperson description of a “real-world” problem which is devoid of mathematical terminology and presenting it in the general form of a mathematical program. For example, classic discrete optimization problems, such as the traveling salesman problem or knapsack problems, are easily describable, even to a nonexpert. The second skill is solution: obtaining an optimal solution to this problem with a specialized algorithmic, typically non-enumerative, technique. Examples of such techniques include the simplex method or the branch-and-bound algorithm. Usually, it is on the second skill that instructors spend most of the course’s time. This article presents an insightful, yet playful, demonstration of the first skill and could be used as a classroom group activity or homework project in an introductory OR course.

In May 2020, Ninjbat published an interesting article about a mathematical puzzle called “The Four Strongest” (FS), showcased at the National Museum of Mongolia (Ninjbat 2020). In this game, toys of four mythological Mongolian animals—Dragon (D), Tiger (T), Lion (L), and Garuda (G)—are to be arranged such that they fit in a given hexagonal wooden container. As Ninjbat points out, the game is a “combinatorial puzzle with a geometric flavor.” After some simplifications, and motivated by an anecdote of a mathematician’s wife, Ninjbat solved this game with an exhaustive enumeration of all the possibilities. To do so required physical effort, as Ninjbat manually arranged all four animals exhaustively and checked if they could indeed be fit in the container. He first identified 192 possible arrangements of the four objects that he denotes as “candidate solutions” and then concludes that only 1 of these 192 combinations provides an arrangement where the toys actually fit. In another reference, this puzzle is called the “Four Dignities” (Munkhzul 2020); here, the author remarks, “it is important to find which one [toy] should first be placed inside.”

Several puzzles can be formulated as mathematical programs using OR techniques; see, for example, Barlow (2024), Lakhani et al. (2023), Harris and Forbes (2023), and Schaeffer et al. (2007). Mythology offers us several other such potential puzzles. In the grand Indian epic Mahabharata, Drona devises a strategic military formulation called as the Chakravyuha to capture the Pandava prince Yudhistra. This formulation is said to be impregnable, except by someone who knows the art of breaking it. The aim of this work is to demonstrate how mathematical models could be formulated from a description, even when little information of the underlying reality is known. To do so requires making a series of axiomatic assumptions that seek to capture reality as closely as possible. To quote John von Neumann, “If you have an application that satisfies the axioms, well use it” (Dantzig 2002). Within this work, we present four exercises that are employable as pedagogical instruments in an OR course to either improve or complement our line of reasoning. The four exercises are multifaceted. Exercise 3 presents an objective solution and requires only a basic knowledge of combinatorics. However, Exercises 1, 2, and 4 are subjective, presenting a variety of solutions, thereby being more suited for a small course project conducted individually or in small groups.

2. Formulating a Mathematical Model

2.1. Measurements

Exact measurements of the toys are unknown to us, as they are housed physically in the National Museum. In the absence of this information that would form the data of any employable mathematical model, how does one formulate reality?

We received a scan of the projected bases of the toys following a few email exchanges with Ninjbat. The figures were not to scale; however, Ninjbat was kind enough to additionally scan a ruler alongside the images so that we have, at least, an estimate of the measurements; see Figure 1. Next, we printed the four figures in figure 6 of Ninjbat (2020) on an A4 sheet of paper, cut them with a pair of scissors to have four bases, and compared the lengths with the ones we received from Ninjbat. This scheme provides us with four scaling factors, by which we ballpark the true dimensions of the toys; see Table S1 in Online Appendix B.1. Because the toys are irregularly shaped, we arbitrarily measure each toy from its middle. We note that this assumption means that the length of an object depends on the way it is placed; we revisit the implications of this assumption in Section 2.2. It is this crafty scheme that we employ to determine the problem’s data.

Figure 1. The Four Animals from Mongolia’s “The Four Strongest” Puzzle (Ninjbat 2020)
Source. Photograph credits: Uuganbaatar Ninjbat; used with permission.
Notes. (a) Dragon, D. (b) Tiger, T. (c) Lion, L. (d) Garuda, G.
Exercise 1.

Describe another method to measure the data of the problem.

The learning objective of Exercise 1 is to encourage alternative thinking mechanisms to assist in mathematically formulating reality (specifically, to estimate the underlying data)—with the very limited information available—by employing intelligible axiomatic assumptions. We recommend employing Exercise 1 and Exercise 4 together as either an individual or a small-group project.

2.2. Optimization

The heights of the objects are unimportant, as the wooden container does not have a lid. Thus, we are reduced to a problem of arranging irregular objects in a two-dimensional plane. This class of problems is closely related to cutting and packing optimization problems; see, for example, the Special Issue of the European Journal of Operational Research (Bischoff and Wäscher 1995). However, there are infinitely many possibilities of orienting an object on a plane—moving an object by a fraction of a degree provides a new orientation. So, again, how does one formulate reality? It is here that we follow Ninjbat’s (2020) suggestion of defining “candidate solutions”; see Section 1. We assume that each toy can be oriented in only two ways that differ with a 180° rotation between them. We denote these two orientations as ↑ and ↓.

Exercise 2.

Provide a description of candidate solutions when objects are allowed infinitely many orientations. List all assumptions.

The learning objective of Exercise 2 is to encourage alternative ways to formulate the same mathematical model with appropriate axiomatic assumptions. We recommend Exercise 2 as an individual exercise that is evaluated on a demonstration of how the employed assumptions result in different mathematical models.

Now, we generalize the puzzle from four to |I| toys, denoting them as i∈I; and from two to |J| orientations, denoting them as j∈J. Then, there are a total of |J||I|×|I|! arrangements. Half of these are repeated, as every arrangement can be flipped as a mirror image in a two-dimensional container. Then, for |I| = 4, |J| = 2, we have 192 possible arrangements, which is the number of candidate solutions that Ninjbat manually searched for (Ninjbat 2020).

Exercise 3.

How many combinations must one measure to determine the total length of r ≤ |I| chosen objects, each of which has |J| possible orientations, arranged continuously?

The learning objective of Exercise 3 is to evaluate a basic understanding of combinatorics and illustrate the concept of astronomical numbers. We recommend solving this exercise within the classroom itself, as there is an objective solution. Although Exercise 3 is relatively simple, we present it here, as we build upon it later in this work.

In Section 1, we describe a procedure where we physically measure the lengths of the four toys in their two positions. Ninjbat, too, physically arranged these 192 combinations to determine the best fit (Ninjbat 2020). If the minimum length of these 192 arrangements is less than the length of the box, the FS puzzle is solved; else, the problem is infeasible. However, such manual measurements are not only cumbersome, but also time-consuming. Similar to any combinatorial optimization problem, this method requires an exponential number of evaluations; specifically, it is the measurements of the total length of an arrangement that have (super) exponential growth. If one wishes to avoid spending significant effort sitting with a ruler and measuring lengths, a better estimation method is needed. This observation is comparable to the traveling salesman problem, where if all tour lengths are known, one simply computes the minimum to determine an optimal solution; however, computing all the tour lengths requires an exponential number of evaluations.

We use the inclusion-exclusion principle for assistance; see, for example, Vilenkin (1971). To measure the individual lengths of our four toys, having 180° rotations, with a ruler, we require eight measurements (see Exercise 3 with r = 1). We denote this measurement, multiplied with the scaling factors, as bij. Next, we determine the length of any two toys placed next to each other in both their orientations; we observe that the arrangements i,i′ and i′,i may have different lengths, which further depend on the respective orientations of the toys. Employing our crafty ruler method, we obtain these measurements in 48 evaluations (see Exercise 3 with r = 2). We denote this measurement as di,j,i′,j′. We provide values of bi,j and di,j,i′,j′ in Tables S2 and S3 of Online Appendix B.1, respectively.

Rather than proceed to measure the length of three toy arrangements, i,i′,i″, we approximate it as the sum of the two adjacent d lengths—i,i′ and i′,i″—minus the b length of the middle object i′ (with their corresponding orientations). Then, we obtain an approximation of the entire arrangement of the four toys as the sums of the d lengths minus the “interior” (i.e., not at either boundary) b lengths. In total, this process requires only 56 measurements, as opposed to 192 conducted by Ninjbat (2020).

With all the data now defined for our approximate mathematical formulation, let xi,j,k=1 indicate that toy i is present in orientation j at position k; else, xi,j,k=0. Then, the total length of the arrangement is the sum of di,j,i′,j′·xi,j,k·xi′,j′,k+1 minus the sum of the interior terms. The nonlinear product term is easily linearized by introducing a new indicator variable, yi,j,k,i′,j′,k+1, that is one if toy i present in orientation j at position k right next to toy i′ which is present in orientation j′ at position k + 1; else, it is zero. The following optimization model captures this.

min∑i,i′∈I;j,j′∈J;k∈K;i≠i′,k<|K|di,j,i′,j′  yi,j,k,i′,j′,k+1−∑i∈I,j∈J,k∈K;1<k<|K|bi,jxi,j,k,(1a)
subject to ∑i∈I,j∈Jxi,j,k=1,∀k∈K,(1b)
∑j∈J,k∈Kxi,j,k=1,∀i∈I,(1c)
yi,j,k,i′,j′,k+1≤xi,j,kyi,j,k,i′,j′,k+1≤xi′,j′,k+1yi,j,k,i′,j′,k+1≥xi,j,k+xi′,j′,k+1−1} ∀i,i′∈I;j,j′∈J;k∈K;i≠i′,k<|K|,(1d)
xi,j,k∈{0,1},∀i∈I;j∈J;k∈K,(1e)
yi,j,k,i′,j′,k+1∈{0,1},∀i,i′∈I;j,j′∈J;k∈K;i≠i′,k<|K|.(1f)

Model (1) is an integer program. The Objective Function (1a) seeks to minimize the total length of the arrangements of the toys using the inclusion-exclusion principle. Constraints (1b) and (1c) ensure that at each position k, exactly one (toy, orientation) pair is placed, and each toy i is placed at exactly one (position, orientation) position, respectively. Constraints (1d) linearize the term xi,j,kxi′,j′,k+1 by introducing the variable yi,j,k,i′,j′,k+1 with its McCormick envelope (McCormick 1976), while Constraints (1e) and (1f) ensure that the x and y are binary, respectively. The binary restrictions on the y variables can be replaced with their continuous relaxation without affecting optimality, and the k + 1 index can be dropped as well.

3. Solution

We use the General Algebraic Modeling System (GAMS) to solve Model (1) for the FS puzzle with the data provided in Online Appendix B.1. An optimal solution is T,D,L,G in orientations ↑, ↑, ↑, ↓, respectively, providing a total length of 29.08 cm. Ninjbat’s optimal solution—D,L,T,G in orientations ↓, ↑, ↓, ↑—is worse for our model and data, providing a total length of 31.54 cm. Despite the indeterminable errors in our crafty physical measurement procedure, the discrepancy is only 7.8%. This discrepancy is due to both our employed axiomatic assumptions, as well as not having more accurate data. However, given our assumptions, as well as the underlying data, the optimal solution provides the shortest length of the arrangement of the four toys.

Exercise 4

(Continued from Exercise 1). Describe another method to better estimate the data b and d, using only the pieces of information within this article (i.e., without using the data in Online Appendix B.1) and that within Ninjbat (2020). Check whether your method obtains a better objective function value of Model (1) than that reported above.

The learning objectives of Exercise 4 are the same as those of Exercise 1. We especially encourage discussing the merits and demerits of the new proposed solution with that we present in this work. Solutions could be verified with the GAMS code we provide in Online Appendix B.2 further assisting in basic programming skills in a modeling language.

There are at least two other reasons we may attribute our model’s differences from reality (where “reality” refers to the solution obtained by Ninjbat by physically using the four toys). First, Ninjbat’s container has a hexagonal base, whereas we assume a rectangular base. For a description of the container, see Ninjbat (2020). See also Exercise S2 in Online Appendix A. Second, we employ an approximation based on the inclusion-exclusion principle to avoid measuring the exponential number of lengths. Could you identify any other sources of error?

4. Conclusion

Exercises 1–4 could be employed as pedagogical instruments in an introductory OR course, especially to broadcast the wide reach of mathematical programming. Here, an instructor is encouraged to promote a variety of solutions (except for Exercise 3) and explore the effect of the underlying assumptions. A comparative analysis of the resulting model formulations could be conducted as well. Rather than explaining solution methods of OR problems, we focus on the art of formulating an OR problem. Another distinguishing factor of this work is the effort spent on measuring objects to determine the data of the problem instance; such methods could be presented in a course on data science as well. This significant amount of physical effort involved in determining the parameters of the problem motivates the approximate model of the puzzle we study.

Acknowledgments

I thank Uuganbaatar Ninjbat for his assistance with the measurements of the toy animals, as well as insights into the studied puzzle. I further thank Area Editor Dries Goossens for his suggestions on improving the manuscript’s exposition.

References

  • Barlow E (2024) Integer linear programming: Spreadsheet solver excellence without Excel. INFORMS Trans. Ed. 24(2):196–199.Link, Google Scholar
  • Bischoff EE, Wäscher G (1995) Cutting and packing. Eur. J. Oper. Res. 84(3):503–505.Crossref, Google Scholar
  • Dantzig GB (2002) Linear programming. Oper. Res. 50(1):42–47.Google Scholar
  • Harris M, Forbes M (2023) The snake eggs puzzle: Preparing students for Benders decomposition. INFORMS Trans. Ed. 23(3):210–217.Link, Google Scholar
  • Lakhani S, Vora M, Mahajan A (2023) An OR approach for WORdle. INFORMS Trans. Ed. 24(1):103–104.Link, Google Scholar
  • McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Program. 10(1):147–175.Crossref, Google Scholar
  • Munkhzul A (2020) Collection of the National Museum of Mongolia: “Four Dignities” puzzle. Accessed September 10, 2024, https://montsame.mn/en/read/246048.Google Scholar
  • Ninjbat U (2020) “The Four Strongest” at the National Museum of Mongolia. Math. Intelligencer 42(2):9–14.Crossref, Google Scholar
  • Schaeffer J, Burch N, Bjornsson Y, Kishimoto A, Muller M, Lake R, Lu P, Sutphen S (2007) Checkers is solved. Science 317(5844):1518–1522.Crossref, Google Scholar
  • Vilenkin NY (1971) Combinatorics (Academic Press, New York).Google Scholar
Previous
Back to Top