How to find all the sub square matrices of this matrix

hi

can u pls help me with dis problem: Using Dynamic programming approach write a O(n^2) algorithm for following. pls reply asap.its URGENT

given a large image of a chip, you have to find the two largest non-overlapping square blocks
which are still unused. The image of the chip is given to you as follows:
 
5 6
R F F R R F
F F F F F F
R R F F F F
F F F F F F
F F F F F F
 
The numbers 5 and 6 are the number of rows and columns respectively, and "R" means reserved
and "F" means free. In this case the largest square is 
 
F F F F
F F F F
F F F F
F F F F
 
and the second largest (non-overlapping with the previous one) is 
 
F F
F F
 
In general, the selection of the largest square conditions the choice and the size of the second,
since the second largest cannot overlap with the largest. 
If there are multiple largest squares (i.e., several squares with the same area), your program
should choose the one that allows the second largest to be as large as possible.
 
Sample Input
2
5 6
R F F F F F
F F R R F F
R R R F F F
F F F F F F
F F F F F F
 
5 5
R R R R R
F R R R R
F R F R R
R R R R R
R R R R R

For each data set in the input file print on a separate line, on the standard output, the area of the
two largest unused non-overlapping square (separated by a space).

Sample Output (corresponding to the sample input above)
9 4
1 1

Thanks

Sorry, I hadn't picked up on the word 'rectangular' there :)

Well I'm sure it's possible to figure that out both in safe and unsafe code but it's going to be very slow compared to the square submatrix case because for every submatrix we're currently examining of size n x n for the 300 x 300 case, you'd need to examine just under 2 x n rectangular submatrices. You'd therefore be talking of an execution time of several minutes rather than a few seconds.

There may be clever algorithms available which can cut the time used by 'brute force' methods but I'm afraid I don't know of any as it's a long time since I did any serious mathematics.

I appreciate the effort its pretty fast... but my concern was to detect rectangular sub matices it still detects square matrices like 2*2 ,3*3, 4*4 and so on..... wat bout sub matrices of order 4*5 ,3*6, m*n where m and n are not equal.

Is it possible to detect such matrices...??

Yes.

In fact, I've recoded the GenerateSubmatrices() method below using 'unsafe' code - nothing else needs changing. My very rough tests on much smaller matrices suggest that you may be able to knock a couple of seconds off the 7 second execution time for the 300 * 300 matrix, the time saving coming from not having to check that the array accesses (of which there are a lot) are within bounds.

As we're reasonably sure now that this won't cause a memory leak, the code should be safe to use provided I haven't made a blunder converting the array accesses to pointer accesses:

    unsafe static List GenerateSubmatrices(int[,] matrix)
    {
         List smiList = new List();
         int rows  = matrix.GetLength(0);
         int cols  = matrix.GetLength(1);
         int maxSize = (rows == cols) ? rows - 1 : Math.Min(rows, cols);
         if (maxSize < 2) return smiList;
         bool[,] used = new bool[rows, cols]; // all false initially
         int first = 0;
         bool isSame = false;
         fixed(int* pMatrix = &matrix[0,0])
         {
            fixed(bool* pUsed = &used[0,0])
            {
              int* pm = pMatrix;
              bool* pu = pUsed;

              for(int size = maxSize; size > 1; size--)
              {
                 for(int x = 0; x < rows - size + 1; x++)
                 {
                    for(int y = 0; y < cols - size + 1; y++)
                    {
                       first = pm[x * cols + y];
                       isSame = true;
                       for(int sx = x; sx < x + size; sx++)
                       {          
                          for(int sy = y; sy < y + size; sy++)
                          {
                             int pos = sx * cols + sy;          
                             if (pu[pos] || first != pm[pos])
                             {
                                isSame = false;
                                goto next;
                             }
                          }
                       }
                       next:
                       if (isSame)
                       {
                          smiList.Add(new SubmatrixInfo(x, y , size , first));
                          for(int ux = x; ux < x + size; ux++)
                          {
                             for(int uy = y; uy < y + size; uy++)
                             {
                                pu[ux * cols + uy] = true;
                             }
                          }
                  
                       }
                    }
                 }
              }
              // remove any submatrix from list which is not isolated
              bool isIsolated = false;
              SubmatrixInfo smi;
              for (int i = smiList.Count - 1; i >= 0; i--)
              {
                 isIsolated = true;
                 smi = smiList[i];
                 if (smi.Y > 0)
                 {
                    for(int ix = smi.X; ix < smi.X + smi.Rows; ix++)
                    {
                       if(pm[ix * cols + smi.Y - 1] == smi.Value)
                       {
                          isIsolated = false;
                          goto finish;
                       }
                    }
                 }
                 if (smi.Y < cols - smi.Rows)
                 {
                    for(int ix = smi.X; ix < smi.X + smi.Rows; ix++)
                    {
                       if(pm[ix * cols + smi.Y + smi.Rows] == smi.Value)
                       {
                          isIsolated = false;
                          goto finish;
                       }
                    }
                 }   
                 if (smi.X > 0)
                 {
                    for(int iy = smi.Y; iy < smi.Y + smi.Rows; iy++)
                    {
                       if(pm[(smi.X - 1) * cols + iy] == smi.Value)
                       {
                          isIsolated = false;
                          goto finish;
                       }
                    }
                 }
                 if (smi.X < rows - smi.Rows)
                 {
                    for(int iy = smi.Y; iy < smi.Y + smi.Rows; iy++)
                    {
                       if(pm[(smi.X + smi.Rows) * cols + iy] == smi.Value)
                       {
                          isIsolated = false;
                          goto finish;
                       }
                    }
                 }
                 // now deal with top diagonal elements
                 if (smi.X > 0 && smi.Y > 0)
                 {
                    if(pm[(smi.X - 1) * cols + smi.Y - 1] == smi.Value)
                    {
                       isIsolated = false;
                       goto finish;
                    }
                 }
                 if (smi.X > 0 && (smi.Y < cols - smi.Rows))
                 {
                    if(pm[(smi.X - 1) * cols + smi.Y + smi.Rows] == smi.Value)
                    {
                       isIsolated = false;
                       goto finish;
                    }
                 }
                 // finally deal with bottom diagonal elements
                 if (smi.Y > 0 && (smi.X < rows - smi.Rows))
                 {
                    if(pm[(smi.X + smi.Rows) * cols + smi.Y - 1] == smi.Value)
                    {
                       isIsolated = false;
                       goto finish;
                    }
                 }
                 if ((smi.X < rows - smi.Rows) && (smi.Y < cols - smi.Rows))
                 {
                    if(pm[(smi.X + smi.Rows) * cols + smi.Y + smi.Rows] == smi.Value)
                    {
                       isIsolated = false;
                       goto finish;
                    }
                 }
                 finish:   
                 if (!isIsolated) smiList.RemoveAt(i);
              }
            }
         }
         return smiList;
    }  

