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
ADEE

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]])
Advertisements