changed trie to dict. 4x4 solution is solved in ~95 seconds