How to encode a unique board position?

Question

How can I encode a unique board position? Reflections and rotations of a particular board position are not considered unique. For example, the positions below are the same:Board positions My idea was to assign a weightage of 1-4 for each row, the total "weight" of an L-piece would be the sum of the weight of the squares covered by the L-piece. For example, the following L-piece has a weight of 12: Weight How should I proceed from here? Or is there another idea for this? I look forward to reading your answer and sorry if the post is off-topic.

Answer 1

I think it is indeed a good idea to code each square individually, and to then encode pieces on the basis of the codes of the squares they occupy, so you are on the right track. However, because you want the function value to be invariant to mirroring and rotation, I suggest that you encode each square that is the 'same' relative to mirroring and rotation with the same code, e.g.:

\begin{array}{|c|c|c|c|} \hline 1&2&2&1\\ \hline 2&3&3&2\\ \hline 2&3&3&2\\ \hline 1&2&2&1\\ \hline \end{array}

Now, to encode an L-piece, we can code an ordered 4-tuple (the order reflecting a path through the squares occupied by the piece) e.g. to encode the piece you have as an example:

\begin{array}{|c|c|c|c|} \hline 1&2&2&1\\ \hline \color{red}2&\color{red}3&3&2\\ \hline \color{red}2&3&3&2\\ \hline \color{red}1&2&2&1\\ \hline \end{array}

we would code $<1,2,2,3>$, which can be done in various ways, but one way would be to concatenate their two-bit binary numbers into an 8-bit number, e.g. $<1,2,2,3>$ becomes $01101011$, or $107$ in decimal.

Note that the order is important, since if you just pick 4 numbers, say 2,2,3,3, then there are 2 different L-piece positions that are like that:

\begin{array}{|c|c|c|c|} \hline 1&2&2&1\\ \hline \color{red}2&\color{red}3&\color{red}3&2\\ \hline \color{red}2&3&3&2\\ \hline 1&2&2&1\\ \hline \end{array}

\begin{array}{|c|c|c|c|} \hline 1&2&2&1\\ \hline \color{red}2&\color{red}3&3&2\\ \hline 2&\color{red}3&3&2\\ \hline 1&\color{red}2&2&1\\ \hline \end{array}

But with the ordering, these two pieces become $<2,2,3,3>$ and $<2,3,3,2>$ respectively, and hence can be distinguished.

Finally, $<3,2,2,1>$ obviously describes the same piece/position as $<1,2,2,3>$, but to make sure the function is injective, we can simply insist on only using the code that results the lower number, so we would never use $<3,2,2,1>$, but instead use $<1,2,2,3>$. Likewise, we would use $<2,1,2,2>$ but not $<2,2,1,2>$