Comment by lukan

"can’t get arbitrarily complex or unreasonable or the reader will be lost or confused."

Indeed, but that is always the challenge of a writer. But if you introduce magic in your story, and you do it in a way to show the limitations and what is roughly possible, then you can give hints later, if there was a murder with the help of a magic trick. But I actually think I only ever read one detective fantasy story

https://www.der-spurenfinder.de/

(just in german as far as I know)

It mostly works, but in one instance there was a surprise fantasy ability, that I could have not guessed before. But the actual murderer in the end, there were enough hints that gave them away despite magic, as the skills were explained and then you could combine.