Obviously if no solution exists then that fact is also provable, since this is a finite problem. The problem is not that it might not be provable. The problem is that verifying a non-existence proof could be hard, because such a proof would probably be something like "I ran my solver for three weeks and it said that there are no solutions".