You asked if all 32 cairo pieces could be placed on the board with blue upper and lower borders, white left and right borders. They can. One solution and piece list attached.

I did some other border configurations also. Some results and a conjecture follow:

1. Blue top and bottom, white left and right: found > 1200 solutions, in ~2 hours, all with first 7 pieces same. CairoSol.gif, below, was simply the first solution found.

2. Blue bottom and right, white top and left: found > 120 solutions, in just a few minutes, all with first 9 pieces same.

3. Blue around the entire border: found > 30 solutions, in ~10 minutes, all with first 8 (I think?) pieces same.

4. Conjecture: A solution exists for each of the 2^30 ( 2^32 /8, 4 for the symmetry, 2 for the color reversal ) possible distinct border colorings. Certainly this is decidable, given enough time.

5. Heuristically, multiplying the average branching factors together, obtained by 2^(number of free sides) times proportion of pieces left at that time, give about 1.6 million for the average number of solutions, but as this seems to ignore the border coloring, I'm not sure how good this is. It might vary (like binomial coefficients), with balanced coloring boards having more solutions than unbalanced boards. Not enough data to really tell.

Complete searches seem to be out of reach, at least for me. Sorry. Enjoy.