Generate a valid sequence of numbers with specific rules The challenge

The program must return a valid sequence of numbers into some rules

Rules


x is the size of the sequence;
x cannot be less than 4 or greater than 9 (Thanks David Carraher);
Digits of the sentence can't repeat, each one must appear once;
All digits between 1 to x must be in the sequence;
A valid sequence never begins nor ends with 1 or x;
Into the sequence, numbers can never appear "together";


Examples

If x=4:
2413 valid
3142 valid

1423 not valid, because begins with 1 and 23 are "together".
2134 not valid, because ends with x and 34 are "together".

Still don't get it?
Other example:

If x=8:
28375146 valid, because don't start with 1 nor x(8), don't end with 1 nor x, and no numbers are "together"(no numbers touches, no numbers are the next or previous)

Sorry, I really don't know how to explain the last rule. Hope the example make it understandable.

Additional Information


x does not need to be an input, you can show the outputs for x=4 and x=9 working;
Since any language will be accepted and, I don't know how all of them work, I will ask you people to help me with this;
The winner will be the one who got more up-votes in 1 week, so please, vote the answer you find the best; I will mark it as the Correct one;


Good, luck. =)
GolfScript (17 16 chars)

Assuming input on stdin and output on stdout.

~:^),(;{-2\^%?}$


Almost alphanumeric-free...