Rust

I'd agree with another comment that this is generally overthinking it. Are you planning on expanding this game to accommodate other features and that's why being deliberate about this memory model is important? How much time are you planning on doing this in? Ask yourself questions about your goals before diving into a solution.

A simple vector seems fine. Each item in the vector is an enum representing cell state. You can translate x y coordinates to an index pretty easily.

Ideally, all of these values should be represented in memory exactly the same way:

If they are represented in the exact same way, only one of them would be able to appear in the game - so which one is it? I think that seems quite strange for a tic tac toe game.

2. The ordering of each row should not matter.

This is true for your abstracted rows, but is maintaining eight sets of three square states, two or three of which must be updated with every move, really a better model than a single sequence of nine, where only one needs to change at a time? It's more complex to think about, and is less efficient to update. When you throw in steps to canonicalize the rotation and reflection, which may produce different transformations from the input/output grid on the first three moves, you may need to change even more set items with each move.

It's true that, mathematically, the mapping from grid to sequence is arbitrary and the only thing that matters is consistency, but if you view programming languages as a way to communicate with humans, then clarity of purpose, rather than mathematical idealism, should be your goal. Use a nine-item array or a three-by-three nested array for the underlying storage and treat your eight win-checking sets as views into that more ordered structure. These views could well be functions that return a set and are themselves held in a set to be applied in any order. Similarly, treat canonicalization as another way to view the underlying board.

You could sidestep the mutable borrowing by not mutating individual squares. Take a leaf from the functional-programming books and use a function that takes a board and a move and returns an entirely new board. Or takes a board and returns one of the abstracted row sets. There are only nine squares and nine moves. The win-checking views aren't needed before move six. A bit of copying isn't going be a problem.

Why does the way you present the data change how the memory is managed? I think you are mixing data storage with display logic.

We need to choose something which most closely represents the data.

Why do you need to do that? You do not have to choose the optimal memory model to code a Tic Tac Toe game.

A Vec works fine, and is also simple to understand (so it is maintainable).

If you invent your own complex data structure for the Tic Tac Toe you trade maintainability for.. what gain?

How to build a grid whose orientation does not matter?

The orientation is how you iterate on your grid. If you iterate from first element to last element on X-axis, you have the "normal" orientation. If you iterate from last to first, you have the Y-symmetrical orientation.

A 2D array is already a grid whose orientation does not matter. No need to over-complexify this.

If you want to be picky, you could say that you want a grid with optimal performance. Meaning that your data should be contiguous (ideally, your data should be in the same cache line to prevent cache misses).

If you start playing with complex data structures with lots of pointer indirections and such, your performance will go down, your code will be more complex to understand, and will (certainly) be bigger in memory. You will lose in both maintainability, performance and size.

A single vector of 9 elements is enough, really.

Do you care about modeling the cells? If not, you could represent each row with just a number. When X plays, add 1 to all the rows that include the position they played, and when O plays, subtract 1. If any row reaches +3 or -3, that player wins.

As for rotation/reflection invariance, that seems more like a math problem than a Rust problem.

I agree with others that this is drastically overthinking it. If you want to take a fancier approach, I'd recommend taking inspiration from chess. You can represent the board using two numbers: X/O, and set/unset (you can combine these into one number even since it'd be a total of 9 * 2 = 18 bits). For checking if a player has won, you could have numbers representing winning boards, and do some math to determine which player has won.

Here's a quick proof of concept.

Edit: And for fun, here's with a nice looking board! macro.

Ideally, all of these values should be represented in memory exactly the same way:

That would make the game hard to play, since you'd have to think about where your move would end up since it won't stay on the cell you click.

I think you're wanting to store them that way so that you can easily check for win conditions, maybe? But that's the wrong approach. Store the cells as they appear to the player, in a 2d Array (or 1d Array with indexing math. That's how I'd do it).

Then you can take advantage of symmetries in your win condition code, if you like. But it really couldn't be much simpler than counting the matching cells in each row, column, and diagonal. That's just 8 groups of 3.

Having thought about this some more with practicality and clarity thrown out the window in favour of abstractions, how about this?

A game is a sequence of moves. Past moves are immutable, future moves unknowable; a singly linked list fits the bill here.

Each move consists of a player token and a position. The position might ordinarily be thought of as a grid index but, as you point out, it could just as well be membership in one of the potentially winning lines. Either a move is part of one of these lines or it isn't. This makes the position equivalent to a bit field. If each potential win line is distinct, they could indeed be held sparsely in a set.

Checking for a win then consists of counting player tokens for each potential win line and checking for crossing the necessary threshold. Filter, sum, max, greater than?, any?

I think this scheme would be applicable to arbitrary game boards, with none of it requiring mutation. Is that the kind of thing you were after? The reflection/rotation equivalence isn't present here, but I still think that's more an artefact of analysis, rather than a property of gameplay.