I eventually need to get written some software, specification below.
Have so far used 5 different developers, mostly in India who have all
failed to come up with a solution. For $100 I would be happy to be
told how a developer should go about solving this. However if anyone
wants to quote for doing the whole web based application please do so.
Specification for a web application for the seating of guests around a
table for 5 consecutive meals on one table.

Requirements:
Written in preferably PHP or Javascript for a Unix Appache server.
Work out the optimal seating arrangement for between 8 and 30 guests
at five consecutive meals, allowing for new and leaving guests and for
input from the user, following 3 rules of which the first is paramount
1.	Spouses do not sit next to each other (this rule can only be broken
by the user placing a husband next to a wife)
2.	Men should as far as possible sit next to women, the only time this
rule should be broken is if the user places people of the same sex
next to each other or that there are uneven numbers eg 5 men and 4
women, then obviously 2 men will have to sit next to each other but
the software must make it as equitable as possible eg the same man
must not always end up sitting next to another man
3.	As far as possible people do not sit next to the same people as
they have sat next to before. Obviously for say a meal of 5 couples
(10 people) by meal 3 this would be impossible so again this would
occur but on an equitable basis

The application would work by the user entering in the names of guests
? Title, first name and surname. It must cope with couples and single
persons
Then the user will place whatever guests he wishes on the table plan,
this will usually entail him putting himself, the host at one end of
the table and perhaps the hostess opposite.
Then he will click ?autofill? and the software will work out the
optimal plan using the rules as above
A seating plan will be produced, possibly if there can be more than
one arrangement which is certainly likely to occur at meal 1, then the
software should produce up to ,say, 5 possible arrangements and the
user can choose his preferred one
When the user has chosen the plan for meal 1 he will have the option
of saving the plan and/or printing it, and the software must remember
the plan
The user will then be shown the list of guests and he can remove or
add to it. Then for meal 2 he again can place any of the guests and
then click ?autofill? and the software will again work out the optimal
seating arrangement, following the rules and remembering the previous
arrangements.
Same for meal 3, 4 and 5

Please note that if a guest is removed at, say, meal 2 but returns at
meal 3, the software must still take into account who she/he had sat
next to previously ie it must not forget the seating arrangements of
guests once they have been removed as they might return for a later
meal
Specification for a web application for the seating of guests around a
table for 5 consecutive meals on one table.

Requirements:
Written in preferably PHP or Javascript for a Unix Appache server.
Work out the optimal seating arrangement for between 8 and 30 guests
at five consecutive meals, allowing for new and leaving guests and for
input from the user, following 3 rules of which the first is paramount
1.	Spouses do not sit next to each other (this rule can only be broken
by the user placing a husband next to a wife)
2.	Men should as far as possible sit next to women, the only time this
rule should be broken is if the user places people of the same sex
next to each other or that there are uneven numbers eg 5 men and 4
women, then obviously 2 men will have to sit next to each other but
the software must make it as equitable as possible eg the same man
must not always end up sitting next to another man
3.	As far as possible people do not sit next to the same people as
they have sat next to before. Obviously for say a meal of 5 couples
(10 people) by meal 3 this would be impossible so again this would
occur but on an equitable basis

The application would work by the user entering in the names of guests
? Title, first name and surname. It must cope with couples and single
persons
Then the user will place whatever guests he wishes on the table plan,
this will usually entail him putting himself, the host at one end of
the table and perhaps the hostess opposite.
Then he will click ?autofill? and the software will work out the
optimal plan using the rules as above
A seating plan will be produced, possibly if there can be more than
one arrangement which is certainly likely to occur at meal 1, then the
software should produce up to ,say, 5 possible arrangements and the
user can choose his preferred one
When the user has chosen the plan for meal 1 he will have the option
of saving the plan and/or printing it, and the software must remember
the plan
The user will then be shown the list of guests and he can remove or
add to it. Then for meal 2 he again can place any of the guests and
then click ?autofill? and the software will again work out the optimal
seating arrangement, following the rules and remembering the previous
arrangements.
Same for meal 3, 4 and 5

