Teaching Kids Programming – Counting the Number of Squares and Rectangles of a NxN Rubik Cube

Teaching Kids Programming: Videos on Data Structures and Algorithms

Each Rubic Cube has 6 sides, and we can just count the number of squares and rectangles for one side and multiply by 6 which gives us the total number of squares and rectangles. We can count for smaller N but with a large N, we can ask the computer to do the counting for us.

The idea is to bruteforce two coordinates the top-left (a, b) and bottom-right (c, d) then we need to compute the two sides (d – b) and (c – a) to determine if it is a square of rectangle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def count(n):
    squares = 0
    rectangles = 0
    for a in range(n):
        for b in range(n):
            for c in range(a + 1, n + 1):
                for d in range(b + 1, n + 1):
                    if c - a == d - b:
                        squares += 1
                    else:
                        rectangles += 1
    return 6*squares, 6*rectangles
 
for i in range(11):
    s, r = count(i)
    print(f"{i}x{i} Rubic Cube has {s} squares and {r} rectangles.")

def count(n):
    squares = 0
    rectangles = 0
    for a in range(n):
        for b in range(n):
            for c in range(a + 1, n + 1):
                for d in range(b + 1, n + 1):
                    if c - a == d - b:
                        squares += 1
                    else:
                        rectangles += 1
    return 6*squares, 6*rectangles

for i in range(11):
    s, r = count(i)
    print(f"{i}x{i} Rubic Cube has {s} squares and {r} rectangles.")

The time complexity is O(N^4) and we have four nested loops. The first coordinate won’t be at the rightmost or bottom-most edge.
 
0x0 Rubic Cube has 0 squares and 0 rectangles.
1×1 Rubic Cube has 6 squares and 0 rectangles.
2×2 Rubic Cube has 30 squares and 24 rectangles.
3×3 Rubic Cube has 84 squares and 132 rectangles.
4×4 Rubic Cube has 180 squares and 420 rectangles.
5×5 Rubic Cube has 330 squares and 1020 rectangles.
6×6 Rubic Cube has 546 squares and 2100 rectangles.
7×7 Rubic Cube has 840 squares and 3864 rectangles.
8×8 Rubic Cube has 1224 squares and 6552 rectangles.
9×9 Rubic Cube has 1710 squares and 10440 rectangles.
10×10 Rubic Cube has 2310 squares and 15840 rectangles.

See also: How Many Squares/Rectangles Does a Rubik Cube Have?

–EOF (The Ultimate Computing & Technology Blog) —