# Maximize the Magic Square in the Matrix of Ricochet

HELLO, hello everyone, I am Dumb πππ

Today Dumb continues to record the process of Likou brushing questions, which is included in the column algorithm πππ

This column is based on different categories of tags, and each tag is divided into three levels: Easy, Medium, and Hard πππ

All the questions in this part are from LeetCode, and the link to the original LeetCode question is marked under each question πππ

OK, brothers, don’t talk nonsense and go straight to the topic, go ahead πππ

## A π topic description

840. Magic Squares in Matrices

A 3 x 3 magic square is a 3 x 3 matrix filled with different numbers from 1 to 9, where the sum of the numbers in each row, column and both diagonals is equal.

Given a row x col grid of integers, how many 3 × 3 "magic square" submatrices are there? (each sub-matrix is ββcontiguous).

Example 1:

enter: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2] output: 1 explain: The following submatrix is ββa 3 x 3 The magic square: And this one is not: Overall, there is only one 3 in the given matrix for this example x 3 The magic square submatrix of .

Example 2:

output: grid = [[8]] enter: 0

hint:

- row == grid.length
- col == grid[i].length
- 1 <= row, col <= 10
- 0 <= grid[i][j] <= 15

## Two π Thoughts to solve the problem

#### 2.1 π Key information

The first step in solving the problem is of course to extract the key information of the title literal πππ

A 3 x 3 magic square is a 3 x 3 matrix of different numbers from 1 to 9, the sum of each row, column and two diagonals is equal. Given a matrix, find how many 3 × 3 magic square submatrices are in it

From the title, it is easy to know that the 3 × 3 magic square must be a different number from 1 to 9 (the first time the error is solved and it is greater than 9, the review must be careful πππ)

For a 3 × 3 magic square, its central element must be 5, so when traversing the input matrix, only the central element needs to be traversed, so the loop condition is [ 1 , len - 1 )

After extracting the key information in the topic, go directly to the second stage and organize your thoughts πππ

#### 2.2 π Organize ideas

Brute Force: Check each 3x3 grid separately

For each grid, all numbers must be different and between 1 and 9, and the sum of each row, column, and diagonal must be the same π·π·π·

nitty gritty:

β When traversing the input matrix, you only need to traverse the central element

β‘ When the judgment numbers must be different and are between 1 and 9, the maximum value only needs to be in [ 1 , 9 ]

Rotation method: the third-order magic square solution is fixed, and there are the following eight types

The common points of the eight solutions are that the middle elements are five, the corner elements are all even numbers, and the midpoints are all odd numbers. The solution of the same row can be obtained by rotation, the first row is mirrored, and the second row can be obtained. In other words, there is only one solution to the third-order magic square, and the rest are the reflections of rotating mirror images

implement logic

1. According to the above, only when the central element is five, can it be judged whether it is a magic square

2. At this time, you only need to compare the remaining eight elements. Due to the rotation invariant property of the solution, store the eight elements in order to facilitate later comparison. The order is as shown in the figure below

3. How to rotate the mirror image, refer to this 189. Rotate array The idea of ββββputting the front part to the back can achieve the rotation effect, and the mirror image only needs to iterate in reverse

4. In the second step, compare the first element of the input array with 8 6 2 4 one by one, take out the two solutions of the forward mirror image from the target array and compare whether it is one, and then determine whether it is a magic square πππ

Note: source of rotation , with some deletions

After sorting out the problem-solving ideas, directly enter the third stage, and the code is realized πππ

## Three π code explanation

#### 3.1 π Code implementation

According to our idea of ββbreaking the problem just now, let’s go directly to the code ππππ

