localSearch.java

private static int[][] swap_values(int[][] sq, int times)
{
    int[][] temp_sq = (int[][]) sq.clone();
    Random rand = new Random();
    for(int i = 0; i < times; i++)
    {
        r1 = rand.nextInt(len(sq));
        c1 = rand.nextInt(len(sq));
        r2 = rand.nextInt(len(sq));
        c2 = rand.nextInt(len(sq));
        int temp = temp_sq[r1][c1];
        temp_sq[r1][c1] = temp_sq[r2][c2];
        temp_sq[r2][c2] = temp;
    }
    return temp_sq;
}

private static ArrayList swapDiag(int[][] sq, int violations, int n)
{
    ArrayList ret = new ArrayList();
    int[][] temp_sq = (int[][]) sq.clone();
    for(int i = 0, int j = sq.length-1; i < sq.length && j >= 0; i++, j--)
    {
        int temp = temp_sq[i][i];
        temp_sq[i][i] = temp_sq[j][j];
        temp_sq[j][j] = temp;
    }
    t_violations = eval_constraints(temp_sq, n);
    if(t_violations < violations)
    {
       sq = temp_sq;
       violations = t_violations;
    }

    ret.add({sq, violations});
    return ret;
}


def swapDiag(sq, violations, n):
    idx = range(0, len(sq))
    temp_sq = list(sq)
    for i,j in zip(idx, idx[::-1]):
        temp_sq[i][i],temp_sq[j][j] = temp_sq[j][j], temp_sq[i][i]
    t_violations = eval_constraints(temp_sq, n)
    if t_violations < violations:
       sq = list(temp_sq)
       violations = t_violations
    return [sq, violations]


private static ArrayList swapCols(int[][] sq, int n)
{
     int[][] sq_cols = new int[sq.length][sq.length];
     for(int i = 0; i < sq.length; i++)
     {
         for(int j = 0; j < sq.length; j++)
         {
             sq_cols[i][j] = sq[j][i];
         }
     }
     int violations = eval_constraints(sq_cols, n);
     ArrayList ret = swapRows(sq_cols, violations, n);
     for(int i = 0; i < sq.length; i++)
     {
         for(int j = 0; j < sq.length; j++)
         {
             sq[i][j] = sq_cols[j][i];
         }
     }
     violations = eval_constraints(sq, n);
     ret.clear();
     ret.add({sq, violations});
     return ret;

}



private static ArrayList swapRows(int[][] sq, int violations, int n)
{
      boolean restart = false;
      ArrayList ret = new ArrayList();
      for(int i = 0; i < sq.length; i++)
      {
          int[][] temp_sq = (int[][]) sq.clone();
          for(int j = i+1; j < sq.length; j++)
          {
              int[] temp = temp_sq[i];
              temp_sq[i] = temp_sq[j];
              temp_sq[j] = temp;
              int t_violations = eval_constraints(temp_sq, n);
              if(t_violations < violations)
              {
                  sq = temp_sq;
                  violations = t_violations;
                  restart = true;
                  break;
              }
          }
          if(restart)
            break;
      }
      ret.add({sq, violations});
      return ret;
}


def swapRows(sq, violations, n):
    restart = False
    for i in range(0, len(sq)):
        temp_sq = list(sq)
        for j in range(i+1, len(sq)):
            temp_sq[i], temp_sq[j] = temp_sq[j], temp_sq[i]
            t_violations = eval_constraints(temp_sq, n)
            if t_violations < violations:
               sq = list(temp_sq)
               violations = t_violations
               restart = True
               break
            else:
               temp_sq[i], temp_sq[j] = temp_sq[j], temp_sq[i]
        if restart:
           break
    return [sq, violations]


private static ArrayList violationDiagR(int[][] sq, int violations, int n)
{
    boolean restart = false;
    ArrayList ret = new ArrayList();
    for(int i = sq.length-1; i >= 0; i--)
    {
        int[][] temp_sq = (int[][]) sq.clone();
        for(int j = i-1, j >= 0; j--)
        {
           int temp = temp_sq[i][i];
           temp_sq[i][i] = temp_sq[j][j];
           temp_sq[j][j] = temp;
           int t_violations = eval_constraints(temp_sq, n);
           if(t_violations < violations)
           {
               sq = temp_sq;
               violations = t_violations;
               restart = true;
           }
           temp = temp_sq[i][i];
           temp_sq[i][i] = temp_sq[j][j];
           temp_sq[j][j] = temp;
        }
        if(restart)
          break
    }
    ret.add({sq, violations});
    return ret;
}


