My graph will be made of 2 disjoint linear paths, with some interconnections added between those 2 paths.

I will want to find if a longer (longest) path can be found thanks to those new connections.

For example, one path might go 1-2-3-4-5-6, the other might be a-b-c-d-e-f.

If a 5-c connection is added, then 1-2-3-4-5-c-d-e-f is the longest path.

(the actual paths might be much longer)

 

I have this problem cause I am trying to join two non-crossing knight path on 2 halves of a square board.

I split the board in two cause finding a good path for the whole board takes too long (years...), so i want to find a good solution for the halves (or the quarters) and join them where they can connect to obtain the longest possible path.

Easier said than done.

 

Wow

This part of a course assignement?

See

It's not an assignment, just a distraction.

I already get results, trying all paths, backtracking when stuck.

I can explore the whole combinatorial space for small boards (up to 9x9), and find the longest possible path.

But for bigger board, I can not. My program will find a tight solution for the terminal part of the path, but not for it's early part because it has only time to backtrack a little. So the solution I can find are far than optimal, and can easily be improved upon visual inspection (which my program doesn't).

 

(insert image not working)

Thus the First moves would also be good.

I can't really help you.

I did find some reference to graph in Java.

This one seems quite good:

http://algs4.cs.princeton.edu/40graphs/

http://algs4.cs.princeton.edu/41undirected/

http://algs4.cs.princeton.edu/41undirected/Graph.java.html

but it's too much for me, since I don't really know Java.