Please note that if a guest is removed at, say, meal 2 but returns at
meal 3, the software must still take into account who she/he had sat
next to previously ie it must not forget the seating arrangements of
guests once they have been removed as they might return for a later
meal
Specification for a web application for the seating of guests around a
table for 5 consecutive meals on one table.

Requirements:
Written in preferably PHP or Javascript for a Unix Appache server.
Work out the optimal seating arrangement for between 8 and 30 guests
at five consecutive meals, allowing for new and leaving guests and for
input from the user, following 3 rules of which the first is paramount
1.	Spouses do not sit next to each other (this rule can only be broken
by the user placing a husband next to a wife)
2.	Men should as far as possible sit next to women, the only time this
rule should be broken is if the user places people of the same sex
next to each other or that there are uneven numbers eg 5 men and 4
women, then obviously 2 men will have to sit next to each other but
the software must make it as equitable as possible eg the same man
must not always end up sitting next to another man
3.	As far as possible people do not sit next to the same people as
they have sat next to before. Obviously for say a meal of 5 couples
(10 people) by meal 3 this would be impossible so again this would
occur but on an equitable basis

The application would work by the user entering in the names of guests
? Title, first name and surname. It must cope with couples and single
persons
Then the user will place whatever guests he wishes on the table plan,
this will usually entail him putting himself, the host at one end of
the table and perhaps the hostess opposite.
Then he will click ?autofill? and the software will work out the
optimal plan using the rules as above
A seating plan will be produced, possibly if there can be more than
one arrangement which is certainly likely to occur at meal 1, then the
software should produce up to ,say, 5 possible arrangements and the
user can choose his preferred one
When the user has chosen the plan for meal 1 he will have the option
of saving the plan and/or printing it, and the software must remember
the plan
The user will then be shown the list of guests and he can remove or
add to it. Then for meal 2 he again can place any of the guests and
then click ?autofill? and the software will again work out the optimal
seating arrangement, following the rules and remembering the previous
arrangements.
Same for meal 3, 4 and 5

Please note that if a guest is removed at, say, meal 2 but returns at
meal 3, the software must still take into account who she/he had sat
next to previously ie it must not forget the seating arrangements of
guests once they have been removed as they might return for a later
meal
Specification for a web application for the seating of guests around a
table for 5 consecutive meals on one table.

Requirements:
Written in preferably PHP or Javascript for a Unix Appache server.
Work out the optimal seating arrangement for between 8 and 30 guests
at five consecutive meals, allowing for new and leaving guests and for
input from the user, following 3 rules of which the first is paramount
1.	Spouses do not sit next to each other (this rule can only be broken
by the user placing a husband next to a wife)
2.	Men should as far as possible sit next to women, the only time this
rule should be broken is if the user places people of the same sex
next to each other or that there are uneven numbers eg 5 men and 4
women, then obviously 2 men will have to sit next to each other but
the software must make it as equitable as possible eg the same man
must not always end up sitting next to another man
3.	As far as possible people do not sit next to the same people as
they have sat next to before. Obviously for say a meal of 5 couples
(10 people) by meal 3 this would be impossible so again this would
occur but on an equitable basis

The application would work by the user entering in the names of guests
? Title, first name and surname. It must cope with couples and single
persons
Then the user will place whatever guests he wishes on the table plan,
this will usually entail him putting himself, the host at one end of
the table and perhaps the hostess opposite.
Then he will click ?autofill? and the software will work out the
optimal plan using the rules as above
A seating plan will be produced, possibly if there can be more than
one arrangement which is certainly likely to occur at meal 1, then the
software should produce up to ,say, 5 possible arrangements and the
user can choose his preferred one
When the user has chosen the plan for meal 1 he will have the option
of saving the plan and/or printing it, and the software must remember
the plan
The user will then be shown the list of guests and he can remove or
add to it. Then for meal 2 he again can place any of the guests and
then click ?autofill? and the software will again work out the optimal
seating arrangement, following the rules and remembering the previous
arrangements.
Same for meal 3, 4 and 5

Please note that if a guest is removed at, say, meal 2 but returns at
meal 3, the software must still take into account who she/he had sat
next to previously ie it must not forget the seating arrangements of
guests once they have been removed as they might return for a later
meal

