Posted after a four hour ISP outage, so somewhat redundant:
The best thing you could do is to NOT change your URLs. Any benefit from text-in-URL is going to be small, and by redirecting this many URLs, you may be setting yourself up for an extended period of reduced ranking because of search engines' loss of "trust" in the stability of your site; It can take some time (weeks to months) for search engines to completely re-index your site and update their link-graphs, returning your pages' rankings to where they were before (or at least close).
Second best would be to put a rule in /cheats/.htaccess (or in a <Directory /cheats> container in httpd.conf or other config file) to internally rewrite all requested URL-paths of the form /<somedir>/<number>.htm to a small script that can look up the "text URL" in a database using the <number> in the requested URL-path, and then generate a 301-Moved Permanently redirect to the proper new URL.
Example rule in /cheats/.htaccess:
RewriteRule ^([^/]+/[0-9]+\.htm)$ /path-to-your-cgi-dir/url-lookup-script.pl?old-path=$1 [L]
BTW, I recommend that you use "example.com/cheats/somedir/sometext" as the new URL. There is no reason to add ".htm" to the end of that URL. Also, very carefully pick the words for "somedir" and "sometext" and use a very restricted character-set to avoid URL-encoding so that you will
never have to change these URLs again.
Never. [w3.org]
Jim