So, let's see what can be a recursive solution. Then, we will check for overlapping sub-problems and will gradually optimize the recursion by memorization.

Let the recursive function be, recurZigzag(matrix, currow, curcolulm, n)

    Function recurZigzag(matrix,currow,curcolulm):
        If (currow reaches n)
            Return 0;
        for i=0 to n except curcolumn
            Return  matrix[currow][curcolumn] + max(recurZigzag(matrix, currow + 1, i))
    End Function

    // In the main function
    for column=0 to n-1
    result=max⁡(result,recurZigzag(matrix,0,column)

So what we did?

We are starting from each column on the top row.

Then we are recursively checking for the next row skipping the current column. So, this checks all combinations possible.

I would recommend to create the recursion tree for example 1 and check whether you can find overlapping sub-problems. There will be a lot of overlapping problems even for smaller inputs.

So, we need to pass that overhead and we can solve that by memorization technique where we store the value of solved sub-problem in DP[][]

So, we first lookup in DP[][] whether it's already solved or not. If it's already solved then we will have some value for DP[i][j] (for subproblem, f(i,j)), Else DP[i][j] will contain the initialized value only.

This is the trick here.

Below is the full CPP implementation for understanding memorization.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int findmax(vector<int> arr, int in, int n, int* lastindex)
{
    int max = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (arr[i] > max && i != in) {
            max = arr[i];
            *lastindex = i;
        }
    }
    return max;
}

int recurZigZag(vector<vector<int> > arr, int row, int col, int n, int** dp)
{
    //memoization part
    if (dp[row][col] != -1) //if already solved, no need to compute again
        return dp[row][col];

    if (row == n - 1) {
        dp[row][col] = arr[row][col];
        return arr[row][col];
    }
    int max = INT_MIN;
    for (int k = 0; k < n; k++) {
        if (k != col) {
            int t = recurZigZag(arr, row + 1, k, n, dp);
            if (max < t)
                max = t;
        }
    }
    dp[row][col] = std::max(dp[row][col], arr[row][col] + max); //store solution
    return dp[row][col];
}

int main()
{
    int t, n, item;

    cout << "Enter test case:\n";
    cin >> t;

    for (int i = 0; i < t; i++) {
        cout << "Input size of square matrix\n";
        cin >> n;

        vector<vector<int> > arr;

        cout << "Input the square matrix\n";
        for (int i = 0; i < n; i++) {
            vector<int> inn;
            for (int j = 0; j < n; j++) {
                cin >> item;
                inn.push_back(item);
            }
            arr.push_back(inn);
        }

        int** dp = (int**)(malloc(sizeof(int*) * n));

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

        int mymax = INT_MIN;

        for (int i = 0; i < n; i++) {
            int p = recurZigZag(arr, 0, i, n, dp);
            if (p > mymax)
                mymax = p;
        }

        cout << "Maximum zigzag sum: " << mymax << endl;
    }

    return 0;
}

Output

Enter test case:
2
Input size of square matrix 
3
Input the square matrix  
3 8 2  
4 8 5  
6 9 7  
Maximum zigzag sum: 22
Input size of square matrix 
3
Input the square matrix  
3 2 1  
10 8 5 
6 6 4  
Maximum zigzag sum: 18