private static ArrayList violationDiagL(int[][] sq, int violations, int n)
{
    boolean restart = false;
    ArrayList ret = new ArrayList();
    for(int i = 0; i < sq.length; i++)
    {
        int[][] temp_sq = (int[][]) sq.clone();
        for(int j = i+1, j < sq.length; j++)
        {
           int temp = temp_sq[i][i];
           temp_sq[i][i] = temp_sq[j][j];
           temp_sq[j][j] = temp;
           int t_violations = eval_constraints(temp_sq, n);
           if(t_violations < violations)
           {
               sq = temp_sq;
               violations = t_violations;
               restart = true;
           }
           temp = temp_sq[i][i];
           temp_sq[i][i] = temp_sq[j][j];
           temp_sq[j][j] = temp;
        }
        if(restart)
          break
    }
    ret.add({sq, violations});
    return ret;
}

private static ArrayList violationCols(int[][] sq, int n)
{
     int[][] sq_cols = new int[sq.length][sq.length];
     for(int i = 0; i < sq.length; i++)
     {
         for(int j = 0; j < sq.length; j++)
         {
             sq_cols[i][j] = sq[j][i];
         }
     }
     int violations = eval_constraints(sq_cols, n);
     ArrayList ret = violationRows(sq_cols, violations, n);
     for(int i = 0; i < sq.length; i++)
     {
         for(int j = 0; j < sq.length; j++)
         {
             sq[i][j] = sq_cols[j][i];
         }
     }
     violations = eval_constraints(sq, n);
     ret.clear();
     ret.add({sq, violations});
     return ret;
}


private static ArrayList violationRows(int[][] sq, int violations; int n)
{
    boolean restart = false;
    ArrayList options = new ArrayList();
    for(int i = 0; i < sq.length; i++)
    {
        int[][] temp_sq = (int[][]) sq.clone();
        for(int j = 0; j < sq.length; j++)
        {
            for(int k = 0; k < sq.length; k++)
            {
                for(int g = 0; g < sq.length; g++)
                {
                   int temp = temp_sq[i][j];
                   temp_sq[i][j] = temp_sq[k][g];
                   temp_sq[k][g] = temp;
                   int t_violations = eval_constraints(temp_sq, n);
                   if (t_violations < violations)
                   {
                      sq = temp_sq;
                      violations = t_violations;
                      restart = true;
                      break;
                   }
                   temp = temp_sq[i][j];
                   temp_sq[i][j] = temp_sq[k][g];
                   temp_sq[k][g] = temp;
                }
                if(restart)
                  break;
            }
            if(restart)
              break;
        }
        if(restart)
          break;
    }
    options.add({sq, violations});
    return options;
}

private static ArrayList violationColsLargest(int[][] sq, int n)
{
     int[][] sq_cols = new int[sq.length][sq.length];
     for(int i = 0; i < sq.length; i++)
     {
         for(int j = 0; j < sq.length; j++)
         {
             sq_cols[i][j] = sq[j][i];
         }
     }
     int violations = eval_constraints(sq_cols, n);
     ArrayList ret = violationRowsLargest(sq_cols, violations, n);
     for(int i = 0; i < sq.length; i++)
     {
         for(int j = 0; j < sq.length; j++)
         {
             sq[i][j] = sq_cols[j][i];
         }
     }
     violations = eval_constraints(sq, n);
     ret.clear();
     ret.add({sq, violations});
     return ret;
}

