Panditah of the Seventh Mountain

Back in the nineties I played a computer game called Jewels of the Oracle. I bought it because the box compared it to Myst which I'm totally into, but Jewels fell short being little more than a bunch of unrelated puzzles joined by the most obnoxious hub world ever designed.

The puzzles were pretty fun at least. There was a Sokoban warehouse puzzle, a solo Mancala variant, a leap frog puzzle with four frogs per side, and a really nice abstract variant of the missionaries and cannibals problem. There were some original puzzles as well, and a cool maze that covered the surface of a cube.

But there's one puzzle, one incredibly obnoxious puzzle, that I remember to this day. It's called Panditah of the Seventh Mountain (everything in the game has this overwrought ancient civilization motif), and it goes like this.

The Puzzle

---

You need to place all twenty tiles into rows and columns that are multiples of seven in order to win.

			A
		B	C	D
	E	F	G	H	I
J	K	L	M	N	O	P
Q	R				S	T

Just to keep things clear, let's give each space in the pyramid a letter. QR and ST are considered separate rows, so there are thirteen rows and columns in total.

Fifteen Years Ago

Some fifteen years ago when I was but a wee Paul, I got stuck on this puzzle and turned to The Internet for help. I stumbled on Balmoral Software's walkthrough, which not only had a solution but also noted, almost as an afterthought:

[T]here are 39,816 distinct solutions.

So not only did the author have a solution, they claimed to have every solution.

This is the problem with puzzles. Often, the answer isn't interesting, and finding a solution for a puzzle just leaves you with more puzzles. Clearly I now needed to find every possible solution to Panditah of the Seventh Mountain.

---

I realized that the pyramid was really just a glorified twenty digit number. You could turn this pyramid arrangement:

			7
		3	9	9
	2	5	6	8	3
1	4	0	6	7	0	1
4	2				8	4

into the number 73,992,568,315,067,014,284. So that meant all I needed to do was write a program that counted from 0 to 99,999,999,999,999,999,999 and see if each number could be converted into a valid solution. It looks sort of like this:

			0
		0	0	0
	0	0	0	0	0
0	0	0	0	0	0	0
0	0				0	0

It was actually really easy to code even though I was pretty new to C at the time. I started running the program and waited a bit. I got bored, did something else for a while, and came back to check on the progress. The program hadn't really gotten very far. I did some math and figured out my mom's blazing fast 233 MHz Power Mac 9600 could check about sixty thousand pyramids every second. At that rate, it would get through every pyramid in about 5.2 million years.

And as much as my mom tried to support my programming, she'd eventually want her computer back.

I tried to make my program faster and managed to shave off a half million years, but there was a fundamental problem with my approach. It wouldn’t matter if I made the program a thousand times faster; I wasn't going to get an answer in my lifetime.

I was twelve and I didn't know what to do next. I gave up and forgot about the puzzle for years.

Last Saturday

I live in constant fear that one day, while taking a shower, the shower head will suddenly pop off and strike me in the back of my neck. It will simultaneously knock me out and slice open a deep bleeding gash. I will fall over and crack my head on the tub and die. I was trying to ignore this last Saturday while taking a shower when suddenly I knew how to solve Panditah of the Seventh Mountain.

The counting method failed in part because it would check so many board positions that were obviously incorrect. Most of the numbers would be invalid because they used too many of one tile type, for example trying to use six 0's when there's only two tiles. What if we instead worked with a different approach, by taking our twenty tiles and putting them down onto the board one by one?

One way to think about how many combinations that need to be checked is to draw an upside down tree picture.

Each row is a spot on the pyramid, and each circle is a tile we could choose to put in that spot. So if we follow the lines in the tree and through a 4 and then a 3, that means we put a 4 in the first spot in the pyramid and a 3 in the second spot.

This tree gets really big really quickly. With just two tiles placed there are already 100 combinations. Instead of drawing the whole thing, let's just label how many circles there are in the last row underneath each part of the tree.

			A
		B	C	D
	E	F	G	H	I
J	K	L	M	N	O	P
Q	R				S	T

But how in the world does this help us? There are still two million billion combinations to check!

Let's say the first row is the tile we're going to place in the A position in the pyramid. It's pretty obvious we can only put a 0 or a 7 there because otherwise we wouldn't have a multiple of 7 across the top row of the pyramid. If we look at our combination tree, we can eliminate any combination in branches with anything but a 0 or 7 in the first position, so our tree now looks like this:

By making a single logical deduction we've already eliminated 80% of the possibilities!

This isn't just a one-off trick either. Next we can look at the positions J and Q. They form a column together that has to be a multiple of seven, so they could be 07, 14, 21, and so on. We can eliminate every combination that doesn't match that.

Computers can't really think quite like this because it would take a ton of memory to build the whole tree. But we get the same effect if we try placing one tile at a time. At each step we check to see if the pyramid could be a valid solution. We keep going as if it might be, otherwise we back up, remove one tile, and try a different one. If we place all 20 tiles, we've found a solution. This approach looks like this:

			A
		B	C	D
	E	F	G	H	I
J	K	L	M	N	O	P
Q	R				S	T

---

But is this really faster than the counting method? It turns out to be insanely faster. Because every deduction we make near the top of the tree eliminates billions of combinations underneath it, we avoid having to check a huge percentage of the possibilities. My laptop needs less than four seconds to find every solution, and home computers from the 90s could have done this in a minute or two without a problem.

Interestingly enough, both the counting approach and tree approach are considered "brute force" algorithms. It just so happens that sometimes brute force can be smart.

So how many solutions did my program find? Actually, it found 208,008 solutions, but the guide claimed there were only 39,816 solutions. Another puzzle?

It appears the author of the guide didn't believe that a row or column could start with a 0, so 07 in the JQ positions wouldn't be accepted. If I add that restriction, my program also finds 39,816 solutions. The game doesn't seem to mind the leading zero, though, so I stand by my claim that there are 208,008 solutions.

The solutions themselves are only mildly interesting, but I feel like I can relax, having finally solved Panditah of the Seventh Mountain.

---

Download

Panditah Source Code