Square-Sum Puzzle

January 16, 2018

I don’t watch a lot of television, but the YouTube channel Numberphile is one of the places I am careful not to miss. Numberphile recently had an episode called “The Square-Sum Puzzle” that makes a good exercise:

Rearrange the numbers from 1 to 15 so that any two adjacent numbers must sum to a square number.

Your task is to write a program to solve the Numberphile square-sum puzzle. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

7 Responses to “Square-Sum Puzzle”

  1. Paul said

    In Python. It is easy to solve this by hand, as there are not many possibilities. A brute force solution should do the trick. There appears only 1 solution.

    numbers = list(range(1, 16))
    squares = set((i ** 2 for i in range(6)))
    successors = {i: set(j for j in numbers if i != j and i + j in squares) for i in numbers}
    # apparently 8 and 9 should be at beginning and end (only 1 possibility)
    def solve():
        Q = [([8], set(numbers)-set([8]))]
        while Q:
            part, remain = Q.pop()
            if not remain:
                print(part)
                continue
            s = successors[part[-1]] & remain
            for i in s:
                Q.append([part + [i], remain - set([i])])
    
    solve()
    # -> [8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]
    
  2. kernelbob said

    @Paul, there are two solutions. The one you listed and its reverse.

    Here’s mine.

    #!/usr/bin/env python3
    
    # https://programmingpraxis.com/2018/01/16/square-sum-puzzle/
    
    N = 15
    A = [None] * N
    squares = {i * i for i in range(N) if i * i < N + N}
    
    def place(pos, prev, unused):
        if unused == 0:
            # All numbers used, solution found
            print(A)
            assert all(a + aa in squares for (a, aa) in zip(A[:-1], A[1:]))
        elif pos == 0:
            # First number
            for i in range(1, N):
                bit = 1 << i
                if unused & bit:
                    A[pos] = i
                    place(pos + 1, i, unused & ~bit)
        else:
            # General case
            for sq in squares:
                dif = sq - prev
                if dif < 0 or dif > N:
                    continue
                bit = 1 << dif
                if unused & bit:
                    A[pos] = dif
                    place(pos + 1, dif, unused & ~bit)
                        
    
    place(0, 0, (1 << N + 1) - 2)
    
  3. Paul said

    @kernelbob: it is indeed more correct to say that there are 2 solutions, but the are essentially the same.

  4. Luke said
    MAX = 15
    
    numCalls = 0
    class Node:
        def __init__(self, value):
            self.value = value
            self.neighbors = []
            
        def addNeighbor(self, neighbor):
            self.neighbors.append(neighbor)
            
        def __add__(self, other):
            return self.value + other.value
            
        def __repr__(self):
            return 'Node(' + str(self.value) + ')'
    
        def findPath(self, used):  
            global numCalls
            numCalls += 1
            for neighbor in self.neighbors:
                if neighbor not in used:          
                    used.add(neighbor)
                    if len(used) == MAX:
                        return [neighbor]
                    else:
                        result = neighbor.findPath(used)
                        if result:
                            result.append(neighbor)
                            return result
                        else:
                            used.remove(neighbor)
            return False
                                    
            
    values = tuple(range(1,MAX+1))
            
    nodes = [Node(i) for i in values]
    
    squares = tuple(i*i for i in values)
    
    # Find all of the paths
    for i in values:
        for j in values[i:]:
            value = i+j
            if value > squares[-1]:
                break
            if value in squares:
                nodes[i-1].addNeighbor(nodes[j-1])
                nodes[j-1].addNeighbor(nodes[i-1])
    
    for node in nodes:
        path = node.findPath(set())
        if path:
            assert all(path[i] + path[i+1] in squares for i in range(MAX-1))
            print([p.value for p in path])
            print()
            print('MAX:', MAX, 'numCalls:', numCalls)
            break
    

    Finding a path to 15 is pretty easy, it only takes 48 tries for my depth-first search. However, the Numberphile2 channel says they searched up to 299. What sort of pathfinding algorithm did they use? 42 my laptop does in a second with 945,000 calls, but even the short jump to 45 takes a long time with over 43,000,000 calls. There must be a smarter way to start winding your way through the paths. Any ideas?

  5. Luke said

    A little more digging shows Charlie used Sage and its hamiltonian_path() function which found a path through 150 nodes in 90 ms. (Bang fist on table) There must be a better way.

  6. Paul said

    In Python using DFS. Function count and takewhile are from the itertools module. This code needs 69 ms for 299 for the first solution. I got an enormous speed up by searching first the nodes that have least amount of successors left (last line of the code).

    def solve(max):
        numbers = set(range(1, max + 1))
        squares = set(takewhile(lambda i: i < 2 * max, (i ** 2 for i in count(1))))
        successors = {i: set(j for j in numbers if i != j and i + j in squares)
                    for i in numbers}
        Q = [([], None, set(numbers))]
        while Q:
            solution, last, remain = Q.pop()
            if not remain:
                print(solution)
                break
            else:
                cand = [(solution + [i], i, remain - set([i]))
                         for i in successors.get(last, numbers) & remain]
                Q += sorted(cand, key=lambda x: len(successors[x[1]] & remain),
                            reverse=True)
    
  7. Rutger said

    Hi Luke,

    There are some options for pruning in your algorithm. On line 53 you have already constructed a full path, but you can check along the way.

    For example, add a check on line 23 that does something like: if we have used an even amount of nodes, check if the last 2 numbers add up to a square.

    if (len(used) % 2) == 0 and self.value + neighbor.value in squares:
        # keep going
    else:
        # stop here, no need to construct the rest of the path
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: