1$ is never self-complementing. In some cases $r(\pi)$ is a symmetry: specifically for square-free permutations, and P-crucial permutations for $P = \{0,n\}$, $\{1,n-1\}$ or $\{0,1,n-1,n\}$. In these cases we excluded all but a canonical solution from each equivalence class, using the standard `lex leader' approach \cite{lexleader}. This is efficient because of the use of specialized constraints for lexicographical ordering \cite{gaclex}. % \textbf{Should say something about what we assume about the ordering, if anything.} We have not reported run-times in detail, but as an example, the $n=17$ run in Table~\ref{tab:maximal} required 54,858 cpu seconds, just under 15.25 cpu hours. This is a rate of just under 7,000 nodes per second. A key advantage of constraint programming is the massively reduced RAM requirements compared to Section~\ref{original-approach}. Because of this we are able to solve much larger problems: for example in Table~\ref{tab:01n1n} we are able to settle all questions for $n=22$ and one for $n=26$, compared to a maximum of $n=18$ with the earlier approach. \section{Open questions and some conjectures}\label{open} It would be interesting to find the missing (exact) solutions in Tables~\ref{tab:maximal} and~\ref{tab:01n1n}. Also, we would like to state the following conjectures. \begin{conjecture}\label{bicrucials2} There exist bicrucial permutations with respect to squares of length $8k+3$ for $k\geq 2$.\end{conjecture} \begin{conjecture}\label{even-length-bicrucial} There exist arbitrary long bicrucial square-free permutations of even length. \end{conjecture} If Conjecture \ref{even-length-bicrucial} is true, it is interesting to know whether such permutations exist for each even length greater than 30. \begin{conjecture}\label{long-S-crucial} There exist arbitrary long S-crucial permutations with respect to squares. \end{conjecture} Table~\ref{tab:01n1n} gives our empirical investigations into this question. While there were no S-crucial permutations of length 18, 19, 20 or 22, we did find (at least) 144,586 symmetrically distinct solutions at $n=21$. % {\bf Ian and Co: can you find an S-crucial permutation of length 18 or confirm that such permutations do not exist? What about $n=19$? 20? If we would have such data, we could add small discussion related to Conjecture \ref{long-S-crucial}.} Finally, a general program of research here is the study of classes of $P$-crucial permutations with respect to a given set of prohibitions $S$ (different from squares considered in this paper). One can study such objects in the way we study, say, right-crucial and bicrucial permutations, that is, to try to classify lengths for which respective $P$-crucial permutations exist, or at least to try to show that arbitrary long such permutations exist. Also, considering words instead of permutations for various (natural) sets $P$ and $S$ is yet another interesting research direction. \section{Acknowledgments} We are extremely grateful to Chris Jefferson for suggesting that square-free permutations may be appropriate for solution using constraint programming. We also grateful to the anonymous referees for a number of useful suggestions. This research is supported in part by EPSRC grants EP/G055181/1 and EP/H004092/1, for which we are very grateful. \appendix \section{Additional results} \begin{table}[H] \begin{center} \scalebox{0.8}{ \begin{tabular}{r|rr|r|rr} $n$ & Solutions & Nodes & Solutions & Solutions & Nodes \\ & & Searched &up to Symmetry & $\pi=r(c(\pi))$& Searched \\ & & & & up to Symmetry& \\ \hline 3 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 6 & 0 & 0 & 5 \\ 5 & 0 & 10 & 0 & 0 & 7 \\ 6 & 0 & 15 & 0 & 0 & 13 \\ 7 & 82 & 351 & 41 & 3 & 28 \\ 8 & 272 & 1862 & 136 & 0 & 25 \\ 9 & 766 & 5955 & 383 & 0 & 112 \\ 10 & 3788 & 19687 & 1894 & 0 & 248 \\ 11 & 14096 & 75932 & 7048 & 58 & 617 \\ 12 & 74568 & 322940 & 37284 & 0 & 61 \\ 13 & 281232 & 1358128 & 140616 & 0 & 2894 \\ 14 & 2026184 & 7636544 & 1013092 & 0 & 848 \\ 15 & 9430962 & 42623572 & 4715481 & 961 & 13787 \\ 16 & 79497550 & 400446913 & 39748775 & 0 & 113 \\ 17 & 422657308 & 2274985904 & 211328654 & 28 & 101644 \\ \end{tabular} } \end{center} \caption{Results for $\{1\}$ and $\{n-1\}$-crucial permutations. Node counts from former.} \label{tab:1} \end{table} In this appendix we include full tables of results for all forms of cruciality not given in full detail in the main part of the paper. These tables are referred to in the main text by Table~\ref{P-crucial}. The tables in this Appendix take one of two forms. As mentioned in the main text, for some sets $P$ we have that if $\pi$ is $P$-crucial then it is guaranteed that $r(\pi)$ is also. In these cases a separate run is required to identify the number of symmetrically distinct solutions. Tables \ref{tab:1n1} and \ref{tab:01n1n} are of this form. Where reversal symmetry is not guaranteed (the remaining tables), the tables are different in two ways. First, no separate run is necessary to count symmetrically distinct solutions: the total is always half the total number of solutions. Second, the table can be computed in one of two ways. For example, Table~\ref{tab:1} shows numbers of $\{1\}$- and $\{n-1\}$-crucial permutations. While it is guaranteed that the number of solutions of each type is the same, the number of nodes searched may be different depending on which type was run. For precision, we indicate in each table which node count we are reporting. For example, in Table~\ref{tab:1} we give node counts for $\{1\}$-crucial permutations. The choice of which case is reported is arbitrary. \begin{table}[H] \begin{center} \scalebox{0.93}{ \begin{tabular}{r|rr|r|rr} $n$ & Solutions & Nodes & Solutions & Solutions & Nodes \\ & & Searched &up to Symmetry & $\pi=r(c(\pi))$& Searched \\ & & & & up to Symmetry& \\ \hline 3 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 0 & 0 & 0 \\ 6 & 0 & 0 & 0 & 0 & 0 \\ 7 & 0 & 102 & 0 & 0 & 16 \\ 8 & 0 & 161 & 0 & 0 & 25 \\ 9 & 0 & 244 & 0 & 0 & 34 \\ 10 & 0 & 351 & 0 & 0 & 232 \\ 11 & 0 & 485 & 0 & 0 & 46 \\ 12 & 0 & 649 & 0 & 0 & 61 \\ 13 & 0 & 846 & 0 & 0 & 122 \\ 14 & 0 & 1079 & 0 & 0 & 845 \\ 15 & 54854 & 1020814 & 27427 & 0 & 4113 \\ 16 & 722114 & 24479482 & 361057 & 0 & 113 \\ 17 & 5144632 & 118675744 & 2572316 & 28 & 53501 \\ \end{tabular} } \end{center} \caption{Results for $\{0,1\}$ and $\{n-1,n\}$-crucial permutations. Node counts from former.} \label{tab:01} \end{table} \begin{table}[H] \begin{center} \scalebox{0.93}{ \begin{tabular}{r|rr|r|rr} $n$ & Solutions & Nodes & Solutions & Solutions & Nodes \\ & & Searched &up to Symmetry & $\pi=r(c(\pi))$& Searched \\ & & & & up to Symmetry& \\ \hline 3 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 0 & 0 & 0 \\ 6 & 0 & 0 & 0 & 0 & 0 \\ 7 & 20 & 111 & 10 & 0 & 16 \\ 8 & 96 & 530 & 48 & 0 & 25 \\ 9 & 0 & 1266 & 0 & 0 & 39 \\ 10 & 1444 & 7815 & 722 & 0 & 232 \\ 11 & 0 & 1294 & 0 & 0 & 46 \\ 12 & 10080 & 66223 & 5040 & 0 & 61 \\ 13 & 0 & 98871 & 0 & 0 & 1135 \\ 14 & 0 & 351920 & 0 & 0 & 845 \\ 15 & 2988 & 1883376 & 1494 & 0 & 4113 \\ 16 & 25781024 & 160519095 & 12890512 & 0 & 113 \\ 17 & 2138998 & 294150147 & 1069499 & 28 & 56458 \\ \end{tabular} } \end{center} \caption{Results for $\{0,n-1\}$ and $\{1,n\}$-crucial permutations. Node counts from latter.} \label{tab:0n1} \end{table} \begin{table}[H] \begin{center} \scalebox{0.9}{ \begin{tabular}{r|rr|rr|rr} $n$ & Solutions & Nodes & Solutions & Nodes & Solutions & Nodes \\ & & Searched &up to Symmetry & Searched & $\pi=r(c(\pi))$& Searched \\ & & & & & up to Symmetry& \\ \hline 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 6 & 0 & 3 & 0 & 3 \\ 5 & 0 & 10 & 0 & 3 & 0 & 3 \\ 6 & 0 & 15 & 0 & 6 & 0 & 6 \\ 7 & 18 & 225 & 6 & 68 & 3 & 12 \\ 8 & 0 & 1385 & 0 & 347 & 0 & 10 \\ 9 & 0 & 4677 & 0 & 1288 & 0 & 52 \\ 10 & 0 & 13971 & 0 & 2936 & 0 & 130 \\ 11 & 8972 & 64562 & 2272 & 16749 & 58 & 294 \\ 12 & 0 & 199164 & 0 & 64118 & 0 & 21 \\ 13 & 281232 & 1216051 & 70308 & 371785 & 0 & 1403 \\ 14 & 0 & 3754582 & 0 & 1312833 & 0 & 434 \\ 15 & 3094458 & 32430311 & 774095 & 7744341 & 961 & 6828 \\ 16 & 1194800 & 257503934 & 298700 & 67920867 & 0 & 36 \\ 17 &{6056996} & 1714652389 & 1514263 & 524235669 & 28 & 52973 \\ \end{tabular} } \end{center} \caption{Results for $\{1,n-1\}$-crucial permutations.} \label{tab:1n1} \end{table} \begin{table}[H] \begin{center} \scalebox{0.9}{ \begin{tabular}{r|rr|r|rr} $n$ & Solutions & Nodes & Solutions & Solutions & Nodes \\ & & Searched &up to Symmetry & $\pi=r(c(\pi))$& Searched \\ & & & & up to Symmetry& \\ \hline 3 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 0 & 0 & 0 \\ 6 & 0 & 0 & 0 & 0 & 0 \\ 7 & 0 & 102 & 0 & 0 & 16 \\ 8 & 0 & 161 & 0 & 0 & 25 \\ 9 & 0 & 244 & 0 & 0 & 34 \\ 10 & 0 & 351 & 0 & 0 & 232 \\ 11 & 0 & 485 & 0 & 0 & 46 \\ 12 & 0 & 649 & 0 & 0 & 61 \\ 13 & 0 & 846 & 0 & 0 & 122 \\ 14 & 0 & 1079 & 0 & 0 & 845 \\ 15 & 0 & 841776 & 0 & 0 & 4113 \\ 16 & 553428 & 23833969 & 276714 & 0 & 113 \\ 17 & 5424 & 107571076 & 2712 & 28 & 53437 \\ \end{tabular} } \end{center} \caption{Results for $\{0,1,n-1\}$ and $\{1,n-1,n\}$-crucial permutations. Node counts from former.} \label{tab:01n1} \end{table} \begin{table}[H] \begin{center} \scalebox{0.6}{ \begin{tabular}{r|rr|r|rr} $n$ & Solutions & Nodes & Solutions & Solutions & Nodes \\ & & Searched &up to Symmetry & $\pi=r(c(\pi))$& Searched \\ & & & & up to Symmetry& \\ \hline 3 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 0 & 0 & 0 \\ 6 & 0 & 0 & 0 & 0 & 0 \\ 7 & 0 & 83 & 0 & 0 & 16 \\ 8 & 0 & 126 & 0 & 0 & 25 \\ 9 & 0 & 479 & 0 & 0 & 43 \\ 10 & 0 & 351 & 0 & 0 & 232 \\ 11 & 0 & 1665 & 0 & 0 & 46 \\ 12 & 0 & 1422 & 0 & 0 & 61 \\ 13 & 0 & 110752 & 0 & 0 & 1243 \\ 14 & 0 & 63292 & 0 & 0 & 845 \\ 15 & 0 & 7381558 & 0 & 0 & 4113 \\ 16 & 0 & 3471394 & 0 & 0 & 113 \\ 17 & 550976 & 282598708 & 275488 & 28 & 56784 \\ \end{tabular} } \end{center} \caption{Results for $\{0,1,n\}$ and $\{0,n-1,n\}$-crucial permutations. Node counts from latter.} \label{tab:01n} \end{table} \begin{table}[H] \begin{center} \scalebox{0.6}{ \begin{tabular}{r|rr|rr|rr} $n$ & Solutions & Nodes & Solutions & Nodes & Solutions & Nodes \\ & & Searched &up to Symmetry & Searched & $\pi=r(c(\pi))$& Searched \\ & & & & & up to Symmetry& \\ \hline 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 0 & 0 & 0 & 0 \\ 6 & 0 & 0 & 0 & 0 & 0 & 0 \\ 7 & 0 & 0 & 0 & 0 & 0 & 0 \\ 8 & 0 & 0 & 0 & 0 & 0 & 0 \\ 9 & 0 & 0 & 0 & 0 & 0 & 0 \\ 10 & 0 & 0 & 0 & 0 & 0 & 0 \\ 11 & 0 & 0 & 0 & 0 & 0 & 0 \\ 12 & 0 & 0 & 0 & 0 & 0 & 0 \\ 13 & 0 & 0 & 0 & 0 & 0 & 0 \\ 14 & 0 & 0 & 0 & 0 & 0 & 0 \\ 15 & 0 & 0 & 0 & 0 & 0 & 0 \\ 16 & 0 & 0 & 0 & 0 & 0 & 0 \\ 17 & 1568 & 9214495 & 406 & 823 & 28 & 55 \\ 18 & 0 & 0 & 0 & 0 & 0 & 0 \\ 19 & 0 & 17819710 & 0 & 0 & 0 & 0 \\ 20 & 0 & 0 & 0 & 0 & 0 & 0 \\ 21 & $\geq$ 289172& {\emph{timeout}} & $\geq 144586$ & $\geq 5795227$ & \multicolumn{2}{c}{\emph{timeout}} \\ 22 & 0 & 0 & 0 & 0 & 0 & 0 \\ 23 & \multicolumn{2}{c|}{\emph{timeout}} & \multicolumn{2}{c|}{\emph{timeout}} & 0 & 0 \\ 24 & \multicolumn{2}{c|}{\emph{timeout}} & \multicolumn{2}{c|}{\emph{timeout}} & 0 & 0 \\ 25 & \multicolumn{2}{c|}{\emph{timeout}} & \multicolumn{2}{c|}{\emph{timeout}}& \multicolumn{2}{c}{\emph{timeout}} \\ 26 & \multicolumn{2}{c|}{\emph{timeout}} & \multicolumn{2}{c|}{\emph{timeout}}& 0 & 0 \\ \end{tabular} } \end{center} \caption{Results for $\{0,1,n-1, n\}$-crucial permutations (also called S-crucial permutations in the main text). A timed out run is one which failed to find any solutions before 6 hours cpu time were used on our machine. Note that problems do not get monotonically harder, presumably because some sizes, e.g., 22, are intrinsically easier to search than other sizes. Interestingly, no solutions were found for 21 in regular search. However, because 144,586 were found up to symmetry before the timeout: all of these and their complements are S-crucial permutations so we obtain the lower bound given in the first column. These experiments were run with SSAC preprocessing and dom/wdeg heuristic.} \label{tab:01n1n} \end{table} \begin{thebibliography}{25} \bibitem{AGHK} S. Avgustinovich, A. Glen, B. V. Halld\'orsson, and S. Kitaev, On shortest crucial words avoiding abelian powers, {\em Discr. Appl. Math.} {\bf 158} (2010), 605--607. \bibitem{AKPV} S. Avgustinovich, S. Kitaev, A. Pyatkin, and A. Valyuzhenich, On square-free permutations, {\em J. Autom., Lang. and Combin.} {\bf 16} (2011) 1, 3--10. \bibitem{AKV} S. Avgustinovich, S. Kitaev, and A. Valyuzhenich, Crucial and bicrucial permutations with respect to arithmetic monotone patterns, {\em Siberian Elect. Math. Reports} {\bf 9} (2012), 660--671. \bibitem{B} E. M. Bullock, Improved bounds on the length of maximal abelian square-free words, {\em Elect. J. Combin.} {\bf 11(1)} (2004), \#R17. \bibitem{lexleader} J. M. Crawford, M. L. Ginsberg, E. M. Luks, and A. Roy, Symmetry-breaking predicates for search problems, {\em Principles of Knowledge Representation and Reasoning - KR} (1996), 148--159. \bibitem{C} L. J. Cummings and M. Mays, A one--sided Zimin construction, {\em Elect. J. Combin.} {\bf 8} (2001), \#R27. \bibitem{pE61some} P. Erd\H{o}s, Some unsolved problems, {\em Magyar Tud. Akad. Mat. Kutat\'o Int. K\"ozl.} {\bf 6} (1961), 221--254. \bibitem{EK} A. Evdokimov and S. Kitaev, Crucial words and the complexity of some extremal problems for sets of prohibited words, {\em J. Combin. Theory Ser. A} {\bf 105/2} (2004), 273--289. \bibitem{gaclex} A. M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, and T. Walsh, Propagation algorithms for lexicographic ordering constraints, {\em Artif. Intell.} {\bf 170} (2006) 10, 803--834. \bibitem{GAP4} The GAP~Group. \emph{GAP -- Groups, Algorithms, and Programming, Version 4.7.2}; 2013, \url{http://www.gap-system.org}. \bibitem{minion} I. P. Gent, C. Jefferson, and I. Miguel, Minion: A fast scalable constraint solver, in {\em Proceedings of the 17th European Conference on Artificial Intelligence -- ECAI 2006}, Frontiers in Artificial Intelligence and Applications, Vol.~141, 2006, pp.~98--102. \bibitem{GHK} A. Glen, B. V. Halld\'orsson, and S. Kitaev, Crucial abelian $k$-power-free words, {\em Discr. Math. and Theoret. Comp. Sci.} {\bf 12} (2010) 5, 83--96. \bibitem{Kit} S. Kitaev, {\em Patterns in Permutations and Words}, Springer-Verlag, 2011. \bibitem{K} M. Korn, Maximal abelian square-free words of short length, {\em J. Combin. Theory Ser. A} {\bf 102} (2003), 207--211. \bibitem{reification} C. Jefferson, N. C. A. Moore, P. Nightingale, and K. E. Petrie, Implementing logical connectives in constraint programming, {\em Artif. Intell.} {\bf 174} (2010) 16--17, 1407--1429. \bibitem{savilerow} P. Nightingale, \"O. Akg\"un, I. P. Gent, C. Jefferson, and I. Miguel, Automatically improving constraint models in Savile Row through associative-commutative common subexpression elimination, in {\em Principles and Practice of Constraint Programming -- CP 2014}, Lecture Notes in Comput. Sci., Vol.~8656, 2014, pp.~590--605. \bibitem{thue} A. Thue. \"Uber unendliche Zeichenreihen, {\em Norske vid. Selsk. Skr. Mat. Nat. Kl.} {\bf 7} (1906), 1--22. Reprinted in {\em Selected Mathematical Papers of Axel Thue}, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp.~139--158. \bibitem{singleton} P. Prosser, K. Stergiou, and T. Walsh, Singleton consistencies, in {\em Principles and Practice of Constraint Programming -- CP 2000}, Lecture Notes in Comput. Sci., Vol.~1894, 2000, pp.~353--368. \bibitem{handbook-cp} F. Rossi, P. van Beek, and T. Walsh, eds., {\em Handbook of Constraint Programming}, Elsevier, 2006. \bibitem{OEIS} N.~J.~A.~Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at \url{http://oeis.org}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 \textit{Mathematics Subject Classification}: Primary 05A05; Secondary 68R15. \noindent \emph{Keywords:} crucial permutation, bicrucial permutation, square, $P$-crucial permutation, S-crucial permutation. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A221989}, \seqnum{A221990}, \seqnum{A238935}, \seqnum{A238937}, and \seqnum{A238942}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 30 2015; revised version received April 12 2015; May 22 2015; June 2 2015. Published in {\it Journal of Integer Sequences}, June 3 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}