A Number Theory Approach to Problem Representation and Solution
Proceedings of the Third International Joint Conference on Artificial Intelligence. General Problem Solving. Pages 606-610.
© 1973 International Joint Conferences on Artificial Intelligence
Abstract
A number theory approach to problem solving is presented using the tower of cubes puzzle as an example. Some conventional methods of solving the puzzle are first discussed. The puzzle is then thoroughly studied using an entirely different approach. Special numbers are used to represent the different colors on the sides of the cubes. A description matrix is used to compress the problem representation. The solution method becomes very efficient because of the concise representation of the problem. Two theorems are developed to verify the solution method. A generalization of the puzzle is also discussed.
- Busacker, R. G. and T. L. Saaty, Finite Graphs and Networks, An Introduction with Applications, McGraw-Hill Book Company, 1965, pp. 153-155.
- Greenblatt, R. et al, "The Greenblatt Chess Program", Proceedings AFIPS Fall Joint Computer Conference, 1967, pp. 801-810.
- Hardy, G. H. and E. M. Wright, An Introduction to the Theory of Numbers, 4th edition, Oxford University Press, London, 1965.
- Nilsson, N. J., Problem-Solving Methods in Arti- ficial Intelligence, McGraw-Hill Book Company, 1971. 5. Ibid., p. 3.
- Slagle, J. and J. Dixon, "Experiments with Some Problems That Search Game Trees", Journal of the ACM, Vol. 16, No. 2, April 1969, pp. 189-207.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
I. Introduction
Two major steps in problem solving are the prob lem representation and the problem solution. These two steps are very much interrelated. Problem repre sentations have a great influence upon the efficiency of solution methods. A number theory 3 approach is proposed in this paper for both the representation and the solution of problems. When applicable, this approach turns out to be very concise in the repre sentation and very efficient in the solution of prob lems. Even though not all problems can be solved with this approach, it still opens up a direction that researchers may want to look into to devise better methods in solving problems.
The tower of cubes puzzle is used to illustrate this approach in problem solving. To play this puz zle, a player is given four cubes with sides in four different colors. Each cube may be different from the other in the sense that one cube may have three red sides, one blue side, one white side, and one green side, while another cube may have two blue sides, two green sides, one red side, and one white side. The four cubes are shuffled and turned randomly before given to the player. The objective of the player is to stack the cubes into a tower so that there are four colors, all different, showing on each side of the tower.
We can describe the state of a cube by a six tuple of the form <front, back, left, right, top, bott,m>. For example, the tuple <R,W,B,B,G,R> des crib3s a cube with the front side in red, the back side in white, the left side in blue, and so forth.
With any given input configuration of the puzzle, the computer can be used to solve the puzzle. Differ ent methods can be used and are briefly discussed in Section II. In Section III, a method using the num ber theory approach is proposed which will find a solution to the puzzle efficiently, or if a solution does not exist, indicate that a solution does not exist. A generalization of the puzzle and some theo retical background is presented in Section IV. A conclusion is presented in Section V.
II. Some Solution Methods
This puzzle may be solved through the use of a state-space representation4 of the problem and by applying some search techniques to discover a solution. The following sub-sections describe some of these methods.
1. Blind Search:
Consider stacking the cubes one by one. There are twenty-four different ways that a cube can be posi tioned. Thus the state-space representation of the problem may be envisioned as pictured in Figure 1.

ror four cubes this method can involve a maximum of 24 = 331,776 paths. Although awkward, it is not prohibitive to use the blind search method on a mod ern computer. However, if one extends the game by adding additional cubes and colors, this method ra pidly becomes unfeasible.
2. Heuristic Searches
Different heuristics may be used to improve the efficiency of .the search. Some of these heuristics are discussed below.
- Assume a solution is found and turn the solution tower 90 degrees clockwise and we obtain another solu tion. This suggests that at level 1, in Figure 1, we do not really need to generate twenty-four nodes. Let us assign numbers to the sides of a cube as in Figure 2.
- It becomes apparent that we need to generate only three nodes at level 1, for example, with Side 1, Side 3 and Side 5 on top, respectively. Hence the search will then involve a maximum of 3 · 24 3 a 42,722 pat~s.
- Before starting the search one may want to select the cube with the most sides in one color and place it on top of the tower. Following this, one attempts to "hide" the dominant colors of each cube. That is, each cube is examined to determine which color, if any, appears most often. The cube is then positioned, if possible, so that this color is on the top and bottom of the cube. Hence the dominant color is, in a sense, "hidden". This heuristic can prevent some unnecessary searching whenever a solution exists.
- The tree searching down a twig may be halted when ever a node is found to be incompatible with a solu tion. That is, no further searching down that twig need be performed if two cubes having the same color on one side of the tower aTe found.
- Other heuristics may also be used. However, when a solution does not exist, an extensive search may be required. If the puzzle is extended by the addition of more cubes and colors then a heuristic search may still be intolerable. The following section des cribes an algorithm which overcomes some of the prob lems of the search methods.

