If a problem is NP-Hard, it does not mean it cannot be solved. Rather, it means it cannot be solved efficiently (in polynomial time). Most NPH problems, now including Mario and 3SAT, can be solved given the time and compute resources to do so.
Well, to be exact, it's an open question whether they can be solved efficiently or not. The general assumption is that they can't, but it hasn't been proven yet.