Marking a piece of code as 'unsafe' in  C#, enables you to use unmanaged pointers in that code with all the attendant risks. So, it's a bit like using C code in C#. Because of this it can only be run in a fully trusted environment.

So, basically, you can try and quicken up any piece of C# code by using pointer manipulations including this one. However, in my experience, improvements are usually only marginal and so it's seldom worth the effort.

hmmm... can we also detect rectangular sub matrices of equal value using this???

No, I don't think multi-threading would help.

We've only got the one 'natural' method here and I can't really see how you could split off some of the processing into a sub-method running on a separate thread without the need for the first thread to wait for the second thread to finish. Given the overhead of an additional method call and context switches by the OS, it's therefore going to be quicker to run it on a single thread.

To be honest, I'm pleasantly surprised that it can process a 300 x 300 matix in as little as 7 seconds. You might be able to shave a bit off that by rewriting it in 'unsafe' code which would remove array bounds checking  and then manipulate the arrays with pointers but, otherwise, I think it's as fast now as we're likely to get it.

yes this works..... I was wondering if multi threading will be a good idea to reduce execution time or will it make the code more complex. It takes about 7 sec for finding the sub matrices of a  300*300 matrix. I need to access 800 such matrices. Do you think using multithreading will help??

If you want to isolate on the adjoining diagonal elements as well, then you'll need to deal with the four elements individually:

            // now deal with top diagonal elements
            if (smi.X > 0 && smi.Y > 0)
            {
                  if(matrix[smi.X - 1, smi.Y - 1] == smi.Value)
                  {
                     isIsolated = false;
                     goto finish;
                  }
            }
            if (smi.X > 0 && (smi.Y < cols - smi.Rows))
            {
                  if(matrix[smi.X - 1, smi.Y + smi.Rows] == smi.Value)
                  {
                     isIsolated = false;
                     goto finish;
                  }
            }
            // finally deal with bottom diagonal elements
            if (smi.Y > 0 && (smi.X < rows - smi.Rows))
            {
                  if(matrix[smi.X + smi.Rows, smi.Y - 1] == smi.Value)
                  {
                     isIsolated = false;
                     goto finish;
                  }
            }
            if ((smi.X < rows - smi.Rows) && (smi.Y < cols - smi.Rows))
            {
                  if(matrix[smi.X + smi.Rows, smi.Y + smi.Rows] == smi.Value)
                  {
                     isIsolated = false;
                     goto finish;
                  }
            }

Just one more question... how to take care of the diagonal elements. I mean how to detect the diagonally neighboring elements
for isolated sub matrices.

I wrote the code but its not working:


  if (smi.X > 0 && smi.Y > 0 && smi.X < rows - smi.Rows && smi.Y < cols - smi.Rows) // diag upper elements
                     {
                         for (int iy = smi.Y; iy < smi.Y + smi.Rows; iy++)
                         {
                             if (matrix[smi.X - 1, iy - 1] == smi.Value || matrix[smi.X - 1, iy + 1] == smi.Value)
                             {
                                 isIsolated = false;
                                 goto finish;
                             }
                         }
                     }


               if (smi.X > 0 && smi.Y > 0 && smi.X < rows - smi.Rows && smi.Y < cols - smi.Rows) // diag lower elements
                {
                   
                    for (int iy = smi.Y; iy < smi.Y + smi.Rows; iy++)
                    {
                        if (matrix[smi.X + smi.Rows, iy - 1] == smi.Value || matrix[smi.X + smi.Rows, iy + 1] == smi.Value)
                        {
                           
                            isIsolated = false;
                            goto finish;
                        }
                    }
                }

