First of all, thanks to all who posted your solutions (publicly or privately).
I got solutions from: Steve Kass, Adam Machanic, Rob Farley,
Maciej Pilecki and FoxTrot.

I got two types of solutions:
1. Brute Force method - generating all possible sentences, then filtering only
the ones that are palindromes. This logic allows for a very short and simple
solution query, but is extremely inefficient.
2. Constructing sentences from the edges, going inwards, and this way not
pursuing sentences that are known not to have potential to become

The winners would have to be Adam Machanic, Rob Farley and Steve Kass;
all three used the second approach.

Here's an example for a solution based on the Brute Force method:

                              with c as                              (                                select cast(' ' + word + ' ' as varchar(max)) as sentence                                from words                                union all                                select c.sentence + w.word + ' '                                from c join words as w                                  on c.sentence not like '% ' + w.word + ' %'                              )                              select rtrim(ltrim(sentence)) as palindrome                              from c                              where replace(sentence, ' ', '') = reverse(replace(sentence, ' ', ''));                              

The nice thing about the brute force solution is of course that it's short
and simple. But it's extremely slow.
For n words, the brute force solution generates the following number of
sentences (before the outer query filters palindromes):

n + n*(n-1) + n*(n-1)*(n-2) + ... + n!

To illustrate how big those numbers can be, here's a recursive CTE that
calculates the number of sentences produced out of n unique words:

                              with c as                              (                                select                                  n as words, cast(n as bigint) as sentences,                                  cast(n as bigint) as v, n-1 as i                                from nums -- auxiliary table of numbers                                where n = 1                              )                              select words, sentences                              from c where i = 0                              order by words;                              words       sentences                              ----------- --------------------                              1           1                              2           4                              3           15                              4           64                              5           325                              6           1956                              7           13699                              8           109600                              9           986409                              10          9864100                              11          108505111                              12          1302061344                              13          16926797485                              14          236975164804                              15          3554627472075                              16          56874039553216                              17          966858672404689                              18          17403456103284420                              19          330665665962403999                              20          6613313319248080000                              

I think that the brute force solution is a good example to use for teaching
purposes to describe the logic of recursive queries.

As for the more efficient method (constructing sentences from the edges,
going inwards), following are the solutions that I got.
I used the following sample data to test the performance of the solutions:

                              create table words(word varchar(50) not null primary key);                              insert into words values('even');                              insert into words values('never');                              insert into words values('odd');                              insert into words values('or');                              insert into words values('r');                              insert into words values('e');                              insert into words values('n');                              insert into words values('er');                              insert into words values('madam');                              insert into words values('adam');                              

Solution by Steve Kass (165 ms):

                              create function ends(                                 @lft varchar(200),                                 @rgt varchar(200),                                 @used varchar(8000)                              ) returns table as return                                 with WW(w1word,w1wordX,w2word,w2wordX) as (                                   select w1.word,@lft+w1.word,w2.word,w2.word+@rgt                                   from words as w1, words as w2                                   where substring(@lft+w1.word,1,len(w2.word+@rgt))                                       = substring(reverse(w2.word+@rgt),1,len(@lft+w1.word))                                   and (w2.word  w1.word)                                   and @used not like '%\[ *\]'+w1.word+'\[ *\]%'                                   and @used not like '%\[ *\]'+w2.word+'\[ *\]%'                                 ), T(w,p,good,side,used) as (                                   select                                     w1wordX+w2wordX as w,                                     left(w1wordX,len(w2wordX)) + '.' +                                     right(w2wordX,len(w1wordX)) as p,                                     len(substring(w1wordX,1,len(w2wordX))) as good,                                     sign(len(w2wordX)-len(w1wordX)) as side,                                     replace(@used,'*',' '+w1word+'*'+w2word+' ') as used                                   from WW                                   union all                                   select                                     @lft+word+@rgt,                                     @lft+word+@rgt,                                     len(@lft+word+@rgt)/2,                                     0,                                     replace(@used,'*',' '+word+' ')                                   from words                                   where @lft+word+@rgt = reverse(@lft+word+@rgt)                                   and @used not like '%\[ *\]'+word+'\[ *\]%'                                 )                                   select *, substring(w,good+1,len(w)-2*good) as middle from T                              go                              with S(w,p,good,side,used,middle) as (                                 select * from ends('','','*')                                 union all                                 select E.*                                 from S                                 cross apply                                   ends(                                     parsename(S.p,2)+case when side=-1 then middle else '' end,                                     case when side=1 then middle else '' end + parsename(S.p,1),                                     S.used                                   ) as E                              )                                 select replace(rtrim(ltrim(used)),'*',' ')                                 from S                                 where middle = reverse(middle)                              go                              