---

Clarification of Question by timmyh-ga on 13 Dec 2005 00:59 PST

Thank you for your thoughts. The absolute golden rule is that no
husbands sit next to wives unless placed by the user which would be
exceptional. The next rule that no-one of the same sex sits next to
each other unless uneven number eg more females than males or placed
by the user again, should not be broken, so the only rule which can be
freely broken by the software is that people can sit next to someone
they have sat next to before, but this should only occur where
necessary ie at meal 3 for 5 couples. By equitable I mean that if in
the above example Mr A sits next to Mrs B for the second time at meal
3 then they should not sit together for meal 4.

The core problem sounds like a job for a rule engine but there's more
to it. Without deeper investigation, I can't say whether
algorithmically your problem can be helped by something like Rete but
you can take a look for yourself.
http://en.wikipedia.org/wiki/Rete_algorithm

Dear friend,
If I understood correctly what is important for you is the optimum
plan according to your input parameters. Am I right?
If yes, you should use one of the artificial life/artificial
computation techniques to find the optimum solution like Genetic
Algorithm, Simulated Annealing, Tabu Search, Ant Colonies, ....
All these techniques go beyond the classical design to provide a
method that is dramatically changing our ability to solve problems of
practical significance. Current applications of these span the realms
of resource planning, telecommunications, VLSI design, financial
analysis, scheduling, space planning, energy distribution, molecular
engineering, logistics, pattern classification, flexible
manufacturing, waste management, mineral exploration, biomedical
analysis, environmental conservation and scores of others. In recent
years, journals in a wide variety of fields have published tutorial
articles and computational studies documenting successes by these
artificial life methods in extending the frontier of problems that can
be handled effectively -- yielding solutions whose quality often
significantly surpasses that obtained by methods previously applied.

In my opinion and based on my experienes in Tabu Search and Genetic
Algorithm, you can not solve your problem according to classical
methods and I think that's why your programmers failed to handle it.

Timmy,
This is your project, so you can make up the rules, but it seems that
in point 2 by allowing yourself to place guests at the table, even two
of one gender next to each other, you are undercutting the general
parameters that you have stated.  You can define where you sit (odd
numbered chair), but then (with an equal number of men and women) your
wife must sit on an even chair.  If you seat two ladies next to each
other, then two men must also sit together (as you have pointed out,
and if you seat anyone else, the problem becomes more difficult).

If husbands and wives may not sit next to each other at any of the
five meals, the wives are eliminated from the pool of women who may
sit adjacent to a man.  With fifteen couples, each man will need ten
women in the party to have as different partners (left and right) for
five meals, so that with less than eleven couples it is obviously
impossible to have a solution for five meals.

I can't prove it, but I suspect that even with 15 couples it will be
impossible to avoid a man's sitting next to his wife.  Of course, with
a single or two, the problem would be easier, but the computer program
has to deal with the more difficult scenario.

Okay, you have recognized that with a smaller group the problem can
only be solved by allowing the exception that then repeated adjacent
seating must be on an equitable basis, which needs defintion.  Is
sitting next to spouse still an absolute no-no?

I expect that a computer program cannot deal with this kind of
exception  - or that the programmers gave up at trying to define it.

But I am not one, so maybe I am being unfair.
Good luck, Myoarin

Dear Timmy, 
"Tabu Search" technique:
1. Solution= Integer Array
   Array Size = Number of guests
   element = The id number of the guest

2. Objecttive function:
2.1. Rule 1: Initialize F1=0
          For i= 1 To Number of Guests
             If IsCouple( Solution(i), Solution(i+1))= True Then F1=F1+1
          End for
2.2. Rule 2: Initialize F2=0
          For i= 1 To Number of Guests
             If HaveSameSex( Solution(i), Solution(i+1))= True Then F2=F2+1
          End for
2.3. Rule 2: Initialize F3=0
          For i= 1 To Number of Guests
             If SatNextBefore( Solution(i), Solution(i+1))= True Then F3=F3+1
          End for
