NY Times recomenda (para Linux) link
No entanto - com um pouco de pesquisa eu encontrei;
Adoro fazer as palavras cruzadas do New York Times e tenho uma assinatura do site on-line há mais de uma década. No Windows e Mac, eles usam o programa AcrossLite da LitSoft, mas sua versão do Linux não foi mantida, e eu nem sei se ainda está disponível. Eu sei que há o XWord, mas ele não suporta todos os recursos mais recentes do AcrossLite, como permitir mais de uma letra por quadrado (um truque frequente nos quebra-cabeças de domingo).
Eu experimentei a versão para Windows do AcrossLite com vinho, mas é surpreendentemente ruim.
EDIT (02/11/2011) Eu entrei em contato com a LitSoft diretamente para ver se eles estavam planejando tornar a versão do Linux novamente disponível. Recebi uma resposta imediata de um desenvolvedor. Estou citando diretamente do e-mail:
Sim, o Across Lite for Linux estará disponível novamente no primeiro trimestre de 2011. No momento, estamos trabalhando em uma compilação v1.2 para novas distribuições Unix como uma primeira etapa e, posteriormente, a evoluiremos para a versão 2.0. Tentamos uma versão do Adobe Air para todas as outras plataformas além do Windows e Mac, mas a experiência do usuário foi terrível, em parte por causa dos problemas do Adobe Air, então voltamos à versão nativa. Daí o atraso.
JClic: quebra-cabeças, exercícios de teste, palavras cruzadas, você pode obter tudo da Synaptic.