I found the answer for my input just a few minutes ago, but I don’t have any code to share yet. (Too messy and it doesn’t solve the complete problem.)
What I did was to programmatically check for mis-wirings for each output (starting with z0). For my input, the first mis-wiring was for z18. Going from that to which wires to swap was not obvious, so I tried to figure it out by manually looking at how the gates were wired. I did a topological sort of the gates, which made it easier to try to understand what was happening.
I managed to figure out which two wires that were likely to fix the problems with z18, and tested that with my program. It fixed the problem and my checker gave me the next incorrect output. I quickly figured out two more pairs.
The final pair had a different kind of mis-wiring, which was harder to figure out manually. At that point I just added a brute-force search, testing swap each possible pair of wires. It finished in a few seconds.
I now think I now how this can be solved programmatically without any need for manual intervention. It might be a couple of days before I’ll have time to try that.