Good question! Some puzzles were designed with known solutions, surrounded by random tiles, while others (mainly the maps I worked on!) are entirely random tiles, with generous replacement reserves so we don't soft-lock anyone. For the latter set, then, whether or not they can be completed without replacements changes with every playthrough. With more time, a known replacement-free solution for every puzzle would be one of my design goals.