This is simple version of harder [Square Sums](/kata/square-sums).

# Square sums

Write function `square_sums_row` (or `squareSumsRow`/`SquareSumsRow` depending on language rules) that, given integer number `N` (in range `2..43`), returns array of integers `1..N` arranged in a way, so sum of each 2 consecutive numbers is a square.

Solution is valid if and only if following two criterias are met:
1. Each number in range `1..N` is used once and only once.
2. Sum of each 2 consecutive numbers is a perfect square.

### Example
For N=15 solution could look like this:

`[ 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 ]`

### Verification

1. All numbers are used once and only once. When sorted in ascending order array looks like this:

`[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ]`

2. Sum of each 2 consecutive numbers is a perfect square:

```
   16    16     16     16     16     16     16
   /+\   /+\    /+\    /+\    /+\    /+\    /+\
[ 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 ]
      \+/    \+/    \+/    \+/    \+/    \+/    \+/
       9     25      9     25      9     25      9

9 = 3*3
16 = 4*4
25 = 5*5
```

If there is no solution, return `false` (or, `None` in scala). For example if `N=5`, then numbers `1,2,3,4,5` cannot be put into square sums row: `1+3=4`, `4+5=9`, but
`2` has no pairs and cannot link `[1,3]` and `[4,5]`

# Have fun!

Harder version of this Kata is [here](/kata/square-sums).

Difficulty: introductory

Starter code:

def square_sums_row(n):
	

Solutions:
def square_sums_row(n):

    def dfs():
        if not inp: yield res
        for v in tuple(inp):
            if not res or not ((res[-1]+v)**.5 % 1):
                res.append(v)
                inp.discard(v)
                yield from dfs()
                inp.add(res.pop())

    inp, res = set(range(1,n+1)), []
    return next(dfs(), False)

def square_sums_row(n):
    r=[]
    def dfs(r):
        if len(r)==n:return 1
        for i in range(1,n+1):
            if not len(r) or (i not in r and not(i+r[-1])**.5%1):
                r.append(i)
                if dfs(r):return 1
                r.pop()
        return 0
    return r if dfs(r) else 0

# ==========================================================================================================================================
# title         : squares, v2: faster with dictionnary instead of graph
# description   :
# author        : JR
# date          : 28.04.20
# version       :
# IDE           : PyCharm
# ==========================================================================================================================================
import math

# code standard graphs (dirty-duct-copy networkx behavior)
class nx(dict):
    @staticmethod
    def empty_graph(nodes):
        return nx(nodes)

    @staticmethod
    def squares_graph(n=23):
        square_candidates = [(x+1)**2 for x in range(1, math.floor(math.sqrt(2*n-1)))]
        G = nx.empty_graph(list(range(1, n+1)))

        for s in square_candidates:
            true_indexes = [x for x in range(1, 1+math.floor((s-1) / 2)) if s-x <= n]
            for k in true_indexes:
                G.add_edge(k, s-k)

        return G

    @staticmethod
    def Graph(G):
    # here we will implement the by-copy
        return nx(G.copy())

    def __init__(self, nodes, edges=None):
        if edges is None:
            if isinstance(nodes, dict):
                # by-copy => this one should not really be used for our problem, but it is simpler at the beginning to be able to concentrate
                # on the central matter
                dict.__init__(self, {n: e.copy() for n,e in list(nodes.items())})
            else:
                dict.__init__(self, {n: set() for n in nodes})
        else:
            dict.__init__(self, {nodes[i]: edges[i] for i in range(len(nodes))})

    def add_edge(self, x, y):
        self[x] |= {y}
        self[y] |= {x}

    def remove_edge(self, x, y):
        self[x] -= {y}
        self[y] -= {x}

    def remove_node(self, n):
        edges = self[n].copy()
        for e in edges:
            self.remove_edge(n, e)

        del self[n]

    def display(self):
        import matplotlib.pyplot as plt
        import networkx as true_nx
        plt.clf()
        true_nx.draw(true_nx.Graph(G), labels={x: x for x in G.nodes})
        plt.show()

    @property
    def nodes(self):
        return list(self.keys())

    @property
    def degree(self):
        return {(n, len(e)) for n, e in list(self.items())}


def square_sums_row(n):
    return dfs_travel(n)


def dfs_travel(G=23, visit_ordered=None, N=None, display=False, verbose=False):
    if isinstance(G, int):
        G = nx.squares_graph(G)

    if N is None:
        N = len(G.nodes)

    if visit_ordered is None:
        visit_ordered = []

    if len(visit_ordered) == N:
        if verbose:
            print('SUCCESS')
        return visit_ordered

    impossible_nodes = [n for n, d in G.degree if d == 0]
    if len(impossible_nodes) > 0:
        return False
    ending_nodes = [n for n, d in G.degree if d == 1]

    if len(ending_nodes) > 2:
        return False

    if len(visit_ordered) == 0:

        # We do the best guess to visit nodes by random... starting by most certain ones
        if len(ending_nodes) > 0:
            if verbose:
                print('Guess zero')
            return dfs_travel(G, [ending_nodes[-1]], N, verbose=verbose)  # if two, it will arrive at the second node !

        degrees = G.degree
        max_degree = max([y for x, y in degrees])
        for d in range(2, max_degree+1):
            for n in [nd for nd, deg in degrees if deg == d]:
                sol = dfs_travel(G, [n], verbose=verbose)
                if sol != False:  # don't want the unsafe "if sol" with list
                    if verbose:
                        print('YESSS')
                    return sol

        if verbose:
            print('Exhausted guesses')
        return False

    elif len(ending_nodes) == 2 and not visit_ordered[-1] in ending_nodes:
        return False

    G2 = nx.Graph(G)  # copy the graph... will need to improve if >100 graphs are needed !

    last_idx = visit_ordered[-1]
    for current_idx in G2[last_idx]: #.keys():
        if verbose:
            print((last_idx, current_idx))
        visit_ordered.append(current_idx)
        if verbose:
            print(visit_ordered)
        G3 = nx.Graph(G2)
        G3.remove_node(last_idx)
        sol = dfs_travel(G3, visit_ordered, N, verbose=verbose)

        if sol != False:
            return visit_ordered

        visit_ordered.pop()
    if verbose:
        print(visit_ordered)
        print((len(visit_ordered) - N))
    return False


