The following gives the backtracking algorithm in pseudo-code for a constraint s

Question

The following gives the backtracking algorithm in pseudo-code for a constraint satisfaction problem. Where U is a set of unassigned variables, and A is the current partial assignment. search (U.A){if (U =={}) return A; remove a variable X from U; for (each value a in X's domain) {if (X=a is consistent with A) {add X = a to A; res = search (U, A); if res ! = false return res remove X=a from A;}} return false;} A magic square of size N is an N times N square grid filled with distinct numbers from 1 to N^2 such that the numbers in each row, in each column, as well as the numbers in the main and secondary diagonals, all add up to the same value. Based on the above algorithm, write a program in C++ or Java to find a 3 times 3 magic square.

Explanation / Answer

Here is the complete program to find the magic square. I have kept two options in it One to get from the file and second to enter from the keyboard.

import java.io.*;
import java.util.*;

class MagicSquares
{
   int n;
   int magic[][];

   MagicSquares()
   {

      String filename = "nums.txt";

     try
     {
      //create Scanner object to read from file
    
      Scanner sc= new Scanner(new File(filename));
   
      
     
   
        // Read first integer from file     
        n = sc.nextInt();
     
        magic = new int[n][n];
      
        for(int i=0; i<n; i++)
         for(int j=0; j<n; j++)
         {
             //System.out.println(sc.nextInt());
            magic[i][j]=sc.nextInt();
          
         }
       }
       catch(Exception e)
       {
         System.out.println(e);
       }

       
   }
   MagicSquares(int a[])
   {
      n= (int)Math.sqrt(a.length);
      magic = new int[n][n];
      int z=0;
    

      for(int i=0;i<n;i++)
         for(int j=0; j<n ;j++)
         {
          
            magic[i][j] = a[z];
            z++;
         }
   }
   int rightLeftDiagonalSum()
   {
      int sum=0;
      for(int i=n-1;i>=0;i--)      
      {
         //System.out.println(magic[i][n-1-i]);
         sum=sum+magic[i][n-1-i];
      }
       return sum;
   }
   int leftRightDiagonalSum()
   {
      int sum=0;
      for(int i=n-1;i>=0;i--)      
      {
         //System.out.println(magic[i][i]);
         sum=sum+magic[i][i];
      }
       return sum;
   }
   int columnSum()
   {
      int sum=0;
      for(int j=0;j<n;j++)
          sum=sum+magic[0][j];
        
       return sum;
    }
    int rowSum()
   {
      int sum=0;
      for(int j=0;j<n;j++)
          sum=sum+magic[j][0];
        
       return sum;
    }
  
    boolean correctNumbers()
    {
      for(int i=0; i<n; i++)
         for(int j=0; j<n;j++)
            if(magic[i][j] < 1 || magic[i][j] > n*n) return false;
         
         
      return true;
  
    }
  
    boolean validMagicSquare()
    {
      if(correctNumbers() && rowSum()==columnSum() && columnSum()== leftRightDiagonalSum() && leftRightDiagonalSum()== rightLeftDiagonalSum() ) return true;
    
      else return false;
    }

   public String toString()
   {
      String str="";
      for(int i=0; i<n; i++)
      {
         for(int j=0; j<n; j++)
            str=str+ magic[i][j]+" ";
       
         str=str+" ";
      }
    
      return str;
   }
}

public class MagicSquaresMatrix
{
   public static void main(String a[])
   {
      MagicSquares m;
      Scanner sc= new Scanner(System.in);
      int ch=0;
      while(ch!=3)
      {
    
         System.out.println("1. Create Magic square from file ");
         System.out.println("2. Create Magic square from input ");
         System.out.println("3. Exit the program ");
       
         ch=sc.nextInt();
       
         if(ch==1)
         {
            m= new MagicSquares();
            System.out.println(m);
            if(m.validMagicSquare())System.out.println("It is a magic Square ");
            else System.out.println("It is not a magic Square ");
         }
         else if(ch==2)
         {
            int n;
            System.out.println("Enter size of square matrix");
            n=sc.nextInt();
            int arr[] = new int[n*n];
          
            System.out.println("Enter "+n*n+" elements ");
            for(int i=0;i<n*n; i++)
               arr[i]=sc.nextInt();
            m= new MagicSquares(arr);
            System.out.println(m);
          
            if(m.validMagicSquare())System.out.println("It is a magic Square ");
            else System.out.println("It is not a magic Square ");
         }
         else if(ch==3)
            break;
       
      }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.