2.4. Objeective Function: F= F1 + F2 + F3
2.5. goal: Try to minimize the objective function value (F)
2.6. move: Swap Move: move Solution(i) to Solution(j) and Solution(j)
to Solution(i) where i<>j

2.5. Tabu Search algorithm:
     IterationCount=40  // The number of iterations the algorithm occurs
     TempBestSolution= InitialSolution
     TempBestValue = GetObjectiveFnctionValue(CurrentSolution)         
     CurrentSolution = TempBestSolution
     CurrentValue = TempBestValue
     BesttMove = {} // empty move
     BestSolution= CurrentSolution
     BestValue= CurrentValue
     For i=1 to IterationCount
          For j= 1 to Number of Guests
              For k= 1 to Number of Guests
                   CurrentSolution= Apply Move(j,k) on CurrentSolution
                   CurrentValue=GetObjectiveFnctionValue(CurrentSolution)
                   If IsTabu(Move(j,k))= False Then
                       If  CurrentValue < TempBestValue Then
                            TempBestSolution = CurrentSolution
                            TempBestValue = CurrentValue
                            BestMove = Move(j,k)
                       Else If 
                   ElseIf CurrentValue < BestValue Then  // Aspiration Criteria
                       TempBestSolution = CurrentSolution
                       TempBestValue = CurrentValue      
                       BestMove = Move(j,k)
                   End If 
               Next k
           Next j
           Call MakeTabu(BestMove)   // This prevents from TempBest
                                     // visited moves and from recycling
           If TempBestValue < BestValue Then
                 BestSolution = TempBestSolution
                 BestValue = TempBestValue
           end If 
     Next i             

This is a pseudo code uses Tabu Search as one of the artificial
computation methods which is a meta-heuristic technique for solving
NP-Complete problems, like yours.
After a few iterations you will have optimum or near optimum (Because
of exceptions) of your problem.

The art of this algorithm is just the Objective function definition.
In here, I didn't explain Tabu Search. If you need to know more about
it let me know then I will explain it in detail for you.
Hope it helps you

After a few iterations finally

Dear Timmy read this one please, in the previous oneI had some dictation mistakes. 

"Tabu Search" technique:
1. Solution= Integer Array
   Array Size = Number of guests
   element = The id number of the guest

2. Objecttive function:
2.1. Rule 1: Initialize F1=0
          For i= 1 To Number of Guests
             If IsCouple( Solution(i), Solution(i+1))= True Then F1=F1+1
          End for
2.2. Rule 2: Initialize F2=0
          For i= 1 To Number of Guests
             If HaveSameSex( Solution(i), Solution(i+1))= True Then F2=F2+1
          End for
2.3. Rule 3: Initialize F3=0
          For i= 1 To Number of Guests
             If SatNextBefore( Solution(i), Solution(i+1))= True Then F3=F3+1
          End for
2.4. Objeective Function: F= F1 + F2 + F3

3. Goal: Try to minimize the objective function value (F)
4. move: Swap Move: move Solution(i) to Solution(j) and Solution(j)
                    to Solution(i) where i<>j

5. Tabu Search algorithm:
     IterationCount=40  // The number of iterations the algorithm occurs
     TempBestSolution= InitialSolution
     TempBestValue = GetObjectiveFnctionValue(TempBestSolution)         
     CurrentSolution = TempBestSolution
     CurrentValue = TempBestValue
     BesttMove = {} // empty move
     BestSolution= CurrentSolution
     BestValue= CurrentValue

     For i=1 to IterationCount
          For j= 1 to Number of Guests
              For k= 1 to Number of Guests
                   CurrentSolution= Apply Move(j,k) on CurrentSolution
                   CurrentValue=GetObjectiveFnctionValue(CurrentSolution)
                   If IsTabu(Move(j,k))= False Then
                       If  CurrentValue < TempBestValue Then
                            TempBestSolution = CurrentSolution
                            TempBestValue = CurrentValue
                            BestMove = Move(j,k)
                       End If 
                   ElseIf CurrentValue < BestValue Then  // Aspiration Criteria
                       TempBestSolution = CurrentSolution
                       TempBestValue = CurrentValue      
                       BestMove = Move(j,k)
                   End If 
               Next k
           Next j
           Call MakeTabu(BestMove)   // This prevents from TempBest revisiting
                                     // and from recycling

           If TempBestValue < BestValue Then
                 BestSolution = TempBestSolution
                 BestValue = TempBestValue
           end If 
     Next i             

