I recently read a similar case in Simon Singh's book Fermat's Enigma http://www.amazon.com/reader/0385493622?_encoding=UTF8&query... about the 14-15 puzzle. It was similarly unsolvable and provable the same way.

Interestingly, his account is rather different than that on wikipedia http://en.wikipedia.org/wiki/15_puzzle Singh claims that Sam Lloyd created the puzzle, secretly proved it was impossible, and offered rewards to anyone who could solve it.