ForumGarden

The rules are simple. A crossword-like grid will be given to you with a few letters already inserted in the grid. Your mission, should you feel up to the challenge, is to fill the rest of the puzzle with the following restrictions:

1) Your words must read left to right and top to bottom.

2) Words cannot be repeated (you can use a word only once in a grid)

3) Words must come from the CSW 15 Lexicon, which is the Official International English Scrabble word list compiled by Harper-Collins. You can check for the validity of a word at https://www.anagrammer.com/ or at the Collins-Harper Scrabble Word finder at

https://www.collinsdictionary.com/sc...e-word-finder/

4) There is ONLY 1 SOLUTION to the puzzle !

Attached files

Henrick;1513047 wrote: The rules are simple. A crossword-like grid will be given to you with a few letters already inserted in the grid. Your mission, should you feel up to the challenge, is to fill the rest of the puzzle with the following restrictions:

1) Your words must read left to right and top to bottom.

2) Words cannot be repeated (you can use a word only once in a grid)

3) Words must come from the CSW 15 Lexicon, which is the Official International English Scrabble word list compiled by Harper-Collins. You can check for the validity of a word at https://www.anagrammer.com/ or at the Collins-Harper Scrabble Word finder at

https://www.collinsdictionary.com/sc...e-word-finder/

4) There is ONLY 1 SOLUTION to the puzzle !


And the solution is:

Attached files

Indeed it is:

$ time sld grid-r

grid-r has 10 clues in 6 columns by 4 rows

initial grid

. . . . . .

c . . . . .

. . . . j .

. . q . . .

final grid - solved

o c c u r s

c r i n a l

t i n a j a

a s q u a t

real 0m1.700s



I came to a grinding halt on setting puzzles though. I can't do it yet and you can, which bothers me.

If, for example, I add one of the letters from A..Z into any blank cell of a blank grid, it takes me 26*cells to test all the alternatives. I can do that but I'm not expecting to find any more unique solutions with just one letter, not at the moment. That exploration takes about 10 minutes with my process in a 6x4 grid.

If I allow two letter permutations, it would take me of the order of 4 hours with 26*(cells)(cells-1) iterations.

Three letters is around 4 days. And so on. And that's just for a single grid-shape, 6x4, and there is a huge range of grid shapes to explore for unique solutions.

Is there a shortcut I'm just not seeing? or can I not exhaustively explore the full set of unique solutions.

Here's the simplest I can come up with:

Attached files

spot;1513199 wrote: Indeed it is:

$ time sld grid-r

grid-r has 10 clues in 6 columns by 4 rows

initial grid

. . . . . .

c . . . . .

. . . . j .

. . q . . .

final grid - solved

o c c u r s

c r i n a l

t i n a j a

a s q u a t

real 0m1.700s



I came to a grinding halt on setting puzzles though. I can't do it yet and you can, which bothers me.

If, for example, I add one of the letters from A..Z into any blank cell of a blank grid, it takes me 26*cells to test all the alternatives. I can do that but I'm not expecting to find any more unique solutions with just one letter, not at the moment. That exploration takes about 10 minutes with my process in a 6x4 grid.

If I allow two letter permutations, it would take me of the order of 4 hours with 26*(cells)(cells-1) iterations.

Three letters is around 4 days. And so on. And that's just for a single grid-shape, 6x4, and there is a huge range of grid shapes to explore for unique solutions.

Is there a shortcut I'm just not seeing? or can I not exhaustively explore the full set of unique solutions.

Here's the simplest I can come up with:


Hello Spot. Congratulations on solving the puzzle.

As you surmised, the problem of making this kind of puzzle is complicated. And yes, it making or solving puzzles is theoretically exponential in nature IF (and that is a big IF) you don't use certain shortcuts. I have been working on this for the past 35 years. Yes, you read this correctly, 35 years.

My first program was on a Commodore 64 and the code was written in Forth64, an implementation of Forth for the Commodore 64. Then I moved to a Commodore Amiga 2000. There, I rewrote my code in JForth, a version of forth that allowed you to use the assembly language of the Motorola 6800 processor in the Amiga. Much better. Finally, I then reluctantly moved to the PC in the early 90's and rewrote everything in C++.