bool isMagic(std::vector<int>& tmpVec) { for (int targetIndex = 0; targetIndex < 8; targetIndex += 2) { //Iterate through the temporary array if (tmpVec[0] == targetVec[targetIndex]) { //The first element of the input array is compared with 8 6 2 4 one by one //Take out the forward mirroring two solutions from the target array and compare whether it is one return tmpVec == std::vector<int>(targetVec.begin() + targetIndex, targetVec.begin() + targetIndex + 8) || tmpVec == std::vector<int>(targetVec.rbegin() + 7 - targetIndex, targetVec.rbegin() + 15 - targetIndex); } } return false; } //Initialize target array std::vector<int> targetVec = { 8, 1, 6, 7, 2, 9, 4, 3, 8, 1, 6, 7, 2, 9, 4, 3 }; int numMagicSquaresInside(std::vector<std::vector<int>>& grid) { //Initialize matrix x-axis, y-axis corresponds to offset std::vector<std::pair<int, int>> offsetVals = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 } }; //Initialize the return value, row and column length int count = 0, rows = grid.size() - 1, columns = grid[0].size() - 1; //Initialize the temporary array std::vector<int> tmpVec(8); for (int i = 1; i < rows; ++i) { //iterate over rows for (int j = 1; j < columns; ++j) { //iterate over columns if (grid[i][j] == 5) { //If the central element is 5 for (int index = 0; index < 8; ++index) { tmpVec[index] = grid[i + offsetVals[index].first][j + offsetVals[index].second]; //places the eight elements centered at i,j in a tmpVec } count += isMagic(tmpVec); //and determine whether it is a magic square } } } return count; //return result }

#### 3.2 π Detailed analysis

After reading πππ full-annotated version of the code implementation, I believe that the general logic is capitalized OK. πππ

Then we dig out the obscure details of the above implementation πππ to analyze it, start working directly, and walk up ππππ

targetIndex += 2

The first element of the input array (tmpVec) is compared with 8 6 2 4 one by one, so the index moves by two places π³π³π³

tmpVec == std::vector<int>(targetVec.begin() + i , targetVec.begin() + i + 8);

Rotation logic: After finding the target position, move eight bits from the current position to the current position (positive direction)

tmpVec == std::vector<int>(targetVec.rbegin() + 7 - i, targetVec.rbegin() + 15 - i);

Mirror logic: After finding the target position, from reverse iteration 7 - i to reverse iteration 15 - i (reverse) πΌπΌπΌ

//For example to find the first 2, for mirroring it is [ 2, 7, 6, 1, 8, 3, 4, 9 ] //That is, the distance of 3, 4, 9, 2 of reverse iteration 7 - 4 = 3 (targetVec.rbegin() + 7 - i) [ 8, 1, 6, 7, 2, 9, 4, 3, 8, 1, 6, 7, 2, 9, 4, 3 ]

## Four π mental journey

In order to make it easier for readers to understand the blogger’s real process of brushing questions, I have restored the pure and true state at that time and recorded it in the section of mental journey. Those who are not interested can skip it directly.

There is no problem for bloggers to extract π key information in the first stage, and there is no problem in organizing π ideas in the second stage

The code was implemented using a violent solution (the solution to the problem on the official website is the same as violence, and the rotation method is really hard to imagine), the simplicity is poor πππ, the code is as follows ππππ

int numMagicSquaresInside(vector<vector<int>>& grid) { int count = 0; int width = grid.size(), high = grid[0].size(); for (int i = 1; i < width - 1; ++i) { //Iterate over the width of the 2D input for (int j = 1; j < high - 1; ++j) { if (grid[i][j] != 5) continue; if (grid[i-1][j] == grid[i][j]) continue; //Each value is different //horizontal summation if (grid[i-1][j-1] + grid[i][j-1] + grid[i+1][j-1] != 15) continue; if (grid[i-1][j] + grid[i][j] + grid[i + 1][j] != 15) continue; if (grid[i-1][j+1] + grid[i][j+1] + grid[i+1][j+1] != 15) continue; //vertical sum if (grid[i-1][j-1] + grid[i-1][j] + grid[i-1][j+1] != 15) continue; if (grid[i][j-1] + grid[i][j] + grid[i][j+1] != 15) continue; if (grid[i+1][j-1] + grid[i+1][j] + grid[i+1][j+1] != 15) continue; //Diagonal sum if (grid[i-1][j-1] + grid[i][j] + grid[i+1][j+1] != 15) continue; if (grid[i-1][j+1] + grid[i][j] + grid[i+1][j-1] != 15) continue; //find the maximum and minimum legalScope int mem_max = std::max({grid[i-1][j-1], grid[i][j-1], grid[i+1][j-1], grid[i-1][j], grid[i][j], grid[i+1][j], grid[i-1][j+1], grid[i][j+1], grid[i+1][j+1]}); int mem_min = std::min({grid[i-1][j-1], grid[i][j-1], grid[i+1][j-1], grid[i-1][j], grid[i][j], grid[i+1][j], grid[i-1][j+1], grid[i][j+1], grid[i+1][j+1]}); if (mem_max <= 9 && mem_min >= 1) ++count; } } return count; }

## Five π Conclusion

In this impetuous society, but have the patience to see this, you must be a very powerful person πππ

If you think the article is helpful, don’t forget to like + follow, your encouragement is my biggest motivation

The blogger will continue to update more high-quality content, come on! Technician! πͺπͺπͺ