Black & White’s Tree Puzzles
The game Black & White offers two non-silver scroll tree puzzles: one on land 2, and a harder one on land 3. In each puzzle, nine trees are arranged in a 3×3 grid. Uprooting a tree causes that tree and the trees directly adjacent to it (no diagonals) to be replaced by trees of a different species. The goal is to make all the trees the same species. Land 2’s puzzle has two species of trees, while land 3’s puzzle has three.
This page gives solutions to both puzzles, as well as demonstrating two different ways to solve similar puzzles.
Land 2’s Tree Puzzle
This tree puzzle is the simpler of the two. Not only does it have just two species of trees, the starting configuration of the puzzle is symmetric. This greatly simplifies analysis of the puzzle.
Starting configuration of land 2’s tree puzzle
Facing the temple, with the nearby Indian village on your right, the puzzle starts like this:
c p c p = pine c c c c = cedar c c c
Following in the footsteps of the analysis of land 4’s Japanese totem puzzle, we can model this as a set of nine simultaneous equations, with variable A corresponding to the state of the upper left corner, B the upper middle, C the upper right, D the middle right, etc:
A B C D E F G H I
In the equations to follow, we let 0 indicate cedar, and 1 indicate pine. The equations are mod 2, since uprooting any tree twice is equivalent to not changing the puzzle at all.
To make all the trees pine, we must solve:
A + B + D = 1 mod 2
A + B + C + E = 0 mod 2 (0 because this tree is already pine)
B + C + F = 1 mod 2
A + D + E + G = 1 mod 2
B + D + E + F + H = 1 mod 2
C + E + F + I = 1 mod 2
D + G + H = 1 mod 2
E + G + H + I = 1 mod 2
F + H + I = 1 mod 2
Nine equations in nine unknowns looks daunting, but the fact that the puzzle’s starting configuration is symmetric about the center column gives us a big shortcut. To keep the symmetry (and we want to, because the goal is symmetric) we must make paired moves: if we uproot tree A, then we must also uproot tree C, and so on for D & F and G & I. The equations A = C, D = F, and G = I simplify the equations:
A + B + D = 1 mod 2
A + B + A + E = 0 mod 2
B + A + D = 1 mod 2
A + D + E + G = 1 mod 2
B + D + E + D + H = 1 mod 2
A + E + D + G = 1 mod 2
D + G + H = 1 mod 2
E + G + H + G = 1 mod 2
D + H + G = 1 mod 2
Since the equations are mod 2, pairs of repeated terms in an equation can be removed. Doing so, and removing now-duplicate equations, leaves this:
A + B + D = 1 mod 2 (i)
B + E = 0 mod 2 (ii)
A + D + E + G = 1 mod 2 (iii)
B + E + H = 1 mod 2 (iv)
D + G + H = 1 mod 2 (v)
E + H = 1 mod 2 (vi)
These are quickly solved. To start, subtracting (vi) from (iv) gives B = 0. Plugging that into (ii) gives E = 0. Plugging both these results into (iv) gives H = 1, and we’re halfway to a solution already.
Subtracting (i) from (iii) gives G = 0. Since H = 1, by (v) D = 0. With B = D = 0, by (i) A = 1, and we have a solution:
1 0 1 0 0 0 0 1 0
So, to solve the puzzle, uproot the trees to the left and right of the starting pine, and also uproot the tree in the center of the row closest to you.
Note that I said a solution, not the solution. There’s an all-cedar solution too, which you can find either through equations or through the technique described in the next section:
0 0 0 0 1 0 1 1 1
Your reward for solving the puzzle is a Winged Creatures miracle dispenser. It’s slow to charge, but the miracle is a big help in converting villages.
Land 3’s Tree Puzzle
This puzzle appears in land 3 after you’ve converted the Indian village. It appears almost equidistant between the Japanese village, your starting Celtic village, and the shaolin’s mountain, on a little bluff just above the unkillable guy’s fire. It’s a harder challenge than the tree puzzle on land 2, for two reasons: there are three species of trees instead of two, and the starting configuration isn’t symmetric. However, we can still solve it without trial and error.
Starting configuration of land 3’s tree puzzle
Facing the shaolin’s mountain, here’s the puzzle’s starting configuration (p = pine, c = cedar, b = birch):
p c b p b p c b c
Uprooted trees are replaced in the order pine → cedar → birch → pine. This makes the puzzle mod 3.
Like the previous puzzle, we can set up nine linear equations that represent the puzzle’s state, but without symmetry to rely on, there’s not much we can do to simplify them. They’re solvable, but not without tedious algebra. We need a different solution.
Start by using numbers instead of letters to identify the trees: pine = 0, cedar = 1, birch = 2. With this notation, uprooting a tree is equivalent to adding one to the tree (mod 3).
0 1 2 0 2 0 1 2 1
What we need is a way to affect only one tree at a time—that is, to add just one to a particular tree. Given that, we could solve the puzzle tree by tree.
Let’s start by considering the corner trees. A little experimentation in a spreadsheet revealed that uprooting trees the number of times indicated below adds one to the top right corner:
uproot change ------ ------ 2 1 2 0 0 +1 0 1 1 → 0 0 0 0 0 2 0 0 0
For corners other than the upper right, just rotate the “uproot” matrix accordingly. To add two to a position, swap the 1s and 2s in the uproot matrix (which is equivalent to uprooting each tree twice as many times).
Another minute of experimentation yielded an uproot matrix that adds one to the middle of a side:
uproot change ------ ------ 1 1 1 0 +1 0 1 1 1 → 0 0 0 0 2 0 0 0 0
Thanks to the puzzle’s symmetry, we’ve taken care of all cases except the center position. An uproot matrix for it too was quickly found:
uproot change ------ ------ 1 1 1 0 0 0 1 0 1 → 0 +1 0 1 1 1 0 0 0
To make all the trees pines (0), we need to add this much to the starting configuration (because addition is mod 3):
puzzle amount start to add result ====== ------ ====== 0 1 2 0 2 1 0 0 0 0 2 0 + 0 1 0 = 0 0 0 1 2 1 2 1 2 0 0 0
We break the “amount to add” matrix into a set of matrices, each of which has only one non-zero element. We know how to solve those. All we have to do is add the appropriate matrices (mod 3) to get our solution:
amount top top bottom bottom bottom
to add center right center left center right
====== ------ ----- ------ ------ ------ ------
0 2 1 0 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 = 0 0 0 + 0 0 0 + 0 1 0 + 0 0 0 + 0 0 0 + 0 0 0
2 1 2 0 0 0 0 0 0 0 0 0 2 0 0 0 1 0 0 0 2
solution
↓ ↓ ↓ ↓ ↓ ↓ (pine)
========
2 2 2 2 1 2 1 1 1 1 0 0 0 2 0 0 0 1 6 6 6 0 0 0
uproot: 2 2 2 + 0 1 1 + 1 0 1 + 2 2 0 + 1 1 1 + 0 2 2 = 6 8 7 mod 3 = 0 2 1
0 1 0 0 0 2 1 1 1 1 2 1 1 1 1 1 2 1 4 7 6 1 1 0
So to make all the trees into pines, uproot the middle tree twice, the right center once, the bottom left once, and the bottom center once.
We can also solve the puzzle by making all the trees cedars, or all the trees birches. Here are all uproot matrices.
pine cedar birch ==== ===== ===== 0 0 0 0 2 0 0 1 0 0 2 1 2 1 0 1 0 2 1 1 0 1 0 0 1 2 0
As for the solution, the power of this technique is that you can use it to solve the puzzle no matter what its current state is. As long as you can add numbers with modulus artithmetic, you can solve the puzzles. (It’s also easily automatable.)
The reward for solving the puzzle is a Winged Creatures miracle offered by the Indian village. This is superior to land 2’s miracle dispenser, as the time between chargings is now under your control.
My Tree Puzzle Doesn’t Look Like This! Why?
Lethys has a nasty habit of stealing trees from your territory. If he steals one from a tree puzzle, it will throw off its configuration.
But what do I do about it?
There’s nothing you can do except (a) set up and work out a new set of equations, or (b) try to make the puzzle symmetric and then keep it that way. First make the outer columns the same. While you’re doing this, don’t worry about the center column. Once the outer columns are the same, either pull up trees in the center column, or pull up the outermost trees of a row.
Last updated 3 November 2006
http://www.rdrop.com/~half/General/GameTips/bw.tree.puzzles.html
All contents ©2006 Mark L. Irons