(jan. 2025) SUBSCRIBE to soundblog_un_public our personal / private old-school email newsletter alternative to FB, X, Insta etc posts, delivering occasional messages, announcing and providing web links to new releases, concert dates, texts related to projects / works by Har$, the ookoi and other collabs. Thank you.

__mins read 🤓

More on sudoku solutions, on Latin and on Costas grids

january 17, 2025

THIS TEXT IS STILL IN THE PROCESS OF BEING WRITTEN. CHECK BACK TO FOLLOW ITS PROGRESS

---

A permutation matrix (of order n) is a square matrix (of size n) for which in each column and in each row there is precisely one entry with value 1. All the other entries in the matrix are 0. There is two ways in which you can view a permutation σ of order n as a permutation matrix, the (what I call) ‘column position’ point of view, and the ‘row position‘, where the ‘row position‘ point of view is the ‘column position’ point of view for σ^-1, and, symmetrically, the ‘row position’ point of view for σ^-1 is the ‘column position’ point of view for σ.

As we are interested in sudoku's and related grids, let's take a permutation (matrix) of order 9 as an example, say:

From column-position point of view, the corresponding permutation matrix is:

And this indeed, as you will easily check, is the permutation matrix of the permutation's inverse from a row-position point of view.

Instead of considering a numerical matrix, we may represent a permutation matrix by a grid in which we replace the number(s) by a symbol, or by a color:

A sudoku solution and an order 9 latin square are both examples of what (e.g. in [ 1 ]) are called full sets of mutually disjoint permutation matrices of order 9: sets of nine permutation matrices such that their sum-matrix has a 1 in every cell, i.e. in each pair of distinct matrices P, Q from that set corresponding cells have at most one '1': P(i,j) × Q(i,j) = 0, for all pairs of indices (i,j).

If in a sudoku solution or an order 9 latin square we replace the numbers 1 to 9 by, e.g., nine different colors, here are two examples of grids that we may get:

It is interesting to observe that the difference in entropy, in degree of order (of balance, of symmetry) between the two images stands out immediately. The left grid was obtained from an order 9 latin square: in the nine 3x3 squares in which the grid is divided, the same colour(s) appear(s) multiple times. This is not the case in the grid on the right, in which the color blocks at a glance of the eye appear instantly far more balanced, long before one finds out why that would be so: in the right image in each of the nine 3x3 squares all nine colours are present. It is a sudoku solution. Or, as we can assign the numbers 1 to 9 to the nine colours in 9! = 362880 ways, it rather are (sic) 362880 soduku solutions. Similarly, the order 9 latin square to the left are (sic) 362880 order 9 latin squares.

A Perished Piano Sudoku Dream Machine

In one of my cherished recurrent dreams I am outfitting my late mother's perished piano with a player system that, controlled by a relatively simple script, would endlessly perform the '27+22 Variations', for all of the 362,880 different colourings of the initial sudoku solution. Placed in a secure and serene space (a chapel, perhaps, or museum) and given some regular technical and mechanical care, the perished piano would play the variations for an estimated duration of approximately 125 years.

This is a bigger-than-human-lifetime duration, but still an oversee-able one, and a period of time over which one may imagine keeping the old piano in a working state. Were one to also include all or some of the variants resulting from (combinations of) permutation of and within 3-blocks of rows (bands)/3-blocks of columns (stacks), from transposition, rotation, reflection in the middle column, middle row or in one of the two diagonals (all of these together form the group of symmetries of a sudoku solution), the number of 24/7 playing years will quickly run into the millions, time here floating into an utterly unimaginable future, whatever be our dreams and/or (il){de}lusions.

(The image is an edited montage of two DALL-E outputs on the prompt 'Perished Piano Sudoku Dream Machine' january 7th 2025)

Premutation meditations

I like the word 'premutation', as a maybe-typo, as a permutation of ‘permutation’—a state preceding change, preceding transformation, a prelude to plots yet to unfold, to knots to be unraveled—and as a word that invites deep thoughts if only you let it bring 'm in.