Thanks a lot. It is working perfectly fine. I appreciate your time and concern. This initiative from your side has encouraged me to learn in depth about C#. It is a great platform.

OK, I think all we need to do is to get the list of disjoint submatrices as before and then remove those which are not isolated from the list. The effect on execution time should be minimal:

using System;
using System.Collections.Generic;

// Information for same value square submatrix
struct SubmatrixInfo
{
   public readonly int X;  // x coordinate in parent of top left element
   public readonly int Y;  // y coordinate in parent of top left element
   public readonly int Rows; // number of rows and hence columns in submatrix
   public readonly int Value; // common value of elements

   public SubmatrixInfo(int x, int y, int rows, int value)
   {
      X = x;
      Y = y;
      Rows = rows;
      Value = value;  
   }
  
   public override string ToString()
   {
      return String.Format("At [{0}, {1}], size {2} x {2}, value {3}", X, Y, Rows, Value);
   }  

}   

             
class Program
{
    static void Main()
    {
       
        int[,] matrix = new int[,]
        {
           {1, 3, 4, 5, 5, 5, 7, 7},
           {2, 3, 4, 5, 5, 5, 4, 3},
           {9, 8, 7, 7, 7, 4, 3, 2},
           {2, 4, 7, 7, 7, 6, 6, 6},
           {3, 2, 7, 7, 7, 5, 3, 1},
           {9, 8, 4, 3, 2, 5, 6, 5},
           {3, 4, 4, 5, 2, 1, 0, 9},
           {2, 4, 4, 6, 3, 2, 1, 9}
        };
          
        List smiList = GenerateSubmatrices(matrix);
        int count = 0;       
        foreach(SubmatrixInfo smi in smiList)
        {
          Console.WriteLine(smi);
          count++;
          if(count % 20  == 0)
          {
            Console.WriteLine("\nPress any key to continue ...\n");
            Console.ReadKey();
          }
        }    
    }

    static List GenerateSubmatrices(int[,] matrix)
    {
         List smiList = new List();
         int rows  = matrix.GetLength(0);
         int cols  = matrix.GetLength(1);
         int maxSize = (rows == cols) ? rows - 1 : Math.Min(rows, cols);
         if (maxSize < 2) return smiList;
         bool[,] used = new bool[rows, cols]; // all false initially
         int first = 0;
         bool isSame = false;
         for(int size = maxSize; size > 1; size--)
         {
            for(int x = 0; x < rows - size + 1; x++)
            {
               for(int y = 0; y < cols - size + 1; y++)
               {
                  first = matrix[x, y];
                  isSame = true;
                  for(int sx = x; sx < x + size; sx++)
                  {          
                     for(int sy = y; sy < y + size; sy++)
                     {          
                        if (used[sx, sy] || first != matrix[sx, sy])
                        {
                           isSame = false;
                           goto next;
                        }
                     }
                   }
                   next:
                   if (isSame)
                   {
                     smiList.Add(new SubmatrixInfo(x, y , size , first));
                     for(int ux = x; ux < x + size; ux++)
                     {
                        for(int uy = y; uy < y + size; uy++)
                        {
                           used[ux, uy] = true;
                        }
                     }
                  
                   }
               }
            }
         }
         // remove any submatrix from list which is not isolated
         bool isIsolated = false;
         SubmatrixInfo smi;
         for (int i = smiList.Count - 1; i >= 0; i--)
         {
            isIsolated = true;
            smi = smiList[i];
            if (smi.Y > 0)
            {
               for(int ix = smi.X; ix < smi.X + smi.Rows; ix++)
               {
                  if(matrix[ix, smi.Y - 1] == smi.Value)
                  {
                     isIsolated = false;
                     goto finish;
                  }
               }
            }
            if (smi.Y < cols - smi.Rows)
            {
               for(int ix = smi.X; ix < smi.X + smi.Rows; ix++)
               {
                  if(matrix[ix, smi.Y + smi.Rows] == smi.Value)
                  {
                     isIsolated = false;
                     goto finish;
                  }
               }
            }   
            if (smi.X > 0)
            {
               for(int iy = smi.Y; iy < smi.Y + smi.Rows; iy++)
               {
                  if(matrix[smi.X - 1, iy] == smi.Value)
                  {
                     isIsolated = false;
                     goto finish;
                  }
               }
            }
            if (smi.X < rows - smi.Rows)
            {
               for(int iy = smi.Y; iy < smi.Y + smi.Rows; iy++)
               {
                  if(matrix[smi.X + smi.Rows, iy] == smi.Value)
                  {
                     isIsolated = false;
                     goto finish;
                  }
               }
            }
            finish:   
            if (!isIsolated) smiList.RemoveAt(i);
         }
         return smiList;
    }
                  
}   

This just returns the 3 x 3 submatrix of 7's  as the two 2 x 2 submatrices are not isolated.

Incidentally, the 15 x 15 matrix returned no results as none of the 9 disjoint submatrices are isolated.

