The New Sudoku Players' Forum

[JPF]

Here is an empty crossword grid:

Grid 1.JPG (16 KiB) Viewed 2248 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 (22.42 KiB) Viewed 2227 times

score = 92

JPF

[Leren]

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

[JPF]

Congratulations for your first grid!
Yes, there are tons of solutions.
Here is one, using your first horizontal word:

Sol Grid 2.JPG (23.74 KiB) Viewed 2206 times

It is not the "optimal" solution ; I do not try to find it by an exhaustive search.

JPF

[JPF]

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 (18.27 KiB) Viewed 2197 times

JPF

[Leren]

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

[JPF]

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

JPF

[Leren]

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 ?

... the search goes on.

Leren

[Leren]

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]

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

[JPF]

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

[Leren]

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

[Leren]

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

[JPF]

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 (17.97 KiB) Viewed 2118 times

JPF

[Leren]

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

[JPF]

OK for two weeks.

Here is my starting solution:

Score 174
---------------------

Grid 2 - Sol 1 b.JPG (33.58 KiB) Viewed 2107 times