However, I was not writing what I have today, but instead I was writting code to try and win a prize from a company called American Holiday Association. They had word puzzle contests where you could win money or cars (Porsches and other nice ones) if you could solve them (you can read about it at https://en.wikipedia.org/wiki/Puzzle_contest).

They made tons of money with people entering all the different stages of the different contests (and paying $5 to enter). I never won and I learned why in the late 80's. At the time, I was a graduate student studying for his Ph.D. in Electrical Engineering at City College Of New York. I was also working at Mount Sinai Hospital on my doctoral research and was a intern at IBM's T.J. Watson's Research Laboratory in Yorktown Heights. I mentioned my efforts one day to a member of my group who was a full time researcher and he laughed saying how he and another employee had entered the contest and one $7000. The rules of the contest were that you could not use a computer, but I knew now why I was always coming up with scores that were 98% or so of the winning score. I am pretty sure many others were also using computers in the contests.

Well, after that major discovery, I knew I would probably never match IBM's computers with their memory and speed. By the way, the list of words for that contest were all the words that were in bold face and against either of the 2 margins in the Merriam-Webster little red dictionary. As you can imagine, there were 1000's of words there. How did I get them in my commodore 64? The old fashion way. I typed them all into my Commodore 64 and saved the file to a diskette! Yes, I was typing all those words, for a couple of weeks while sitting in front of the TV. And, yes, there were some typos which I would discover in a solution of a puzzle. I would then edit the file and rerun the program.

Anyway, at that time I decided that what I had could be the basis for a crossword puzzle making program. My program could take a crossword grid and, based on a dictionary (my list of words for the contest, but it could be any language), fill the puzzle. One would now have to come up with the clues, but I figured that one could come up with some database of clues. Spending my days at Mount Sinai Hospital, I was close to where the major newspapers were in Manhattan. I called a number of them to see if they would be interested in a program that could make crossword puzzles. They all said that they prefer making them by hand (remember, this is in the mid to late 80's). I did not let that answer discourage me. I just kept on working on my algorithm as I enjoyed the challenge of trying to make it better, faster and more efficient.

Well a few years went by. Sometimes, I wouldn't touch the algorithm for a year at a time (as when I moved to FLorida and had to concentrate on my new job). But every so often I would go back to it, such as when I would get a new computer and needed to make sure that my program, which now had nice graphics, would work.

Then I got a teaching position in the Department of Computer Science at the University Of South Florida. Based on my industry experience, I saw that the Department needed to have a course teaching C++. I created that course and it is now part of the curriculum. This made me spend more time on the application. Then the following year, seeing that there was no course in C# in the department, I created an object-oriented programming Course in C#. That course is also, now, part of the curriculum. As I was teaching the C# course, I wanted to give myself a project that would use C#. The project I gave myself was to translate my C++ puzzle making program to C#. Though there were tens of 1000's of lines, this would take about 3 days because of the syntactic similarities between the 2 languages. I ended up with a nice C# library and a prototype for my C# application and also realized that I had the makings of an interesting game based on my application.

So, I went ahead and built prototypes of games based on my library. I even got the help of a bright student who helped make a Unity version of an application based on the library. The fruit. so far of that is a game called "Typing Tiles" which is available for free for Android and IOS. You can get it at https://itunes.apple.com/us/app/typi...255271144?mt=8 for IOS or at https://play.google.com/store/apps/d...ingTiles&hl=en for Android. I mention this to you because I believe that if you get the app, you will get an inkling of how the algorithm works.

My algorithm is pretty fast and solved your puzzle in the blink of an eye and came up with:

It can generate a 6x4 puzzle in a split second and a number of them at the rate of perhaps 10 per second. The puzzles can have any rectangular shape.

As for the game that I mentioned to you, the goal is simple. The application will present you with a number of grids. The goal is for you to fill the grid by placing letters in the different squares. My algorithm makes sure that a letter insertion is accepted only if there is still a solution to the puzzle at that point. The unique thing about the app is the "FORCING" rule. That rule stipulates that whenever you place a letter and other letters have only 1 choice, those letters are placed in the grid for you. So, for instance, looking at your puzzle effort above, my algorithm saw right away that given the "X" in the upper left corner the only top horizontal words would be "XRAY" or "XYST", the first column can only be "XI" or "XU" and quickly working through constraints it found the solution I posted below.

As you fill the grid, you get points for the letters you put in (the same values as the letter values used in Scrabble). You are also given a limit to the number of insertions you can make. That limit is the number of empty squares in the grid. So, if the puzzle has 20 empty squares. you are given 20 insertions, at most, to fill the grid. If you are able to force many moves, you could fill the grid and be left with extra moves. Those extra moves give you bonus points. Also, as you FORCE words, their definitions appear in a marquee at the top of the screen. In this way, should you FORCE and unknown word, you can learn its meaning. Finally, the app keeps track of the words you use and gives extra points when you use new words that you have not used in the past. As you solve grids, more difficult ones are presented to you.

It is a great way to learn new words and, in particular, to learn esoteric spelling quirks of words. You quickly learn things like "What is the only 4-letter word with a 'Q' as its 2nd letter?" (AQUA), or "What is the only 5-letter word starting with 'AO'?" (AORTA) or "What letter comes after 'Q' in every 5-letter word where the Q is the 2nd letter?" ('U'), etc...

I am working on making the game available in other languages (Spanish, French, etc...) and on versions that use the words from a particular book as lexicon (Moby Dick, Alice in Wonderland, King James Bible, etc...)

You might also want to read a good article about puzzle making algorithms at https://www.cs.rpi.edu/~dhulena/CS44Fin ... Report.pdf

Well, this response has turned out a little longer than I anticipated, but you seem genuinely interested in what I have done and you have also seen how complicated this can be.

Feel free to ask specific questions and I will see if I can offer answers,

Regards,

Henrick

Attached files

I haven't read that post at all yet, only having a few minutes with a coffee before walking my boy up to school, but I'm very much looking forward to reading it when I get back. Thank you.

spot;1513224 wrote: I haven't read that post at all yet, only having a few minutes with a coffee before walking my boy up to school, but I'm very much looking forward to reading it when I get back. Thank you.


Something else we have in common. I am writing this as I am about to take my boy to school.

Hopefully you will get a better idea of what I do. Again, just ask questions and I will answer them the best I can on such a platform.

Regards,

Henrick

spot;1513224 wrote: I haven't read that post at all yet, only having a few minutes with a coffee before walking my boy up to school, but I'm very much looking forward to reading it when I get back. Thank you.


You might also enjoy reading http://ai.stanford.edu/~jduchi/projects ... riteup.pdf

I'll go and download it, thank you.

I wrote some grid starting state generator code and I'm about to reconfigure it in light of how it performed, I'll post what I've done in a couple of days. I can make puzzles which have unique solutions but they all seem to require at least one of x,z,q or j at the moment. I've not explored using four starting letters yet either, that seems a bit processor-intensive on my desktop.

Henrick;1513315 wrote: You might also enjoy reading http://ai.stanford.edu/~jduchi/projects ... riteup.pdf


Well well. I enjoyed it so much I went through it twice.

I imagine coding techniques like that have a ready market in, for example, homeland security word farms. The nearest I've been to that level of optimizing was back in the mid-70s, investigating whether Huffman coding might extend hardware lifetime by perhaps a couple of years in a Burroughs Medium Systems setting or whether it would slow down main record-handling processes to an impractical degree. When hardware costs millions of pounds it's worth throwing an assembler programmer a budget for what-if questions like that. I asked for the budget and enjoyed the exploration. Being a 2MHz 50kB machine, the answer was no we couldn't - we identified too many instances in the existing systems where we had to unpack the compressed file areas. When we did the sums we found we had too few production hours to handle the calculated overheads.

I think - I'll do this later to confirm it, but at the moment I think - that the existing utilities I wrote last week will solve those four example crosswords without any amendment to their current form. I think they will all solve in under ten seconds real time. Actually doing it instead of just thinking it will help. I'll build a 20,000 word list since the article doesn't provide the one used for the original processing but obviously if I were to use CSW15 the solution would no longer be unique so I can't do that.

My code is a grotesque parody of efficiency compared with what's described in the paper but I'm not sure coding efficiency is essential in order to stay with the pack. Design efficiency is, clearly. If the technique adopted quenches letter combinations which lead away from the solution, and it quenches them at a sufficiently steep gradient, then the correct answer will pop out using either approach.

I am happy you enjoyed the article.

I don't think that Homeland Security needs my crossword puzzle creating algrithm. Perhaps someone who would like to create crosswords, but no one really knows about this algorithms except, perhaps you and a few others.

But to tell you the truth, the problem is not exponential in nature. Actually, far from that because of the constraints imposed on the solution by the dictionary. What I have found is that my algorithm is extremely fast, particularly with smaller size dictionaries (around 5000 words). With much smaller dictionaries (1000 words or less) you can only handle simple puzzles. By simple, I mean puzzles where words may only intersect a single other word rather than "complex" puzzles where words might have intersections at each one of ther characters. The CSW 15 has about 273,000 words which allows for dense puzzles, but also makes for longer solution time (due to having to deal with so many words. But there are ways to trim the tree of possibilities quite drastically)

As described in my little historical message, my algorithm is written in C#.

Here what you might want to look into:

1) Before doing anything else, you need to write an algorithm which "analyzes" the grid. By that, I mean an algorithm which looks at your grid and determines:

a) How many words (horizontal and vertical) there are (you will need to make 2 lists, 1 for horinzontal and 1 for vertical words, of some class that will hold information about the words. I call that class aGword (for. a Grid Word)

b) How many squares need to be filled in the grid. Each square should have a reference to the grid word it belongs to, and each grid word (described above) should have a list of references to the squares comprising it.

