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).

Source: codewars | Difficulty: EASY
Tags: Mathematics

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) ** 0.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]) ** 0.5 % 1)):
				r.append(i)
				if dfs(r):
					return 1
				r.pop()
		return 0
	return r if dfs(r) else 0


import math

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):
		return nx(G.copy())

	def __init__(self, nodes, edges=None):
		if edges is None:
			if isinstance(nodes, dict):
				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:
		if len(ending_nodes) > 0:
			if verbose:
				print('Guess zero')
			return dfs_travel(G, [ending_nodes[-1]], N, verbose=verbose)
		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:
					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)
	last_idx = visit_ordered[-1]
	for current_idx in G2[last_idx]:
		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) ** 0.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]) ** 0.5 % 1:
				stack.append((existing_nums - {num}, out + [num]))
	return False