Squares Daily Word Game Answers

[Salvador Baltimore]

Squareword is a word game similar to wordle, but it's a 5x5 grid, and all rows and columns are actual words. I've created a program to find all possible square word solutions, but it takes days to run. I'd love to get some feedback on runtime speed, and code quality as this is my first 'big' rust program.

That's not going to be easy to improve. The naive brute-force solution is exponential in the number of squares, and 26^(5 * 5) is not exactly a small number, even if you apparently reduce it somewhat by filtering valid words. Since the problem somewhat resembles discrete tomography, I'd expect it to be NP-hard. I'm not sure how much it is easier compared to a general constraint satisfaction problem, but it's likely that you'll need some fairly advanced heuristics and combinatorial optimization to reduce runtimes to something bearable.

instead of filling in the next column (and dealing with N^3) it probably makes sense to look at rows (conditioned restricted on the first two letters, dealing with (N/AB)^5 ) [and you can prune this even further]; basically you should build a dictionary of prefixes of words, and use it to prune as aggressively as possible

Let's consider how you could proceed by choosing one word per column. Once you choose a word for the first column, the only words eligible for the first row are those that start with the first letter of the chosen word, the words eligible for the second row are those that start with the second letter of the chosen word, and so on.

If you have a sorted list of all the words, each list of eligible words is a contiguous sublist. Instead precomputing prefix lists, you could use binary search to shrink the eligibility lists. In this way, you can store a slice per row as the eligibility list, with no allocation. (If an eligibility list shrinks to zero, there are no solutions for the partially filled square.)

So the next step is to combine these approaches, and at each step, choose to either fill the first unfilled column or fill the first unfilled row -- whichever has the smallest number of eligible words remaining.

They stated that they used Dancing Links for the problem. Dancing Links is linked-list based [1] and not necessarily a great fit for Rust, but we can consider more generally how Dancing Links works: It solves exact cover problems.

And vice-versa for vertically placed words. By this design, words that cross are forced to have the same letter in order to create an exact cover of the columns for that cell, and any two words in the same position always collide.

The cell is chosen based on having the smallest number of words to iterate over. It's therefore close to a generalization of the prefix approach above, wherein you could choose any unfilled row or column, as opposed to just the first unfilled row or column.

Also, something I just thought of for the prefix approach: When you pick the first word -- let's say your place it in the first row -- you can limit the first column word to candidates lexicographically greater than or equal to the first word. This will cut the number of squares you find roughly in half, as you will eliminate most squares that are just mirrors across the diagonal; every square you find represents two solutions (unless completely symmetric across the diagonal).

So, I've got a function that should be able to prune as quickly as possible. The WordList struct has a contains method. I believe this has an O(1) time complexity since it's just a bunch of hashMap lookups. (It really has O(n), where n is the length of the word, but that is no longer than 5 in this case). It's also able to check an incomplete word, as it doesn't look down the whole tree. That seems to me to be faster than a binary search, which would be O(log(n)), where n is the number of words. That seems to me to be the case, but I could be wrong.