Mind Blowing my friend. You have actually put it down in the simplest way. Thanks a lot. The execution time is exceptional. But the problem of isolated matrices still remain. Is there a way by which I can access the neighboring elements of each square sub matrix to check whether it has a neighboring element which is of the same value as that of the sub matrix. Just to ensure I get distinct isolated square matrix which has no neighboring element same as its own.

For eg:
6 8 5 2 1 0
9 7 7 7 7 8
3 7 7 7 7 0
1 7 7 7 7 8
3 7 7 7 7 5
9 4 4 6 2 9

In the above matrix the 4*4 matrix of 7's is an isolated matrix since there are no neighboring 7's.(no extra one or more  '7''s surrounding the sub matrix.

Please help this will be the final stage. I will appreciate your concern.

I think I must have been half asleep yesterday as there are in fact nine mutually exclusive submatrices with the same value in the 15 x 15 matrix, not four!

They are:

At [0, 0]  11 x 11, value 222
At [0, 11]  4 x  4, value 222
At [4, 11]  4 x  4, value 222
At [11, 0]  4 x  4, value 222
At [11, 4]  4 x  4, value 222
At [11, 8]  3 x  3, value 222
At [11, 12] 3 x  3, value 206
At [9, 11]  2 x  2, value 214
At [9, 13]  2 x  2, value 214

As it's clear that the previous approach wasn't working and was too slow anyway, I've rethought the problem and come up with a much simpler and faster non-recursive algorithm which, compared to the last one, was almost trivially easy to code :)

The new algorithm doesn't need any final sorting or filtering and works with rectangular as well as square 'parent' matrices.

Basically, I'm just searching iteratively now for all submatrices from the biggest size downwards but I've introduced a bool array which keeps track of whether particular elements in the parent matrix have been used before or not and so there's no longer any problems with duplicated or overlapping submatrices.The biggest matrix I've tested it on is the 15 x 15 one but I hope that the running time for even your 300 x 300 matrix will be more acceptable now as well:

using System;
using System.Collections.Generic;

// Information for same value square submatrix
struct SubmatrixInfo
{
   public readonly int X;  // x coordinate in parent of top left element
   public readonly int Y;  // y coordinate in parent of top left element
   public readonly int Rows; // number of rows and hence columns in submatrix
   public readonly int Value; // common value of elements

   public SubmatrixInfo(int x, int y, int rows, int value)
   {
      X = x;
      Y = y;
      Rows = rows;
      Value = value;  
   }
  
   public override string ToString()
   {
      return String.Format("At [{0}, {1}], size {2} x {2}, value {3}", X, Y, Rows, Value);
   }  

}   

             
class Program
{
    static void Main()
    {
       
        int[,] matrix = new int[,]
        {
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 214, 214, 214},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 214, 214, 214},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 206, 206, 206},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 206, 206, 206, 206},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 206, 206, 206, 206},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 214, 214, 214}
        };
          
        List smiList = GenerateSubmatrices(matrix);
        int count = 0;       
        foreach(SubmatrixInfo smi in smiList)
        {
          Console.WriteLine(smi);
          count++;
          if(count % 20  == 0)
          {
            Console.WriteLine("\nPress any key to continue ...\n");
            Console.ReadKey();
          }
        }    
    }

    static List GenerateSubmatrices(int[,] matrix)
    {
         List smiList = new List();
         int rows  = matrix.GetLength(0);
         int cols  = matrix.GetLength(1);
         int maxSize = (rows == cols) ? rows - 1 : Math.Min(rows, cols);
         if (maxSize < 2) return smiList;
         bool[,] used = new bool[rows, cols]; // all false initially
         int first = 0;
         bool isSame = false;
         for(int size = maxSize; size > 1; size--)
         {
            for(int x = 0; x < rows - size + 1; x++)
            {
               for(int y = 0; y < cols - size + 1; y++)
               {
                  first = matrix[x, y];
                  isSame = true;
                  for(int sx = x; sx < x + size; sx++)
                  {          
                     for(int sy = y; sy < y + size; sy++)
                     {          
                        if (used[sx, sy] || first != matrix[sx, sy])
                        {
                           isSame = false;
                           goto next;
                        }
                     }
                   }
                   next:
                   if (isSame)
                   {
                     smiList.Add(new SubmatrixInfo(x, y , size , first));
                     for(int ux = x; ux < x + size; ux++)
                     {
                        for(int uy = y; uy < y + size; uy++)
                        {
                           used[ux, uy] = true;
                        }
                     }
                  
                   }
               }
            }
         }
         return smiList;
    }
                  
}   

Excellent work my friend. It is working fine. But the execution time is still a problem and it is a big problem since I am gonna work on 300*300 matrix. I was thinking that may be we can reduce time if we look for square matrices of order higher than 9*9 and we look for isolated square matrices for eg:

