Crossword Squares

Anything goes, but keep it seemly...

Crossword Squares

Postby JPF » Wed Apr 26, 2017 11:13 pm

Here is an empty crossword grid:

Grid 1.JPG
Grid 1.JPG (16 KiB) Viewed 243 times

There are lots of solutions to fill out the grid with this dictionnary.
The challenge is to maximize the value of the grid using the - english - scrabble value of each letter.

Edit:
Here is an example:
Sol Grid 1.JPG
Sol Grid 1.JPG (22.42 KiB) Viewed 222 times
score = 92


JPF
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: Crossword Squares

Postby Leren » Sat Apr 29, 2017 8:23 am

Here is my first crossword square find.

Code: Select all
---------------------
| A A R D V A R K S |
| A # E R I C A # U |
| R A V I G O T E S |
| D # A V A S T # P |
| V A L E # M I C E |
| A # U L M I N # N |
| R E A L I S E R S |
| K # T E R M S # E |
| S E E R E S S E S |
---------------------
Score = 107

It was quite finnicky just to get this stage. Finding a maximum score might be tricky, my code is slow at the moment, so I am hoping for a speed improvement.

Nevertheless, having the first 9 letter word in both Row 1 and Column 1 suggests that the number of solutions may be quite large. Only time will tell.

Leren
Leren
 
Posts: 2704
Joined: 03 June 2012

Re: Crossword Squares

Postby JPF » Sat Apr 29, 2017 10:21 am

Congratulations for your first grid!
Yes, there are tons of solutions.
Here is one, using your first horizontal word:
Sol Grid 2.JPG
Sol Grid 2.JPG (23.74 KiB) Viewed 201 times
It is not the "optimal" solution ; I do not try to find it by an exhaustive search.

JPF
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: Crossword Squares

Postby JPF » Sat Apr 29, 2017 6:27 pm

While algorithms are in the process to be improved, some thoughts on the grids.
A "selection" is the series of contiguous white boxes on the same horizontal line or on the same vertical line between two black boxes. A selection must have at least 2 (white) boxes. The proposed grid has 18 selections.
To fill the grid with words of a dictionary, one have to consider for each selection of n boxes, all the n letter words.
Let E(n) be the number of words in the dictionary having n letters .
In theory, the total number of cases to consider for the p selections is Ind = E(n1).E(n2)...E(np), where nk is the the number of letters of selection k.
Of course, Ind is a large upper bound of the cases to study by an efficient algorithm, but it gives an index of the complexity of the grid.
As Ind is a huge number, I chose Log(Ind) rather than Ind itself.
The proposed grid (18 selections) has an index = 178.

I tried to find 9x9 grids with the highest index of complexity. I came up with this kind of grids (13 black boxes, 34 selections, Ind = 258):
Difficult grid.JPG
Difficult grid.JPG (18.27 KiB) Viewed 192 times

JPF
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: Crossword Squares

Postby Leren » Sun Apr 30, 2017 7:17 pm

A new high score for me. Will keep investigating.

Code: Select all
---------------------
| Q U I Z Z I N G S |
| U # N O I S E # U |
| A L C O L O C K S |
| N # E P A C T # P |
| T A N H # H A Z E |
| I # S A B I R # N |
| Z O O G A M I E S |
| E # R A K E E # E |
| S H Y N E S S E S |
---------------------
Score = 153

Leren
Leren
 
Posts: 2704
Joined: 03 June 2012

Re: Crossword Squares

Postby JPF » Sun Apr 30, 2017 8:44 pm

Sol Grid 3.JPG
Sol Grid 3.JPG (23.75 KiB) Viewed 179 times

JPF
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: Crossword Squares

Postby Leren » Mon May 01, 2017 4:56 am

I've verified that JPF's last solution is the highest scoring of 186,610 solutions with CHAZZANIM in Row1. Full details of all these solutions are given here :

Hidden Text: Show
Gotcha ! You didn't think I'd really be crazy enough to generate a huge volume of useless information, did you ? :D

... the search goes on.

Leren
Leren
 
Posts: 2704
Joined: 03 June 2012

Re: Crossword Squares

Postby Leren » Mon May 01, 2017 5:52 am

Code: Select all
---------------------
| B I T M A P P E D |
| A # R E D Y E # R |
| Z O O M O R P H Y |
| Z # P O S I T # N |
| A J A R # D O Z E |
| Z # E I K O N # S |
| Z O O T O X I N S |
| E # L E N I S # E |
| S T A R K N E S S |
---------------------
Score = 165, and
---------------------
| B I T M A P P E D |
| E # R E D Y E # R |
| Z O O M O R P H Y |
| Z # P O S I T # N |
| A J A R # D O Z E |
| Z # E I K O N # S |
| Z O O T O X I N S |
| E # L E N I S # E |
| S T A R K N E S S |
---------------------
Score = 165

Leren
Leren
 
Posts: 2704
Joined: 03 June 2012

Re: Crossword Squares

Postby Leren » Mon May 01, 2017 6:39 am

Code: Select all
---------------------
| P R E S S F U L S |
| A # X E N O N # H |
| Z O O M O R P H Y |
| Z # C I D E R # N |
| A Z Y M # W E X E |
| Z # T A R O C # S |
| Z O O T O M I E S |
| E # S T O A S # E |
| S L E E K N E S S |
---------------------
Score = 168, and
---------------------
| P R E S S F U L S |
| I # X E N O N # H |
| Z O O M O R P H Y |
| Z # C I D E R # N |
| A Z Y M # W E X E |
| Z # T A R O C # S |
| Z O O T O M I E S |
| E # S T O A S # E |
| S L E E K N E S S |
---------------------
Score = 168

