Should I leave the first authorship of our paper to the student who did the project whereas I solved it? I (as a Ph.D. student) supervised a masters project.

In particular, I defined the problem statement and prepared a sketch of the solution, that is, the steps which had to be done to achieve the solution. The masters student basically followed those steps which were mostly programming implementations. I composed the paper. Now, the paper is ready to be published, and I'm in a dilemma in selecting the first author of the paper.

On the one hand, I feel I am the right one because I solved the critical part of the problem, and the student just implemented what I had already planned. On the other hand, he may want to apply for a graduate position later, and I understand that he would morally expect to be the first author as this paper is his only serious research output. My supervisor left the issue to me by stating that my opinion would be his.

We unfortunately didn't set any specific set of expectations beforehand, particularly regarding papers and authorships.

According to a neutral mind, who most deserves to be the first author?

PS. The field is electrical engineering.
It would, perhaps, be generous of you to do so, but not necessarily wrong. In math and CS, listing authors alphabetically would probably be appropriate with little or no attention to "first" authorship. 

But an academic being seen as generous is not a bad thing. Too many questions here are just the opposite, demanding first authorship, sometimes properly and sometimes not. But such generosity is more typical in a professor with an established reputation than in a current grad student. 

But a serious consideration would entail looking at whether the student made a significant intellectual contribution to the work. If not, then first authorship is probably overly generous and might set a bad precedent in the mind of that student. 

I'm with your professor on this. Your call. But the advice in comments (BrianH) on setting expectations at the start is good - even essential.