The list shortening will be O(log(k)) where k is the number of eligible words, so O(log(words)) in the worse case, yes (though that's only in the teens). The ranges for prefixes could be pre-calculated to improve this, but it sounds like your way isn't prefix limited either, which could pay off.

With the prefix method, you know the count for each column, so you can still short circuit out even if it's not the next column/row to empty of candidates. If I understand your question, it sounds like "a column isn't contained in the tree" is the same idea.

I threw together a quick version of what I suggested (not further optimized, single threaded) and it took 30 minutes to enumerate 1,787,056 squares on a 15 year old desktop; even more crudely modifying it for the symmetric case found the 541,968 squares in about 4.5 seconds (using Knuth's 5757 word list for both cases; all it does aside from enumeration is keep count). I can share it if you'd like. Simple as it is, I'm certain it can be much improved without much effort (even just making it parallel might get you to a minute range on a modern processor). It might at least give you a baseline.

If you don't need to enumerate, but only need to count or generate randomly (say), there are probably even better approaches, like ZDDs. (At a guess, I haven't tried it.) ZDDs can also be used to store the word list and perform queries like r#s#c.

You might have noticed the internet being peppered by little green, white and yellow squares over the past week. They're from Wordle, a free once-a-day word puzzle where everyone is trying to guess the same five letter word. I've been hooked on it since Christmas - and you should be playing it, too.

It really is simple. Wordle presents you with a blank grid of squares, into which you type letters. You've got six guesses to get the word. Personally I like to begin with what I call "the farts gambit", and always use FARTS as my first word. It helps to find, or rule out, a common vowel and some of the most common consonants.

If a letter in a word you enter contains a correct letter, it turns yellow. If it's the correct letter in the correct place, it turns green. Make your way to the end, and you're offered a chance to share your completed grid stripped of any letters. Since everyone is playing the same puzzle, and there's only one a day, it's oddly compelling to compare colour grids with other players.

I've been playing Wordle daily and comparing results with friends every day for a couple of weeks now. I'm having a lovely time - although I admit I'm still not sure whether or not Wordle is even a good game.

There is a lot of luck involved, in how many letters and positions you find with your first guess or any subsequent guesses. It doesn't even necessarily reward having a large vocabulary: it's easy to have four correct letters and still have four or more possible winning words, at which point there's no way to tell which is correct beyond just guessing and hoping you get it right before you run out of tries.

Yet it's undeniably compelling. No matter how much luck is involved, it feels skillful to shape your guesses around each discovered letter. That it can only be played once a day also adds tension; I've yet to fail a puzzle and I want to keep my streak going.

Not that there's any in-game recognition of that streak. Wordle is wonderfully barebones, playable via a simple webpage. No sign-in, no rewards, nothing to make it "sticky" other than the fun of it. As reported by the New York Times, Wordle was designed by a man called Josh Wardle as a gift for his wife, and it shows in the best way.

Invented by Josh Wardle, a New York-based software engineer, the online game was created as a way to entertain his partner during the coronavirus pandemic. The couple shared a love of crossword puzzles, so he developed Wordle as a way for them to spend quality time together.

Wordle was first released to the public in October 2021, and rapidly exploded from 90 users on November 1 that year to 300,000 on January 2, 2022, according to figures by Statista. The New York Times then purchased the game in January 2022 for an undisclosed low seven-figure fee.

As is to be expected with any brainteaser, some players may be stuck on Sunday's answer, but you're not alone, even the creator said in an interview with Newsweek that he's not the best player, usually taking "at least four or five attempts" to guess right.

As such, Newsweek has supplied some helpful hints below to help users on their way to those five green squares. But be warned, the answer to today's puzzle will be revealed at the end of this article, so scroll with caution.

Aleks Phillips is a Newsweek U.S. News Reporter based in London. His focus is on U.S. politics and the environment. He has covered climate change extensively, as well as healthcare and crime. Aleks joined Newsweek in 2023 from the Daily Express and previously worked for Chemist and Druggist and the Jewish Chronicle. He is a graduate of Cambridge University. Languages: English.

Find a fresh angle for your daily Wordle game with our collection of tips and advice, or give today's puzzle a quick boost with a clue written exclusively for the April 16 (1032) challenge. Need something more direct? Then make sure you click your way to today's answer.

Looking to extend your Wordle winning streak? Perhaps you've just started playing the popular daily puzzle game and are looking for some pointers. Whatever the reason you're here, these quick tips can help push you in the right direction:

There's no racing against the clock with Wordle so you don't need to rush for the answer. Treating the game like a casual newspaper crossword can be a good tactic; that way, you can come back to it later if you're coming up blank. Stepping away for a while might mean the difference between a win and a line of grey squares.

Wordle solutions that have already been used can help eliminate answers for today's Wordle or give you inspiration for guesses to help uncover more of those greens. They can also give you some inspired ideas for starting words that keep your daily puzzle-solving fresh.

3a8082e126