2) Once you have analysed the grid you can load the words from your dictionary. Each grid word should have a list of potential candidates that could fit in it. So, in your example puzzle the analysis should state that you have:

2 horizontal words: 1A ???? and 2A ???? (to use the typical crossword naming convention to identify the words)

4 vertical wors : 1D ?? 2D ?? 3D ?? and 4D ??

There are 3625 candidates for 1A and 2A (from AAHS to ZZZS) and about 124 candidates for the vertical words (from AA to ZO)

3) Now, what will speed things up is for you to eliminate those words which cannot word when you place a particular letter in the grid.

For example, in your puzzle, starting with a blank set of 2 4-letter rows, once you attempt to place the 'X' in row 0, column 0. you can scan your candidates for those that start with the letter 'X'.

The algorithm would find that only XRAY and XYST can fit. You have just reduced the search space of the top word from 3625 to 2 for the top horizontal word

Another thing that needs to be done is to also keep a histogram of what characters can go in each square.

Here, after placing the X, you will find that 1D can only be XI or XU.

4) You need a "trimming" function which goes through the list of candidates and removes those that cannot fit and updates the histograms of letters of the squares (which letters can go in the square and how many times that letter occurs). Basically you want a Dictionary where the key is a letter and the value is a count. So, for instance, in your example, after placing the X, the histogram for square[1,0] in the vertical direction is [[I.1].[U.1]] meaning that as far as vertical words are concerned, square[1,0] can only be "I" (and there is only 1 word -XI-] or "U" (and there is only 1 word -XU-)

