Data Science Stack Exchange is a question and answer site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field. It only takes a minute to sign up.
This 2019 paper states that all the current image classification models are actually doing the same thing, i.e. classifying jumbled image patches. The reason is that they are weak at peaking up long-range dependencies (relations between pixels far away). As a result, breaking these dependencies by shuffling the image patches does not affect them substantially. Here is a post that explains the findings and the BagNet method that suits your need.
CNNs are indeed state-of-the-art in computer vision for image recognition, categorization, and classification. Simply taking the jumbled images and learning a mapping from them to the label via a CNN is likely to be the most straightforward and likely to work approach.
One thing missing from the above idea for problems where the label one is trying to learn relies on some global structurally coherent aspects, which are destroyed during the scrambling. In this case, one can either try to learn to reconstruct the images (see below) or take every image and try several random rearrangements as input (per permuted image), and take, say, the prediction the network is most confident in.
Separately, if you want to reconstruct the jumbled images (i.e., solve the scrambled puzzle), there are some recent papers looking at how to do exactly that. E.g.,