Remember the short scene at the beginning of "A Man Alone" where Bashir tries his hand at the Altonian brain teaser that Dax had been trying to master for over 140 years?
He tries the game (with Dax present) and does horribly. She jokes that he must have "something on his mind" and then leaves, but encourages him to try the game again. As the scene ends we hear Bashir say "computer, reset" but we don't see his next attempt at the game.
I think that with Bashir's genetically enhanced and structured mind that this game would actually not be all that difficult for him. Although not shown on screen, I think that when he tried the game again (alone in the room so he doesn't have to worry about what people are seeing) that he easily wins.
And we never again see Bashir trying the game. It's too easy for him.