The horizontal histogram for square[0,1] is [[R,1],[Y,1]] which means that only an 'R' or a 'Y' can fit there horizontally and each obly has 1 word (xRay and xYst)

You can iteratively trim squares as you remove potential letters from consideration in squares. For instance, now, you know that only 'R' and 'Y' can fit in square[0,1]. So, you can look at column[1] and see what vertical words can fit there.

If you place an 'R' in square[0,1]., then square[1,1] can only be 'E' because the only 2 letter word starting with 'R' is 'RE'. On the other hand, if you place a 'Y' in square[0,1]. then column 1 has 4 candidates "YA YE YO YU". This would be reflected in a vertical

histogram for square[1,1] like so: [[A,1] [E,1] [O,1] [U,1]]

Through such a process of elimination, you would find that the letter "U" cannot fit in square[1,0] despite having 64 candidates (UDAL to UVAS), but remember that the square[1,1] can only be "A E O or U". Since there are no 4-letter words starting with "UA UE UO or UU" (the histogram would let you know that once you tried to insert a "U" in square[1,0]. you are now left with the only possibility for square[1,0] being the letter "I". This now reduces the 2 row's candidates to "IAMB IOTA and IONS". Since square[0,1] can only be "R" or "Y" and "R" only admits "RE" vertically, "R" is eliminated. This leaves "Y" as the only potential letter fitting square[0,1]. This would imply "XYST" on row 1

If you now try to place "A" in square[1,1] (rember, only "A E O or U" might fit there, you basically force "IAMB" on the 2nd horizontal word, since "IAMB" is the only 4-letter word starting with "IA". However tjis would make the 2-letter vertical word "SM" in column 2.

But "SM" is not in the CSW 15. Thus, the 2nd horizontal word cannot be IAMB and therefore square[1,1] cannot be "A".

This leaves "IOTA" for the 2nd horizontal word. This in turn requires that "YO" "ST" and "TA" be valid, which they are. And further look at the histograms would show that these are the only possibilities.

Therefore, this puzzle has only 1 solutions and iti is made up of "XYST" and "IOTA"



I understand that this might be a bit confusing, but that is partially it, along with a number of subtleties that I discovered as I played with a large number of puzzles. THere is a need to be able to backtrack, so as you try to insert a letter in a square, you eliminate all the words in the orthogonal direction that do not have that letter in them. If after scanning all the words in the orthogonal direction you are left with none, then this means that the letter you considered entering in the square simply cannot fit there at this stage of the puzzle. You need to "UNDO" that insertion and restore all the words that you had eliminated in the orthogonal word.

I hope you enjoy that little tidbit.