Arrange the numbers

[Arjun Shastry]

This one is simpler:
Arrange the numbers from 1 to 9(1 & 9 inclusive) along a circle such that sum of two neighbors is NEVER divisible by 3,5,7.

[David Weitzman]

Finding the solution isn't too hard, but I found that the question afforded me an opportunity to write some code in ML to get some practice.
The solution can be found with this SML code. It's quite snappy for this problem, however it's not all that scalable overall due to the problem constraints. I represent the problem as a graph and attempt to find a Hamiltonian cycle, which is an NP problem.

fun legalEdge (a, b) = not (a = b orelse 0 = foldl (fn (x, y) => x * y) 1 (map (fn m => (a + b) mod m) [3, 5, 7]))
fun mkGraph (0, graph : int list list) = graph
  | mkGraph (n, graph : int list list) =
  let
    val empty : int list = []
    fun mkGraphH (a, 0, graph) = graph
      | mkGraphH (a, n, first :: rest) = if (legalEdge(a, n)) then mkGraphH(a, n - 1, (n :: first) :: rest) else mkGraphH(a, n - 1, first :: rest)
  in
    mkGraph(n - 1, mkGraphH (n, 9, empty :: graph))
  end
val graph = mkGraph (9, [])
(* We've got the graph. Time to find the longest cycle *)
fun notSeen seen value = not (List.exists (fn n => value = n) seen)
fun getAdj (first::rest, 1) = first
  | getAdj (first::rest, n) = getAdj(rest, n-1)
fun findCycle (graph, node, seen, con) =
  let
    val legalNextStops = List.filter (notSeen seen) (getAdj(graph, node))
    fun findCycleH (graph, [], seen, cont) = if List.length seen = 9 andalso legalEdge (hd seen, List.last seen) then seen else cont ()
      | findCycleH (graph, node :: rest, seen, cont) = findCycle(graph, node, seen, fn () => findCycleH(graph, rest, seen, cont))
  in
   findCycleH (graph, legalNextStops, node :: seen, con)
  end;
val solutions = findCycle (graph, 1, [], (fn () => []))

[Arjun Shastry]

Havn't gone through thr program.Hamiltonian Path soln. is right.We can start with any digit and connect to another digit by given condition.I made a table containing digit and its possible neighbors.and started with digits which has least number of neighbors.

[Karthikeyan Rajendraprasad]

the solution is

                          1
                    3            7
               8                      4
                  5               9
                      6       2
 

got it manually.......... still trying to find the same solution using a program
[ February 24, 2004: Message edited by: Karthikeyan Rajendraprasad ]