The example image contains a large scale object spanning the whole image and has lots of fine-grained detail. While an impressive demo, it probably won't work as well on black-and-white documents, because the edge will have very little information to determine adjacency. Additionally, shredded documents can have two sides and the shredded stripes might be so small that it becomes difficult to tell up from down. That adds another exponential search space on top of the Traveling Salesman Problem.

That said, reconstruction of shreds is probably possible in most cases, although there is still lots of research to be done in this space. For example the Fraunhofer Society has a project to reconstruct torn documents of the East German StaSi surveillance agency [1]. There seem to be very few detailed publications on their methods, but I did find a high-level overview [2]

[1] http://www.bstu.bund.de/EN/Archives/ReconstructionOfShredded...

[2] https://doi.org/10.1007/978-1-4471-4763-3_8 (The Springer page is paywalled, but the DOI can help you find cheaper sources.)