Magnet Puzzle

Last Updated : 22 Jan, 2024

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)

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

Remove Invalid Parentheses

Anuj Chauhan (anuj0503)

Improve

Article Tags :

Practice Tags :

Magnet Puzzle

Similar Reads

Standard problems on backtracking

Easy Problems on Backtracking

Medium prblems on Backtracking

Hard problems on Backtracking

Thank You!

What kind of Experience do you want to share?