Nonograms are a simple but sometimes fiendishly difficult puzzle that my partner and I have become slightly addicted to. She is much better at them than me so in a desperate attempt to even the odds I thought it might help give me the edge to make them myself.
Conceptually a lot of the algorithms for a nonogram are quite simple. It actually makes for a nice little interview question because the key lies in breaking down the problem into smaller easy to reason parts. However, I hit a stumbling block when I realised there was an edge case where a random generation might not have just one unique solution. This was a problem because when it was generated it would store the "correct" answer it had in mind. This meant you could correctly solve the puzzle but not be awarded for the win; Disaster!!
After staring down the rabbit hole of having to potentially wrestle with holistic ways of approaching a "P vs NP", I came to a much more sensible solution.
Instead of solving for the difficult case of guaranteeing a unique solution, I could just change how the game checked whether it was in the "won" state. This problem seems difficult at first, especially when you consider the original implementation just compared the user's proposed solution with a stored one... but it actually turned out simple in a really pleasing way!
Each horizontal and vertical line of the puzzle has a list of numbers that represent the number of consecutive blocks of colour in that line, these are like "clues" to help you solve the puzzle. If you want to check any arbitrary proposed solution you can simply generate what the clues would be if the solution was a puzzle itself and then use those as your comparison.
I think there something really pleasing about this solution, and it's a great reminder that sometimes you need to stop and just take a minute to consider problems from a completely different angle.