Steve's description of the solution:

"It first finds single words that are palindromes or pairs of
words that could be the leftmost and rightmost words in a
palindrome, such as "odder do" or "re bracer" For this to
be possible, left(first,minLen) = left(reverse(second),minLen)
where minLen is the minimum length of the two words.

To fill in "odder do" to a palindrome, we need to find words
that fit between odder and do that make a palindrome if
"der" (the unpaired middle) is appended to the left of those

One way to start is by finding all possible single or double
words ending in red and having an appropriate variation of the
property above, so that they still can be extended inward to
a palindrome. For example, inserting "oblate bored" is ok,
because all the new mismatch occurs in oblate. On the other
hand, inserting "cat tarred" does not work, because the
sentence "odder cat tarred do" cannot be made a palindrome
by adding words in the middle. The c and the r will never

The ends() function finds appropriate single or double words
that can take a potential palindrome and make it closer to one
(based on number of characters from each end that match).

I start with nothing, so there is no unmatched @lft or @rgt, nor
@used (which holds used words). That's the base case of the
recursive query. Then for every potential palindrome found,
@lft or @rgt is identified, and @used is, so when ends() is
invoked again, it finds fill-ins for the existing mismatch
in that potential palindrome. Because we need a table of
fill-ins for each potential palindrome, and to do this,
ends() needs information specific to that potential palindrome
(the @lft or @rgt along with the @used string of used words)
a CROSS APPLY is the appropriate way to go.

Once there are no more possible fill-ins, there will be both
incomplete and complete palindromes in the table. The complete
ones are those for which @lft+@rgt is itself a palindrome,
so that ' is a solution for the fill-in, meaning that the
potential palindrome is already a palindrome."

Solution by Adam Machanic (41 ms):

                              with n as                              (                                 select                                    convert(varchar(1000), a.word) as parta,                                    convert(varchar(1000), b.word) as partb,                                  convert(varchar(1000), a.word) as repparta,                                    convert(varchar(1000), reverse(b.word)) as reppartb                                 from words a, words b                                 where a.word  b.word                                and ((len(a.word) > len(b.word)                                    and a.word like reverse(b.word) + '%')                                  or                                  (reverse(b.word) like a.word + '%'))                                 union all                                 select                                    convert(varchar(1000),                                       case                                    when len(repparta) > len(reppartb) then parta                                          when len(repparta)  len(repparta) then partb                                    when len(repparta) > len(reppartb) then w.word + ' ' + partb                                    when p.n = 1 then partb                                    else w.word + ' ' + partb                                       end) as partb,                                    convert(varchar(1000),                                       replace(case                                    when len(repparta) > len(reppartb) then parta                                          when len(repparta)  len(repparta) then partb                                    when len(repparta) > len(reppartb) then w.word + ' ' + partb                                    when p.n = 1 then partb                                    else w.word + ' ' + partb                                       end, ' ', '')))                                 from n                                cross join words w                                cross apply                                (                                  select 1                                  union all                                  select 2 where len(repparta) = len(reppartb)                                ) p(n)                                 where                                  case when ' ' + parta + ' ' + partb + ' ' not like '% ' + word + ' %'                                    then                                      case                                        when len(repparta) > len(reppartb) then                                          case                                            when len(word) > len(repparta)-len(reppartb) then                                              case when right(word, len(repparta)-len(reppartb)) =                                                         right(repparta, len(repparta)-len(reppartb))                                                then 1                                                else 0                                              end                                            else                                              case when word = substring(repparta, len(reppartb)+1,                                                                          len(word))                                                then 1                                                else 0                                              end                                          end                                        when len(reppartb) > len(repparta) then                                          case when len(word) > len(reppartb) - len(repparta) then                                            case when left(word, len(reppartb)-len(repparta)) =                                                       substring(reppartb, len(repparta)+1,                                                                len(reppartb)-len(repparta))                                              then 1                                              else 0                                            end                                          else                                            case when word = substring(reppartb, len(repparta)+1,                                                                        len(word))                                              then 1                                              else 0                                            end                                          end                                        else 1 --equal                                      end                                    else 0                                  end = 1                              )                              select final                              from                              (                                 select distinct                                    rtrim(ltrim(parta + ' ' + partb)) final                                 from n                              ) m                              where replace(final, ' ', '') = reverse(replace(final, ' ', ''))                              union all                              select                                word                              from words                              where word = reverse(word)                              

