With the growth of wireless technologies in sectors like the military, aviation, etc, there is a need to determine the authenticity of a genuine user. Today's conventional authentication mechanisms are based on three factors: knowledge, possession and biometrics. These factors are prone to theft, hardware failure, expensive, etc. Consequently, there is a need of a stronger solution. One such solution is Location Based Authentication that considers the location information of a user. The location information is time based and thus hard to steal. However, accuracy of the GPS, signal strength inside the building, etc, affects its potential. Consequently, there is a need to address alternatives. One such alternative is to implement a puzzle-based authentication scheme based on the location information. In the proposed scheme, the server asks dynamic location-based questions and the client answers them based on the proposed route of travel. This scheme strengthens the current authentication mechanisms.