How to make a N×N matrix each of i-th row and i-th column having all the elements 1 to 2N-1?

this has simple solution for square matrices where n is power of 2 so n=1,2,4,8,16,... do not ask me why there surely is some math proof for it ...

The algorithm to create such matrix is easy:

1. clear matrix (with 0)

2. loop i through all values i=1,2,3...2n-1

3. for each i find all locations where i matrix is not yet filled (0) and there is not i present in row and column

   fill the position with i and repeat until no such location found.

In C++ something like this:

//---------------------------------------------------------------------------
const int n=8;
int m[n][n];
//---------------------------------------------------------------------------
// compute histogram u[n+n] of values per ith row,col of m[n][n]
void hist_rst(int *u                  ) { for (int j=0;j<n+n;j++) u[j]=0; }
void hist_row(int *u,int m[n][n],int i) { for (int j=0;j<n;j++) u[m[j][i]]=1; }
void hist_col(int *u,int m[n][n],int i) { for (int j=0;j<n;j++) u[m[i][j]]=1; }
//---------------------------------------------------------------------------
void matrix_init(int m[n][n])
    {
    int i,x,y,h[n][n+n];
    // clear matrix (unused cells)
    for (x=0;x<n;x++)
     for (y=0;y<n;y++)
      m[x][y]=0;
    // clear histograms
    for (i=0;i<n;i++) hist_rst(h[i]);
    // try to fill values 1..2n-1
    for (i=1;i<n+n;i++)
        {
        // find free position
        for (x=0;x<n;x++) if (!h[x][i])
         for (y=0;y<n;y++) if (!h[y][i])
          if (!m[x][y])
            {
            // set cell
            m[x][y]=i;
            h[x][i]=1;
            h[y][i]=1;
            break;
            }
        }
    }
//---------------------------------------------------------------------------

here few outputs:

  1

  1  3
  2  1

  1  5  6  7
  2  1  7  6
  3  4  1  5
  4  3  2  1
            
  1  9 10 11 12 13 14 15
  2  1 11 10 13 12 15 14
  3  4  1  9 14 15 12 13
  4  3  2  1 15 14 13 12
  5  6  7  8  1  9 10 11
  6  5  8  7  2  1 11 10
  7  8  5  6  3  4  1  9
  8  7  6  5  4  3  2  1

for non power of 2 matrices you could use backtracking but take in mind even 4x4 matrix will have many iterations to check ... so some heuristics would need to be in place to make it possible in finite time... as brute force is (n+n)^(n*n) so for n=4 there are 281474976710656 combinations to check ...

[edit1] genere&test solution for even n

//---------------------------------------------------------------------------
const int n=6;
int m[n][n];
//---------------------------------------------------------------------------
// compute histogram u[n+n] of values per ith row,col of m[n][n]
void hist_rst(int *u                  ) { for (int j=0;j<n+n;j++) u[j]=0; }
void hist_row(int *u,int m[n][n],int i) { for (int j=0;j<n;j++) u[m[j][i]]=1; }
void hist_col(int *u,int m[n][n],int i) { for (int j=0;j<n;j++) u[m[i][j]]=1; }
//---------------------------------------------------------------------------
void matrix_init2(int m[n][n])  // brute force
    {
    int x,y,a,ax[(n*n)>>1],ay[(n*n)>>1],an,u[n+n];
    // clear matrix (unused cells)
    for (x=0;x<n;x++)
     for (y=0;y<n;y++)
      m[x][y]=0;
    // main diagonal 1,1,1,1...
    for (x=0;x<n;x++) m[x][x]=1;
    // 1st row 1,2,3...n
    for (x=1;x<n;x++) m[x][0]=x+1;
    // cells for brute force
    for (an=0,x=0;x<n;x++)
     for (y=0;y<x;y++)
      if (!m[x][y])
        {
        ax[an]=x;
        ay[an]=y;
        an++;
        m[x][y]=2;
        }
    // brute force attack values 2,3,4,5,...,n-1
    for (;;)
        {
        // increment solution
        for (a=0;a<an;a++)
            {
            x=ax[a];
            y=ay[a];
            m[x][y]++;
            if (m[x][y]<=n) break;
            m[x][y]=2;
            }
        if (a>=an) break;   // no solution
        // test
        for (x=0;x<n;x++)
            {
            hist_rst(u);
            hist_col(u,m,x);
            hist_row(u,m,x);
            for (y=1;y<=n;y++) if (!u[y]) { y=0; x=n; break; }
            }
        if (y) break;       // solution found
        }

    // mirror other triangle
    for (x=0;x<n;x++)
     for (y=0;y<x;y++)
      m[y][x]=m[x][y]+n-1;
    }
//---------------------------------------------------------------------------

however its slow so do not try to go with n>6 without more optimizations/better heuristics... for now it is using triangle+mirror and diagonal + first row hard-coded heuristics.

maybe somehow exploit the fact that each iterated value will be placed n/2 times could speed this up more but too lazy to implement it ...

Here output for n=6:

[  52.609 ms]
  1  2  3  4  5  6
  7  1  6  5  3  4
  8 11  1  2  4  5
  9 10  7  1  6  3
 10  8  9 11  1  2
 11  9 10  8  7  1

iterating through 5^10 cases ...