1 3 4 5 5 5 7 7
2 3 4 5 5 5 4 3
9 8 7 7 7 4 3 2
2 4 7 7 7 6 6 6
3 2 7 7 7 5 3 1
9 8 4 3 2 5 6 5
3 4 4 5 2 1 0 9
2 4 4 6 3 2 1 9 in the above matrix the 3*3 order matrix of 7's in the center is an isolated matrix since it stands apart not surrounded by any other 7 but the 2*2 matrix of 4's at bottom left is not an isolated square matrix since there is an extra 4 in the neighboring elements... , similarly the 2*2 matrix of 5's in top center is not an isolated square matrix due to the two extra neighboring 5's

So we can just find all the isolated square matrices of order 9*9 and above....

OK, I've come up with a solution which deals with this problem for the 15 x 15 matrix but I'm not sure whether it solves it completely or not.

The idea is to have two passes to remove the intersections. The first pass only removes those matrices which intersect on  both sides of the sort order and the second pass removes the remaining intersections. The full code is reproduced for convenience:

using System;
using System.Collections.Generic;

// Information for same value square submatrix
struct SubmatrixInfo : IComparable, IEquatable
{

   public static int ParentRows; // number of rows in parent matrix
   public readonly int X;  // x coordinate in parent of top left element
   public readonly int Y;  // y coordinate in parent of top left element
   public readonly int Rows; // number of rows and hence columns in submatrix
   public readonly int Value; // common value of elements

   public SubmatrixInfo(int x, int y, int rows, int value)
   {
      X = x;
      Y = y;
      Rows = rows;
      Value = value;  
   }
  
   public long Key
   {
      get{ return ParentRows * ParentRows * Rows + ParentRows * (ParentRows - X) + ParentRows - Y;}
   }

   public int CompareTo(object smi)
   {
      SubmatrixInfo other = (SubmatrixInfo)smi;
      return Math.Sign(other.Key - this.Key);
   }

   public override string ToString()
   {
      return String.Format("At [{0}, {1}], size {2} x {2}, value {3}", X, Y, Rows, Value);
   }  

   public bool Equals(SubmatrixInfo other)
   {
     
      if (this.Key == other.Key) return true;
      return false;     
   }

   public bool IsSubmatrixOf(SubmatrixInfo other)
   {
      if (this.Rows >= other.Rows) return false;
      if ((other.X <= X) && (X + Rows <=other.X + other.Rows) &&
          (other.Y <= Y) && (Y + Rows <=other.Y + other.Rows)) return true;
      return false;
   }
  
   public bool IntersectsWith(SubmatrixInfo other)
   {
    return (other.X <= (X + Rows - 1)) && (X <= (other.X + other.Rows - 1)) && (other.Y <= (Y + Rows - 1)) && (Y <= (other.Y + other.Rows - 1));
   }
}   

             
class Program
{
    static void Main()
    {
       
        int[,] matrix = new int[,]
        {
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 214, 214, 214},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 214, 214, 214},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 206, 206, 206},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 206, 206, 206, 206},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 206, 206, 206, 206},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 214, 214, 214}
        };
          
        List smiList = GenerateSubmatrices(matrix);
        int count = 0;       
        foreach(SubmatrixInfo smi in smiList)
        {
          Console.WriteLine(smi);
          count++;
          if(count % 20  == 0)
          {
            Console.WriteLine("\nPress any key to continue ...\n");
            Console.ReadKey();
          }
        }    
    }

    static List GenerateSubmatrices(int[,] matrix)
    {
         int n = matrix.GetLength(0);
         if (n < 3) return new List();
         SubmatrixInfo.ParentRows = n;
         List smiList = GetSubmatrices(matrix, 0, 0);
         smiList.Sort();
         if (smiList.Count == 1) return smiList;
         // remove submatrices which are submatrices of others in list        
         for (int i = smiList.Count - 1;  i > 0; i--)
         {
            for (int j = i - 1;  j >= 0; j--)
            {
               if (smiList[i].IsSubmatrixOf(smiList[j]))
               {
                  smiList.RemoveAt(i);
                  break;
               }
            }
         }
       
         // remove submatrices which intersect with others in list
         // first remove those that intersect on both sides
         for (int i = smiList.Count - 2;  i > 0; i--)
         {
            for (int j = i - 1;  j >= 0; j--)
            {
               if (smiList[i].IntersectsWith(smiList[j]) && smiList[i].IntersectsWith(smiList[i + 1]))
               {
                  smiList.RemoveAt(i);
                  break;
               }
            }
         }
         // now remove any remaining intersections
         for (int i = smiList.Count - 1;  i > 0; i--)
         {
            for (int j = i - 1;  j >= 0; j--)
            {
               if (smiList[i].IntersectsWith(smiList[j]))
               {
                  smiList.RemoveAt(i);
                  break;
               }
            }
         }
         
         return smiList;
    }
   
    static List GetSubmatrices(int[,] matrix, int absX, int absY)
    {
         List smiList = new List();
         int n = matrix.GetLength(0);
         if (n < 3) return smiList;
                
         for (int z = 0; z < 4; z++)
         {
            int startX = 0, endX = n - 2, startY = 0, endY = n - 2;

            switch(z)
            {
               case 0 : // top left
                 break;
               case 1 : // top right
                 startX = 1;
                 endX = n - 1;
                 startY = 0;
                 endY = n - 2;
                 break;
               case 2 : // bottom left
                 startX = 0;
                 endX = n - 2;
                 startY = 1;
                 endY = n - 1;
                 break;
               case 3 : // bottom right
                 startX = startY = 1;
                 endX = endY = n - 1;
                 break;
             }
           
             int[,] submatrix = new int[n - 1, n - 1];
             int first = matrix[startX, startY];
             int next = first;
             bool isSame = true;

             for (int x = startX; x <= endX; x++)
             {
                for (int y = startY; y <= endY; y++)
                {                 
                  next = matrix[x, y];
                  if (isSame && next != first)
                  {
                    isSame = false;
                  }
                  submatrix[x - startX, y - startY] = next;
                }
             }
             if (isSame)
             {
                 SubmatrixInfo smi = new SubmatrixInfo(absX + startX, absY +startY, n - 1, first);         
                 if(!smiList.Contains(smi)) smiList.Add(smi);
             }
             else if (n > 2)
             {
                 List temp = GetSubmatrices(submatrix, absX + startX, absY + startY);
                 foreach(SubmatrixInfo smi in temp)
                 {
                     if (!smiList.Contains(smi)) smiList.Add(smi);
                 }
             }
       }
       return smiList;                 
    }    
}