def square_sums_row(n):
    def dfs():
        if not n: yield r
        for p in tuple(n):
            if not r or not ((r[-1]+p)**.5 % 1):
                r.append(p)
                n.discard(p)
                yield from dfs()
                n.add(r.pop())
    n, r = set(range(1,n+1)), []
    return next(dfs(), False)

squares = {x**2 for x in range(10)}

def square_sums_row(n):
    def rec(x, L):
        if not L:
            return x and [x]
        for i,y in enumerate(L):
            if x==0 or x+y in squares:
                test = rec(y, L[:i]+L[i+1:])
                if test:
                    return (x and [x] or []) + test
        return False
    return rec(0, list(range(1, n+1)))

from math import sqrt

class Graph:
    def __init__(self, connections):
        self.n = len(connections)
        self.connections = connections
        self.adjacency_matrix = [[0] * (self.n) for _ in range(self.n)]

        for i, j in enumerate(self.connections):
            for k in j:
                self.adjacency_matrix[i][k - 1] = 1

    def hamilton(self):
        for i in range(self.n):
            visited = [False] * self.n
            path = []

            def _hamilton(curr):
                path.append(curr)
                if len(path) == self.n:
                    return True

                visited[curr] = True
                for next in range(self.n):
                    if self.adjacency_matrix[curr][next] == 1 and not visited[next]:
                        if _hamilton(next):
                            return True
                visited[curr] = False
                path.pop()
                return False

            if _hamilton(i):
                return [n + 1 for n in path]

        return False

def square_sums_row(n):
    connections = []
    temp = []
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if sqrt(i + j).is_integer():
                temp.append(j)
        connections.append([*temp])
        temp.clear()

    g = Graph(connections)
    return g.hamilton()


ans = [0 for i in range(44)]
hash1 = [False for i in range(44)]

def Dfs(num, cnt):

    if(num == cnt):
        return True

    for i in range(1, cnt + 1):
        if not hash1[i] and (not((i + ans[num])**0.5%1)):
            ans[num + 1] = i
            hash1[i] = True
            if Dfs(num + 1, cnt): return True
            hash1[i] = False
    return False


def square_sums_row(n):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            hash1[j] = False
        ans[1] = i
        hash1[i] = True
        if Dfs(1, n):
            return ans[1: n + 1]

    return False

def square_sums_row(n):
    solutions = {
    15: [9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8],
    16: [16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8],
    17: [16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17],
    30: [18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 6, 30, 19, 17, 8, 28, 21, 4, 5, 11, 25, 24, 12, 13, 3, 1, 15],
    31: [31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 6, 30, 19, 17, 8, 28, 21, 4, 5, 11, 25, 24, 12, 13, 3, 1, 15],
    32: [1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15],
    33: [2, 23, 26, 10, 6, 30, 19, 17, 8, 28, 21, 15, 1, 3, 13, 12, 24, 25, 11, 14, 22, 27, 9, 16, 33, 31, 18, 7, 29, 20, 5, 4, 32],
    34: [1, 8, 17, 32, 4, 5, 11, 25, 24, 12, 13, 3, 33, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 6, 19, 30, 34, 15, 21, 28],
    35: [1, 3, 6, 19, 30, 34, 2, 7, 18, 31, 33, 16, 9, 27, 22, 14, 11, 25, 24, 12, 13, 23, 26, 10, 15, 21, 28, 8, 17, 32, 4, 5, 20, 29, 35],
    36: [1, 3, 6, 10, 26, 23, 2, 7, 18, 31, 33, 16, 9, 27, 22, 14, 35, 29, 20, 5, 11, 25, 24, 12, 13, 36, 28, 8, 17, 19, 30, 34, 15, 21, 4, 32],
    37: [1, 3, 13, 36, 28, 8, 17, 32, 4, 21, 15, 34, 30, 19, 6, 10, 26, 23, 2, 7, 18, 31, 33, 16, 9, 27, 22, 14, 35, 29, 20, 5, 11, 25, 24, 12, 37]}
    
    return solutions[n] if n in solutions else False

def square_sums_row(n):
    stack = [ (set(range(1, n+1)), []) ]

    while stack:
        existing_nums, out = stack.pop()
        if len(out) == n:
            return out
        
        for num in existing_nums:
            if not out or not ((num+out[-1])**.5)%1:
                stack.append( (existing_nums-{num}, out+[num]) )

    return False