## Problem: Puzzle (Backtracking)

*Difficulty: Easy

Problem: Given a grid of squares, each square has a character. Player have to find all ways to form a given word by concatenate all adjacent squares. Two squares are considered to be adjacent to each other in three directions: horizontal, vertical and diagonal.

Example:

We have grid

ABCE
SFCS

and a word: ABCCED
we can form that word by concatenate squares at positions : (0,0) , (0, 1), (0, 2), (1, 2), (2, 2), (2, 1)

Here are source code as well as some example:

```def find_s(s, table, x, y, i, steps):
for j in possible_moves:
temp_x, temp_y = x + j[0], y + j[1]
if temp_x >= 0 and temp_x < len(table) and temp_y >= 0 and temp_y < len(table[0]) \
and table[temp_x][temp_y] == s[i]:
x, y = temp_x, temp_y
steps.append([temp_x, temp_y])
if i < len(s)-1:
find_s(s, table, x, y, i+1, steps)
else:
if ''.join(table[row][col] for (row,col) in steps) == s:
for x in [steps.count(_) for _ in steps]:
if x > 1:
return False
else:
print 'FOUND'
print steps
return True
steps.pop()

possible_moves = [(-1, -1), (0, -1), (1,-1), (1, 0), (1,1), (0, 1), (-1, 1), (-1, 0)]

if __name__ == '__main__':
#table = [['A', 'B', 'C', 'E'],
#         ['S', 'F', 'C', 'S'],
#         ['A', 'D', 'E', 'E']]

#table = [['A', 'B', 'C', 'E'],
#         ['S', 'F', 'C', 'S'],
#         ['A', 'D', 'E', 'E']]

#s = 'ABCCED'
#s = 'ABCB'
table = [['A', 'B', 'C', 'D', 'E'],
['A', 'A', 'B', 'F', 'G'],
['A', 'C', 'D', 'E', 'F'],
['G', 'H', 'H', 'I' ,'J']]
#s = 'AAA'
s = 'CD'
for x in range(len(table)):
for y in range(len(table[0])):
if table[x][y] == s[0]:
find_s(s, table, x, y, 1, [[x,y]])
```