> They are difficult. As I'm not a native English speaker

Kudos to you. That would be insanely difficult. There is a lot of American-based pop culture, knowledge, and slang that makes it even difficult if you are a native, English American speaker.

the rubiks cube is in P space, but has a large state space

towers of hanoi is also in P-space, has a trick to latch onto, and is still popular - though maybe this strays from being interesting and is popular for different reasons

What's the midi? Or do you mean the Mini (Crossword)?

Letter boxed is quite difficult if you want to do it in 2 words (which should always be possible), often taking me well over an hour. But they accept you 'winning' with 3-4 or sometimes 5 words. It's my favourite game as a non-native English speaker since knowledge of other languages is extremely helpful for optimal solutions. Especially as I speak French, Dutch, German and studied Latin and ancient Greek, don't think Swahili or Mandarin would help much.

If someone wants a challenging Wordle variant, I've made this: https://squareword.org

It's a combination of 2D Wordle, crosswords and Sudoku. Been running for over 4 years :)

I still think the ultimate puzzle is the Sunday crossword (followed closely by Thur-Sat), though Connections is great. And definitely difficult (but never feels unfair).

I cancelled my subscription a few years back due to the way NYT was covering the current administration. At the time, I believed they'd never offer a "puzzles only" subscription because then they'd lose a large part of their subs. But, I was wrong. And now they offer a puzzle-only subscription.

There's a great documentary about the Crossword with Will Shortz that came out about a decade ago that's interesting.

Spelling bee is also pretty consistent.

Just Connections, Wordle, and Mini for me (in that order), with the occasional Crossword (tend towards a barbell strategy of just doing maybe Mon, Tue, Sun to get the quick hits and a real challenging puzzle).

Also experience the odd difficulty due to Americanisms, but can't really fault a puzzle coming from something called the New York Times for that. I do however think the puzzle setting for Connections is inferior to The Wall from Only Connect, where they got the idea from. If you haven't seen that yet it's definitely worth a watch (it gets harder as as a season progresses).

I think the hardest part of connections is that there are intentionally overlaps between most (if not all) of the categories. When my wife and I would do them daily, she would steadfastly refuse to make a single guess until she was fairly confident in the entire solution because in practice it was hard to be sure of the current four for a given category even with high confidence of what the category is. (I agreed with her but in practice have both less patience and more trouble figuring out certain categories, so I would often guess and either take a few misses before figuring it out or sometimes completely fail).

Connections are the only one that can't be solved by either a regexp grep against /usr/share/dict/words or an LLM query. I was actually surprised how poorly LLMs fared against it---I thought they'd be better at associating peripheral connections.