# Project Euler 90: An unexpected way of using two cubes to make a square.

In the ninetieth problem of Project Euler  we are back in combinatorics with a problem description that reads

Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.

For example, the square number 64 could be formed:

In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.

For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.

However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.

In determining a distinct arrangement we are interested in the digits on each cube, not the order.

{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}

But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.

How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?

This problem can be solved brute forcing all combinations of dices since the solution space is not that big. But before going on solving the problem lets have a look at how many potential solutions we have.

Let us look at how many dice combinations we can have. This is a typical combinatorics problem where we have to choose 6 out of 10 items.  We can calculate that number based on the binomial coefficient

$\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}$

Which in our case is

$\displaystyle \binom{10}{6}=\frac{10!}{6!(10-6)!}=210$

Or for the lazy just type “10 choose 6” in google and the calculator in google will give you the answer.  So we have 210 dice combinations. Since we have two dice that means we have 210*210= 44100 combinations to check. However, half of the combinations is just a solution where dice 1 is switched with dice 2, so they don’t count. That leaves us with 22050 solutions to check.

Since 6 can replace 9 and vice verse, we will need to just choose one of them. However, the sets are still distinct and therefore we need to count them as such.

Furthermore we need dice where the numbers are {0,1,2,3,4,5,6,8}. That means we can’t have two of the same dice, since then we will only have 6 out of 8 distinct numbers. That subtracts another 210 solutions. So now we have limited the search space to (210*209)/2 = 21945 solutions.

## Generating all combinations

In order to brute force this problem we need to generate all combinations of dices . Donald Knuth’s The Art of Computer Programming Vol 4A has a whole section on algorithms for generating combinations depending on what properties you want them to come out with.

I have chosen one where I simply increment the last element as long I can and then going back when I hit the upper limit. That means the elements in the sets come out in a sorted way which is nice.

It is not a very pretty implementation I have made but it works and it will substitute any 9’s with 6’s so the comparison becomes easier

private List> allCombination(int k, int n) {

List> combs = new List>();
List comb = new List();
for (int i = 0; i < k; i++) {
}
while (true) {
//create new array with old solution
comb = new List(comb);
// Substitute 9 with 6 in the last solution
if (combs[combs.Count - 1][k - 1] == 9)
combs[combs.Count - 1][k - 1] = 6;
int i = k - 1;
++comb[i];
while ((i > 0) && (comb[i] >= n - k + 1 + i)) {
--i;
++comb[i];
}

if (comb[0] > n - k)
break;

for (i = i + 1; i < k; ++i)
comb[i] = comb[i - 1] + 1;
}

return combs;
}


## Checking valid combinations

So now we have all combinations, all we need to do is to check if it is a valid combination. The only way I have found to do this is by brute force checking. The code for checking if two dice make a valid combination looks like this

private bool isValidCombinations(List d1, List d2){
int[,] combs = {{ 0, 1 }, {0,4}, {0,6}, {1,6}, {2,5}, {3,6},{4,6}, {6,4}, {8,1} };

bool valid = true;
for (int i = 0; i < combs.GetLength(0); i++) {
if (!((d1.Contains(combs[i, 0]) && d2.Contains(combs[i, 1])) ||
(d2.Contains(combs[i, 0]) && d1.Contains(combs[i, 1])))) {
valid = false;
break;
}
}
return valid;
}


Not very brilliant and not very nice, but it works. The last bit we need is to loop through all possible combinations. The code looks as

List> combs = allCombination(6, 10);
for (int i = 0; i < combs.Count; i++) {
if (combs[i][0] != 0) break;
for (int j = i+1; j < combs.Count; j++) {
if(isValidCombinations(combs[i], combs[j])) result++;
}
}


I have only done one clever thing here. Since we know that the sets are ordered and we need a zero in the combinations, if the first entry of the first dice is not a zero, then we wont have more valid combinations and we can stop the search.

This brute force solution gives us

There are 1217 valid combinations
Solution took 28,0553 ms


## Wrapping up

This was it I guess. It was the best solution that I was capable of finding for this problem. As always you can find the full solution source code for download right here.

I took a while debugging this code because I for some reason decided that 7*7= 47, something which it is not! After I removed that bug the code gave the right solution

The blog image of dices is taken by Doug Wheller who shared it under the creative commons license.

One thing I thought I would mention when talking about dices is that James Grime has a set of 5 non-transitive dices and a whole lot more on non-transitive dices in general. A fun thing to take a look at.

### Posted by Kristian

Titus

I don’t know what is wrong with my answer. It is 6806. My method is like this. Please tell me where is the wrong.. I chose 1st set as ‘a’ and second as ‘b’. Then I took [0,8] and [4,1] as a and b since those should be on different cubes.. Then I create permutation like this..
a=[0,8,9 or 6,5 or 2,any number or 3,any number]
b=[4,1,9 or 6, 2 or 5,3 or any number, any number]
For 4th number, if a=2,then b=5 or if a=5,then b=2.. For 5th number, if a!=3, then b=3. If a=3 then b can be any.. Likewise. Then I got all permutation 15200.. Then I checked those things.. I got about 8000 correct answers. For remove similar ones, I sorted a and b, then join it, add to a list while checking. Then I ended up with 6806.. What was wrong there? Could u explain it for me..