Leren
Leren
 
Posts: 2704
Joined: 03 June 2012

Re: Crossword Squares

Postby JPF » Tue May 02, 2017 10:35 pm

Hi Leren,
Congratulations for your first results.
I find that my code works well to find a solution quickly, but is not well suited to the search for an optimum - scrabble value or equivalent.
So I have to rethink my algorithm, which will take some time, being unavailable at the moment.

JPF
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: Crossword Squares

Postby Leren » Wed May 03, 2017 8:45 am

Hi JPF,

I will be surprised if the 168 and 165 scores I posted above are equaled or exceeded.

The reason is that there are four nine letter words that have Scrabble scores of 47, eight more than the next highest scoring 9 letter word. It would seem reasonable to expect that the highest scoring solution ought to contain one or more of these words. So far,I've found that they only produce solutions when placed in Column 1. I've checked Row 1, Column 3 and Column 9 for the top six or so words and they do not produce any solutions in these positions. The reason that Column 1 seems to produce solutions for high scoring words is obvious, the black squares in Column 2 quarantine some high scoring letters and make solutions much more likely. Column 9 doesn't have this effect because only 7 words end in Z and none end in J or Q.

The attached (incomplete) table shows the results I've achieved so far, for a variety of high scoring nine letter words. The best result I've achieved so far in Row 1 is for CHAZZANIM which you found has a solution with a score of 157.

I've just completed an enormous run for CHAZZANIM in Column 1 and found the following maximum solution with a score of 162, one of about 1.4 Million solutions, which took many hours of CPU time.

Code: Select all
---------------------
| C O C K S C O M B |
| H # H A P A X # A |
| A Z O T E M I A S |
| Z # W A K E D # E |
| Z A C K # R I A L |
| A # H A H A S # I |
| N E O N O M I A N |
| I # W A K E N # E |
| M E S S E N G E R |
---------------------
Score = 162

The attached table gives more details of the results I've achieved so far.

Leren
Attachments
Table.xlsx
(15.19 KiB) Downloaded 3 times
Leren
 
Posts: 2704
Joined: 03 June 2012

Re: Crossword Squares

Postby Leren » Sat May 06, 2017 6:40 am

Being in the Coffee Bar has probably kept this thread from being popular. Nevertheless I'm still searching for a surprising high score, even though I think the highest has probably been found.

Just found the 5th highest score ever, 163, using BUZZWORDS (which has a relatively modest score of 33 vs 47 for the big four) in Column 1.

Code: Select all
---------------------
| B L A C K C A P S |
| U # T A L A S # I |
| Z O O L I T H I C |
| Z # M A K A R # K |
| W H I M # M A Z E |
| O # Z I R A M # N |
| R H E T O R I Z E |
| D # R E S A T # R |
| S I S S Y N E S S |
---------------------
Score = 163

Also of interest are these two, which use ZZZS, a four letter word with a score of 31.

Code: Select all
---------------------
| B E S P O T T E D |
| E # C H I R O # E |
| M O U R N I N G S |
| U # Z A K A T # K |
| Z Z Z S # Z I F F |
| Z # B E G I N # A |
| L O A M I N E S S |
| E # L A V E R # T |
| D U L N E S S E S |
---------------------
Score = 162

and

Code: Select all
---------------------
| H I G H J A C K S |
| I # R E A L O # Y |
| B R O A D B E A N |
| E # G R E E N # I |
| R A S T # Z Z Z S |
| N # H A P P Y # E |
| I S O C R Y M E S |
| Z # P H O N E # E |
| E I S E G E S E S |
---------------------
Score = 160

Based on my investigations so far it looks like the total number of solutions could be something like 10 Billion, give or take an order of magnitude or so, shall we say. I've also attached an update of my high scoring seed words search summary.

Leren
Attachments
Table.xlsx
(14.43 KiB) Downloaded 5 times
Leren
 
Posts: 2704
Joined: 03 June 2012

Re: Crossword Squares

Postby JPF » Sat May 06, 2017 9:14 pm

you wrote:Being in the Coffee Bar has probably kept this thread from being popular. Nevertheless I'm still searching for a surprising high score, even though I think the highest has probably been found.
With 168 you won.
To make this thread more attractive and dynamic, let's move to a new grid and spend no more than a week on each grid.
There are more than 10^30 possible 10x10 grids and nobody really cares about the exact maximum scrabble-value for each grid.
Let me suggest this new one with a initial score of 174:
Grid 2.JPG
Grid 2.JPG (17.97 KiB) Viewed 113 times

JPF
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: Crossword Squares

Postby Leren » Sat May 06, 2017 11:21 pm

OK I'll stop work on the first Grid. Your new grid looks harder but I'm prepared to give it a go.

For efficiency, my search code is specific to each grid, so it might take me some time to produce it. It might be better to allow, say, 2 weeks for this grid.

Leren
Leren
 
Posts: 2704
Joined: 03 June 2012

Re: Crossword Squares

Postby JPF » Sun May 07, 2017 7:19 am

OK for two weeks.

Here is my starting solution:
Grid 2 - Sol 1 b.JPG
Score 174
---------------------
Grid 2 - Sol 1 b.JPG (33.58 KiB) Viewed 102 times
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Next

Return to Coffee bar