Adam's description of the solution:

"Much like the other solutions, the goal here is to build the palindrome from
the outside in. The anchor part of the recursive CTE finds all pairs in the
words table, then finds the shorter word and uses it in a LIKE predicate
against the longer word. The solution I discovered is to always reverse the
rightmost word/group of words in the list: If the two words are "abcd" and
"cba", the predicate 'abcd' LIKE REVERSE('cba') + '%' is true. Likewise, if
the words are "abc" and "dcba", the predicate REVERSE('dcba') LIKE 'abc' +
'%' is true. Based on these, the anchor part finds potential palindromes.

The recursive part continues this logic in a slightly different way. It
uses a cross-join to the Words table to get all combinations of words with
the input set. The case expression does the following: First, it makes sure
that the given word has not already been used in the input set. Next, it
determines whether the right part or left part is longer. The same basic
logic is used in both cases, so we'll follow the right part being longer.
Assume that the two parts are: "abc" and "dcba". The difference is one
character, and that character is "d". The logic is to append any possible
words onto the left part, so the CASE expression finds all words in this
case that start with the letter "d". There is also a special case for the
differential being longer than the input. For instance, if the two parts
were "abc" and "gfedcba", and the word being compared were "de", that should
be a match. In that case, the expression looks at only as many characters
in the difference as the number of characters in the input word.

Finally, there is a special case for if the two input words are equal in
length. If so, a new row will be generated using the CROSS APPLY operator
(using the correlation name P). If the input set has the parts "abc" and
"cba", the idea is that any possible word could be a seed for a new
palindrome, appended to either the right or left part. So if the lengths are
equal and P.n = 1, the input word is appended to the left part. Otherwise,
it's appended to the right part.

After all of the recursion is done, the outer query does a final check to
determine whether or not each row is a palindrome. This final set is
unioned with any single words in the table that are, themselves, palindromes
(checked using REVERSE)."

Solution by Rob Farley (22 ms):

                              with pals as                              (                              --Base                               select                                cast('' as varchar(max)) as startchars,                                cast('' as varchar(max)) as endchars,                                cast(' ' as varchar(max)) as startwords,                                cast(' ' as varchar(max)) as endwords                              union all                              --Sides even, so find a suitable word                               select                                startchars + w.word,                                endchars,                                startwords + w.word + ' ',                                endwords                               from pals p cross join words w                               where len(p.startchars) = len(p.endchars)                               and exists (select * from words w2 where w.word like reverse(w2.word) + '%'                               or reverse(w2.word) like w.word + '%')                               and startwords not like '% ' + w.word + ' %'                               and endwords not like '% ' + w.word + ' %'                              union all                              --Right longer than left, so find a word for there                               select                                startchars + w.word,                                endchars,                                startwords + w.word + ' ',                                endwords                               from pals p cross join words w                               where len(p.startchars)  len(p.endchars)                               and (w.word like '%' +                               reverse(right(startchars,len(startchars)-len(endchars)))                                or                                reverse(right(startchars,len(startchars)-len(endchars))) like '%' +                               w.word)                               and startwords not like '% ' + w.word + ' %'                               and endwords not like '% ' + w.word + ' %'                              )                              select rtrim(ltrim(startwords)) + ' ' + rtrim(ltrim(endwords))                              from pals                              where len(startchars) > 0                              and startchars + endchars = reverse(startchars + endchars)                              

Rob's description of the solution:

