[algogeeks] Re: Arrange Matrices In Order

[siva]

This is the solutions that I am able to arrive at.
This generates all the permutations in the order required. but takes
quite a lot of time for 6th generation.

Need to check whether this solution can be optimized more.

public class P2D
{
  boolean usedr[][];
  boolean usedc[][];
  //temp matrix for generation
  int t[][];
  int N;
  void p(int N)
  {
    usedr = new boolean[N][N];
    usedc = new boolean[N][N];
    t=new int[N][N];
    this.N = N;

    _p(0, 0);
  }
  int found;
  void _p(int xlevel_, int ylevel_)
  {
    //Output.print("T: ", t);
    if (xlevel_== N && ylevel_ == N-1)
    {
      //Output.print("Found: ", t);
      //print the generated matric in the 't'
      found++;
      return;
    }
    else if (xlevel_ == N)
    {
      ylevel_++;
      xlevel_ = 0;
    }

    for(int i=0; i<N; i++)
    {
      if (!usedc[xlevel_][i] && !usedr[ylevel_][i]) {
        usedc[xlevel_][i]=true;
        usedr[ylevel_][i] = true;
            t[xlevel_][ylevel_]=(i+1);
            _p(xlevel_+1, ylevel_);
        usedc[xlevel_][i]=false;
        usedr[ylevel_][i] = false;
      }
    }
  }

  public static void main(String[] args)
  {
    P2D p = new P2D();
    p.p(5);
    System.out.println("Found: "+p.found);
  }
}

Regards,
siva