I've just tried the new version with the 15 x 15 matrix:

         int[,] matrix = new int[,]
        {
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 214, 214, 214},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 214, 214, 214},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 206, 206, 206},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 206, 206, 206, 206},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 206, 206, 206, 206},
           {222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, 214, 214, 214, 214}
        };

and there's a problem which I hadn't anticipated with the three intersecting 2 x 2 matrices starting at [9,11], [9,12] and [9,13]. Unfortunately, working backwards, the last one is eliminated because it intersects with the last but one and then that one is eliminated because it intersects with the other one!

We do,of course, want the two disjoint matrices [9,11] and [9,13] to be returned here. I can't immediately see how to deal with this but I'm working on it :)

Incidentally, I think there should be just four results here (not 8) : the 11 x 11, the 3 x 3 and the two 2 x 2 matrices. 

OK, I've fixed it to exclude submatrices which intersect with bigger submatrices or with submatrices of the same size but earlier in the sorting order. Can't do anything about the speed though as the trouble with the algorithm is that there's a lot of redundant operations :(

using System;
using System.Collections.Generic;

// Information for same value square submatrix
struct SubmatrixInfo : IComparable, IEquatable
{

   public static int ParentRows; // number of rows in parent matrix
   public readonly int X;  // x coordinate in parent of top left element
   public readonly int Y;  // y coordinate in parent of top left element
   public readonly int Rows; // number of rows and hence columns in submatrix
   public readonly int Value; // common value of elements

   public SubmatrixInfo(int x, int y, int rows, int value)
   {
      X = x;
      Y = y;
      Rows = rows;
      Value = value;  
   }
  
   public long Key
   {
      get{ return ParentRows * ParentRows * Rows + ParentRows * (ParentRows - X) + ParentRows - Y;}
   }

   public int CompareTo(object smi)
   {
      SubmatrixInfo other = (SubmatrixInfo)smi;
      return Math.Sign(other.Key - this.Key);
   }

   public override string ToString()
   {
      return String.Format("At [{0}, {1}], size {2} x {2}, value {3}", X, Y, Rows, Value);
   }  

   public bool Equals(SubmatrixInfo other)
   {
     
      if (this.Key == other.Key) return true;
      return false;     
   }

   public bool IsSubmatrixOf(SubmatrixInfo other)
   {
      if (this.Rows >= other.Rows) return false;
      if ((other.X <= X) && (X + Rows <=other.X + other.Rows) &&
          (other.Y <= Y) && (Y + Rows <=other.Y + other.Rows)) return true;
      return false;
   }
  
   public bool IntersectsWith(SubmatrixInfo other)
   {
    return (other.X <= (X + Rows - 1)) && (X <= (other.X + other.Rows - 1)) && (other.Y <= (Y + Rows - 1)) && (Y <= (other.Y + other.Rows - 1));
   }
}   

             
class Program
{
    static void Main()
    {
       
        int[,] matrix = new int[,]
        {
          {1, 4, 5, 6, 7, 8, 5, 3, 4},
          {3, 7, 7, 9, 4, 2, 2, 2, 5},
          {8, 7, 7, 8, 5, 3, 2, 2, 1},
          {6, 6, 7, 8, 6, 3, 1, 2, 3},
          {6, 6, 8, 3, 1, 1, 4, 9, 0},
          {3, 3, 3, 6, 1, 1, 2, 2, 0},
          {3, 3, 3, 4, 5, 6, 0, 9, 1},
          {3, 3, 3, 4, 5, 6, 2, 1, 0},
          {3, 3, 3, 4, 5, 6, 7, 8, 9}
        };
          
        List smiList = GenerateSubmatrices(matrix);
        int count = 0;       
        foreach(SubmatrixInfo smi in smiList)
        {
          Console.WriteLine(smi);
          count++;
          if(count % 20  == 0)
          {
            Console.WriteLine("\nPress any key to continue ...\n");
            Console.ReadKey();
          }
        }    
    }

