Colloidal nanoparticles with anisotropic interactions are promising building blocks for the fabrication of complex functional materials. A challenge in the self-assembly of colloidal particles is the rational design of geometry and chemistry to program the formation of a desired target structure. We report an inverse design procedure integrating Langevin dynamics simulations and evolutionary algorithms to engineer anisotropic patchy colloidal clusters to spontaneously assemble into a cubic diamond lattice possessing a complete photonic band gap. The combination of a tetrahedral cluster geometry and optimized placement of a single type of anisotropic interaction patch results in a colloidal building block predicted to assemble a cubic diamond lattice with more than 82% yield. This design represents an experimentally viable colloidal building block capable of high-fidelity assembly of a cubic diamond lattice.