Does anyone know how to solve WORDGRID ?

general
, ,
1

Hi guys,

Can anyone help me think in the right direction to solve Word Grid. This years ICPC qualifiers third question
WORDGRID

I thought of solving it by using the method of BACKTRACKING like one would solve N Queens problem, but I was stuck as to how I would Tell whether a permutation was safe or not and if not to which position would I revert back to.

If it can be solved by any other method, Iā€™d love to know that too!

Any help is appreciated. Thanks :slight_smile:

2

When you take a word(all words are of length 4), there are 16 possibilities for the word to fit inside the 4x4 grid ( 4 rows, 4 columns and reverse). Now do recursion and check all the possible cases of grids(n,t are small enough).

Explanation for the recursion, first put the 1st word in row 1. then take the second word check if it is compatible in row 1, if not then try row 2 and so on. By doing this you reach all the possible cases and you can just make another arr[4][4] and store grid[4][4] if its lexographically lesser.

Hope this helped. Cheers!

1 Like