Magnet Puzzle
The puzzle game Magnets involves placing a set of domino-shaped magnets (or electrets or other polarized objects) in a subset of slots on a board so as to satisfy a set of constraints. For example, the puzzle on the left has the solution shown on the right:
Each slot contains either a blank entry (indicated by ‘x’s), or a “magnet” with a positive and negative end. The numbers along the left and top sides show the numbers of ‘+’ squares in particular rows or columns. Those along the right and bottom show the number of ‘-’ signs in particular rows or columns. Rows and columns without a number at one or both ends are unconstrained as to the number of ‘+’ or ‘-’ signs, depending on which number is not present. In addition to fulfilling these numerical constraints, a puzzle solution must also satisfy the constraint that no two orthogonally touching squares may have the same sign (diagonally joined squares are not constrained). You are given top[], bottom[], left[], right[] arrays indicates the count of + or – along the top(+), bottom(-), left(+) and right(-) edges respectively. Values of -1 indicate any number of + and – signs. Also given matrix rules[][] contain any one T, B, L or R characters. For a vertical slot in the board, T indicates its top end and B indicates the bottom end. For a horizontal slot in the board, L indicates left end and R indicates the right end.
Examples:
Input : M = 5, N = 6
top[] = { 1, -1, -1, 2, 1, -1 }
bottom[] = { 2, -1, -1, 2, -1, 3 }
left[] = { 2, 3, -1, -1, -1 }
right[] = { -1, -1, -1, 1, -1 }
rules[][] = { { L, R, L, R, T, T },
{ L, R, L, R, B, B },
{ T, T, T, T, L, R },
{ B, B, B, B, T, T },
{ L, R, L, R, B, B }};
Output : + - + - X -
- + - + X +
X X + - + -
X X - + X +
- + X X X -
Input : M = 4, N = 3
top[] = { 2, -1, -1 }
bottom[] = { -1, -1, 2 }
left[] = { -1, -1, 2, -1 }
right[] = { 0, -1, -1, -1 }
rules[][] = { { T, T, T },
{ B, B, B },
{ T, L, R },
{ B, L, R } };
Output : + X +
– X –
+ – +
– + –
We can solve this problem using Backtracking.
C++
// Write Python3 code here #include<bits/stdc++.h> using namespace std; bool checkConstraints(vector<vector< char >> &rules){ int M = 5; int N = 6; vector< int > top = { 1, -1, -1, 2, 1, -1 }; vector< int > bottom = {2, -1, -1, 2, -1, 3 }; vector< int > left = {2, 3, -1, -1, -1}; vector< int > right = {-1, -1, -1, 1, -1}; vector< int > pCountH(rules.size(), 0); vector< int > nCountH(rules.size(), 0); for ( int row = 0; row < rules.size(); row++){ for ( int col = 0; col < rules[0].size(); col++){ char ch = rules[row][col]; if (ch == '+' ){ pCountH[row] += 1; } else if (ch == '-' ){ nCountH[row] += 1; } } } vector< int > pCountV(rules[0].size(), 0); vector< int > nCountV(rules[0].size(), 0); for ( int col = 0; col < rules[0].size(); col++){ for ( int row = 0; row < rules.size(); row++){ char ch = rules[row][col]; if (ch == '+' ){ pCountV[col] += 1; } else if (ch == '-' ){ nCountV[col] += 1; } } } for ( int row = 0; row < rules.size(); row++){ if (left[row] != -1){ if (pCountH[row] != left[row]){ return false ; } } if (right[row] != -1){ if (nCountH[row] != right[row]){ return false ; } } } for ( int col = 0; col < rules[0].size(); col++){ if (top[col] != -1){ if (pCountV[col] != top[col]){ return false ; } } if (bottom[col] != -1){ if (nCountV[col] != bottom[col]){ return false ; } } // if (top[col] != -1 and pCountH[col] != top[col]) or (bottom[col] != -1 and nCountH[col] != bottom[col]) : // return False } return true ; } bool canPutPatternHorizontally(vector<vector< char >> &rules, int i, int j, string pat){ if ( j-1>=0 and rules[i][j-1] == pat[0]){ return false ; } else if (i-1>=0 and rules[i-1][j] == pat[0]){ return false ; } else if (i-1>=0 and rules[i-1][j+1] == pat[1]){ return false ; } else if (j+2 < rules[0].size() and rules[i][j+2] == pat[1]){ return false ; } return true ; } bool canPutPatternVertically(vector<vector< char >> &rules, int i, int j, string pat){ if ( j-1>=0 and rules[i][j-1] == pat[0]){ return false ; } else if (i-1>=0 and rules[i-1][j] == pat[0]){ return false ; } else if (j+1 < rules[0].size() and rules[i][j+1] == pat[0]){ return false ; } return true ; } void solveMagnets(vector<vector< char >> &rules, int i, int j){ // check the constraint before printing if ( i == rules.size() and j == 0){ if (checkConstraints(rules)){ // Printing rules array. cout << "[" ; for ( int indxi = 0; indxi < rules.size(); indxi++){ cout << "[" ; for ( int indxj = 0; indxj < rules[0].size(); indxj++){ cout << "'" << rules[indxi][indxj] << "', " ; } cout << "]" ; } cout << "]" ; } } else if (j >= rules[0].size()){ solveMagnets(rules, i+1, 0); } // normal cases else { if (rules[i][j] == 'L' ){ // option 1 +- if (canPutPatternHorizontally(rules,i,j, "+-" )){ rules[i][j] = '+' ; rules[i][j+1] = '-' ; solveMagnets(rules,i,j+2); rules[i][j] = 'L' ; rules[i][j+1] = 'R' ; } // option 2 -+ if (canPutPatternHorizontally(rules,i,j, "-+" )){ rules[i][j] = '-' ; rules[i][j+1] = '+' ; solveMagnets(rules,i,j+2); rules[i][j] = 'L' ; rules[i][j+1] = 'R' ; } // option 3 xx if ((1 == 1) || canPutPatternHorizontally(rules,i,j, "xx" )){ rules[i][j] = 'x' ; rules[i][j+1] = 'x' ; solveMagnets(rules,i,j+2); rules[i][j] = 'L' ; rules[i][j+1] = 'R' ; } } // vertical check else if (rules[i][j] == 'T' ){ // option 1 +- if (canPutPatternVertically(rules,i,j, "+-" )){ rules[i][j] = '+' ; rules[i+1][j] = '-' ; solveMagnets(rules,i,j+1); rules[i][j] = 'T' ; rules[i+1][j] = 'B' ; } // option 2 -+ if (canPutPatternVertically(rules,i,j, "-+" )){ rules[i][j] = '-' ; rules[i+1][j] = '+' ; solveMagnets(rules,i,j+1); rules[i][j] = 'T' ; rules[i+1][j] = 'B' ; } // option 3 xx if ((1 == 1) or canPutPatternVertically(rules,i,j, "xx" )){ rules[i][j] = 'x' ; rules[i+1][j] = 'x' ; solveMagnets(rules,i,j+1); rules[i][j] = 'T' ; rules[i+1][j] = 'B' ; } } else { solveMagnets(rules,i,j+1); } } } void doTheStuff(vector<vector< char >> &rules, int i, int j){ if (rules[i][j] == 'L' || rules[i][j] == 'R' ){ // option 1 +- if (canPutPatternHorizontally(rules, i, j , "+-" )){ rules[i][j] = '+' ; rules[i][j+1] = '-' ; solveMagnets(rules,i,j); } // option 2 -+ // option 3 xx } } // Driver code int main(){ vector<vector< char >> rules = { { 'L' , 'R' , 'L' , 'R' , 'T' , 'T' }, { 'L' , 'R' , 'L' , 'R' , 'B' , 'B' }, { 'T' , 'T' , 'T' , 'T' , 'L' , 'R' }, { 'B' , 'B' , 'B' , 'B' , 'T' , 'T' }, { 'L' , 'R' , 'L' , 'R' , 'B' , 'B' } }; solveMagnets(rules,0,0); } // The code is contributed by Gautam goel. |
Java
// java code implementation import java.util.*; import java.lang.*; import java.io.*; import java.util.stream.*; public class Main { public static boolean canPutPatternHorizontally( char [][] rules, int i, int j, char [] pat){ if ( j- 1 >= 0 && rules[i][j- 1 ] == pat[ 0 ]){ return false ; } else if (i- 1 >= 0 && rules[i- 1 ][j] == pat[ 0 ]){ return false ; } else if (i- 1 >= 0 && rules[i- 1 ][j+ 1 ] == pat[ 1 ]){ return false ; } else if (j+ 2 < rules[ 0 ].length && rules[i][j+ 2 ] == pat[ 1 ]){ return false ; } return true ; } public static boolean checkConstraints( char [][] rules){ int M = 5 ; int N = 6 ; int [] top = { 1 , - 1 , - 1 , 2 , 1 , - 1 }; int [] bottom = { 2 , - 1 , - 1 , 2 , - 1 , 3 }; int [] left = { 2 , 3 , - 1 , - 1 , - 1 }; int [] right = {- 1 , - 1 , - 1 , 1 , - 1 }; int [] pCountH = new int [rules.length]; for ( int i= 0 ; i < rules.length; i++){ pCountH[i] = 0 ; } int [] nCountH = new int [rules.length]; for ( int i = 0 ; i < rules.length; i++){ nCountH[i] = 0 ; } for ( int row = 0 ; row < rules.length; row++){ for ( int col = 0 ; col < rules[ 0 ].length; col++){ char ch = rules[row][col]; if (ch == '+' ){ pCountH[row] += 1 ; } else if (ch == '-' ){ nCountH[row] += 1 ; } } } int [] pCountV = new int [rules[ 0 ].length]; for ( int i= 0 ; i < rules[ 0 ].length; i++){ pCountV[i] = 0 ; } int [] nCountV = new int [rules[ 0 ].length]; for ( int i = 0 ; i < rules[ 0 ].length; i++){ nCountV[i] = 0 ; } for ( int col = 0 ; col < rules[ 0 ].length; col++){ for ( int row = 0 ; row < rules.length; row++){ char ch = rules[row][col]; if (ch == '+' ){ pCountV[col] += 1 ; } else if (ch == '-' ){ nCountV[col] += 1 ; } } } for ( int row = 0 ; row < rules.length; row++){ if (left[row] != - 1 ){ if (pCountH[row] != left[row]){ return false ; } } if (right[row] != - 1 ){ if (nCountH[row] != right[row]){ return false ; } } } for ( int col = 0 ; col < rules[ 0 ].length; col++){ if (top[col] != - 1 ){ if (pCountV[col] != top[col]){ return false ; } } if (bottom[col] != - 1 ){ if (nCountV[col] != bottom[col]){ return false ; } } // if (top[col] != -1 and pCountH[col] != top[col]) or (bottom[col] != -1 and nCountH[col] != bottom[col]) : // return False } return true ; } public static boolean canPutPatternVertically( char [][] rules, int i, int j, char [] pat){ if ( j- 1 >= 0 && rules[i][j- 1 ] == pat[ 0 ]){ return false ; } else if (i- 1 >= 0 && rules[i- 1 ][j] == pat[ 0 ]){ return false ; } else if (j+ 1 < rules[ 0 ].length && rules[i][j+ 1 ] == pat[ 0 ]){ return false ; } return true ; } public static void solveMagnets( char [][] rules, int i, int j){ // check the constraint before printing if ( i == rules.length && j == 0 ){ if (checkConstraints(rules)){ // Printing rules array. System.out.print( "[" ); for ( int indxi = 0 ; indxi < rules.length; indxi++){ System.out.print( "[" ); for ( int indxj = 0 ; indxj < rules[ 0 ].length; indxj++){ System.out.print( "'" + rules[indxi][indxj] + "', " ); } System.out.print( "]" ); } System.out.print( "]" ); } } else if (j >= rules[ 0 ].length){ solveMagnets(rules, i+ 1 , 0 ); } // normal cases else { if (rules[i][j] == 'L' ){ // option 1 +- if (canPutPatternHorizontally(rules,i,j, "+-" .toCharArray()) == true ){ rules[i][j] = '+' ; rules[i][j+ 1 ] = '-' ; solveMagnets(rules,i,j+ 2 ); rules[i][j] = 'L' ; rules[i][j+ 1 ] = 'R' ; } // option 2 -+ if (canPutPatternHorizontally(rules,i,j, "-+" .toCharArray()) == true ){ rules[i][j] = '-' ; rules[i][j+ 1 ] = '+' ; solveMagnets(rules,i,j+ 2 ); rules[i][j] = 'L' ; rules[i][j+ 1 ] = 'R' ; } // option 3 xx if (( 1 == 1 ) || canPutPatternHorizontally(rules,i,j, "xx" .toCharArray()) == true ){ rules[i][j] = 'x' ; rules[i][j+ 1 ] = 'x' ; solveMagnets(rules,i,j+ 2 ); rules[i][j] = 'L' ; rules[i][j+ 1 ] = 'R' ; } } // vertical check else if (rules[i][j] == 'T' ){ // option 1 +- if (canPutPatternVertically(rules,i,j, "+-" .toCharArray()) == true ){ rules[i][j] = '+' ; rules[i+ 1 ][j] = '-' ; solveMagnets(rules,i,j+ 1 ); rules[i][j] = 'T' ; rules[i+ 1 ][j] = 'B' ; } // option 2 -+ if (canPutPatternVertically(rules,i,j, "-+" .toCharArray()) == true ){ rules[i][j] = '-' ; rules[i+ 1 ][j] = '+' ; solveMagnets(rules,i,j+ 1 ); rules[i][j] = 'T' ; rules[i+ 1 ][j] = 'B' ; } // option 3 xx if (( 1 == 1 ) || canPutPatternVertically(rules,i,j, "xx" .toCharArray()) == true ){ rules[i][j] = 'x' ; rules[i+ 1 ][j] = 'x' ; solveMagnets(rules,i,j+ 1 ); rules[i][j] = 'T' ; rules[i+ 1 ][j] = 'B' ; } } else { solveMagnets(rules,i,j+ 1 ); } } } public static void doTheStuff( char [][] rules, int i, int j){ if (rules[i][j] == 'L' || rules[i][j] == 'R' ){ // option 1 +- if (canPutPatternHorizontally(rules, i, j , "+-" .toCharArray()) == true ){ rules[i][j] = '+' ; rules[i][j+ 1 ] = '-' ; solveMagnets(rules,i,j); } // option 2 -+ // option 3 xx } } public static void main(String[] args) { char [][] rules = { { 'L' , 'R' , 'L' , 'R' , 'T' , 'T' }, { 'L' , 'R' , 'L' , 'R' , 'B' , 'B' }, { 'T' , 'T' , 'T' , 'T' , 'L' , 'R' }, { 'B' , 'B' , 'B' , 'B' , 'T' , 'T' }, { 'L' , 'R' , 'L' , 'R' , 'B' , 'B' } }; solveMagnets(rules, 0 , 0 ); } } // The code is contributed by Nidhi goel. |
Python3
# Write Python3 code here M = 5 N = 6 top = [ 1 , - 1 , - 1 , 2 , 1 , - 1 ] bottom = [ 2 , - 1 , - 1 , 2 , - 1 , 3 ] left = [ 2 , 3 , - 1 , - 1 , - 1 ] right = [ - 1 , - 1 , - 1 , 1 , - 1 ] rules = [["L","R","L","R","T","T" ], [ "L","R","L","R","B","B" ], [ "T","T","T","T","L","R" ], [ "B","B","B","B","T","T" ], [ "L","R","L","R","B","B" ]]; def canPutPatternHorizontally(rules,i,j,pat): if j - 1 > = 0 and rules[i][j - 1 ] = = pat[ 0 ]: return False elif i - 1 > = 0 and rules[i - 1 ][j] = = pat[ 0 ]: return False elif i - 1 > = 0 and rules[i - 1 ][j + 1 ] = = pat[ 1 ]: return False elif j + 2 < len (rules[ 0 ]) and rules[i][j + 2 ] = = pat[ 1 ]: return False return True def canPutPatternVertically(rules,i,j,pat): if j - 1 > = 0 and rules[i][j - 1 ] = = pat[ 0 ]: return False elif i - 1 > = 0 and rules[i - 1 ][j] = = pat[ 0 ]: return False elif j + 1 < len (rules[ 0 ]) and rules[i][j + 1 ] = = pat[ 0 ]: return False return True def doTheStuff(rules,i,j): if rules[i][j] = = "L" or rules[i][j] = = "R": # option 1 +- if canPutPatternHorizontally(rules,i,j," + - "): rules[i][j] = " + " rules[i][j + 1 ] = " - " solveMagnets(rules,i,j) # option 2 -+ # option 3 xx def checkConstraints(rules): pCountH = [ 0 for i in range ( len (rules))] nCountH = [ 0 for i in range ( len (rules))] for row in range ( len (rules)): for col in range ( len (rules[ 0 ])): ch = rules[row][col] if ch = = " + ": pCountH[row] + = 1 elif ch = = " - ": nCountH[row] + = 1 pCountV = [ 0 for i in range ( len (rules[ 0 ]))] nCountV = [ 0 for i in range ( len (rules[ 0 ]))] for col in range ( len (rules[ 0 ])): for row in range ( len (rules)): ch = rules[row][col] if ch = = " + ": pCountV[col] + = 1 elif ch = = " - ": nCountV[col] + = 1 for row in range ( len (rules)): if left[row] ! = - 1 : if pCountH[row] ! = left[row]: return False if right[row] ! = - 1 : if nCountH[row] ! = right[row]: return False for col in range ( len (rules[ 0 ])): if top[col] ! = - 1 : if pCountV[col] ! = top[col]: return False if bottom[col] ! = - 1 : if nCountV[col] ! = bottom[col]: return False # # if (top[col] != -1 and pCountH[col] != top[col]) or (bottom[col] != -1 and nCountH[col] != bottom[col]) : # return False return True def solveMagnets(rules,i,j): if i = = len (rules) and j = = 0 : # check the constraint before printing if checkConstraints(rules): print (rules) elif j > = len (rules[ 0 ]): solveMagnets(rules,i + 1 , 0 ) # normal cases else : if rules[i][j] = = "L": # option 1 +- if canPutPatternHorizontally(rules,i,j," + - "): rules[i][j] = " + " rules[i][j + 1 ] = " - " solveMagnets(rules,i,j + 2 ) rules[i][j] = "L" rules[i][j + 1 ] = "R" # option 2 -+ if canPutPatternHorizontally(rules,i,j," - + "): rules[i][j] = " - " rules[i][j + 1 ] = " + " solveMagnets(rules,i,j + 2 ) rules[i][j] = "L" rules[i][j + 1 ] = "R" # option 3 xx if True or canPutPatternHorizontally(rules,i,j,"xx"): rules[i][j] = "x" rules[i][j + 1 ] = "x" solveMagnets(rules,i,j + 2 ) rules[i][j] = "L" rules[i][j + 1 ] = "R" # vertical check elif rules[i][j] = = "T": # option 1 +- if canPutPatternVertically(rules,i,j," + - "): rules[i][j] = " + " rules[i + 1 ][j] = " - " solveMagnets(rules,i,j + 1 ) rules[i][j] = "T" rules[i + 1 ][j] = "B" # option 2 -+ if canPutPatternVertically(rules,i,j," - + "): rules[i][j] = " - " rules[i + 1 ][j] = " + " solveMagnets(rules,i,j + 1 ) rules[i][j] = "T" rules[i + 1 ][j] = "B" # option 3 xx if True or canPutPatternVertically(rules,i,j,"xx"): rules[i][j] = "x" rules[i + 1 ][j] = "x" solveMagnets(rules,i,j + 1 ) rules[i][j] = "T" rules[i + 1 ][j] = "B" else : solveMagnets(rules,i,j + 1 ) # Driver code solveMagnets(rules, 0 , 0 ) |
C#
using System; class Program { // Arrays to store constraints for each side static int [] top = { 1, -1, -1, 2, 1, -1 }; static int [] bottom = { 2, -1, -1, 2, -1, 3 }; static int [] left = { 2, 3, -1, -1, -1 }; static int [] right = { -1, -1, -1, 1, -1 }; // Function to check if the current configuration satisfies the constraints static bool CheckConstraints( char [][] rules) { int [] pCountH = new int [rules.Length]; int [] nCountH = new int [rules.Length]; // Count the number of '+' and '-' in each row for ( int row = 0; row < rules.Length; row++) { for ( int col = 0; col < rules[0].Length; col++) { char ch = rules[row][col]; if (ch == '+' ) { pCountH[row] += 1; } else if (ch == '-' ) { nCountH[row] += 1; } } } int [] pCountV = new int [rules[0].Length]; int [] nCountV = new int [rules[0].Length]; // Count the number of '+' and '-' in each column for ( int col = 0; col < rules[0].Length; col++) { for ( int row = 0; row < rules.Length; row++) { char ch = rules[row][col]; if (ch == '+' ) { pCountV[col] += 1; } else if (ch == '-' ) { nCountV[col] += 1; } } } // Check constraints for each side for ( int row = 0; row < rules.Length; row++) { if (left[row] != -1) { if (pCountH[row] != left[row]) { return false ; } } if (right[row] != -1) { if (nCountH[row] != right[row]) { return false ; } } } for ( int col = 0; col < rules[0].Length; col++) { if (top[col] != -1) { if (pCountV[col] != top[col]) { return false ; } } if (bottom[col] != -1) { if (nCountV[col] != bottom[col]) { return false ; } } } return true ; } // Function to check if a horizontal pattern can be placed at the specified position static bool CanPutPatternHorizontally( char [][] rules, int i, int j, string pat) { if (j - 1 >= 0 && rules[i][j - 1] == pat[0]) { return false ; } else if (i - 1 >= 0 && rules[i - 1][j] == pat[0]) { return false ; } else if (i - 1 >= 0 && rules[i - 1][j + 1] == pat[1]) { return false ; } else if (j + 2 < rules[0].Length && rules[i][j + 2] == pat[1]) { return false ; } return true ; } // Function to check if a vertical pattern can be placed at the specified position static bool CanPutPatternVertically( char [][] rules, int i, int j, string pat) { if (j - 1 >= 0 && rules[i][j - 1] == pat[0]) { return false ; } else if (i - 1 >= 0 && rules[i - 1][j] == pat[0]) { return false ; } else if (j + 1 < rules[0].Length && rules[i][j + 1] == pat[1]) { return false ; } return true ; } // Function to solve the magnet puzzle using backtracking static void SolveMagnets( char [][] rules, int i, int j) { // If the entire grid is processed, check and print the solution if valid if (i == rules.Length && j == 0) { if (CheckConstraints(rules)) { Console.Write( "[" ); for ( int indxi = 0; indxi < rules.Length; indxi++) { Console.Write( "[" ); for ( int indxj = 0; indxj < rules[0].Length; indxj++) { char magnet = rules[indxi][indxj]; if (magnet == 'L' || magnet == 'R' || magnet == 'T' || magnet == 'B' ) { Console.Write( "'x', " ); } else { Console.Write($ "'{magnet}', " ); } } Console.Write( "]" ); } Console.WriteLine( "]" ); } } // If the end of a row is reached, move to the next row else if (j >= rules[0].Length) { SolveMagnets(rules, i + 1, 0); } else { // Check for placing horizontal patterns if (rules[i][j] == 'L' ) { if (CanPutPatternHorizontally(rules, i, j, "+-" )) { rules[i][j] = '+' ; rules[i][j + 1] = '-' ; SolveMagnets(rules, i, j + 2); rules[i][j] = 'L' ; rules[i][j + 1] = 'R' ; } if (CanPutPatternHorizontally(rules, i, j, "-+" )) { rules[i][j] = '-' ; rules[i][j + 1] = '+' ; SolveMagnets(rules, i, j + 2); rules[i][j] = 'L' ; rules[i][j + 1] = 'R' ; } if (CanPutPatternHorizontally(rules, i, j, "xx" )) { rules[i][j] = 'L' ; rules[i][j + 1] = 'R' ; SolveMagnets(rules, i, j + 2); rules[i][j] = 'L' ; rules[i][j + 1] = 'R' ; } } // Check for placing vertical patterns else if (rules[i][j] == 'T' ) { if (CanPutPatternVertically(rules, i, j, "+-" )) { rules[i][j] = '+' ; rules[i + 1][j] = '-' ; SolveMagnets(rules, i, j + 1); rules[i][j] = 'T' ; rules[i + 1][j] = 'B' ; } if (CanPutPatternVertically(rules, i, j, "-+" )) { rules[i][j] = '-' ; rules[i + 1][j] = '+' ; SolveMagnets(rules, i, j + 1); rules[i][j] = 'T' ; rules[i + 1][j] = 'B' ; } if (CanPutPatternVertically(rules, i, j, "xx" )) { rules[i][j] = 'T' ; rules[i + 1][j] = 'B' ; SolveMagnets(rules, i, j + 1); rules[i][j] = 'T' ; rules[i + 1][j] = 'B' ; } } // Move to the next cell else { SolveMagnets(rules, i, j + 1); } } } static void Main() { // Initial configuration of magnets char [][] rules = new char [][] { new char [] { 'L' , 'R' , 'L' , 'R' , 'T' , 'T' }, new char [] { 'L' , 'R' , 'L' , 'R' , 'B' , 'B' }, new char [] { 'T' , 'T' , 'T' , 'T' , 'L' , 'R' }, new char [] { 'B' , 'B' , 'B' , 'B' , 'T' , 'T' }, new char [] { 'L' , 'R' , 'L' , 'R' , 'B' , 'B' } }; // Solve the magnet puzzle SolveMagnets(rules, 0, 0); } } |
Javascript
<script> // javascript code here function checkConstraints(rules){ let M = 5; let N = 6; let top = [ 1, -1, -1, 2, 1, -1 ]; let bottom = [2, -1, -1, 2, -1, 3 ]; let left = [2, 3, -1, -1, -1]; let right = [-1, -1, -1, 1, -1]; let pCountH = new Array(rules.length).fill(0); let nCountH = new Array(rules.length).fill(0); for (let row = 0; row < rules.length; row++){ for (let col = 0; col < rules[0].length; col++){ let ch = rules[row][col]; if (ch == '+' ){ pCountH[row] += 1; } else if (ch == '-' ){ nCountH[row] += 1; } } } let pCountV = new Array(rules[0].length).fill(0); let nCountV = new Array(rules[0].length).fill(0); for (let col = 0; col < rules[0].length; col++){ for (let row = 0; row < rules.length; row++){ let ch = rules[row][col]; if (ch == '+' ){ pCountV[col] += 1; } else if (ch == '-' ){ nCountV[col] += 1; } } } for (let row = 0; row < rules.length; row++){ if (left[row] != -1){ if (pCountH[row] != left[row]){ return false ; } } if (right[row] != -1){ if (nCountH[row] != right[row]){ return false ; } } } for (let col = 0; col < rules[0].length; col++){ if (top[col] != -1){ if (pCountV[col] != top[col]){ return false ; } } if (bottom[col] != -1){ if (nCountV[col] != bottom[col]){ return false ; } } // if (top[col] != -1 and pCountH[col] != top[col]) or (bottom[col] != -1 and nCountH[col] != bottom[col]) : // return False } return true ; } function canPutPatternHorizontally(rules, i, j, pat){ if ( j-1>=0 && rules[i][j-1] == pat[0]){ return false ; } else if (i-1>=0 && rules[i-1][j] == pat[0]){ return false ; } else if (i-1>=0 && rules[i-1][j+1] == pat[1]){ return false ; } else if (j+2 < rules[0].length && rules[i][j+2] == pat[1]){ return false ; } return true ; } function canPutPatternVertically(rules,i,j, pat){ if ( j-1>=0 && rules[i][j-1] == pat[0]){ return false ; } else if (i-1>=0 && rules[i-1][j] == pat[0]){ return false ; } else if (j+1 < rules[0].length && rules[i][j+1] == pat[0]){ return false ; } return true ; } function solveMagnets(rules, i,j){ // check the constraint before printing if ( i == rules.length && j == 0){ if (checkConstraints(rules)){ // Printing rules array. console.log(rules); } } else if (j >= rules[0].length){ solveMagnets(rules, i+1, 0); } // normal cases else { if (rules[i][j] == 'L' ){ // option 1 +- if (canPutPatternHorizontally(rules,i,j, "+-" )){ rules[i][j] = '+' ; rules[i][j+1] = '-' ; solveMagnets(rules,i,j+2); rules[i][j] = 'L' ; rules[i][j+1] = 'R' ; } // option 2 -+ if (canPutPatternHorizontally(rules,i,j, "-+" )){ rules[i][j] = '-' ; rules[i][j+1] = '+' ; solveMagnets(rules,i,j+2); rules[i][j] = 'L' ; rules[i][j+1] = 'R' ; } // option 3 xx if ((1 == 1) || canPutPatternHorizontally(rules,i,j, "xx" )){ rules[i][j] = 'x' ; rules[i][j+1] = 'x' ; solveMagnets(rules,i,j+2); rules[i][j] = 'L' ; rules[i][j+1] = 'R' ; } } // vertical check else if (rules[i][j] == 'T' ){ // option 1 +- if (canPutPatternVertically(rules,i,j, "+-" )){ rules[i][j] = '+' ; rules[i+1][j] = '-' ; solveMagnets(rules,i,j+1); rules[i][j] = 'T' ; rules[i+1][j] = 'B' ; } // option 2 -+ if (canPutPatternVertically(rules,i,j, "-+" )){ rules[i][j] = '-' ; rules[i+1][j] = '+' ; solveMagnets(rules,i,j+1); rules[i][j] = 'T' ; rules[i+1][j] = 'B' ; } // option 3 xx if ((1 == 1) || canPutPatternVertically(rules,i,j, "xx" )){ rules[i][j] = 'x' ; rules[i+1][j] = 'x' ; solveMagnets(rules,i,j+1); rules[i][j] = 'T' ; rules[i+1][j] = 'B' ; } } else { solveMagnets(rules,i,j+1); } } } function doTheStuff(rules, i, j){ if (rules[i][j] == 'L' || rules[i][j] == 'R' ){ // option 1 +- if (canPutPatternHorizontally(rules, i, j , "+-" )){ rules[i][j] = '+' ; rules[i][j+1] = '-' ; solveMagnets(rules,i,j); } // option 2 -+ // option 3 xx } } // Driver code let rules = [ [ 'L' , 'R' , 'L' , 'R' , 'T' , 'T' ], [ 'L' , 'R' , 'L' , 'R' , 'B' , 'B' ], [ 'T' , 'T' , 'T' , 'T' , 'L' , 'R' ], [ 'B' , 'B' , 'B' , 'B' , 'T' , 'T' ], [ 'L' , 'R' , 'L' , 'R' , 'B' , 'B' ] ]; solveMagnets(rules,0,0); // The code is contributed by Nidhi goel. </script> |
Output:
[['+', '-', '+', '-', 'x', '-', ]['-', '+', '-', '+', 'x', '+', ]['x', 'x', '+', '-', '+', '-', ]['x', 'x', '-', '+', 'x', '+', ]['-', '+', 'x', 'x', 'x', '-', ]]
Source :https://people.eecs.berkeley.edu/~hilfingr/programming-contest/f2012-contest.pdf
Contact Us