Finding the number of possible squares in this picture [closed]

Question

The following is a visual problem I came across today. The question here is simply how many squares there are in the picture.

How would you go about solving something like this though code ? Furthermore, if the actual picture isn't processed, how would you go about modelling it ?

P.S: I sense that the actual resolution would require a rule to define what can be considered as a square. Something along the lines of saying that sides are equal in length and can be composed of any number of segments as long as they fit within the enclosing square. I'm not sure how you could represent a position though.

Answer 1

If you can model this as a matrix, then the only information you need is the position of vertices. Then for every vertex check all the vertices in the same row and for each of found vertex check their column. then delete the processed vertex. Do the same column-wise. The worst case complexity would be n! (?)

I added the code for clarification.

public class SqFinder {
        int calculateSquares(int[][] vertices, int n) {
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (vertices[i][j] == 1) {
                        for (int k = 1; k < n-j; k++) {
                            if (i + k < n && vertices[i][j+k] == 1 && vertices[i + k][j] == 1 && vertices[i + k][j + k] == 1)
                                count++;
                        }
                    }
                    vertices[i][j] =0;
                }
            }
            return count;
        }

        public static void main(String[] args) {
            SqFinder a = new SqFinder();
    //      int [][] test = {{1,1,1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1}};
            int [][] test = {{1,1,1},{1,1,1},{1,1,1}};
            System.out.println(a.calculateSquares(test, 3));
        }
    }

Answer 2

The simplest way would be to loop through every vertex, and check to see if it can be the upper-left vertex of a square of width 1, then of width 2, of 3, etc.

Answer 3

Encoding: what you have is a network. Encode this as a network connecting nodes situated in a discrete two-dimensional space.

The question is really asking you to count the number of paths that meet the following properties:

1. There are 3 turns
2. The length between each such turn is equal
3. The beginning and end of the path are the same.

A turn in this case is when either (a) if the previous move resulted in a change in the y-co-ordinate, this move results in a change in the x-co-ordinate; or (b) if the previous move resulted in a change in the x-co-ordinate, this move results in a change in the y-co-ordinate.

As to keeping track of the process: The best suggestions I've seen on this page are simply to iterate over each node, and for each such node to check all possible sizes of square. That should obviate the need to keep track any further.

If you have a smarter method, as long as your paths are always left-handed or always right-handed, each square is uniquely identified by the starting vertex, and length of side.