I will attempt to give you an algorithm which you hopefully could turn into actual C code. A brute force approach might be to do this:

1. For every point in your set, choose another point in the set.
2. Based on the resulting line, determine what the next perpendicular line in the square would be, and check to see if a point exists in the set matching what would be needed.
3. If this third point (and hence second side) be found, then repeat step 2 for the the third side of the square.
4. Finally, if three valid points be found, then see if the third point connects appropriately back to the original point. If it does, then you have a match.
5. If during any of these steps there is a failure, then discard the first point as a candidate, and return to step 1, choosing another point. Once you have iterated over all points, you will have either found a square, or determined that none exist.

Update and Improvement:

1. For each point in the set, compare against every other point in the set looking for two perpendicular diagonals to other points. If found, store the ids of the two points to which it connects. If not found, then permanently discard this point from your set. This step will be O(N^2) but I see no way of avoiding it.

2. Next, iterate over the "chosen" points (i.e. those having one or more half-sqaures), and check to see if the points to which they connect also themselves connect back to another chosen point. If so, then you have found a square. The trick here is that you don't do anymore computations here. You simply iterate over the state you already have, which should be way faster than the calculations in the first step.

This approach beats the pulp out of the brute force method because it only has to calculate half-squares. Computing squares brute force is an O(N^4) affair. This approach is O(N^2) but in practice would likely be faster since the set of points would shrink as the algorithm progresses.

Given two points of a square, only 3 kinds of square can be constructed as the following picture shows. And for each case, we can simply calculate the coordinates of the other two points. We can check if such points exist using map or else a simple flag table (bool exist[MAX_X][MAX_Y]) and satisfy the “same number rule” or not.

So just enumerate all N*N cases, and each check the 3 kinds. Overall time complexity is O(N^2*logN) using C++ STL map or O(N^2) using flag table or C++ STL unordered_map.

First some terminology: The grid/network runs horizontally "x" left-to-right 1..N and vertically likewise "y" top-down. The squares to be found have vertices (corners) that we number clockwise 1..4. The first such corner, which we'll call TopLeft, is the one with lowest vertical (y) value; if there are two (a non-rotated quadrangle) it is the one with the lower horizontal (x) value.

Algorithm: scan all points and try to construct a quandrangle with the given point as vertex #1, i.e. TopLeft. This results in the following pseudocode:

// for each TopLeft candidate...
for x1 = 1 to N-1 // TopLeft can never have x=N
  for y1 = 1 to N-1 // TopLeft van never have y=N

// scan vertex #2 candidates...
for x2 = x1+1 to N // #2 is always strictly to the right of #1
  for y2 = y1 to N // #2 is never above #1

  // resulting #3 coordinates
  x3  = x2 - (y2 - y1)
  if x3 < 1 then exit 'for y2' // all next y2 will also yield x3<1
  y3 = y2 + (x2 - x1)
  if y3 > N then exit 'for y2' // all next y2 will also yield y3>N

// resulting #4
x4 = x1 - (y2 - y1)
if x4 < 1 then exit 'for y2' // all next y2 will also yield x4<1
y4 = y1 + (x2 - x1)
if y4 > N then exit 'for x2' // all next x2 will also yield y4>N

// colors ok?
if grid(x1,y1)==grid(x2,y2) && grid(x1,y1)==grid(x3,y3) && grid(x1,y1)==grid(x4,y4) then  // FOUND!
  count+=1
endif

next y2
next x2
next y1
next x1