This is a pseudo code, uses Tabu Search as one of the artificial
computation methods which is a meta-heuristic technique for solving
NP-Complete problems, like yours.
After a few iterations you will have optimum solution or near optimum
solution (Because of exceptions) for your problem.

The art of this algorithm is just the Objective function definition.

In here, I didn't explain Tabu Search. If you need to know more about
it let me know then I will explain it in detail for you.
Hope it helps you

Timmy and Nejla,
Google Answers may delete questions that list alternate contact addresses.
So keep the discussion here in the open.  It is very interesting.
Regards, Myoarin

I think for this particular problem a combination of tabu search with
genetic algorithm is more appropriate.

I am very knowledgeable of both heuristics and php software
development. If you want I can produce a document that would outline
the entire software development but you seem to already have a lead,
if it is still not what you want, get back to me and I will do it for
you.

grosnombril,
Unlike you, I don't think using a hybrid model, I mean a combination
of Tabu Search and Genetic Algorithm, will be apprepriate in this
case.

We shouldn't make things dificult! One of our important goals is to
solve problems in a simple and easy manner. Timmy's problem can be
solve easily with one of the artificial life techniques. we do not
need to use hybrid ones in here, and among these techniques I believe
Tabu Search is easeir to understand for a person who is noth familiar
with artificial computation techniques.

I editted a little the step5 to make it more clear.

5. Tabu Search algorithm:
     IterationCount=40  // The number of iterations the algorithm occurs
     CurrentSolution= InitialSolution
     CurrentValue = GetObjectiveFnctionValue(TempBestSolution)         

     TempBestSolution= CurrentSolution
     TempBestValue = CurrentValue         

     BestSolution= CurrentSolution
     BestValue= CurrentValue

     BesttMove = {} // empty move

     For i=1 to IterationCount
         // Find the best simple move(one swap move) at each iteration
          For j= 1 to Number of Guests
              For k= 1 to Number of Guests
                   CurrentSolution= Apply Move(j,k) on CurrentSolution
                   CurrentValue=GetObjectiveFnctionValue(CurrentSolution)

                   If IsTabu(Move(j,k))= False Then
                       If  CurrentValue < TempBestValue Then
                            TempBestSolution = CurrentSolution
                            TempBestValue = CurrentValue
                            BestMove = Move(j,k)
                       End If 
                   ElseIf CurrentValue < BestValue Then  // Aspiration Criteria
                       TempBestSolution = CurrentSolution
                       TempBestValue = CurrentValue      
                       BestMove = Move(j,k)
                   End If 

                   // Apply again the move Move(j,k) to return the
                  //  CurrentSolution to its previous state for other move
                 // evaluations at this iteration
                 CurrentSolution= Apply Move(j,k) on CurrentSolution
               Next k
           Next j

           Call MakeTabu(BestMove)   // This prevents from BestMove revisiting
                                     // and from recycling

           If TempBestValue < BestValue Then
                 BestSolution = TempBestSolution
                 BestValue = TempBestValue
           end If 
           
           CuurentSolution=TempBestSolution
     Next i    

Now your solution is in the BestSolution.
Other things like the solution format, Objective Function,and Move
type are still the same as my previous note.

About Tabu Search(TS):
TS is first introduced by prof. Fred glover as a general itertive
meta-heuristic for solving combinatorial optimization problem. TS is
conceptually simple and elegant. It is a form of local neighbourhood
search. Each solution: S, has an asociated set of Neighbours: N(S).
Asolution SS which belongs to the N(S) set, can be reached from S by
an operation called "Move". To avoid cycling, solutions that were
recently explored are declared forbidden or "Tabu" for a number of
iterations. The tabu status of a solution may be overridden when
certain criteria "Aspiration Criteria" are satisfied. To produce good
results any implimentation of TS muct be engineered to suite the
structure of the problem at hand.