There are a few aspects to the non-oviousness (US) / inventive step (EU) requirement.
You're asking why the difficulty of implementation is not relevant to patentability. I take it that your question is about the difficulty of inventing the invention (the invention that is to be patented), not about actually implementing it afterwards. However, the premise is not exactly correct. First, we should clearly parse between theory and (case) law.
In theory, non-obviousness and inventive step are the burden of not only providing a new combination of known objects/steps/whatever, but doing so in an inventive manner. That means, that a person skilled in the field(s) of the invention would not reach this invention if confronted with the problem, without acting "inventive". In other words, a person merely using the known skills and products would not necessarily arrive at the invention. The necessarily is important, because it doesn't matter if the person skilled in the art could arrive at the solution, but rather if they would.
If the person skilled in the art would not necessarily find the solution, it is considered inventive. The wikipedia page (section "rationale" and "Controversies and alternatives") provides some theoretical discussion and research for the question if that's enough, however it seems to be a little anti-patent-system, so I wouldn't say it's completly unbiased.
In the EU patent law, this has led to the problem solution approach, which I cite from the same wikipedia page:
Problem-solution approach
The Examining Divisions, the Opposition Divisions, and the Boards of Appeal of the EPO almost always apply the "problem-solution approach" in order to assess and decide whether an invention involves an inventive step. The approach consists in:
identifying the closest prior art, the most relevant prior art, or at least a realistic starting point;
determining the objective technical problem, that is, determining, in the view of the closest prior art, the technical problem which the claimed invention addresses and successfully solves; and
examining whether or not the claimed solution to the objective technical problem is obvious for the skilled person in view of the state of the art in general.
This last step is conducted according to the "could-would approach". Pursuant to this approach, the question to address in order to assess whether the invention involves an inventive step is the following (the question is the climax of the problem-solution approach):
Is there any teaching in the prior art, as a whole, that would, not simply could, have prompted the skilled person, faced with the objective technical problem formulated when considering the technical features not disclosed by the closest prior art, to modify or adapt said closest prior art while taking account of that teaching [the teaching of the prior art, not just the teaching of the closest prior art], thereby arriving at something falling within the terms of the claims, and thus achieving what the invention achieves?
If the skilled person would have been prompted to modify the closest prior art in such a way as to arrive at something falling within the terms of the claims, then the invention does not involve an inventive step.
The point is not whether the skilled person could have arrived at the invention by adapting or modifying the closest prior art, but whether he would have done so because the prior art incited him to do so in the hope of solving the objective technical problem or in expectation of some improvement or advantage. This must have been the case for the skilled person before the filing or priority date valid for the claim under examination.
Problem inventions
"The discovery of an unrecognised problem may in certain circumstances give rise to patentable subject-matter in spite of the fact that the claimed solution is retrospectively trivial and in itself obvious." However, "[t]he appreciation of a technical problem could thus only contribute to the inventive step in very exceptional circumstances."[19]
For a discussion of the inventive step test for "software patents" and "computer-implemented inventions" under the EPO case law, see also "Inventive step test" section in Software patents under the EPC.
Combination inventions
Since most inventions comprise a combination of know features, European Patent Convention establishes specials rules regarding the inventive step requirement for such combinations. Briefly, in such cases involving "any combination of features having known advantages (and disadvantages) is obvious unless it provides an unexpected effect."2 For example, "in the absence of any unexpected effect, the mere substitution of an element by another known for its relevant properties to provide that known effect could not be regarded as patentable." http://www.epo.org/law-practice/legal-texts/html/caselaw/2013/e/clr_i_d_9_6.htm "It was said to be obvious to try to solve the individual problems as long as the corresponding solutions were "merely aggregated together" in the claim."http://www.epo.org/law-practice/legal-texts/html/caselaw/2013/e/clr_i_d_9_7.htm
The quote provides some more readings, especially to the question of what is considered inventive for combinations of known stuff.
There are other secondary indicators for inventivess, namely
Predictable disadvantage; non‑functional modification; arbitrary choice
Unexpected technical effect; bonus effect
Long‑felt need; commercial success.
As you can see, the "difficulty" is part of the inventive step. Or rather, it comes down to a binary decision - was something "easy", meaning someone skilled in the art would have had to find it if prompted with the objective technical problem, or was it "difficult", meaning the person skilled in the art would have to invent a solution and might arrive at a different one or not at all? If I tell you to turn the screwdriver to get the screw into the wall, without telling you in which direction, it's still obvious that it's either right or left, so you have to come to the conclusion that it's right after trying left. However, if I gave you a Hammer and you invented the nail, that wasn't obvious, because you could have used it to bash in my head, to pick your teeth or anything. (Bad example, I know, but I'm trying to brake it down).
For the US, let's say, they have some problems with defining their non-obviousness. If you read the rest of the wikipedia article, at the moment they combine something close to the EU definition with a question of combining elements in a predictable manner which yields obviousness. So without knowing the problem, if your solution could have been predicted to yield the result it did by knowing the prior art, it is obvious (very short, not complete explanation).
Citing wikipedia as to what is obvious in the US:
- Combining prior art elements according to known methods to yield predictable results;
- Simple substitution of one known element for another to obtain predictable results;
- Use of known technique to improve similar devices (methods, or products) in the same way;
- Applying a known technique to a known device (method, or product) ready for improvement to yield predictable results;
- "Obvious to try" – choosing from a finite number of identified, predictable solutions, with a reasonable expectation of success;
- Known work in one field of endeavor may prompt variations of it for use in either the same field or a different one based on design incentives or other market forces if the variations are predictable to one of ordinary skill in the art;
- Some teaching, suggestion, or motivation in the prior art that would have led one of ordinary skill to modify the prior art reference or to combine prior art reference teachings to arrive at the claimed invention.
But still, and I think this might be the answer to your question, but the rest was necessary for explaining anyways, if you combine something and the result is unexpected (meaning the prior art doesn't hint that the result would be as it is) and it wasn't the obvious thing to try, it does not matter how easy it is to try. Selecting, even by luck, a good solution from an infinite number of possible solutions is, per definition, inventive. Either in the EU (secondary indicators cited above) or the US (one of the 7 points in the wikipedia page). This is the difference between an ex post facto and an ex ante analysis. It's a nice little latin phrase, but it just means that an invention, to be obvious, has to be obvious before knowing it. If I'm standing on a big Island and ask a hundred persons to dig for a gold treasure and one of them finds it, ex post it's obvious where it was - where he digged, but ex ante it was almost impossible to find and if the person that did thought of something the others didn't and saw some kind of different growing grass patern and therefore found the treasure, that was inventive (well, another bad example, but I think it makes my point).
In summary however, there is no one "obviousness" or "inventiveness". They definition is subject to change with every case that is decided and from patent examiner to patent examiner. It's not a line, it's a big grey region. Which explains why some patents are granted, that never should have been and maybe later revoked. or why the supreme court seems to change the definition every other decade.
There's a lot more of literature around this topic and a lot of case law. If your interested, follow the links behind the links I provided and you'll find some of it. It's not possible to give a complete analysis of inventiveness, but I think a good summary would be to say that an invention should be conceivable only by doing something which not everyone would do that way. In practice, sometimes examiners rely too much on prior art to prove non-obviousness, because they have to establish a case with what they have and cannot just say "ah but that's obviously obvious". But that's, especially in the US, a bug in the implementation which is beeing fixed bit by bit as you can see from the recent and not so recent supreme court decisions.