Rearrange pixels to maximize visually distinguishable pattern
This will not be an algorithm in the usual sense. It's a bunch of heuristics that you may find useful. The main difficulty comes from the undefined nature of the phrase "visually similar".

If I understand your question correctly. You have a few separate problems:

Defining what pairwise "visual similarity" is

You are looking for a function $S$ of two vectors to the interval $[0, 1]$. I imagine that you want it to ideally satisfy the following:


$S(\vec{x}, \vec{x}) = 1$, which means that a vector is most visually similar to itself.
$S(\vec{x}, \vec{y}) = S(\vec{y}, \vec{x})$, which means that measuring similarity between $x, y$ does not depend on their order.
$S(\vec{1}, \vec{0}) = 0$, which means that the most unsimilar vectors are the all-ones-vector and all-zeroes-vector.


Even with these restrictions you have a lot of choices. You can just count the number of matching pixels, but a one pixel shift in the image could give you maximum mismatch even if the images are visually very similar.

One simple heuristic that may suffice is counting all matching pixels. Then adding the number of $2\times2$ squares having a matching number of ones (sliding the comparison over all possible sub-squares), ..etc. You can try giving less weight to bigger squares. If you normalize by the maximum value you get (which is computed by comparing an image to itself). You get a value from 0 to 1. It's clear that this satisfies the assumptions above and captures similarity better than just comparing pixels.

These ideas are just examples of what you can do. If you experiment a bit, you can find some interesting $S$'s that capture your personal notion of visual similarity.

Deciding what you want to maximize for the data set.

Now assuming you have such an $S$, the question becomes what do you want to optimize. For a column (resp row), you can compute the sum or the median or the minimum (resp maximum). You can try to maximize the average column similarities minus the average row similarities or something of that sort.

Again, for an abstract $S$ that is not perfectly defined, you need to try different options and see what works best. As a guideline, optimizing for median vaguely means you optimize the common case, while allowing for outliers.

Quickly computing a permutation on $[1 \dots 64]$ that maximizes this quantity.

For some choice of $S$ and a choice of optimization criterion, it is extremely unlikely that you will find an efficient algorithm that finds the permutation optimizing that criterion. As you noticed in your question, the number of permutation grows very quickly with the size of the image.

One common heuristic that works quite well and is really easy to code, is local search. The idea is:

// Obj(p) is the criterion to be maximized.
opt = null
for t trials:
  p = random permutation
  for s steps:
    p' = copy p
    randomly swap two (or three) elements of p'
    if Obj(p') &gt; Obj(p): p = p'
  if Obj(p) &gt; Obj(opt): opt = p

This usually works well in practice. You have the knobs s and t that control the running time, you can even run the different trials fully in parallel. Increasing them usually yields better and better results. t controls the number of "starting points" for the search, which s controls the depth of the search. Again, you will need to experiment a bit.

Hope this helps.