The Collaborative International Dictionary of English v.0.48:

puzzle \puz"zle\ (p[u^]z"z'l), n. [For opposal, in the sense of
   problem. See Oppose, Pose, v.]
   1. Something which perplexes or embarrasses; especially, a
      toy or a problem contrived for testing ingenuity; also,
      something exhibiting marvelous skill in making.
      [1913 Webster]

   2. The state of being puzzled; perplexity; as, to be in a
      puzzle.
      [1913 Webster]

The Collaborative International Dictionary of English v.0.48:

puzzle \puz"zle\, v. t. [imp. & p. p. puzzled (p[u^]z"z'ld);
   p. pr. & vb. n. puzzling (p[u^]z"zl[i^]ng).]
   1. To perplex; to confuse; to embarrass; to put to a stand;
      to nonplus.
      [1913 Webster]

            A very shrewd disputant in those points is dexterous
            in puzzling others.                   --Dr. H. More.
      [1913 Webster]

            He is perpetually puzzled and perplexed amidst his
            own blunders.                         --Addison.
      [1913 Webster]

   2. To make intricate; to entangle.
      [1913 Webster]

            They disentangle from the puzzled skein. --Cowper.
      [1913 Webster]

            The ways of Heaven are dark and intricate,
            Puzzled in mazes, and perplexed with error.
                                                  --Addison.
      [1913 Webster]

   3. To solve by ingenuity, as a puzzle; -- followed by out;
      as, to puzzle out a mystery.
      [1913 Webster]

   Syn: To embarrass; perplex; confuse; bewilder; confound. See
        Embarrass.
        [1913 Webster]

The Collaborative International Dictionary of English v.0.48:

Puzzle \Puz"zle\, v. i.
   1. To be bewildered, or perplexed.
      [1913 Webster]

            A puzzling fool, that heeds nothing.  --L'Estrange.
      [1913 Webster]

   2. To work, as at a puzzle; as, to puzzle over a problem.
      [1913 Webster]

WordNet (r) 3.0 (2006):

puzzle
    n 1: a particularly baffling problem that is said to have a
         correct solution; "he loved to solve chessmate puzzles";
         "that's a real puzzler" [syn: puzzle, puzzler,
         mystifier, teaser]
    2: a game that tests your ingenuity
    v 1: be a mystery or bewildering to; "This beats me!"; "Got me--
         I don't know the answer!"; "a vexing problem"; "This
         question really stuck me" [syn: perplex, vex, stick,
         get, puzzle, mystify, baffle, beat, pose,
         bewilder, flummox, stupefy, nonplus, gravel,
         amaze, dumbfound]
    2: be uncertain about; think about without fully understanding
       or being able to decide; "We puzzled over her sudden
       departure"

Moby Thesaurus II by Grady Ward, 1.0:

159 Moby Thesaurus words for "puzzle":
   Chinese puzzle, Gordian knot, addle, ail, amaze, apply the mind,
   baffle, bafflement, baffling problem, bamboozle, be the matter,
   beat, befog, befuddle, beset, bewilder, bewilderment, boggle,
   bother, brain twister, brain-teaser, buffalo, cap,
   complicate matters, concern, confound, confoundment, confuse,
   confusion, consider, contemplate, conundrum, crossword puzzle,
   crux, dark horse, daze, decipher, dilemma, discommode,
   discomposure, disconcert, disconcertedness, disconcertion,
   disconcertment, distract, distress, disturb, disturbance,
   dumbfound, embarrassment, enigma, enigmatic question, figure out,
   fix, flabbergast, floor, floorer, flummox, foil, frontier,
   frontiers of knowledge, frustrate, fuddle, get, hammer at,
   hammer away at, harass, inconvenience, irk, jam, jigsaw puzzle,
   keep in suspense, knot, knotty point, lick, matter of ignorance,
   maze, mind-boggler, muddle, mull over, muse on, muse over, mystery,
   mystification, mystify, n, node, nodus, nonplus, nut to crack,
   oxymoron, paradox, perplex, perplexed question, perplexity,
   perturb, perturbation, pickle, plague, plight, ponder over,
   pons asinorum, pose, poser, pother, predicament, problem, put out,
   put to it, puzzle out, puzzle over, puzzlement, puzzler, quandary,
   question, question mark, reflect over, riddle, scrape, sealed book,
   sixty-four dollar question, solve, sort out, stew, stew over,
   stick, sticker, study, stumble, stump, stumper, stymie, teaser,
   terra incognita, the incalculable, the strange, the unfamiliar,
   the unknowable, the unknown, think hard, think through, throw,
   torment, tough proposition, trouble, unassuredness,
   unexplored ground, unexplored territory, unknown quantity, unlock,
   unravel, upset, vex, vexed question, why, work out, worry, x, z