Picross - How Many Possibilities?

One of my favorite games back in the old days was Mario Picross. It introduced me to the Japanese Nonograms. A puzzle that requires you with the help of a few numbers as hints to fill out squares. In the end, the result will resemble a picture of something.

Here's an example of what it would look like:

				1	1
				1	1	1
			5	1	1	1	0
		4
		1
		3
		1
		4

And solved it looks like this:

				1	1
				1	1	1
			5	1	1	1	0
		4
		1
		3
		1
		4

As you can see this one is five times five in their size. In Mario Picross, there were three different sizes in Mario Picross: five times five, ten times ten and 15x15. Though you could technically make them any size.

The game features 256 puzzles in total but that's not all you can make. You can probably make a lot more puzzles. So...

Let's-A-Go!

Let's start with the smallest size. We have five times five, which results in 5 * 5 = 25 squares. Each square can be either filled or empty. So our first one would be to leave all empty. Our second bunch would be filling one square. We have 25 squares that could technically be filled so 25 possibilities here. Next up is filling the 25 squares with two. There are 2 out of 25 possibilities or C(25, 2) = 300 to fill it up. Our next case is filling the 25 squares with 3. This time it's 3 out of 25 possibilities or C(25, 3) = 2300. Now without going through each calculation you already notice something? The only difference is that we increase the X out of 25 or C(25, X). So we can just do this:

C(25, 0) + C(25, 1) + C(25, 2) + C(25, 3) + C(25, 4) + C(25, 5) + C(25, 6) + C(25, 7) + C(25, 8) + C(25, 9) + C(25, 10) + C(25, 11) + C(25, 12) + C(25, 13) + C(25, 14) + C(25, 15) + C(25, 16) + C(25, 17) + C(25, 18) + C(25, 19) + C(25, 20) + C(25, 21) + C(25, 22) + C(25, 23) + C(25, 24) + C(25, 25) = 33554432

or alternatively we can write it like this: 

25

Σ C(25, i) = 33554432

i = 0

However, having none of the squares filled is not a valid option. So we have to subtract one, which means 33554432 - 1 = 333554431 levels could be possible. That's.. extremely many. Unfortunately, many of these don't make much sense. Anyways that's how much we have for the size of five times five.

What About 10 Times 10?

We're definitely not going to iterate through 100. So let's see if we can find a different way to calculate it. Let's look at how they behave if the first number changes.

5

Σ C(5, i) = C(5, 0) + C(5, 1) + C(5, 2) + C(5, 3) + C(5, 4) + C(5, 5) = 32

i = 0

6

Σ C(6, i) = C(6, 0) + C(6, 1) + C(6, 2) + C(6, 3) + C(6, 4) + C(6, 5) + C(6, 6) = 64
i = 0

That's interesting it doubled. It could be a coincidence though. Let's go through the list. 7 would be 128, 8 would be 256, 9 would be 512, 10 would be 1024. Let's try it with ten:

10

Σ C(10, i) = 1024
i = 0

Okay. 1024 that's 2^10 and 2^5 is 32. So the previous number we've calculated for a five times five field should be 2^25. Let's see: 2^25 = 33554432 and that's exactly the number we had before.

Makes sense. We have a chance for a field to be either filled or not filled. That means we have two states for each field. You can show these fields like a binary number. Using the example of a Picross or Nonogram I gave it would be 11110 10000 11100 10000 11110.

That's funny, this is basically how QR-codes work.

Calculating the Rest

Well since we know this now we can easily calculate the rest.

So for a ten times ten field we have: 2^(10 * 10) = 2^100 = 1.2676506 * 10^30 that's about one Nonillion (US) or one Quintillion. Though don't forget to subtract one, since an empty field would be an instant win.

And for 15 times 15 we get even more: 2^(15 * 15) = 2^225 = 5,391989333 * 10^67 that's over 53919 Vigintillion (US) or 53 Undecillion. Again don't forget to subtract one.

Those numbers...

The Best Part Last

There are Nonograms and Picross games or puzzles that even use colors. So each color adds a new set of possibilities, but it's easy to calculate that with what we know. We calculate two to the power of n, where n equals the number of squares we have. The two resembles the number of states a square can have. So far we only had filled or not filled. With different colors, we could say it could be either red, green, blue or black. So that's four states plus none of those. Five states total. So we would calculate five to the power of n, where n equals the number of squares we have. Our example with a 5x5 field would be:

5^(5 * 5) = 5^25 = 2.980232239*10^17 

That's 298 Quadrillion (US) or 298 Billiard instead of the previous 333554432 possibilities.