Last week I come across a code challenge at Hackerrank
Crossword Puzzle | HackerRank
A Crossword grid is provided to you, along with a set of words (or names of places) which need to be filled into the…
This is a problem about putting the keywords at the available zones on a crossword puzzle for both horizontal and vertical directions.
This was fun to solve it. Let me try to explain step by step with the function names on code;
- First of all, we need a function to find all the available zones. This is a little bit tricky because of the vertical direction. findSpaces()
- We need a function to determine if the zone is fitting with the keyword. isValidSpace()
- We‘ll do backtracking. So we need forward() and backward() functions. forward() will put the keyword on the corresponding place before recursion, backward() will undo it after recursion.
- Lastly, we need a recursive function named solve(). This is the wedding part. It will find the possible spaces by length and try to put the words on zones recursively one by one. If it fails it’ll do a rollback. Usual backtracking.