private static ArrayList violationRowsLargest(int[][] sq, int violations, int n)
{
    boolean restart = false;
    ArrayList options = new ArrayList();
    for(int i = 0; i < sq.length; i++)
    {
        int[][] temp_sq = (int[][]) sq.clone();
        for(int j = 0; j < sq.length; j++)
        {
            for(int k = 0; k < sq.length; k++)
            {
                for(int g = 0; g < sq.length; g++)
                {
                   int temp = temp_sq[i][j];
                   temp_sq[i][j] = temp_sq[k][g];
                   temp_sq[k][g] = temp;
                   int t_violations = eval_constraints(temp_sq, n);
                   if (t_violations < violations)
                   {
                      int[] idx1 = {i,j};
                      int[] idx2 = {k,g};
                      Object[] out = {idx1, idx2, t_violations}
                      options.add(out)
                   }
                   temp = temp_sq[i][j];
                   temp_sq[i][j] = temp_sq[k][g];
                   temp_sq[k][g] = temp;
                }
            }
        }
    }

    if(options.size() > 0)
    {
        ArrayList<Integer> costs = new ArrayList<>();
        for(Object[] o: options)
        {
            costs.add(((Integer) o[2]));
        }
        Object[] swap = options.get(costs.indexOf(Collections.max(costs)));
        int temp = sq[(Integer) swap[0][0]][(Integer) swap[0][1]];
        sq[(Integer) swap[0][0]][(Integer) swap[0][1]] = sq[(Integer) swap[1][0]][(Integer) swap[1][1]];
        sq[(Integer) swap[1][0]][(Integer) swap[1][1]] = temp;
        violations = swap[2]
    }
    options.clear();
    options.add({sq, violations});
    return options;
}

private static int eval_constraints(int[][] sq, int n)
{
    int rowDiff = 0;
    int colDiff = 0;
    int rDiagonal = 0;
    int lDiagonal = 0;
    for(int row = 0; row < sq.length; row++)
    {
        sum_col = 0;
        sum_row = 0;
        for(int col = 0; i < sq.length; i++)
        {
            sum_col += sq[col][row];
            sum_row += sq[row][col];
            if(row == col)
               leftDiagonal += sq[row][col];
            if(row+col == sq.length-1):
               rightDiagonal += sq[row][col];
        }
        rowDiff += Math.abs(sum_row-n);
        colDiff += Math.abs(sum_col-n);
    }
    return Math.abs(rDiagonal-n)+Math.abs(lDiagonal-n)+rowDiff+colDiff;
}

private static int[][] initial_square(ArrayList<Integer> l)
{
       int[][] sq = new int[l.size()][l.size()]
       for(int i = 0; i < sq.length; i++)
       {
           for(int j = i*sq.length; j < (i+1)*sq.length; j++)
           {
               sq[i][j] = l.remove(j);
           }
       }
       return sq;
}

public static boolean local_search(ArrayList<Integer> l, int n, int max_iter)
{
       int[][] sq = initial_square(l);
       int violations = eval_constraints(sq, n);
       int iteration = 0;
       int rand = 0;
       int last_violations = 0;
       ArrayList ret;
       if(violations == 0)
         return true
       while(violations != 0)
       {
          last_violations = violations;
          ret = violationRowsLargest(sq,violations,n);
          (int[][]) (int[][]) sq = ret.get(0);
          (int) (int) violations = ret.get(1);
          ret = violationColsLargest(sq, n);
          (int[][]) sq = ret.get(0);
          (int) violations = ret.get(1);
          ret = violationRows(sq,violations,n);
          (int[][]) sq = ret.get(0);
          (int) violations = ret.get(1);
          ret = violationCols(sq,n);
          (int[][]) sq = ret.get(0);
          (int) violations = ret.get(1);
          ret = violationDiagL(sq,violations,n);
          (int[][]) sq = ret.get(0);
          (int) violations = ret.get(1);
          ret = violationDiagR(sq,violations,n);
          (int[][]) sq = ret.get(0);
          (int) violations = ret.get(1);
          ret = swapRows(sq,violations,n);
          (int[][]) sq = ret.get(0);
          (int) violations = ret.get(1);
          ret = swapCols(sq,n);
          (int[][]) sq = ret.get(0);
          (int) violations = ret.get(1);
          ret = swapDiag(sq, violations, n);

          if(last_violations == violations)
          {
              sq = swapValues(sq, 2);
              violations = eval_constraints(sq, n);
              rand++;
          }
          iteration++;
          System.out.println(String.format("Iteration %d | Violations: %d (Random %d)", iteration, violations, rand));
          if(iter == max_iter)
          {
              break;
          }
          if(violations == 0)
          {
              break;
          }
       }
       if(violations == 0)
          return true;
       return false;
}