A key feature of the sudoku-generated pieces as I did them up till now is their touching on the extremes of, on the one side, the near to total determinism once a sudoku grid has been picked as its source, and, on the other side, the contingency of the choice of that particular sudoku grid. {[()—Except, of course for the fact that I did choose not any other but that particular sudoku, any of the astronomical many different ones could equally well have been used to 'materialise’ (is there a better word? ... sort of like an observational collapse of a superposition of probabilities) this one among all possible pieces, like we live this one among all possible lifes, in this one among all possible worlds.—()]} That is the actual heart of the ‘Perished Piano Sudoku Dream Machine‘, and its proposed cycling through all of the 9! possible ways to ’name‘ by 1 to 9 the elements of the full set of permutation matrices that corresponds to the sudoku: it is an unfolding, a sequentialisation, of all possible worlds rather than the instantaneous collapse into a single one.

“war drift“ ( Sudoku 4, for violoncello )

After the first one, the ‘let me show you exactly who you are‘ for Shih-wen's double bass, over the past weeks I scored a second sudoku solution for a traditional acoustic classical instrument, for the violoncello, planned to be premiered early this summer. The violoncello score follows the same pattern of interpretions of the sudoku solution as that for the double bass (and, very likely, for several other pieces yet to come). The main difference then is, obviously, the soduku solution used (it is sudoku2004, the one used for fourth week's K7 sudoku in 2020). Also, the 'diagonal sudoku' used for the split of the solution in two 'puzzles', is a different one, and the initial movement chosen was not 'up', but 'down'.

(The image is a cut out part of a DALL-E output on the prompt 'realistic and atmospheric photo-like image of a single-turn ribbon with music notes, shaped like a ring, floating above a stormy, empty sea, slight slope, not touching the water' january 15th 2025)

Just like the piano pieces, these pieces are cyclic, they may be thought of as ‘looping‘, as closed ribbons, that for a recording or performance one might just cut open at any desired point, and linearize. The cello piece starts with the second (C) of the two 'filtered' parts, followed by the 'unfiltered' one A (whose starting note is the one that ends C) and ending with first 'filtered' part (B, that starts with the note that ends—and starts— the A-part).

Here is a graphic rendering of the pitches-durations of the parts in the order proposed for a performance (note how the piece indeed closes (pitchwise) onto itself, it is circle):

The parts that are outside the range of the cello, in this piece I have filled with words. Dutch words, during a live performance to be spoken by (at least) two voices, preferably by more (small choir). The text/poem, cyclic as is the music (its title is also the title of the full piece: war drift) can be found on Medium.

towards (?) costas sudokus

I am pretty sure there are more pieces to come in this cyclic form, though I doubt I will get to produce one for all of the fifty-two 2020 sudokus 😏, intend as I am to follow up on the divers trains of sudokist thoughts that—in a most entertaining manner, let me assure you— come and ago while playing around within and around these number grids.

Among these trains, one that I jumped on around the past Xmas days was due to reflections on picking out certain among the astronomically many sudoku grids because of specific additional properties, either of the sudoku solution as a whole, or because of special properties of the order 9 permutations that they are made of. In ‘the early days‘ of K7-sudokus such properties were that of what I called the sudoku's drift (for those K7-plays {with a reading that is what we might call the ‘occidental’ or ‘western‘-way: as a left-to-right / top-to-bottom +/- walk} the drift is the difference between between the sudoku-walk's starting point and its end point) and that of its stretch (the difference between the walk's max on the positive side, and its min on the negative side), the details are in one of the early sudoku writings.

This then had me revisit another one of my pre-mutation preoccupations, from a time that sudokus actually were far from my mind, namely that of costas arrays. Would it be possible, I asked myself, to find sudoku solutions in which all row and column permutations, and maybe even the squares' permutations, have the costas property?

It actually appears to be so [1] that, at least up to order 27, for uneven numbers u, the largest number of disjoint costas arrays of order u is less than u. Hence for uneven orders up to 27 there are no full sets of disjoint costas arrays, and therefore no costas latin squares of, in particular, order 9. As a suduko solution is also a latin square, this implies that there are no sudoku solutions where all rows and/or all columns have the costas property.

costas 12-sudokus

But for some even orders we do find such full sets, in particular for the (from a compositional point of view) interesting order 12. The reference [1] gives the (computationally obtained) results that the largest number of disjoint costas arrays of order 12 is 12, and that there are 16,346 costas latin squares. The authors of reference [1] understand a ‘costas latin square’ to be the superposition of the disjoint permutation matrices, which is (sort of) equivalent to a costas latin square in our sense, as taking the disjoint costas arrays as the rows or as the columns of a grid, conserves the latin property of the grid, and obviously the costas property is obtained for, at least, the rows of the grid.

We can design, in (at least) two variants, of what would be a latin square of order 12 that may count as an order 12 sudoku. Here are examples, in the form of color grids. Note that they are (rotationally) equivalent.

Using the fact that (what I called) a cyclic latin square can be made into a sudoku by a permutation of rows or columns (see The Art of K7 :: Südokaising [i]), and the Welch construction of costas arrays (of order q-1 for prime numbers q) that are (what I called) cyclic (‘single periodic’ i.e. cycling them conserves the costas property, see The eerie symmetry of a perfect ping) it is easy to construct a set of order 12 sudokus, such that all of the sudoku's rows or the sudoku's columns have the costas property.

In the sudoku(s) thus obtained from the order 12 costas sequence generated by 2, the smallest primitive root of GF(13), even more than the expected minimal costas arrays popped up. Here are two costas latin squares thus obtained. The initial sequence is the first row in the grids; the latin square on the left then is obtained by cycling to the left, the one on the right by cycling to the right. Each row and each column of the two grids is obtained as cyclic variation of the initial sequence, and all of them therefore have the costas property. (That, though, is obviously not the case for the permutations corrronding to the disjoint permutation matrices of which these grids are the superposition; the grids obtained seem not to be costas latin squares in the sense that term is used by the authors of [1].)

This is the sudoku obtained from the left variant above, by applying the permutation σ(1:12)=(1, 5, 9, 2, 6, 10, 3, 7, 11, 4, 8, 12) to its columns. In this sudoku all columns have the costas property, as do the rectangles, when read column-wise in ‘western way‘, that is, from top-to-bottom, left-to-right. We see e.g. that thus written the first rechtangle linearizes to the initial costas array, and all the others, counted from left-to-right, top-to-bottom, will linearize to the rows of the left variant costas latin square.

The costas arrays that thus make up this 12-sudoku are just the 12 cycles of the initiating exponential Welch costas array. There are, however, two other costas arrays that we can identify in this grid: also the sixth and the twelfth row, (12,5,1,8,11,10,2,3,9,7,4,6) and (1,8,12,5,2,3,11,10,4,6,9,7) are costas arrays. These, however, are not cyclic (single periodic). It is unclear whether these ‘costas appearance’ here is necessary, and a consequence of the construction applied; it actually seems to be a mere coincidence. {{(à voir ...)}}. The same costas arrays appear when we apply the permutation σ(1:12)=(1, 5, 9, 2, 6, 10, 3, 7, 11, 4, 8, 12) to the rows of the left variant (the result of this operation is the transpose of the above grid), to the columns of the right variant, or (in the 5th and 11th column, top to bottom) when we apply the permutation σ(1:12)=(1, 5, 9, 2, 6, 10, 3, 7, 11, 4, 8, 12) to the rows of the right variant. Here the cycles of the initiating exponential Welch costas array make up the rows and the rectangles (read left-to-right, from bottom row to top row) of the sudoku grid.

One feels, of course, that somehow, these four 'costa' sudokus are equivalent. Also the four obtained starting from the costas array generated by 7, the multiplicative inverse modulo 13 of 2 (which is a cyclic variation of the one generated by 2) fall somehow in the same league, though they do not come with the two ‘extra‘ costas permutations that were brought to us by 2 above.

references __ ::
[1] J.H. Dinitz, P.R.J. Östergård, D.R. Stinson (2021). “Packing Costas Arrays” [ ^ ]

---

---

tags: sudokism, permutations, costas permutations, latin squares

# .550.