Intuition for SHA3 sponge construction
So if it's just a permutation of 0s and 1s as we've concluded, what is hard about finding an alternate message string that satisfies the constrains I've mentioned on the permutation outcome? 


To be more precise, it is a pseudo-random permutation from $\mathbb{Z}_{2^{1600}}$ to $\mathbb{Z}_{2^{1600}}$. It is not just 0s and 1s changing positions.

Because of the size of $\mathbb{Z}_{2^{1600}}$ (which contains $2^{1600}$ elements!), the input and output are related in a somewhat random (but  deterministic way), and it cannot be predicted without actually evaluating the permutation (or its inverse) on a given input and checking the result.

There are tools such as linear and differential cryptanalysis that can be used to try and predict the output, but keccak-f was explicitly designed so that using these techniques would be computationally intractable.


  It seems like I have a very localized problem


You cannot isolate parts of the state and work on them independently. Changing one bit of the state and then applying the permutation diffuses those changes across the entire state in an unpredictable manner.