New Scientist Enigma 1780 and Python

Sometimes a body has to take a break from all this Software Engineering stuff and instead delve into some recretional programming, so with this in mind I decide to see if I could write a small python program to solve the New Scientist Enigma #1780. This enigma is kind of like suduku on an icosahedron of all things (a 20 faced thing).

Anyway it was just for fun and I wasn’t looking for the ‘best’ or most ‘elegant’ solution to the problem, just one that kinda worked! So I wrote a little program over Christmas which I got working (more or less).

I enjoyed the challenge decided to try my hand at future enigmas – only to find out that Enigma #1780 was the last one ever, the New Scientist is giving them up – which is a great pity seeing as I have only started to get interested in them.

Today I came across this site which has python solutions for tonnes of Enigmas including 1780, it was on this site that I learned that 1780 is the last enigma. They point out that there is a large archive of enigmas.

In an attempt to codify the puzzle, I decided think about the flattened out icosahedron (its net) as a grid of 4 rows of 5 triangles, in this way an individual triangle can be referenced using a pair of numbers (i, j), where i varies between 0 and 4 and specifies the triangle’s ‘column’ while j specifies its row. Next I tried to come up with some rules that would find the coordinates of all of the triangles ‘connected’ to the triangle at (i, j).

Once all of that is done solving the puzzle given a valid input net is a matter of finding an empty triangle, finding the set of numbers that can go into that triangle, picking one of these numbers and recursively solving the puzzle for the update net, if the recursive solve fails for that number we try the next number and so on….

Anyway, the solve() function is called like this:

solve(start_net, 0)

#
# Try to solve New Scientist Enigma 1780 (the last one!)
#
# Run like:
#
# solve(start_net, 0)
#
all_values = {1, 2, 3, 4, 5}
net_width = 5
net_height = 4;
# get the value at (i, j)
def value_at(net, a):
    i, j = a
    return net[i + j * net_width]
# set the value at (i, j)
def set_value_at(net, a, val):
    i, j = a
    net[i + j * net_width] = val

# Create list to hold net values, initialised with zeros
start_net = [0] * (net_height * net_width)
# insert the starting values
set_value_at(start_net, (0,0), 2)
set_value_at(start_net, (0,1), 5)
set_value_at(start_net, (0,3), 1)
set_value_at(start_net, (4,0), 4)
#set_value_at(start_net, (4,2), 3)
set_value_at(start_net, (4,3), 2)

# loop i around if i > net_width (modulo)    
def mi(i):
    return i % net_width
# The connection rules for each row
i_0 = [lambda i: (mi(i+1), 0), lambda i: (mi(i+2), 0), lambda i: (mi(i+3), 0), lambda i: (mi(i+4), 0), lambda i: (mi(i-1), 1),
       lambda i: (mi(i-1), 2), lambda i: (mi(i), 1), lambda i: (mi(i+1), 2), lambda i: (mi(i+1), 1)]
i_3 = [lambda i: (mi(i+1), 3), lambda i: (mi(i+2), 3), lambda i: (mi(i+3), 3), lambda i: (mi(i+4), 3), lambda i: (mi(i-1), 2),
       lambda i: (mi(i), 1), lambda i: (mi(i), 2), lambda i: (mi(i+1), 1), lambda i: (mi(i+1), 2)]
i_1 = [lambda i: (mi(i-1), 0), lambda i: (mi(i-1), 1), lambda i: (mi(i-1), 2), lambda i: (mi(i-1), 3), lambda i: (mi(i), 0),
       lambda i: (mi(i), 2), lambda i: (mi(i), 3), lambda i: (mi(i+1), 0), lambda i: (mi(i+1), 1)]
i_2 = [lambda i: (mi(i), 0), lambda i: (mi(i), 1), lambda i: (mi(i), 3), lambda i: (mi(i-1), 2), lambda i: (mi(i-1), 3),
       lambda i: (mi(i+1), 0), lambda i: (mi(i+1), 1), lambda i: (mi(i+1), 2), lambda i: (mi(i+1), 3)]
cons = [i_0, i_1, i_2, i_3]
# is a connected to b?
def connected(a,b):
    (i, j) = a
    
    if a == b:
        return True;
    return b in [d(i) for d in cons[j]]
# gets a list of all triangle coordinates
def all_triangles():
    return [(i % net_width, i // net_width) for i in range(0,net_height*net_width) ]
# gets a list of all triangles connectd to a    
def connected_triangles(a):
    return [b for b in all_triangles() if connected(a,b)]
def find_loc_of_first_empty_triangle(net):
    try:
        index = net.index(0)
        return (index % net_width, index // net_width)
    except:
        return None 
# returns a list of all empty triangles
def all_empty_triangles(net):
    return [a for a in all_triangles() if value_at(net, a) == 0]
# returns the possible values (1..5) that can go into
# the triangle a
def possible_values(net, a):
    ct = connected_triangles(a)
    used_values = {value_at(net, t) for t in ct}
    return all_values - used_values - {value_at(net, a)}
    
# solve given a valid input net    
def solve(net, depth):
    print ('solve, depth: ' + str(depth))
    a = find_loc_of_first_empty_triangle(net)
    
    # if there are no free locations then the
    # net if full and we have finished
    if not a:
        print ('net is full ' + str(net))
        return net
    
    # get list of possible values for this triangle
    possible = possible_values(net, a)
    
    # If we can't make a move then we need
    # to backtrack
    if not possible:
        print ('No more possible moves for ' + str(a))
        return []
    
    for v in possible:
        
        # create a copy of our current net
        new_net = list(net)
        
        set_value_at(new_net, a, v)
        result_net = solve(new_net, depth+1) 
        if result_net:
            return result_net
    return []
if __name__ == "__main__":
    res = solve(start_net, 0)
#    

Update, 07/02/2014
The answer to this Enigma as announced here is: 324125, thankfully the same as that announced by the Python program! Unfortunately I didn’t win the competition, but I had loads of fun trying to write some software to solve it! I might try a Haskell version next if I find the time…