Old time puzzles were die cut out of extra heavy weight cardstock, which you can source that from your local Hobby Lobby or Michaels.
I have done some puzzles from this material and once you dial in the settings you can kiss cut with barely any edge singe. I recommend @evansd2