We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This takes the strategy which does not use predefined "Solution table" for num combination of magic square.
Strategy:
For being correct magic square matrix,
the center is 5 and the four corner's number is {8, 6, 2, 4} or {8, 4, 2, 6} clockwisely.
And the sum of any edge (three nums forming the edge) is 15.
Explanation:
We need four combinations with equivalent sum values, excluding the central number.
example: {if center is 1, combination:{2,9},{3,8},{4,7},{5,6}}
So the candidates of the center is 1,5, or 9.
On selecting the center, If we choose a number that is too large or too small, we would notice that the sum of the numbers in adjacent corners will be too small or too large.
example: {if center is 1, adjacent corner pair {9,8} or {9 ,7} exists}
So the center is 5.
Adjacent corner pair selectin rule applies to selection the four corner, and desirable four number combination is {8, 6, 2, 4} or {8, 4, 2, 6} clockwisely.
When above 5 number is put in matrix, we can see that the edge sum is 15.
intformingMagicSquare(vector<vector<int>>s){// constancesconstexprarray<array<int,4>,2>magic_corner_nums{{{8,6,2,4},{8,4,2,6}}};constexprintSUM_OF_EDGE{15};// utilitiesautodeep_copy{[](vector<vector<int>>&matrix){vector<vector<int>>copied{};for(constauto&row:matrix){copied.push_back(row);}returncopied;}};autofind_next_corner_clockwisely{[](intr_i,intc_i)->pair<int,int>{switch((r_i<<1)+c_i){case0:return{0,2};break;case2:return{2,2};break;case6:return{2,0};break;case4:return{0,0};break;default:throwinvalid_argument{"cannot find the next"};}}};autoaverage_2{[](intx,inty){return(x+y)/2;}};// returned valueintmin_cost{numeric_limits<int>::max()};// convert the center of square to 5 if it isn'tintcost{0};if(s[1][1]!=5){cost=abs(5-s[1][1]);s[1][1]=5;}// find the largest of the four corner and treat it as start positionpair<int,int>start_pos{0,0};for(autopos{find_next_corner_clockwisely(start_pos.first,start_pos.second)};pos.first!=0||pos.second!=0;pos=find_next_corner_clockwisely(pos.first,pos.second)){intnum{s[pos.first][pos.second]};if(num>s[start_pos.first][start_pos.second])start_pos=pos;}for(constauto&mcn:magic_corner_nums){for(autopos{start_pos};;){intcurrent_cost{cost};autocp_s{deep_copy(s)};// assign the number of magic square corner to// the matrix's corner and calc the current costinti_mcn{0};for(autopos_dash{pos};;){current_cost+=abs(mcn[i_mcn]-cp_s[pos_dash.first][pos_dash.second]);if(current_cost>min_cost)gotomiddle_loop_next;cp_s[pos_dash.first][pos_dash.second]=mcn[i_mcn];++i_mcn;pos_dash=find_next_corner_clockwisely(pos_dash.first,pos_dash.second);if(pos_dash==pos)break;}// calc the cost for converting the number in the center// of the edgefor(autopos_dash{pos};;){autonext{find_next_corner_clockwisely(pos_dash.first,pos_dash.second)};intdesired_value{SUM_OF_EDGE-cp_s[pos_dash.first][pos_dash.second]-cp_s[next.first][next.second]};intr_c_edge{average_2(pos_dash.first,next.first)};intc_c_edge{average_2(pos_dash.second,next.second)};current_cost+=abs(desired_value-cp_s[r_c_edge][c_c_edge]);if(current_cost>min_cost)gotomiddle_loop_next;cp_s[r_c_edge][c_c_edge]=desired_value;pos_dash=next;if(pos_dash==pos)break;}// update min costmin_cost=current_cost;middle_loop_next:pos=find_next_corner_clockwisely(pos.first,pos.second);if(pos==start_pos)break;}}returnmin_cost;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Forming a Magic Square
You are viewing a single comment's thread. Return to all comments →
c++ solution.
This takes the strategy which does not use predefined "Solution table" for num combination of magic square.
Strategy:
For being correct magic square matrix,
the center is 5 and the four corner's number is {8, 6, 2, 4} or {8, 4, 2, 6} clockwisely.
And the sum of any edge (three nums forming the edge) is 15.
Explanation:
We need four combinations with equivalent sum values, excluding the central number.
example: {if center is 1, combination:{2,9},{3,8},{4,7},{5,6}}
So the candidates of the center is 1,5, or 9.
On selecting the center, If we choose a number that is too large or too small, we would notice that the sum of the numbers in adjacent corners will be too small or too large.
example: {if center is 1, adjacent corner pair {9,8} or {9 ,7} exists}
So the center is 5.
Adjacent corner pair selectin rule applies to selection the four corner, and desirable four number combination is {8, 6, 2, 4} or {8, 4, 2, 6} clockwisely.
When above 5 number is put in matrix, we can see that the edge sum is 15.