"I figure that the best way of approaching this would be to build it up,
looking for words that would fit as candidates for being added to the start
or end of my palindromes. I wanted to have a space-separated word list as
well as a spaces-removed word list - one is good for both presentation at
the end and checking for unique words, the other is good for actually making
sure that the palindrome is being built correctly.

So taking the 'build it up' approach, a CTE seemed the way to go. I put a
starting scenario in which was to have an empty string at the start and end.
I was originally planning to remove this entry once the CTE was done, but
then later decisions changed my mind for me.

I figured I had three states that I could find myself in. One was when the
string holding the start of the palindrome was longer than the string
holding the end, another was when the string holding the end was longer than
the start, and the third state was when they were the same length. This
could then form a foundation for building the CTE (which I will come to in
the next paragraph). Once the CTE was built, I could filter out the working
lines - which were those ones where the result wasn't a palindrome, and the
base (empty) entry.

So when one string was longer than the other, I wanted to add a word to the
other side. This word had to be a candidate, so that if the difference
between the start-part and end-part was 'never' in the end-part, I could add
any word to the start-part that matched 'reven%', or was one of 'r', 're',
'rev', 'reve' (which translates into: 'reven' like word + '%'). Similar
logic would apply to the end. If the sides were even, I would have to find a
word for which there was candidate for the other side. So I wouldn't pick
'never' for the end-part if there wasn't a word that I would be able to
populate in the next step. I figured I could probably just throw in any word
here and the algorithm would still be valid (because it would get discarded
as a candidate later), but I included it anyway, thinking that it would be
good to get rid of bad candidates earlier.

Regardless of what state I was in, I also had to make sure I hadn't already
used the word, which is why lines like

startwords not like '% ' + w.word + ' %'

--keep appearing everywhere.

The fact that I wanted to cater for when I had the same length string on
both sides influenced me to leave the base case in there as an empty string.
Otherwise I would need to have a base which queried the words table for
candidate words, and that didn't really appeal to me all that much. And I
wasn't really looking for the fastest way of doing it, I was just looking
for a way of doing it.

And that's about it really... I just built the palindromes from the outside
in, populating a CTE, which I then queried to make sure that I only returned
completed palindromes."

And here's the solution that I came up with (267 ms):

                              with c as                              (                                select                                  cast(word as varchar(max)) as st,                                  cast('' as varchar(max)) as ed,                                  0 as consider                                from words                                where word = reverse(word)                                union all                                select                                  ' ' + w1.word + ' ',                                  w2.word + ' ',                                  1                                from words as w1                                  join words as w2                                    on w1.word  w2.word                                where w1.word like reverse(w2.word) + '%'                                   or reverse(w2.word) like w1.word + '%'                                union all                                select                                  st + word + ' ',                                  ed,                                  0                                from c join words                                  on consider = 1                                  and st + ed not like '% ' + word + ' %'                                where replace(st + word + ed, ' ', '') =                                       reverse(replace(st + word + ed, ' ', ''))                                union all                                select st + w1.word + ' ', w2.word + ' ' + ed,     1                                from c                                  join words as w1                                    on consider = 1                                    and st + ed not like '% ' + w1.word + ' %'                                  join words as w2                                    on w1.word  w2.word                                    and st + ed not like '% ' + w2.word + ' %'                                where replace(st, ' ', '') + w1.word like                                         reverse(w2.word + replace(ed, ' ', '')) + '%'                                   or reverse(w2.word + replace(ed, ' ', '')) like                                         replace(st, ' ', '') +                               w1.word + '%'                              )                              select ltrim(rtrim(st + ed)) as palindrome                              from c                              where replace(st + ed, ' ', '') = reverse(replace(st + ed, ' ', ''));                              

The logic in my solution is similar to the others who did not use the brute
force method.

The first CTE query (non recursive) simply isolates the single words that are

The second CTE query (also non recursive) generates two parts of sentences
(start part and end part) out of pairs of words that are either palindromes or
have potential to become palindromes. Start and end pairs have potential to
become a palindrome if start begins with the reverse of end, or the reverse of
end begins with the start.

The third CTE query (recursive) adds a word between start and end
only for words that do not yet appear in the sentence, and make the sentence
a palindrome.

The fourth CTE query (recursive) adds a pair of words; one after the start and
one before the end, only in cases that become palindromes or have the
potential to become palindromes.