In this work we investigate an auction mechanism for sharing available wireless bandwidth among competing cognitive radios. The bandwidth under consideration may be either in an unlicensed spectrum or in an unused licensed band. Spectrum sharing is achieved via a mechanism in which a cognitive radio acting as the auctioneer advertises spectrum availability to bidding cognitive radios and defines a puzzle to solve as a method to access it. The cognitive radios act as bidders by computing the solution to the problem (i.e., the 'puzzle'). The winner is the bidder who submits the first correct bid and thus gains access to the spectrum for the next time interval. We consider two different variances of our scheme based on parallelizable and non-parallelizable problems and demonstrate that the latter provides a fair auction in contrast to the former. We propose a verification database to counter malicious 'greedy' players. Our algorithm provides a centralized, easy-to-implement, and computationally fast multiple-access scheme that is verifiable by all participating cognitive radios.