What part of maths covers Factory Balls?

Question

There is this nice little game called Factory Balls. Playing it for 2 minutes (you can buy it on Steam or play for free on Kongregate) will probably give you a better overview of my screenshot example. But I digress:

The game provides you a clear ball, a target template(the one shown in the box's label), and some tools to modify your ball. In this example (B27), you have 4 paint tools in the left side, and 4 "region coverage" tools in the right side. The puzzle's trick is the order in which to use the tools so as to achieve the target template.

As long as the tools are only of the aforementioned 2 types, paint and region covering, then my question is:

Which branch of mathematics can help me formulate a solution, not for one, but for all levels of this game?

Answer 1

This problem is somewhere in the domain of combinatorics - and it's hard to specify much beyond that (and "combinatorics" is very broad), because it doesn't fit neatly into some smaller field of study. The most relevant mathematical objects are really sets and functions (for really elementary things), directed graphs (if we just use brute force), and orders (if we look deeper). In fact, it's not so hard to completely draw out the theory here.

To describe the question mathematically: You have some set $P$ of positions on the objects and a set of objects $O$, each of which is some subset of $P$ (the subset it covers). You also have some set of colors $C$. Every "state" of the game is represented as some function $f:P\rightarrow C$ giving the colors of each position, and legal transitions are choosing some subset $X$ of objects and some color $c$ and changing the value of $f$ on every point $p$ not covered by something in $X$ to the color $c$.

You could represent the set of states and transitions as a directed graph, but this doesn't give great insight - better is to study the definition a bit and reduce it to something more manageable.

If you think about this definition more rigorously, but without reference to any external theorems, you can describe a strategy that always works. In particular, there's a relation hiding here:

A point $p$ is at least as specific as a point $q$ if every object that covers $q$ also covers $p$.

This is equivalent to saying that $p$ is at least as specific as $q$ if it is not possible to cover $q$ without also covering $p$. Equivalently, if $q$ is not covered by some set of objects, $p$ is not covered either. This is really important because if we wished to color them different colors, then we'd have to color $q$ first, then color $p$, since otherwise we could not color $q$ without overwriting the color of $p$.

Let's denote this relation by writing $p \leq q$, referring to how the smallest region including $q$ that can be left uncovered must, under this definition, contain the smallest region including $p$ that can be left uncovered. This is transitive meaning that if $p \leq q$ and $q\leq r$ then $p\leq r$ and it is symmetric meaning that $p\leq p$. This defines a structure known as a preorder. There is an associated idea of congruence given by $p\sim q$ if $p\leq q$ and $q\leq p$ - which, in elementary terms, means that $p$ and $q$ are covered by exactly the same set of objects.

We can then prove a theorem, with an explicit description of the strategy (assuming finitely many objects):

A coloring $f:P\rightarrow C$ can be achieved if and only if $p\sim q$ implies $f(p)=f(q)$.

Which basically says that only the obvious constraint applies. To prove this, we can first look at the equivalence classes of $P$ under $\sim$ - which basically means that we can either pick one point $p$ to represent each region defined as "the set of points covered by this set of objects and no others" or we can consider each such region as its own object. This reduces us to having only finitely many elements to work with; for notation, the set of such regions is denoted $P/\sim$ and each of them, due to the hypothesis, has some desired color valid over that whole region.

However, once we have chosen these representatives, the relation $\leq$ becomes a partial order - meaning that if $p\leq q$ and $q\leq p$ then $p=q$. Then the strategy becomes easiest:

Let $S$ be the set of regions in $P/\sim$ that are not the correct color and choose a maximal $x\in S$ (i.e. some $x$ so that if $y\in S$ and $x\leq y$ then $x=y$). Cover the ball with every object not covering $x$ and color that region with the color desired for $x$. Repeat this until you finish.

The proof of correctness is easy: the set of points in $P/\sim$ which are at least as specific as one which is incorrectly colored gets smaller each time we apply this move.

Then, we can translate back into simple terms:

Look at all the points that are not yet the correct color. Of these points, find one which could be covered by the largest number of objects. Cover the ball with all the objects not covering that point and color that point with the color it ultimately wishes to be. Repeat until you win.

This is guaranteed to work on any puzzle that is not blatantly impossible (i.e. has two points, covered by the same set of objects, but of differing desired colors).

Note that this solution only really grazes any branch of mathematics: we borrow the terminology of order theory to solve and visualize things, but we didn't use any substantive theorem other than "every finite partially ordered set (poset) has a maximal element" - and we wouldn't have known that orders would be relevant just looking at the question. Basically, this is less of a "go study this specific field" problem and more of a "have a broad view of mathematics and get your hands dirty" problem.

Answer 2

I don't think permutation groups apply here, having played through a little of the game. The reason is that there are actions that cannot be undone. For example, once you paint the entire ball, you cannot reach any state where any part of the ball is white (some of the goal states have white regions). There's also a "pump" tool that inflates the ball, so that only the bottom portion of it gets painted when it is dipped in a bucket. Pumping cannot be undone.

One of the requirements for a collection of things to be a group is invertibility (in Rubik's Cube terms, every move has an inverse move that undoes it).

I would look to graph theory, or finite state machines. The ball can be in a (finite) number of states, and from each state you can choose one of the tools to transition to another (possibly equivalent) state. If you consider states to be "nodes" and transitions to be directed "edges" connecting the nodes, your goal is to find a path in the graph (crossing edges in the correct direction) that begins at the initial state (white ball) and ends at the target state. Finding paths in graphs is broadly referred to as "search" and there are many graph search algorithms that will provably find the path, if one exists.

Answer 3

The puzzle is a bit like Rubik’s Cubes, which has been analysed using permutation groups.

The set you operate on would be the union of all the individual segments made available by slicing the ball with various region tools. Assuming the ‘back’ doesn’t matter (or alternatively, that it follows the colouring between the two cheeks), your example shows 8 regions: the hat creates the top and bottom hemispheres, the belt cuts each hemisphere in two, and the earmuffs create 4 more regions. I’m not sure why there are two sets of earmuffs, so if my guess is off, feel free to define the regions to suit the game.

The possible values (of each member of the set) would be the colours available (including the null colour), perhaps with a duplicate set of colours to represent the frozen states arising from segments that the region tools hide. An alternative is to enumerate all region+paint combinations, but duplicating the colours is probably simpler and more flexible to changes in the kinds of operations permitted.

The operations would be paint(colour), freeze(segment) and unfreeze(segment), where paint only changes unfrozen colours. These correspond to applying paint, applying a region tool and removing the region tool.

If you wanted to apply multiple region tools and remove them in any order while painting at will, you can discard the ‘frozen’ colours and replace the values with tuples of the form (colour, depth), where ‘depth’ is the number of region tools applied to a particular element.

Answer 4

There is a family of physical puzzles very similar to this, called Transposer puzzles. These consist of a set of cards that have various areas that are either coloured or have a hole punched through. You have to stack these cards such that only one colour is visible. Placing a card on the stack is very much like applying paint to some of the areas (wherever the card has colours), while leaving other areas untouched (wherever the card has holes). You can see these puzzles on my site, and the official website is still online though I don't know if it is maintained.

The Kaboozle variant of this puzzle has been shown to be NP-complete (Kaboozle Is NP-complete, Even in a Strip), which kind of means that when you make the puzzle large enough it can get so hard to solve that you basically have to just try out all the possibilities.

Of course, the Factory Balls puzzle is relatively small so it can be done with pen and paper, or with a little practice in your head. The trick is to think in reverse, from the final state backwards to the uncoloured ball:

• If you put all the protections on (or just the hat and belt - the headphones don't cover anything that the belt doesn't) then you can paint the bottom part of the ball without affecting any other region. So you can do this as the last step, and before that only have to colour the rest of the ball correctly.
• If you put on only the belt, you can paint the top and bottom parts of the ball. As noted above, the bottom part can be repainted afterwards, so you can paint these top/bottom parts as you wish. You can now completely ignore the top/bottom parts and only think about the middle section.
• If you put on the hat and both headphones, you can colour the lower ring (and the bottom cap but we can ignore that). So you can now ignore the caps and the lower ring.
• If you put on just the two headphones, you can colour the upper ring (and the caps and lower ring but we can ignore those). So you can now ignore both the caps and the rings.

A solution is now becoming clear. You just need to get the "ears" right, which is easy in this case.

• First get the "ears" the right colour. (No protection, paint orange; Hat, paint yellow). Then do the above steps in reverse.
• Paint upper ring (Both headphones, paint green)
• Paint lower ring (Both headphones and hat, paint red)
• Paint upper cap (Belt, paint yellow)
• Paint bottom cap (Belt and hat, paint orange)

If the "ears" were different colours, you would have to unpack the solution method a little further by leaving one set of headphones on, with and without the hat.

This does not necessarily give the shortest solution, especially if putting on or taking off protection is counted as a move.

The above works because we found a sequence of ways to place the protection that uncovered one region at a time (possibly covering a previously uncovered region again). When done in reverse, it permanently covers one more region each time, the region we just painted the right colour (possibly also uncovering or temporarily covering regions that we haven't painted properly yet). You can imagine more complicated puzzles where no such sequence is possible, and that is where the NP-completeness comes in, i.e. where you have to try all the ways of uncovering two or more regions. I don't think any version of Factory Balls will be that complicated.

Answer 5

Factory balls can be modeled by a deterministic finite automaton, an object that shows up in the theory of formal languages.

Per wikipedia, a deterministic finite automaton is a $5$-tuple $(Q, \Sigma, \delta, q_0, F)$ where $Q$ is a finite set of states, $\Sigma$ is a finite alphabet of letters, $\delta : Q \times \Sigma \to Q$ is a transition function, $q_0 \in Q$ is a start state, and $F \subset Q$ is a set of accept states.

In factory balls, the family of states is the possible state of the balls, the alphabet is the set of tools/paints that you can apply to the ball, the transition function $\delta$ tells you what happens to the ball when you apply a tool, the start state is the white ball you start with, and the accept state is the ball you're trying to create.

A deterministic finite automaton represents a set of words called a "regular language"- this is a family of words that land you on an accept state after iteratively applying the transition function, starting with the start state, and applying the transition function with each successive letter of the word. The problem of factory balls is then equivalent to finding a word accepted by your DFA.