We present methods for searching for Costas arrays of arbitrary size starting from a random permutation matrix. The permutation is made ? more Costas? by swapping a small number of elements in the permutation so that number of repeated values within each line of the difference triangle is reduced. This process is iterated until each line of the difference triangle contains no repeated values which indicates that a Costas array has been found. In the event that the method cannot improve further the permutation, the process is started again from another random permutation. We compare the performance of variants of this method. Also, we present results of analysis and test runs on the database of known Costas arrays up to size 26 which show that such stochastic techniques are extremely unlikely to succeed for the N we are interested in, namely N > 26. Also, as a result of the database analysis, we unveil a 23-by-23 Costas array with a most interesting property.