We present a machine learning based approach for automatically synthesizing a memristor crossbar design from the specification of a Boolean formula. In particular, our approach employs deep neural networks to explore the design space of crossbar circuits and conjecture the design of an approximately correct crossbar. Then, we employ simulated annealing to obtain the correct crossbar design from the approximately correct design. Our experimental investigations show that the deep learning system is able to prune the search space to less than $$0.0000011\%$$ of the original search space with high probability; thereby, making it easier for the simulated annealing algorithm to identify a correct crossbar design. We automatically design an adder, subtractor, comparator, and parity circuit using this combination of deep learning and simulated annealing, and demonstrate their correctness using circuit simulations. We also compare our approach to vanilla simulated annealing without the deep learning component, and show that our approach needs only 6.08% to 69.22% of the number of circuit simulation queries required by simulated annealing alone.