Yep. That's exactly it. Completely and in a nutshell.
Link to new URLs from the pages of your site. Rewrite those requests to old horrible format now used only inside the server. Redirect external requests for horrible URLs to nice new pretty ones.
That short bit of (PHP) code I gave above, generates the text part of the URL for each page based on the name field in the database for that particular page id number.
The full URL of the page looks like this:
example.com/p<number>-<name>
for products
example.com/r<number>-<name>
for product reviews
example.com/s<number>-<name>
for product spec sheets, and so on.
The PHP (in my case, other systems are available :) ) script that generates the HTML content page first checks that the exact right name has been requested for the current page number and redirects to the correct URL if not.
This automated closed-loop system ensures that visitors and bots cannot stray. It also allows the page name to be changed at a later date and all old links to that page automatically be redirected without any additional work.
You have the page number on the end of the URL. For more efficient RegEx patterns I prefer it at the beginning, as above.
Oh. And if the page numbers are truly unique site-wide, you don't need to specify /category/ in the URL. The benefits of that decision will become utterly apparent should you ever implement any form of multi-faceted navigation system.
If you do wish to retain /category/ in the URL, you should get the script to check it and redirect if it is not the right category requested for this page. That is a big source of duplicate content problems.
example.com/widgets/p543-acme-purple-widget
example.com/gadgets/p543-acme-purple-widget
example.com/doodads/p543-acme-purple-widget
example.com/sale-items/p543-acme-purple-widget
You don't want to be able to request a page as if it were in another category and have content directly returned. The request should either redirect to the correct URL or should directly fail as 404.