Solved using optimised backtracking algorithm. But sometimes it fails with 'Invalid grid should raise exception' at random tests. I check for multiple solutions. Fixed test with multiple solution passed. What can be wrong with grid that I don't check?
P.S. I've managed to submit solutions since it passes sometimes :)