Problem 741

[roosephu]

Hello, can anyone explain a little bit about "unique up to rotations and reflections"? I don't really understand it.

My current understanding is that two colorings are the same iff there exists a sequence of rotations/reflections (can be applied to both rows and columns) which turns one to another. However, my brute-force solutions only finds 8 unique colorings for g(4), which are

Code: Select all

===
1100
1100
0011
0011
===
1100
1010
0101
0011
===
1010
1100
0101
0011
===
1100
0110
1001
0011
===
0110
1100
1001
0011
===
1100
0011
1100
0011
===
1010
1010
0101
0101
===
1010
0101
1010
0101

I'd appreciate it if anyone can show an example of a missing coloring from above.

Thanks!

[roosephu]

I realized that *rotation* here doesn't mean rotating rows/columns (like numpy.roll), but probably rotating the grid for 90 degrees (like numpy.rot90).

[amagri]

Yes indeed, rotations are centered on the center of the grid with angles Pi/2, Pi or 3Pi/2.
Good luck!

[Bashar_AL-Rfooh]

Hi I am really confused about reflections and rotations if some one can verify for me how many unique and repeated pattern are there in 3 * 3 matrix I will be thankful

[philiplu]

Hi I am really confused about reflections and rotations if some one can verify for me how many unique and repeated pattern are there in 3 * 3 matrix I will be thankful

Let me see if it helps to explain a bit more before giving out hint numbers. Consider the following 3x3 matrices:

$
\begin{pmatrix} 1&2&3 \\ 4&5&6 \\ 7&8&9 \end{pmatrix}
\begin{pmatrix} 7&4&1 \\ 8&5&2 \\ 9&6&3 \end{pmatrix}
\begin{pmatrix} 9&8&7 \\ 6&5&4 \\ 3&2&1 \end{pmatrix}
\begin{pmatrix} 3&6&9 \\ 2&5&8 \\ 1&4&7 \end{pmatrix}
\\
\begin{pmatrix} 3&2&1 \\ 6&5&4 \\ 9&8&7 \end{pmatrix}
\begin{pmatrix} 9&6&3 \\ 8&5&2 \\ 7&4&1 \end{pmatrix}
\begin{pmatrix} 7&8&9 \\ 4&5&6 \\ 1&2&3 \end{pmatrix}
\begin{pmatrix} 1&4&7 \\ 2&5&8 \\ 3&6&9 \end{pmatrix}
$

"Up to rotations and reflections", those are all the same matrix. Start with the upper left matrix, then pick it up and rotate it 90 degrees clockwise at a time, and you'll get the other 3 on that row. The lower left matrix is just the upper left one, flipped across the vertical axis of the middle column. That's a reflection. You can then take that reflected matrix, and rotate it 90 degrees clockwise at a time to get the other 3 on the second row. So there are 8 ways to move this matrix around, and still have fundamentally the same matrix.

[Bashar_AL-Rfooh]

Hi I am really confused about reflections and rotations if some one can verify for me how many unique and repeated pattern are there in 3 * 3 matrix I will be thankful

Let me see if it helps to explain a bit more before giving out hint numbers. Consider the following 3x3 matrices:

$
\begin{pmatrix} 1&2&3 \\ 4&5&6 \\ 7&8&9 \end{pmatrix}
\begin{pmatrix} 7&4&1 \\ 8&5&2 \\ 9&6&3 \end{pmatrix}
\begin{pmatrix} 9&8&7 \\ 6&5&4 \\ 3&2&1 \end{pmatrix}
\begin{pmatrix} 3&6&9 \\ 2&5&8 \\ 1&4&7 \end{pmatrix}
\\
\begin{pmatrix} 3&2&1 \\ 6&5&4 \\ 9&8&7 \end{pmatrix}
\begin{pmatrix} 9&6&3 \\ 8&5&2 \\ 7&4&1 \end{pmatrix}
\begin{pmatrix} 7&8&9 \\ 4&5&6 \\ 1&2&3 \end{pmatrix}
\begin{pmatrix} 1&4&7 \\ 2&5&8 \\ 3&6&9 \end{pmatrix}
$

"Up to rotations and reflections", those are all the same matrix. Start with the upper left matrix, then pick it up and rotate it 90 degrees clockwise at a time, and you'll get the other 3 on that row. The lower left matrix is just the upper left one, flipped across the vertical axis of the middle column. That's a reflection. You can then take that reflected matrix, and rotate it 90 degrees clockwise at a time to get the other 3 on the second row. So there are 8 ways to move this matrix around, and still have fundamentally the same matrix.

Thanks, I understood rotations and reflections right now my problem is to understand the difference between the unique solutions and the repeated ones when we consider the solution unique

[DJohn]

The problem is asking how many equivalence classes there are, under the equivalence relation "the same after some rotation or reflection". So: take all of the grids that satisfy the conditions, and sort them into groups. Two grids will be assigned to the same group if one is a rotation or reflection of the other. Then count the groups.
Since this is Project Euler, actually carrying out that process is likely to be impractical. The challenge is to find an efficient method that produces the same number.