    static List GenerateSubmatrices(int[,] matrix)
    {
         int n = matrix.GetLength(0);
         if (n < 3) return new List();
         SubmatrixInfo.ParentRows = n;
         List smiList = GetSubmatrices(matrix, 0, 0);
         smiList.Sort();
         if (smiList.Count == 1) return smiList;
         // remove submatrices which are submatrices of others in list
         for (int i = smiList.Count - 1;  i > 0; i--)
         {
            for (int j = i - 1;  j >= 0; j--)
            {
               if (smiList[i].IsSubmatrixOf(smiList[j]))
               {
                  smiList.RemoveAt(i);
                  break;
               }
            }
         }
         // remove submatrices which intersect with others in list
         for (int i = smiList.Count - 1;  i > 0; i--)
         {
            for (int j = i - 1;  j >= 0; j--)
            {
               if (smiList[i].IntersectsWith(smiList[j]))
               {
                  smiList.RemoveAt(i);
                  break;
               }
            }
         }
 
         return smiList;
    }
   
    static List GetSubmatrices(int[,] matrix, int absX, int absY)
    {
         List smiList = new List();
         int n = matrix.GetLength(0);
         if (n < 3) return smiList;
                
         for (int z = 0; z < 4; z++)
         {
            int startX = 0, endX = n - 2, startY = 0, endY = n - 2;

            switch(z)
            {
               case 0 : // top left
                 break;
               case 1 : // top right
                 startX = 1;
                 endX = n - 1;
                 startY = 0;
                 endY = n - 2;
                 break;
               case 2 : // bottom left
                 startX = 0;
                 endX = n - 2;
                 startY = 1;
                 endY = n - 1;
                 break;
               case 3 : // bottom right
                 startX = startY = 1;
                 endX = endY = n - 1;
                 break;
             }
           
             int[,] submatrix = new int[n - 1, n - 1];
             int first = matrix[startX, startY];
             int next = first;
             bool isSame = true;

             for (int x = startX; x <= endX; x++)
             {
                for (int y = startY; y <= endY; y++)
                {                 
                  next = matrix[x, y];
                  if (isSame && next != first)
                  {
                    isSame = false;
                  }
                  submatrix[x - startX, y - startY] = next;
                }
             }
             if (isSame)
             {
                 SubmatrixInfo smi = new SubmatrixInfo(absX + startX, absY +startY, n - 1, first);         
                 if(!smiList.Contains(smi)) smiList.Add(smi);
             }
             else if (n > 2)
             {
                 List temp = GetSubmatrices(submatrix, absX + startX, absY + startY);
                 foreach(SubmatrixInfo smi in temp)
                 {
                     if (!smiList.Contains(smi)) smiList.Add(smi);
                 }
             }
       }
       return smiList;                 
    }    
}

Hi :

Thanks for the reply. Very helpful indeed but the prob is it takes ages to compute for a 300*300 matrix. There is some prob in the detection and i think you will be able to help. It doesnt detect unique sub matrices for eg.

Consider this matrix

222 222 222 222 222 222 222 222 222 222 222 222 222 222 222
222 222 222 222 222 222 222 222 222 222 222 222 222 222 222
222 222 222 222 222 222 222 222 222 222 222 222 222 222 222
222 222 222 222 222 222 222 222 222 222 222 222 222 222 222
222 222 222 222 222 222 222 222 222 222 222 222 222 222 222
222 222 222 222 222 222 222 222 222 222 222 222 222 222 222
222 222 222 222 222 222 222 222 222 222 222 222 222 222 222
222 222 222 222 222 222 222 222 222 222 222 222 222 222 222
222 222 222 222 222 222 222 222 222 222 222 222 222 222 222
222 222 222 222 222 222 222 222 222 222 222 214 214 214 214
222 222 222 222 222 222 222 222 222 222 222 214 214 214 214
222 222 222 222 222 222 222 222 222 222 222 214 206 206 206
222 222 222 222 222 222 222 222 222 222 222 206 206 206 206
222 222 222 222 222 222 222 222 222 222 222 206 206 206 206
222 222 222 222 222 222 222 222 222 222 222 214 214 214 214

In this matrix the number of sub matrices with all elements having same value is 8 but your code detects it as 14. There is a submatrix of dimension 11*11 with all 222's. It should detect it a 11*11 sub matrix(largest) and proceed but it detects a 11*11 matrix of 222 5 times. This due to intersection of elements.

Can we fix this. I
ll appreciate your help.

Thank you,

This isn't an easy one to figure out but I've come up with the program below which seems to be working OK.

The program uses a recursive algorithm to generate all possible sub-matrices whose elements have the same value. I've then sorted them so that the bigger matrices are displayed first and filtered them to exclude matrices which are themselves submatrices of other matrices in the list (for example the 3 x 3 matrix has four 2 x 2 submatrices with values of 3). However, I haven't attempted to exclude matrices which simply intersect one another as it's not clear which one should be removed!

