  A permutation is square-free if it does not contain two consecutive factors
of length two or more that are order-isomorphic. A permutation is bicrucial
with respect to squares if it is square-free but any extension of it to the
right or to the left by any element gives a permutation that is not
square-free.
  Bicrucial permutations with respect to squares were studied by Avgustinovich
et al., who proved that there exist bicrucial permutations of lengths $8k+1,
8k+5, 8k+7$ for $k\ge 1$. It was left as open questions whether bicrucial
permutations of even length, or such permutations of length $8k+3$ exist. In
this paper, we provide an encoding of orderings which allows us, using the
constraint solver Minion, to show that bicrucial permutations of even length
exist, and the smallest such permutations are of length 32. To show that 32 is
the minimum length in question, we establish a result on left-crucial (that is,
not extendable to the left) square-free permutations which begin with three
elements in monotone order. Also, we show that bicrucial permutations of length
$8k+3$ exist for $k=2,3$ and they do not exist for $k=1$.
  Further, we generalise the notions of right-crucial, left-crucial, and
bicrucial permutations studied in the literature in various contexts, by
introducing the notion of $P$-crucial permutations that can be extended to the
notion of $P$-crucial words. In S-crucial permutations, a particular case of
$P$-crucial permutations, we deal with permutations that avoid prohibitions,
but whose extensions in any position contain a prohibition. We show that
S-crucial permutations exist with respect to squares, and minimal such
permutations are of length 17.
  Finally, using our software, we generate much of relevant data showing, for
example, that there are 162,190,472 bicrucial square-free permutations of
length 19.
