Almost always optimally solves the blacksmithing puzzle in the online game Puzzle Pirates (http://www.puzzlepirates.com/). The algorithm uses branch and bound along with local search.