is it possible to solve this problem with "smart" backtracking algo using a lot of restrictions ?

As I know YES.
But there easy and beautiful math solution.

give me a hint how to solve it without using backtracking algorithm

thank you

ur e-mail ...

wetdrag@gmail.com

Please send it to me too.
eros_89@yandex.ru

About math solution.. I am trying to it by the following way:
Assume a connection between stops A and B. Then connection from B to A exists too. Then, to satisfy the problem's conditions, we have to introduce (2*n-1)*n connections (ordered in such a way that each tram route has 2*n-1 connections). All the connections are distinct.
Next, each tram stop has exactly 2*n-1 connections to other distinct stops. It is always odd integer, so every tram stop must appear exactly once at the beginning of single route, and next time it must appear (2*n-2)/2=n-1 times in the middle of other routes. It is true for all the routes.
So first we should build the following answer matrix if we consider n = 3:
1 x x x x 4
2 x x x x 5
3 x x x x 6

Then I am trying to place other elements to the matrix according to some placement rules from the thoughts above, but I am still unable to come up with a good solution.
Could someone point out, am I going correct in my math thoughts or such approach leads to naive backtracking solution? Thanks!
Sorry I was so verbose :D

No more math is needed. Now you can use backtracking.

I resisted the idea of writing a backtracking algo, but decided to implement it with rule of placing elements leftmost and outermost as you suggested and got AC :) Thank you.
PS. I wonder if it is possible to write a backtracking solution without any initial placements or not.

2 Chmel_Tolstiy: Could you please give me small hint about a math solution? master.wsd064 (no spam) gmail.com

Edited by author 03.04.2008 18:27

your Idea is a 2/3 of all way. just try to find a regularity between this paths. I think it's easy.

naxart[at]yandex[dot]ru

it's my email.

I've found simple maths solution, here is my solution for n=3
1 2 3 4 5 6
2 4 6 1 3 5
3 6 2 5 1 4

Edited by author 02.06.2008 05:28

Edited by author 02.06.2008 05:28

There is no need for _smart_ backtracking. I placed 1..n on the left side and n..2n on the right side. Then I launched recursion over all cells row-by-row, column-by-column, taking every edge (i;j) exactly once, and it's AC in 0.078 sec.

For n=100 there occurs only 562 returns. So, it's almost greedy algo.

The only problem was expanding that recursion into a loop 'cuz I had stack overflow with 200x100 calls.

Edited by author 25.07.2008 17:31

I want to know too.
pkkj@tom.com

Thanks.

Only math solution   acceptable
because this is structure design problem.
I spent a lot of time but was unable to find it.
Solution easy to find in internet with key words
"decomposing complete graph in hamilton paths"
Use diameters and  walk left-rigth- down with respect to them.

Edited by author 14.08.2009 11:02

no subject

Edited by author 14.08.2009 11:03

Nice article about graph decompositions.
http://people.qc.cuny.edu/faculty/christopher.hanusa/courses/634sp11/Documents/634ch2-3.pdf

Edited by author 21.08.2011 14:38

Continue filling the matrix from both left and right.
Keep each pair of opposite columns contain every tram stops.