For my blog article "Fewest moves vs God's number" http://www.terabo.net/blog/fmc-vs-gods-number/

count_tree_nodes_3.py

#!/usr/bin/env python

"""
This scripts counts number of nodes
in 3x3x3 search tree (3)
http://www.terabo.net/blog/fmc-vs-gods-number/
"""

ALL_POS = 43252003274489856000
print 'All possible positions: {0:,d}'.format(ALL_POS)
print '----'

MAX_N = 20
nums = [1 for _ in range(0, MAX_N + 1)]
numsl = [{'U': 3, 'F': 3, 'R': 3, 'D': 3, 'B': 3, 'L': 3} for _ in range(0, MAX_N + 1)]

# Calculation part
nums[1] = nums[0] + 18
for i in range(2, MAX_N + 1):
    primary = numsl[i-1]['U'] + numsl[i-1]['F'] + numsl[i-1]['R']
    numsl[i]['U'] = (numsl[i-1]['F'] + numsl[i-1]['R'] + numsl[i-1]['B'] + numsl[i-1]['L']) * 3
    numsl[i]['F'] = (numsl[i-1]['U'] + numsl[i-1]['R'] + numsl[i-1]['D'] + numsl[i-1]['L']) * 3
    numsl[i]['R'] = (numsl[i-1]['U'] + numsl[i-1]['F'] + numsl[i-1]['D'] + numsl[i-1]['B']) * 3
    numsl[i]['D'] = (primary + numsl[i-1]['B'] + numsl[i-1]['L']) * 3
    numsl[i]['B'] = (primary + numsl[i-1]['D'] + numsl[i-1]['L']) * 3
    numsl[i]['L'] = (primary + numsl[i-1]['D'] + numsl[i-1]['B']) * 3

    nums[i] = nums[i-1]
    for n in numsl[i].values():
        nums[i] += n

# Printing part
for i in range(1, MAX_N + 1):
    print "{0:2d}: {1:,d} (+{2:,d})".format(i, nums[i], nums[i] - nums[i-1])