III. A Number Theory Approach
A number theory approach to problem representa tion and solution is presented in this section. In short, this approach will make use of specially de rived numbers to represent a problem concisely and solve it efficiently. Unfortunately there is no algorithm or rule of thumb that can be established to derive the appropriate numbers for a problem.
This approach can be described by the f ollowing steps.
- Find a good notation or language for describing the problem.
- Derive an appropriate set of numbers useful for
problem representation.
- Construct a set, or sets, of production rules which can be used to perform valid transformations of the problem representation into problem solutions or into forms from which solutions can be easily derived.
- Attempt to revise the production rules, to obtain an optimal set of rules, and describe them abstractly, hopefully in some computer compatible language.
- Apply the production rules to a problem repre sentation to obtain an intermediate representation from which solutions can be more easily derived, or when possible, to obtain the solutions directly.
- If necessary, select an appropriate search pro cedure and apply it to find the solutions.
These steps are clearly interdependent. The selection of a notation for describing the problem will likely enhance or inhibit the optimization of the production rules, and the successful abstraction of a set of production rules can make the search pro cess efficient or even unnecessary. The tower of cubes puzzle provides an excellent example of a suc cessful application of the number theory approach. The following is a description of the application of this approach to the tower of cubes puzzle.
To begin with, the properties of a problem must be thoroughly investigated. For the tower of cubes puz zle, the convention was adopted to describe each cube as a six-tuple of the form <front, back, left, right, top, bottom>. Using this description, the following properties are noted.
- Although each cube is described as a six-tuple, the description of a solution configuration for each cube is only a four-tuple of the form <front, back, left, right>, This is obvious since a description of any four sides of a cube will uniquely determine the description of the two remaining sides. However, it should be noted that the initial description of a cube must contain a description of all six sides, since the <top, bottom> sides may be rotated into the position of the <front, back> or <left, right> sides.
- The Production Rules. A series of simple produc tion rules may be used. However, it should be noted that these rules rely on the principle that the des cription of the <top, bottom> sides is of no interest in the final solution. Thus, <·, ·> will be used to indicate either <top, bottom> or <bottom, top>, noting that it is not necessary to make a distinction. Given any description of a cube of the form <(al,a2), (bl,b2), (c 1 ,c 2 ) >, it can be transformed into other descriptions by the following rules.
- Interchange-within-tuple production schema:
- Interchange-tuple production schema:
- 3 . We can assign unique numbers to each of the four
colors which will greatly simplify the analysis of the puzzle. These numbers should be chosen in such a way that if one adds any eight of the numbers assigned to the sides then an examination of the resulting sum will indicate if each number (or color) appears in the sum mation exactly twice. The theorems concerning the selection of these numbers are presented in Section IV. The following numbers were selected for the four cube, four color tower of cubes puzzle:
| Red 1 |
| White z |
| Blue 5 |
| Green zo |
- The Description Matrix. A 4 by 3 "description matrix" can be computed, describing only essential information needed to discover the solution configura tion. Given an input configuration of the form:
The corresponding description matrix V is com puted as:
Note that vij is computed as:
and ai., bi. and cij are the numbers assigned to the sides 6f tn~ cubes using the scheme of section 3 above.
The interchange-within-tuple production schema will not affect the description matrix. However, the interchange-tuple production schema can be extended to the description matrix as follows:
It can easrly be shown that the description matrix corresponding to the solution configuration has the following property:
Thus a search for the solution conceptually is just a
search in the description matrix for a rearrangement of the description matrix such that the above equa tions are satisfied. If such a search fails, then no solution exists for the given puzzle. Section IV contains the theorems which verify and describe this process. It should be noted that, after a successful search, the necessary rearrangement of the description matrix can be performed by applying the appropriate interchange-tuple production schema.
- Solving the Puzzle. The following is a step by step procedure that can be used to obtain a solution to the puzzle.
- Read the input configuration and construct the corresponding description matrix [vij], i=l,Z,3,4 and j=l,Z,3.
v 4 -f_,> such that i+i': j+j', k+k', and t+l', and
If one fails to find these two four-tuples, then there is no solution to the puzzle.
The search process is to find two independent paths from the top row to the bottom row in the des cription matrix such that the values of these two paths are both 56. A path is defined to be a set containing one ·and only one element from each row of the description matrix. Paths are said to be inde pendent if they are mutually exclusive sets. The value of a path is the sum of the values of the ele ments in the path.
The search proces~ in the description matrix will involve a maximum of 3 = 81 paths. This number is considerably smaller than the maximum numbers of paths that may be involved in the other search methods des cribed in Section II.
Another property of this search process that should be mentioned is that a node is simply an inte ger number instead of a six-tuple or a four-tuple as in the search methods described in Section II. Hence the overall saving in this search process is tremen dous.
- Rearrange the input configuration to conform to the solution description matrix found in Step (Z). In other words, get two cube-sides in each different color on the front-and-back sides of the tower and on the left-and-right sides of the tower. This can be performed by applying the interchange-tuple production schema appropriately.
Specifically, let the input configuration have the form:
and let the objective configuration of this step have the form:
Note that the top-and-bottom sides of the cubes are eliminated from the objective configuration since they are irrelevant.
By applying the interchange-tuple production schema appropriately, we get:
i, j, k, .t, i'' j t' Step (2). k' , and .f. ' are all defined in
- The last step is to rearrange the configuration determined in Step (3) to conform to the solution requirement. In other words, get the four distinct colors on each side of the tower. This step can be performed by applying appropriately the interchange within-tuple production schema. This step is veri fied and described in Theorem 2 below. The final solution can then be printed as output.
IV. Two Theorems and a Generalization ~f the Puzzle
It is clear that the method described in Sec tion III will terminate when there exists no solu tion to a given input configuration of the puzzle. However, to show that this method does offer a solu tion and that it guarantees a solution when a solu tion exists, we need the following two theorems. The theorems also show that a generalization of the puz zle to n cubes and n colors can also be solved effi ciently with this method.
Lemma 1: Let a 1 , a 2 , ... be numbers such that a 1 = 1, a 2 ai_1-2(a 1 +a 2 +: ·. +ai_ 2 ) fori aj-l > 0 for J · 2,3, ... a sequence of real 2, and ai > (2i-3) 3, 4, .·. , then a. > J
- From (1) and (2), matical induction that j - 2, 3, 4, ... one can conclude by mathe a. > a. 1 > 0 for J J-
- i-1 Suppose a > 2 ~ a . for integer i and i ~4, then i j=l J
by assumption we have:
Considering (2) and by mathematical induc tion, one has:
Theorem 1: Let n be an integer greater than or equal to two, and let A be a set consisting of exactly 2n elements arbitrarily chosen from the set {a 1 , a 2 , . an} where a 1 = 1, a 2 = 2, and ai > (2i-3)ai-l -
2(a +a 2 + .·. +a._ 2 ) fori= 3, 4, ... , n. If the sum of the elements in A is equal to 2(a 1 +a 2 + ... +an), then A is the set {al,al,a2,a2·····~·~ } .
Proof: Let S*=2(a 1 +a 2 + ... +an) and letS equal the sum of all the elements in A.
- Suppose A does not contain two and only two ~'s. If A contains one or fewer ~·s then:
Thus s <S*. If A contains three or more an's, then: by Lemma 1 >2an+2(al+ a2+ ... +an-1) =2(a 1 +a 2 + ... +an)=S* by Lenuna 2
Thus S >S*. Hence one can conclude that if S=S·~, then A con tains two and only two an's.
- Suppose A contains two and the elements an, an-1· and A does not contain two If A contains one or fewer only two of each of ., an-k for Osk<n-1, and only two an-k-l's. an-k-l's then:
Thus S<S*.
If A contains three or more an-k-l's, then:
Thus S>S*
Hence one can conclude that if S=S*, then A must have two and only two ~-k-l's.
- From (1) and (2) one can conclude by mathemati cal induction that if S=S*, A is the set {al, al, a2, ;12, ... , an, an}.
The preceding theorem gives sufficient condi tions for the assignment of the numbers al, a2, . · ~ to the n different colors respectively. It also suggests a simple procedure for their generation, specifically let a 1 = 1, a2 = 2, and ai = (2i-3)ai-l -2(a 1 +a 2 + ... +ai_ 2 )+1 fori= 3, 4, .·. , n. The assignment of these numbers is then used to produce the description matrix. Theorem 1 guarantees that if we apply the solution algorithm to the description matrix, then we can, whenever possible, apply the interchange-tuple production schema such that the front-and-back and the left-and-right sides of the tower w,ill each be composed of 2n cube-sides whose colors will consist of two and only two of each of the n colors. This is the first of the two steps in ar ranging the cubes to conform to the solution of the puzzle.
Theorem 2: Let B be the 2n-element set {a 1 , a 1 , a 2 , a 2 , ··. , an, an} where ai #a. if i ~ j. Let A be a set of n ordered pairs where th~ pairs are chosen by arbitrarily selecting, without replacement, the 2n elements from the set B. Then one can rearrange the elements in the ordered pairs in A by possibly switch ing the order of the elements of some pairs in A such that one gets a new set, C, of ordered pairs where all the elements a1, a 2 , ... , an appear exactly once on both the left and the right positions of the pairs.
Proof: This theorem can be proved via the following constructive procedure. The new set, C, is originally null.
~: Select the first available ordered pair from A and call the pair a. Call the right element in a by the name b. Stop if A is empty.
~: There must be one and only one other b in the available ordered pairs in A including the pair a. Search for b in the available ordered pairs and this search process must succeed. If the other b is in the pair a, then go to Step 3. Otherwise, go to Step 4.
~: The other b is in the pair a and it must be in the left position of a. Remove a from A and add it to C. At this step, every element that appears on the left position of a pair in C must also appear on the right position of a pair in C. Go to Step 1.
~: The other b may be in either the left or the right position of the new ordered pair. Switch the order of the elements in the pair if the other b is ir. the right position in the pair. Now call the right element of the pair by the name b. Remove the pair from A and add it to C. Go to Step 2.
Since the set A has a finite number of ordered pairs in it, the preceding procedure must terminate after a finite number of steps. It is also apparent that upon termination, the set C must have the desired property.
Theorem 2 guarantees that if both the front-and back and the left-and-right sides of the tower of cubes are each composed of 2n cube-sides on which each of the n colors is represented exactly twice then the interchange-within-tuple production schema will allow us to arrange the tower of cubes to conform to the solution of the puzzle. Furthermore, the proof of this theorem gives a simple procedure that can be used in the second step to arrange the cubes to conform to the
solution.
V. Conclusion:
As Nilsson 5 says, "Research on solving puzzles and games has generated and refined many problem-solving ideas that are . also genuinely useful on less frivolous tasks". Puzzles and games provide a rich source of example problems for resea;ch in problem-s2lving. Many researchers such as Slagle and Greenblatt reported on research with games but much less research with puzzles is reported.
The tower of cubes puzzle with four cubes and four colors is by no means a prohibitive puzzle to be solved in any method on the modern computer. How ever, the solution of a generalized tower of cubes puzzle with n cubes and n colors rapidly becomes more and more time consuming as n gets larger.
As discussed in this paper, the selection of a problem-solving method can make a big difference in the efficiency of the problem solution. The methods discussed in Section II are rather conventional and are used to illustrate the effect of the differences in solution methods. They are also used to serve as a contrast to the number theory approach proposed in Section III. It should be noted that the procedure described in Section III is not the only efficient solution procedure for the puzzle. There are several other very efficient methods. The Busacker-Saaty approach which makes use of a 12-arc, 4-node graph is also an efficient method. It uses a search for two disjoint subgraphs having certain properties.
The number theory approach illustrates how logi cal reasoning and number theory techniques may be used in the representation and the solution of a prob lem. When applicable, the number theory approach may result in a very concise representation of a problem and a very efficient solution method of the problem. At this time it is unknown just how widely applicable this approach is to general problem solving. However, it is hoped that this paper may stimulate other re searchers to attempt to apply it to various problems.
@inproceedings{ijcai1973p75,
title = {A Number Theory Approach to Problem Representation and Solution},
author = {Shen, Stewart N. T. and Jones, Edward R.},
booktitle = {Proceedings of the Third International Joint Conference on
Artificial Intelligence, {IJCAI-73}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Nils J. Nilsson},
pages = {606--610},
year = {1973},
month = {8},
note = {General Problem Solving},
url = {https://ijcai.org/proceedings/1973/75},
}
TY - CPAPER TI - A Number Theory Approach to Problem Representation and Solution AU - Shen, Stewart N. T. AU - Jones, Edward R. T2 - Proceedings of the Third International Joint Conference on Artificial Intelligence, IJCAI-73 PB - International Joint Conferences on Artificial Intelligence PY - 1973 SP - 606 EP - 610 UR - https://ijcai.org/proceedings/1973/75 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: