A Word Search with Every Country

It should first be mentioned that all grids produced in this blog follow standard word search "laws". These are:

Now, the only rule here we slightly bend is the final one, where we do allow "embedded" words, such as OMAN inside ROMANIA. This only applies to a handful of countries, states and capital cities though.

First up, we start simple. We're looking for the smallest word search with every single U.S. state hidden away inside. First of all, what would be the "trivial" answer, that is if we just placed every state horizontally with no overlaps. Well, there are 412 characters (ignoring spaces) in all 50 U.S. states, and so the smallest grid which could trivially fit all 50 U.S. states is a 21x21 grid.

Let's go smaller! First up was 20x20, this would require at least 12 intersections, however this was managed with 79 free spaces left on the board, as you can see from the picture below they were very spread out. This means we achieved 91 intersecting characters, almost 25%!

But can we go further? What about 19x19. First, let's look at the theorhetical minimum, that is the length of the longest state, being 13 characters of:

Massachusetts, North Carolina and South Carolina.

So, our theorhetical minimum would be 13x13, however that provides only 169 spaces on the board, which means every letter must be reused in 2.4 words on average, with no gaps leftover. This seems very unreasonable to happen, especially considering 20x20 above happened with 20% of the spaces being empty!

After many attempts, I managed to produce a 19x19 grid with all 50 U.S. states inside it. I won't reveal the positions or answers, as I leave it here as a puzzle for you to solve:

I tried to go further, but hit a bottleneck. I wrote a script to do this for me in the end, and after thousands of attempts, leaving it running overnight even, the best it could manage was 43. 43 out of 50 is very far away from perfect, and it feels unlikely that we'll be able to push closer. Because of this, I believe 19x19 is the best possible arrangement for all 50 U.S. states.

Next, we move onto capitals. There are 200 capital cities recognised on JetPunk, and they comprise of a total of 1518 characters (again, excluding characters, hyphens etc...). This means the "trivial" solution this time is 39x39, which gives 1521 spaces in the grid. Overall, a much much larger grid. We can do better, surely?

Let's look at the theorhetical minimum again, the longest capital city this time is Sri Jayawardenepura Kotte with a total of 23 characters, quite long! Using my script from above, I adapted it to try placing all 200 capital cities. It sailed through making a 39x39, 38x38 and 37x37 by grid. I wondered how much further it could go, then I found that at 36x36 it wouldn't budge past 196 / 200, but I continued waiting, and after 100 tries it finally managed a 36x36 grid!

As with the U.S. states above, I have provided the grid below, unsolved, for you to try at home! Bear in mind this contains all 200 capitals though, so it may take some time to solve!

The best that could be done beyond this is... disappointing. I tried 35x35 several times, but didn't get beyond 190. I believe 36x36 is the smallest possible to fit all 200 capital cities.

Now, the one you've been waiting for! There are (currently) 196 countries recognised on JetPunk, and using their common names produces 1641 characters. This means are trivial maximum is 41x41, but surely we can do better!

Well, it started by making a 41x41 grid... okay fairly easy.

Let's try a 40x40 grid? Okay so place one country, place another... after a couple tries it seems we got there.

In fact, after re-using the script from the previous two, we managed to get it down to 37x37! This is fantastic news, especially given the rules we have to abide to for word searches. Below you can see the puzzle for the countries of the world.

Looking beyond, I tried tirelessly for 36x36, and after 400+ tries it didn't do better than 191, pitiful. I thought, maybe let's go one step further and try replacing United States, United Kingdom and United Arab Emirates with USA, UK and UAE respectively. Even after this, it only managed 193, which feels as though 36x36 is possible, but would require a near-perfect setup to do so, and unfortunately this is just not realistic to achieve.

Now, the most restrictive rule mentioned in the preface is the 3rd one. What happens if we allow these situations? Surely we can access more compact positions, perhaps even go one step lower than we have done previously. Well, here was the results:

Overall, I hope you enjoyed this and good luck solving the word searches should you choose to do so! If you'd like to share your solutions with me, I can verify them and perhaps give you a reward of some kind for completing it first :)

Congratulations to Iluvbread123 for being the first person to complete the U.S. States puzzle above!

Impressively, after less than 24 hours, Simon1006 is now the first person to complete the Countries of the world puzzle from above!

And less than 24 hours after that, Simon completes the Capitals puzzle as well!