## 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

## Problem: Word Boggle | loctv 8:54 am

onFebruary 13, 2017 Permalink |[…] This problem is almost the same with this. The mechanism gonna be used here is back tracking. There are only two main parts in the […]