spiral matrix

Note: Code snippet loading may take few seconds.
Generate a square matrix of size n, such that

1. it has elements from 1 to n*2 (or 0 to n*2-1)
2. lowest element is at [n,n] (or [n-1,n-1])
3. elements are arranged in a spiral order as shown in Figure.

For instance, when n=2 and n=3
M2 =           M3=
| 3 4 |           | 5   6   7 |
| 2 1 |           | 4   9   8 |
                     | 3   2   1 |

This is really simple when we consider pattern of filling these elements at an abstract level. Our general approach is to find position for element in order {1, 2, 3, ..., n*n}

We start with rightmost bottom position and put first element there. Then we decide direction to proceed in, which is horizontal in this case. For every next element, we seek a position for it in following way-
We consider adjacent positions of current position in the direction we are in, i.e. here we consider [n,n-1] and [n,n+1] (with [n,n] as our rightmost bottom position. We see if any of this is free. We generalize any position outside matrix dimensions to be non-free and thus next position we have is [n,n-1]. We fill next element in this position and keep going.
At some point, we will find no position free for next element in the direction we are in, which is signal for us to change direction. We switch to vertical direction now and keep going with same logic. This w
ay, we keep moving ahead, find a free slot and change direction if we don't find one.
Note that when we fill in last element, we no longer find free position in either direction and we are done.

Following is the C code.

// generates a spiral square matrix of n*n
// @author Girija

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    int i, j, num;
    int pi, pj;
    bool pfound;

    // setup
    int n = atoi(argv[1]);
    bool horizontal = true;
    int max_num = num*num; // starts at 1

    // allocate
    int **matrix = (int **) malloc(sizeof(int) * n * n);

    // initialize
    for(i=0; i<n; i++) {
     matrix[i] = (int *) malloc(sizeof(int) * n);
      for(j=0; j<n; j++) {
        matrix[i][j] = -1;
      }
    }

    pi = pj = n-1;

    // generate spiral matrix
    num = 1;
    while(1) {
      // place current number at pi,pj
      matrix[pi][pj] = num;
      // get position to place next number
      pfound = false;
      if(horizontal) {
        // we are following horizontal direction, check left-right empty slots first
        // check if empty slot, reset pj
        if(pj-1 >=0 && matrix[pi][pj-1] == -1) {
            pj--;
            pfound = true;
        }
        else if(pj+1 <= n-1 && matrix[pi][pj+1] == -1) {
            pj++;
            pfound = true;
        }
        if(!pfound) {
            // time to change direction
            horizontal = false;
            // reset pi
            if(pi-1 >= 0 && matrix[pi-1][pj] == -1) {
              pi--;
              pfound = true;
            }
            else if(pi+1 <= n-1 && matrix[pi+1][pj] == -1) {
              pi++;
              pfound = true;
            }
        }
      } else {
        // we are following vertical direction, check up-down empty slots first
        // check if empty slot, reset pi
        if(pi-1 >=0 && matrix[pi-1][pj] == -1) {
            pi--;
            pfound = true;
        }
        else if(pi+1 <= n-1 && matrix[pi+1][pj] == -1) {
            pi++;
            pfound = true;
        }
        if(!pfound) {
            // time to change direction
            horizontal = true;
            // reset pj
            if(pj-1 >= 0 && matrix[pi][pj-1] == -1) {
              pj--;
              pfound = true;
            }
            else if(pj+1 <= n-1 && matrix[pi][pj+1] == -1) {
              pj++;
              pfound = true;
            }
        }
      }
      // not found? we are done!
      if(!pfound)
        break;
      num++;
    }

    for(i=0; i<n; i++) {
      printf("n");
      for(j=0; j<n; j++) {
        printf("%dt", matrix[i][j]);
      }
    }
    printf("n");
}

Thanks to Template changes to add code snippet in blog and Parsing code to add to html (blog)