Kristian

It sounds to me like you are counting something which is not squares, or you count something where some of the combinations aren’t square, but I don’t know exactly.

Maybe use my code to generate all correct solutions and then use yours to generate solutions until you find a wrong one and analyse what is wrong with that solution.

Titus

problem is i can’t run C codes..ok, I will try again. May be the wrong is in checking part..thank u very much for ur reply.

Titus

no, i think u didn’t understand my method correctly.. I generate all permutations such that it can make all square numbers.. All the permutations are correct.. If it isn’t true, please point out that for me..

Titus

hm… this is my method…
we should make 01,04,09,16,25,36,49,64 and 81… it is sure enough that one set must have 0 and 8 while other set have 1 and 4 . we can’t make 01,04 and 81 without this combination. so we have now set1=[0,8] , set2=[1,4] . from this combination we can create 01,04 and 81..
for the 3rd element in set one it should be 9 (or 6 since it can be turn them upside down).. so now we can create 64,49 and 16.. to make 09, set 2 also should have 6 or 9.. with all combinations of set1=[0,8,6 or 9] set2=[1,4,6 or 9] we can make 01,04,09,16,49,64 and 81…
next, to create 25 we should have 2 and 5 in set1 and set 2.. if 2 in set1 then 5 should be in set2, if 5 in set1 then 2 should be in set2..
now we have a set with 4 elements like this.. set1=[0,8,6 or 9,5 or 2] set2=[1,4,6 or 9,2 or 5].. now from this 2 set we can make all the numbers except 36.. we can add 3 as 5th element in any set since both sets have 6 inside now.. if we add 3 to set1, then 5th element in set 2 is free because now 2 set can make any number.. so 5th element of set2 will be unusable.. so it can be any number.. if 5th element of set2 is 3, then 5th element of set 1 is also unusable..
since with 5 element we can create any number, 6th element of each set can be any because we don’t need it.. this is my method.. i generate permutations like this. what is wrong with this.. for example, if i have [0,8,6,2,3] and [1,4,6,5,1] i can create all square numbers.. 01,04,09(using 6 upside down),16,25,36,49(using 6 upside down),64,81.. then what is wrong here.. i can’t understand. they allow to take 6 as 9.. so…:(

Kristian

Do you still have too many, or do you have too few combinations now. If you still have too many, I would urge you to go through the combinations until you find one which is indeed not correct.

Titus

yes.. i did it as u said.. using combinations it can be solved. problem of my method is there may not be different numbers in a cube.. i didn’t see that before.. although [0,8,6,2,3,6][1,4,6,5,1,0] can make all square numbers, it isn’t accepted here because same number can’t be reapeated in a cube.. that’s why i had lot before.. thank u for ur help.. i advanced to 4th level yesterday. this was my 99th problem.. u helped me a lot throughout my journey in projecteuler..thanx again 🙂

Kristian

Ah so that was the problem. I should have thought of that, but glad you solved it and congratulations on reaching level 4.

Jean-Marie Hachey

Table 1
Application and non-application of the 6/9 reversal and its effects on the number of distinct valid combinations generated.

http://img11.hostingpics.net/pics/233708pe90tab1cubedig.jpg

All the results in Table 1 were obtained using adaptations of Kristian’s algorithm (1).

A drastic decrease in the number of valid combinations is observed if the 6/9 reversal is not applied.
___

Sources:
1) Project Euler, problem 90
http://www.mathblog.dk/files/euler/Problem90.cs
2) Microsoft Visual C# 2010 Express
3) Microsoft Office Excel (2007)

Carl J Appellof

I used a different way of representing dice and generating all possible “10 choose 6” values.
Consider a 10-bit binary number with low order bit numbered 0 up to a high order bit of 9. Sounds like dice face numbers, doesn’t it? Now run a loop from 1 – 1023 and pick out the numbers that have only 6 bits set. (The old HAKMEM memo has a neat way of counting bits in a number.) This set of binary numbers has 210 members (10 choose 6).

Now pick dice in pairs (avoiding duplicates by running 2 loops like this:

for (i = 0; i < 210; ++i)
{
for (j = i; j < 210; ++j)
{
}
}

I used the following function to test of two dice (binary numbers d1 and d2) could be used to make up all squares from 1 to 81. I am a Jimi Hendrix fan, so the function “IfSixWasNine()” adds a “9” bit if the die contains a 6 and adds a “6” bit if the die contains a 9, before testing if we can make up all squares with this pair of dice.
The numbers on the dice can appear in either order, so we need to do 2 tests to see of a square is possible.

bool AllSquares(int d1, int d2)
{
int i;
int c1, c2;

d1 = IfSixWasNine(d1); d2 = IfSixWasNine(d2); for (i = 0; i < _countof(SquareBits); ++i) { c1 = (d1 & SquareBits[i].first) | (d2 & SquareBits[i].second); c2 = (d2 & SquareBits[i].first) | (d1 & SquareBits[i].second);

 

 if ((c1 != Squares[i]) && (c2 != Squares[i])) { return false; } } return true; 

}

The resulting loop gives the correct answer of 1217, and took only about 0.4 ms to run. A big improvement over Kristian’s method, I think.