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".
Obviously the non-existence of a solution might itself be unprovable, so you'd still have to set some time limit. Oh Gödel, always there to ruin our plans.