Because of the algorithm used (which, frankly, isn't ideal), the program only works when the 'parent' matrix is itself square so I've had to add a further row to your example matrix to make it 9 x 9 (I also allowed for a 3 x 3 intersection here). However, it should in theory work for your 300 x 300 matrix as long as the processing time is acceptable and the recursive calls don't overflow the stack.

using System;
using System.Collections.Generic;

// Information for same value square submatrix
struct SubmatrixInfo : IComparable, IEquatable
{

   public static int ParentRows; // number of rows in parent matrix
   public readonly int X;  // x coordinate in parent of top left element
   public readonly int Y;  // y coordinate in parent of top left element
   public readonly int Rows; // number of rows and hence columns in submatrix
   public readonly int Value; // common value of elements

   public SubmatrixInfo(int x, int y, int rows, int value)
   {
      X = x;
      Y = y;
      Rows = rows;
      Value = value;  
   }
  
   public long Key
   {
      get{ return ParentRows * ParentRows * Rows + ParentRows * (ParentRows - X) + ParentRows - Y;}
   }

   public int CompareTo(object smi)
   {
      SubmatrixInfo other = (SubmatrixInfo)smi;
      return Math.Sign(other.Key - this.Key);
   }

   public override string ToString()
   {
      return String.Format("At [{0}, {1}], size {2} x {2}, value {3}", X, Y, Rows, Value);
   }  

   public bool Equals(SubmatrixInfo other)
   {
     
      if (this.Key == other.Key) return true;
      return false;     
   }

   public bool IsSubmatrixOf(SubmatrixInfo other)
   {
      if (this.Rows >= other.Rows) return false;
      if ((other.X <= X) && (X + Rows <=other.X + other.Rows) &&
          (other.Y <= Y) && (Y + Rows <=other.Y + other.Rows)) return true;
      return false;
   }
  
}   

             
class Program
{
    static void Main()
    {
       
        int[,] matrix = new int[,]
        {
          {1, 4, 5, 6, 7, 8, 5, 3, 4},
          {3, 7, 7, 9, 4, 2, 2, 2, 5},
          {8, 7, 7, 8, 5, 3, 2, 2, 1},
          {6, 6, 7, 8, 6, 3, 1, 2, 3},
          {6, 6, 8, 3, 1, 1, 4, 9, 0},
          {3, 3, 3, 6, 1, 1, 2, 2, 0},
          {3, 3, 3, 4, 5, 6, 0, 9, 1},
          {3, 3, 3, 4, 5, 6, 2, 1, 0},
          {3, 3, 3, 4, 5, 6, 7, 8, 9}
        };
          
        List smiList = GenerateSubmatrices(matrix);
        int count = 0;       
        foreach(SubmatrixInfo smi in smiList)
        {
          Console.WriteLine(smi);
          count++;
          if(count % 20  == 0)
          {
            Console.WriteLine("\nPress any key to continue ...\n");
            Console.ReadKey();
          }
        }    
    }

    static List GenerateSubmatrices(int[,] matrix)
    {
         int n = matrix.GetLength(0);
         if (n < 3) return new List();
         SubmatrixInfo.ParentRows = n;
         List smiList = GetSubmatrices(matrix, 0, 0);
         smiList.Sort();
         if (smiList.Count == 1) return smiList;
         // remove submatrices which are submatrices of others in list)
         for (int i = smiList.Count - 1;  i > 0; i--)
         {
            for (int j = i - 1;  j >= 0; j--)
            {
               if (smiList[i].IsSubmatrixOf(smiList[j]))
               {
                  smiList.RemoveAt(i);
                  break;
               }
            }
         }
         return smiList;
    }
   
    static List GetSubmatrices(int[,] matrix, int absX, int absY)
    {
         List smiList = new List();
         int n = matrix.GetLength(0);
         if (n < 3) return smiList;
                
         for (int z = 0; z < 4; z++)
         {
            int startX = 0, endX = n - 2, startY = 0, endY = n - 2;

            switch(z)
            {
               case 0 : // top left
                 break;
               case 1 : // top right
                 startX = 1;
                 endX = n - 1;
                 startY = 0;
                 endY = n - 2;
                 break;
               case 2 : // bottom left
                 startX = 0;
                 endX = n - 2;
                 startY = 1;
                 endY = n - 1;
                 break;
               case 3 : // bottom right
                 startX = startY = 1;
                 endX = endY = n - 1;
                 break;
             }
           
             int[,] submatrix = new int[n - 1, n - 1];
             int first = matrix[startX, startY];
             int next = first;
             bool isSame = true;

             for (int x = startX; x <= endX; x++)
             {
                for (int y = startY; y <= endY; y++)
                {                 
                  next = matrix[x, y];
                  if (isSame && next != first)
                  {
                    isSame = false;
                  }
                  submatrix[x - startX, y - startY] = next;
                }
             }
             if (isSame)
             {
                 SubmatrixInfo smi = new SubmatrixInfo(absX + startX, absY +startY, n - 1, first);         
                 if(!smiList.Contains(smi)) smiList.Add(smi);
             }
             else if (n > 2)
             {
                 List temp = GetSubmatrices(submatrix, absX + startX, absY + startY);
                 foreach(SubmatrixInfo smi in temp)
                 {
                     if (!smiList.Contains(smi)) smiList.Add(smi);
                 }
             }
       }
       return smiList;                 
    }    
}