Polymerase Chain Reaction, a mainstay of biomedical laboratory work, requires the design of good primers. Modern day applications such as "metagenomics" require these primers to be more widely applicable, which is achieved by allowing the primers to be degenerate. While the exact set of rules for ideal degenerate primer design is unknown, practitioners follow a widely accepted set of rules for designing good primers that have worked. Given that even simplified versions of the problem of computing optimal degenerate primers are NP-hard, how does one design good heuristics for this problem. We also discuss its connections to the Hamming Center problem.