A tavern puzzle is a mechanical puzzle consisting of small metal pieces like rings and other objects that has to be disentangled and put back together. They are forged by blacksmiths to amuse their friends at taverns and inns, and apparently they are a well-known game in the Westlands.
Mahiro Shukosa is working a tavern puzzle in the common room of the Crown of Roses, an inn in Caemlyn. After completing it, he puts it back together, then takes one from another stack. It is mentioned that he is very skilled in working the puzzles.
Birgitte Silverbow looks at Matrim Cauthon as if he was "a tavern puzzle," suggesting that the mechanics of the game were hard to figure out. It is also mentioned that Mat was lucky only at games of chance like dice or cards; the pieces of tavern puzzles elude him, it being a game of skill and order.
Disentanglement puzzles were known in Europe and China since medieval times.