The accuracy level is already very high, but how to motivate the agent to find the target as quickly as possible?
You already are, in two different ways:
A penalty (negative reward) for each time step taken.
A positive reward for completing a task, plus discounting.
Both of these choices are sufficient that action values will be maximised by taking the most direct route to complete a task, and minimise expected time steps from any starting point.
In theory you could completely lose one of the two approaches, and the reward system would still work.
For DQN I would lose the positive reward at the end and use a relatively high discount factor, e.g. $\gamma = 0.99$ - which is only required for numerical stability, and not really part of the problem definition. If your goal is to minimise number of time steps, then a simple count of number of remaining time steps is already a good cost function, and negating it to make a reinforcement learning return is close to ideal. It often works well with Q learning too because it will explore away from repetition, even if at the start of training it cannot reach the target state.
What's the effect of $\gamma$ on the agent's task solving speed?
This can be complex, but is a scenario with the only positive reward at the end and a discount factor, then expected reward will depend on expected future time steps in a geometric series. If in state $s_1$, action choice $a_1$ would lead to the end goal in 3 time steps and action choice $a_2$ would lead to the end goal in 4 time steps, with the only reward $r_T$ for reaching the goal state, then $q(s_1, a_1) = \gamma^3 r_T \gt q(s_1, a_2) = \gamma^4 r_T$, making $a_1$ the obvious choice.
A stochastic environment may muddy this a little, but in general the agent is going to prefer the lower number of timesteps to get to the goal. If distribution of number of timesteps can be very different, then different $\gamma$ values may cause slightly different gambling options made by the agent to complete faster. This is the reason why I suggest dropping the positive reward at the end, if your goal is to minimise expected number of timesteps to complete. That is because technically a change to $\gamma$ is a change to the problem definition - muddied slightly by usually needing $\gamma \lt 1$ when training a DQN to improve stability.
Which one is correct? I have tried training the network with $\gamma=0.1, 0.5, 0.9, 0.99$, but the network can only learn with $\gamma=0.1, 0.5$.
Both are correct, although you do have to be concerned about $\gamma$'s dual role as problem definition parameter and solution hyper-parameter when working with approximators.
I think (but without looking at your code) that you have a problem with your neural network hyperparameters. A discount factor of $0.9$ or $0.99$ should work with DQN, and is a very common choice. I suggest try a few different architecture choices, and also DQN hyperparameters such as experience replay size, time between copying learning network to target network etc.
Another thing that occurs to me, and may be specific to the environment that you are working with: If you are comparing the performance of your agent with a human, then a human may be able to apply their memory of previous attempts to this problem, and look for trends between time steps. If your state vector does not capture or summarise the history of guesses so far, and such "trend" information is actually useful for your problem, then you may need to add some kind of memory. You could modify the state to summarise attempts so far, or you could use an agent with memory, such as one based on a RNN.
Whether an agent with memory would help depends on the nature of the different "locations" that are being guessed at, and the hints. A very simple example of where memory would make a huge difference is game where the locations are all the numbers between 1 and 100, and the agent is told "higher" or "lower" when it makes an incorrect guess. Storing (or learning to store) the bounds implied by guesses so far would be critical to good performance of the agent.
