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 variable, 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 number, 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

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.