I was researching the mathematics of this puzzle and wondered where it is be thought to originate. Any information, including context and precedents, would be greatly appreciated. (I'm particularly interested in puzzles that are thought of as combinatorial.)
MAA has a very nice presentation of the problem's history and solution authored by Paoletti. The problem did not originate with Euler, although he was first to formalize it as a problem of existence of what is now called the Eulerian path in a graph, and the one who gave it its historical significance. Apparently, Euler was asked about the Königsberg bridge problem by Carl Gottlieb Ehler, an astronomer, mathematician, and later a mayor of Danzig. In his reply to Ehler in 1736 Euler dismissed the problem as not even mathematical:
"...Thus you see, most noble Sir, how this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle. Because of this, I do not know why even questions which bear so little relationship to mathematics are solved more quickly by mathematicians than by others."
This despite the fact that a year earlier, on August 26, 1735, Euler presented a paper Solutio Problematis ad Geometriam Situs Pertinentis (Solution of a Problem Relating to the Geometry of Position) to the St. Petersburg Academy devoted to solving just this problem. It was published in 1741, and is considered to be the first publication that started (mathematical) graph theory. Paoletti mentions that the puzzle was urban folklore in Königsberg:
"According to lore, the citizens of Königsberg used to spend Sunday afternoons walking around their beautiful city. While walking, the people of the city decided to create a game for themselves, their goal being to devise a way in which they could walk around the city, crossing each of the seven bridges only once. Even though none of the citizens of Königsberg could invent a route that would allow them to cross each of the bridges only once, still they could not prove that it was impossible."
Unfortunately, he cites no sources. But this is partially confirmed by Euler himself, who writes in his paper:
"The problem, which I am told is widely known, is as follows: in Königsberg in Prussia, there is an island $A$ called the $Kneipho\!f$; the river which surrounds it is divided into two branches, as can be seen in Fig. [1.2], and these branches are crossed by seven bridges, a, b, c, d, e, f and g. Concerning these bridges it was asked whether anyone could arrange a route in such a way that he would cross each bridge once and only once. I was told that some people asserted that this was impossible, while others were in doubt; but nobody would actually assert that it could be done. From this, I have formulated the general problem: whatever be the arrangement and division of the river into branches, and however many bridges there be, can one find out whether or not it is possible to cross each bridge exactly once?"
[Translation from Graph Theory, 1736-1936 by Biggs, Lloyd and Wilson]