Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

She sells cshs by the cshore.


devel / comp.theory / Crossword filling

SubjectAuthor
* Crossword fillingMalcolm McLean
+* Crossword fillingB.H.
|`* Crossword fillingMalcolm McLean
| `* Crossword fillingB.H.
|  `- Crossword fillingB.H.
+* Crossword fillingJeff Barnett
|`* Crossword fillingMalcolm McLean
| `* Crossword fillingJeff Barnett
|  `- Crossword fillingMalcolm McLean
`* Crossword fillingJulio Di Egidio
 `* Crossword fillingMalcolm McLean
  `- Crossword fillingJulio Di Egidio

1
Crossword filling

<9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29852&group=comp.theory#29852

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a37:b442:0:b0:69a:fc75:ca52 with SMTP id d63-20020a37b442000000b0069afc75ca52mr8482614qkf.730.1649596881891;
Sun, 10 Apr 2022 06:21:21 -0700 (PDT)
X-Received: by 2002:a05:690c:39a:b0:2e6:d7e2:c66c with SMTP id
bh26-20020a05690c039a00b002e6d7e2c66cmr23844057ywb.482.1649596881729; Sun, 10
Apr 2022 06:21:21 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Sun, 10 Apr 2022 06:21:21 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:c0bc:8b0c:ac8a:2335;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:c0bc:8b0c:ac8a:2335
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
Subject: Crossword filling
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Sun, 10 Apr 2022 13:21:21 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Malcolm McLean - Sun, 10 Apr 2022 13:21 UTC

I hope this post isn't too practical for comp.theory.

As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. Version 1.6 is almost ready, and I have focused
on the user-interface side of things.

But the heart of a crossword design program is the auto-fill algorithm. English-style grids, where each block of four squares is constrained to have at least one black square, usually fill almost instantaneously. American-style grids,
with a dense network of interlocking short words and only a few black
squares,a re far more challenging. Whilst I have had some successes,
usually the algorithm fails to complete before boredom sets in and I
terminate it.

I've checked some papers, and the problem is NP-hard. Currently I use
a fairly naive backtracking algorithm. Another problem is that, to give
the algorithm a fighting chance, I give it a very large dictionary. But
really obscure words should be kept to a minimum.

Work on a better way of doing American-style grids is pencilled in
for version 1.7.

comp.theory readers might be interested in the first completed
American-style crossword. It's at
https://malcolmmclean.github.io/CrosswordDesigner/AmericanGrid1.html

The project is on github
https://github.com/MalcolmMcLean/CrosswordDesigner

Re: Crossword filling

<05f0f545-f1e8-46cb-a84f-4c3ea32cfbc1n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29853&group=comp.theory#29853

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:6214:2607:b0:444:3e1c:9491 with SMTP id gu7-20020a056214260700b004443e1c9491mr2650631qvb.12.1649602024109;
Sun, 10 Apr 2022 07:47:04 -0700 (PDT)
X-Received: by 2002:a81:7b43:0:b0:2ec:8bb:3aef with SMTP id
w64-20020a817b43000000b002ec08bb3aefmr2487528ywc.267.1649602023917; Sun, 10
Apr 2022 07:47:03 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Sun, 10 Apr 2022 07:47:03 -0700 (PDT)
In-Reply-To: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <05f0f545-f1e8-46cb-a84f-4c3ea32cfbc1n@googlegroups.com>
Subject: Re: Crossword filling
From: xlt....@gmail.com (B.H.)
Injection-Date: Sun, 10 Apr 2022 14:47:04 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 46
 by: B.H. - Sun, 10 Apr 2022 14:47 UTC

On Sunday, April 10, 2022 at 9:21:22 AM UTC-4, malcolm.ar...@gmail.com wrote:
> I hope this post isn't too practical for comp.theory.
>
> As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. Version 1.6 is almost ready, and I have focused
> on the user-interface side of things.
>
> But the heart of a crossword design program is the auto-fill algorithm. English-style grids, where each block of four squares is constrained to have at least one black square, usually fill almost instantaneously. American-style grids,
> with a dense network of interlocking short words and only a few black
> squares,a re far more challenging. Whilst I have had some successes,
> usually the algorithm fails to complete before boredom sets in and I
> terminate it.
>
> I've checked some papers, and the problem is NP-hard. Currently I use
> a fairly naive backtracking algorithm. Another problem is that, to give
> the algorithm a fighting chance, I give it a very large dictionary. But
> really obscure words should be kept to a minimum.
>
> Work on a better way of doing American-style grids is pencilled in
> for version 1.7.
>
> comp.theory readers might be interested in the first completed
> American-style crossword. It's at
> https://malcolmmclean.github.io/CrosswordDesigner/AmericanGrid1.html
>
> The project is on github
> https://github.com/MalcolmMcLean/CrosswordDesigner

Is the problem to decide if the user adding a particular square would lead to an solvable/unsolvable crossword grid, given a dictionary?

I would go with annealing if you're looking for "good enough" NP-complete problem solving algorithms; genetic algorithms tend to be conceptually elegant but poorly performing, in my (limited) experience. I don't think backtracking is much more efficient than brute-force, unless you're dealing with an easy or small instance that brute force would be good enough for anyway....not that I'm sure about that.

-Philip White

Re: Crossword filling

<t2v443$r7h$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29868&group=comp.theory#29868

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: jbb...@notatt.com (Jeff Barnett)
Newsgroups: comp.theory
Subject: Re: Crossword filling
Date: Sun, 10 Apr 2022 11:28:33 -0600
Organization: A noiseless patient Spider
Lines: 55
Message-ID: <t2v443$r7h$1@dont-email.me>
References: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 10 Apr 2022 17:28:35 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="c672e717dd472967e26e8c69c46229fd";
logging-data="27889"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18F4Gq03hC9+L2suVOkzQrfHRzrm1k8SGI="
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.8.0
Cancel-Lock: sha1:AVm0DDpBNzifpTjMgrsLz6Axau4=
In-Reply-To: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
Content-Language: en-US
 by: Jeff Barnett - Sun, 10 Apr 2022 17:28 UTC

On 4/10/2022 7:21 AM, Malcolm McLean wrote:
> I hope this post isn't too practical for comp.theory.
>
> As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. Version 1.6 is almost ready, and I have focused
> on the user-interface side of things.
>
> But the heart of a crossword design program is the auto-fill algorithm. English-style grids, where each block of four squares is constrained to have at least one black square, usually fill almost instantaneously. American-style grids,
> with a dense network of interlocking short words and only a few black
> squares,a re far more challenging. Whilst I have had some successes,
> usually the algorithm fails to complete before boredom sets in and I
> terminate it.
>
> I've checked some papers, and the problem is NP-hard. Currently I use
> a fairly naive backtracking algorithm. Another problem is that, to give
> the algorithm a fighting chance, I give it a very large dictionary. But
> really obscure words should be kept to a minimum.
>
> Work on a better way of doing American-style grids is pencilled in
> for version 1.7.
>
> comp.theory readers might be interested in the first completed
> American-style crossword. It's at
> https://malcolmmclean.github.io/CrosswordDesigner/AmericanGrid1.html
>
> The project is on github
> https://github.com/MalcolmMcLean/CrosswordDesigner

I haven't read your papers and am not an expert crossword (American
style) solver or creator. However, my guess is that those who do this
for a living follow this set of steps:

----
1. Select a theme for the "long" entries.

2. Collect candidate long answers. This step may take days, weeks, or
months. It's the "wow" step of puzzle creation.

3. Sub-select long answers based on length (or other interesting feature).

4. Develop a compatible grid and insert long answers.

5. Now fill the rest in.

If not successful, iterate steps 3 thru 5. If problems still remain, do
more of 2.
-----

It's steps 1-3 that separate competent from inspired puzzles. Step 4
should radically reduce remaining generation time: there are more
constraints AKA less degrees of freedom.

I can't swear this is how it's done by the experts but I'd bet a nickle
that it's close.
--
Jeff Barnett

Re: Crossword filling

<63d72533-6ee9-4636-8c35-84103db738e6n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=30010&group=comp.theory#30010

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a37:785:0:b0:69c:d66:1120 with SMTP id 127-20020a370785000000b0069c0d661120mr5303154qkh.93.1649681280599;
Mon, 11 Apr 2022 05:48:00 -0700 (PDT)
X-Received: by 2002:a05:6902:1009:b0:641:6603:fbfe with SMTP id
w9-20020a056902100900b006416603fbfemr2683374ybt.149.1649681280385; Mon, 11
Apr 2022 05:48:00 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Mon, 11 Apr 2022 05:48:00 -0700 (PDT)
In-Reply-To: <t2v443$r7h$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=81.143.231.9; posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 81.143.231.9
References: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com> <t2v443$r7h$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <63d72533-6ee9-4636-8c35-84103db738e6n@googlegroups.com>
Subject: Re: Crossword filling
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Mon, 11 Apr 2022 12:48:00 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 72
 by: Malcolm McLean - Mon, 11 Apr 2022 12:48 UTC

On Sunday, 10 April 2022 at 18:28:38 UTC+1, Jeff Barnett wrote:
> On 4/10/2022 7:21 AM, Malcolm McLean wrote:
> > I hope this post isn't too practical for comp.theory.
> >
> > As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. Version 1.6 is almost ready, and I have focused
> > on the user-interface side of things.
> >
> > But the heart of a crossword design program is the auto-fill algorithm. English-style grids, where each block of four squares is constrained to have at least one black square, usually fill almost instantaneously. American-style grids,
> > with a dense network of interlocking short words and only a few black
> > squares,a re far more challenging. Whilst I have had some successes,
> > usually the algorithm fails to complete before boredom sets in and I
> > terminate it.
> >
> > I've checked some papers, and the problem is NP-hard. Currently I use
> > a fairly naive backtracking algorithm. Another problem is that, to give
> > the algorithm a fighting chance, I give it a very large dictionary. But
> > really obscure words should be kept to a minimum.
> >
> > Work on a better way of doing American-style grids is pencilled in
> > for version 1.7.
> >
> > comp.theory readers might be interested in the first completed
> > American-style crossword. It's at
> > https://malcolmmclean.github.io/CrosswordDesigner/AmericanGrid1.html
> >
> > The project is on github
> > https://github.com/MalcolmMcLean/CrosswordDesigner
> I haven't read your papers and am not an expert crossword (American
> style) solver or creator. However, my guess is that those who do this
> for a living follow this set of steps:
>
> ----
> 1. Select a theme for the "long" entries.
>
> 2. Collect candidate long answers. This step may take days, weeks, or
> months. It's the "wow" step of puzzle creation.
>
> 3. Sub-select long answers based on length (or other interesting feature).
>
> 4. Develop a compatible grid and insert long answers.
>
> 5. Now fill the rest in.
>
> If not successful, iterate steps 3 thru 5. If problems still remain, do
> more of 2.
> -----
>
> It's steps 1-3 that separate competent from inspired puzzles. Step 4
> should radically reduce remaining generation time: there are more
> constraints AKA less degrees of freedom.
>
> I can't swear this is how it's done by the experts but I'd bet a nickle
> that it's close.
>
You're probably right. I'm British so I don't take an American newspaper.
British crosswords rarely have themes, and they don't allow a square to
be intersected by more than two words. Using my program, you can
generate a blank "English-style" grid with a click, then fill it with another
mouse click.
So obviously American users will expect the same. But it's a lot harder
to generate reasonable American-style grids at random. I resorted to
stripping someone else's database and recycling the grids. (I hope it's
all out of copyright, or that you can't copyright a blank grid).
It's also a lot harder to fill an American-style grid. Whilst formally it's
the same problem, the naive backtracking algorithm doesn't come
back instantaneously with a fill the way it usually does with an English-
style grid.
I think most serious American constructors will do the theme first, as
you say, then work around the short words. But if they are very serious,
they will use paid-for software, and it's hard for a hobby project to
compete with that. I'm aiming at schoolmasters or people who run
church magazines, who will design the occasional crossword but can't
justify a paid subscription.

Re: Crossword filling

<52c5da9a-5cbd-4566-932e-310937b3797cn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=30011&group=comp.theory#30011

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a37:6382:0:b0:69b:fbde:42d1 with SMTP id x124-20020a376382000000b0069bfbde42d1mr6810753qkb.48.1649681456937;
Mon, 11 Apr 2022 05:50:56 -0700 (PDT)
X-Received: by 2002:a0d:f883:0:b0:2d0:ee66:5f97 with SMTP id
i125-20020a0df883000000b002d0ee665f97mr24928859ywf.313.1649681456770; Mon, 11
Apr 2022 05:50:56 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Mon, 11 Apr 2022 05:50:56 -0700 (PDT)
In-Reply-To: <05f0f545-f1e8-46cb-a84f-4c3ea32cfbc1n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=81.143.231.9; posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 81.143.231.9
References: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com> <05f0f545-f1e8-46cb-a84f-4c3ea32cfbc1n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <52c5da9a-5cbd-4566-932e-310937b3797cn@googlegroups.com>
Subject: Re: Crossword filling
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Mon, 11 Apr 2022 12:50:56 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 51
 by: Malcolm McLean - Mon, 11 Apr 2022 12:50 UTC

On Sunday, 10 April 2022 at 15:47:05 UTC+1, B.H. wrote:
> On Sunday, April 10, 2022 at 9:21:22 AM UTC-4, malcolm.ar...@gmail.com wrote:
> > I hope this post isn't too practical for comp.theory.
> >
> > As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. Version 1.6 is almost ready, and I have focused
> > on the user-interface side of things.
> >
> > But the heart of a crossword design program is the auto-fill algorithm. English-style grids, where each block of four squares is constrained to have at least one black square, usually fill almost instantaneously. American-style grids,
> > with a dense network of interlocking short words and only a few black
> > squares,a re far more challenging. Whilst I have had some successes,
> > usually the algorithm fails to complete before boredom sets in and I
> > terminate it.
> >
> > I've checked some papers, and the problem is NP-hard. Currently I use
> > a fairly naive backtracking algorithm. Another problem is that, to give
> > the algorithm a fighting chance, I give it a very large dictionary. But
> > really obscure words should be kept to a minimum.
> >
> > Work on a better way of doing American-style grids is pencilled in
> > for version 1.7.
> >
> > comp.theory readers might be interested in the first completed
> > American-style crossword. It's at
> > https://malcolmmclean.github.io/CrosswordDesigner/AmericanGrid1.html
> >
> > The project is on github
> > https://github.com/MalcolmMcLean/CrosswordDesigner
> Is the problem to decide if the user adding a particular square would lead to an solvable/unsolvable crossword grid, given a dictionary?
>
> I would go with annealing if you're looking for "good enough" NP-complete problem solving algorithms; genetic algorithms tend to be conceptually elegant but poorly performing, in my (limited) experience. I don't think backtracking is much more efficient than brute-force, unless you're dealing with an easy or small instance that brute force would be good enough for anyway....not that I'm sure about that.
>
Simulated annealing might be the way to go. The problem, as always, is writing the fitness and mutate
functions so that there aren't too many local minima that are non-solutions.. In this case, a non-global
minimum that is still an acceptable solution is fine, even preferable.

Re: Crossword filling

<17e8ca28-753d-4369-9c81-175b8ff347f4n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=30021&group=comp.theory#30021

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:622a:10d:b0:2e1:db41:66d with SMTP id u13-20020a05622a010d00b002e1db41066dmr26479814qtw.670.1649689869618;
Mon, 11 Apr 2022 08:11:09 -0700 (PDT)
X-Received: by 2002:a0d:e20b:0:b0:2ec:8cb:3edf with SMTP id
l11-20020a0de20b000000b002ec08cb3edfmr5834070ywe.315.1649689869181; Mon, 11
Apr 2022 08:11:09 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Mon, 11 Apr 2022 08:11:09 -0700 (PDT)
In-Reply-To: <52c5da9a-5cbd-4566-932e-310937b3797cn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
<05f0f545-f1e8-46cb-a84f-4c3ea32cfbc1n@googlegroups.com> <52c5da9a-5cbd-4566-932e-310937b3797cn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <17e8ca28-753d-4369-9c81-175b8ff347f4n@googlegroups.com>
Subject: Re: Crossword filling
From: xlt....@gmail.com (B.H.)
Injection-Date: Mon, 11 Apr 2022 15:11:09 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 60
 by: B.H. - Mon, 11 Apr 2022 15:11 UTC

On Monday, April 11, 2022 at 8:50:58 AM UTC-4, malcolm.ar...@gmail.com wrote:
> On Sunday, 10 April 2022 at 15:47:05 UTC+1, B.H. wrote:
> > On Sunday, April 10, 2022 at 9:21:22 AM UTC-4, malcolm.ar...@gmail.com wrote:
> > > I hope this post isn't too practical for comp.theory.
> > >
> > > As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. Version 1.6 is almost ready, and I have focused
> > > on the user-interface side of things.
> > >
> > > But the heart of a crossword design program is the auto-fill algorithm. English-style grids, where each block of four squares is constrained to have at least one black square, usually fill almost instantaneously. American-style grids,
> > > with a dense network of interlocking short words and only a few black
> > > squares,a re far more challenging. Whilst I have had some successes,
> > > usually the algorithm fails to complete before boredom sets in and I
> > > terminate it.
> > >
> > > I've checked some papers, and the problem is NP-hard. Currently I use
> > > a fairly naive backtracking algorithm. Another problem is that, to give
> > > the algorithm a fighting chance, I give it a very large dictionary. But
> > > really obscure words should be kept to a minimum.
> > >
> > > Work on a better way of doing American-style grids is pencilled in
> > > for version 1.7.
> > >
> > > comp.theory readers might be interested in the first completed
> > > American-style crossword. It's at
> > > https://malcolmmclean.github.io/CrosswordDesigner/AmericanGrid1.html
> > >
> > > The project is on github
> > > https://github.com/MalcolmMcLean/CrosswordDesigner
> > Is the problem to decide if the user adding a particular square would lead to an solvable/unsolvable crossword grid, given a dictionary?
> >
> > I would go with annealing if you're looking for "good enough" NP-complete problem solving algorithms; genetic algorithms tend to be conceptually elegant but poorly performing, in my (limited) experience. I don't think backtracking is much more efficient than brute-force, unless you're dealing with an easy or small instance that brute force would be good enough for anyway...not that I'm sure about that.
> >
> Simulated annealing might be the way to go. The problem, as always, is writing the fitness and mutate
> functions so that there aren't too many local minima that are non-solutions. In this case, a non-global
> minimum that is still an acceptable solution is fine, even preferable.

Yes, and you might want to be creative with the crossover function, too.

-Philip White

Re: Crossword filling

<ba5b5ddb-fee0-4fbb-8613-2057a9a41796n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=30022&group=comp.theory#30022

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a0c:c250:0:b0:444:4193:7eb1 with SMTP id w16-20020a0cc250000000b0044441937eb1mr5277138qvh.40.1649689931902;
Mon, 11 Apr 2022 08:12:11 -0700 (PDT)
X-Received: by 2002:a05:6902:84:b0:63d:4a3d:eb5 with SMTP id
h4-20020a056902008400b0063d4a3d0eb5mr22341949ybs.145.1649689931592; Mon, 11
Apr 2022 08:12:11 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Mon, 11 Apr 2022 08:12:11 -0700 (PDT)
In-Reply-To: <17e8ca28-753d-4369-9c81-175b8ff347f4n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
<05f0f545-f1e8-46cb-a84f-4c3ea32cfbc1n@googlegroups.com> <52c5da9a-5cbd-4566-932e-310937b3797cn@googlegroups.com>
<17e8ca28-753d-4369-9c81-175b8ff347f4n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <ba5b5ddb-fee0-4fbb-8613-2057a9a41796n@googlegroups.com>
Subject: Re: Crossword filling
From: xlt....@gmail.com (B.H.)
Injection-Date: Mon, 11 Apr 2022 15:12:11 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 69
 by: B.H. - Mon, 11 Apr 2022 15:12 UTC

On Monday, April 11, 2022 at 11:11:11 AM UTC-4, B.H. wrote:
> On Monday, April 11, 2022 at 8:50:58 AM UTC-4, malcolm.ar...@gmail.com wrote:
> > On Sunday, 10 April 2022 at 15:47:05 UTC+1, B.H. wrote:
> > > On Sunday, April 10, 2022 at 9:21:22 AM UTC-4, malcolm.ar...@gmail.com wrote:
> > > > I hope this post isn't too practical for comp.theory.
> > > >
> > > > As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. Version 1.6 is almost ready, and I have focused
> > > > on the user-interface side of things.
> > > >
> > > > But the heart of a crossword design program is the auto-fill algorithm. English-style grids, where each block of four squares is constrained to have at least one black square, usually fill almost instantaneously. American-style grids,
> > > > with a dense network of interlocking short words and only a few black
> > > > squares,a re far more challenging. Whilst I have had some successes,
> > > > usually the algorithm fails to complete before boredom sets in and I
> > > > terminate it.
> > > >
> > > > I've checked some papers, and the problem is NP-hard. Currently I use
> > > > a fairly naive backtracking algorithm. Another problem is that, to give
> > > > the algorithm a fighting chance, I give it a very large dictionary. But
> > > > really obscure words should be kept to a minimum.
> > > >
> > > > Work on a better way of doing American-style grids is pencilled in
> > > > for version 1.7.
> > > >
> > > > comp.theory readers might be interested in the first completed
> > > > American-style crossword. It's at
> > > > https://malcolmmclean.github.io/CrosswordDesigner/AmericanGrid1.html
> > > >
> > > > The project is on github
> > > > https://github.com/MalcolmMcLean/CrosswordDesigner
> > > Is the problem to decide if the user adding a particular square would lead to an solvable/unsolvable crossword grid, given a dictionary?
> > >
> > > I would go with annealing if you're looking for "good enough" NP-complete problem solving algorithms; genetic algorithms tend to be conceptually elegant but poorly performing, in my (limited) experience. I don't think backtracking is much more efficient than brute-force, unless you're dealing with an easy or small instance that brute force would be good enough for anyway...not that I'm sure about that.
> > >
> > Simulated annealing might be the way to go. The problem, as always, is writing the fitness and mutate
> > functions so that there aren't too many local minima that are non-solutions. In this case, a non-global
> > minimum that is still an acceptable solution is fine, even preferable.
> Yes, and you might want to be creative with the crossover function, too.
>
> -Philip White

Wait, I was thinking of genetic algorithms...whoops.

I haven't actually coded annealing algorithms, they just look more sensible and effective on paper than genetic algorithms.

-Philip

Re: Crossword filling

<t31oe4$p28$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=30028&group=comp.theory#30028

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: jbb...@notatt.com (Jeff Barnett)
Newsgroups: comp.theory
Subject: Re: Crossword filling
Date: Mon, 11 Apr 2022 11:27:31 -0600
Organization: A noiseless patient Spider
Lines: 110
Message-ID: <t31oe4$p28$1@dont-email.me>
References: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
<t2v443$r7h$1@dont-email.me>
<63d72533-6ee9-4636-8c35-84103db738e6n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 11 Apr 2022 17:27:32 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="543a38df0357e7555d2ca7fdc4e71e30";
logging-data="25672"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18oryMkCxRX9cLfUOGqEOJxHu9xAn4Mw0s="
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.8.0
Cancel-Lock: sha1:p+eY3WGkqJueuhepId1D62LE1AA=
In-Reply-To: <63d72533-6ee9-4636-8c35-84103db738e6n@googlegroups.com>
Content-Language: en-US
 by: Jeff Barnett - Mon, 11 Apr 2022 17:27 UTC

On 4/11/2022 6:48 AM, Malcolm McLean wrote:
> On Sunday, 10 April 2022 at 18:28:38 UTC+1, Jeff Barnett wrote:
>> On 4/10/2022 7:21 AM, Malcolm McLean wrote:
>>> I hope this post isn't too practical for comp.theory.
>>>
>>> As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. Version 1.6 is almost ready, and I have focused
>>> on the user-interface side of things.
>>>
>>> But the heart of a crossword design program is the auto-fill algorithm. English-style grids, where each block of four squares is constrained to have at least one black square, usually fill almost instantaneously. American-style grids,
>>> with a dense network of interlocking short words and only a few black
>>> squares,a re far more challenging. Whilst I have had some successes,
>>> usually the algorithm fails to complete before boredom sets in and I
>>> terminate it.
>>>
>>> I've checked some papers, and the problem is NP-hard. Currently I use
>>> a fairly naive backtracking algorithm. Another problem is that, to give
>>> the algorithm a fighting chance, I give it a very large dictionary. But
>>> really obscure words should be kept to a minimum.
>>>
>>> Work on a better way of doing American-style grids is pencilled in
>>> for version 1.7.
>>>
>>> comp.theory readers might be interested in the first completed
>>> American-style crossword. It's at
>>> https://malcolmmclean.github.io/CrosswordDesigner/AmericanGrid1.html
>>>
>>> The project is on github
>>> https://github.com/MalcolmMcLean/CrosswordDesigner
>> I haven't read your papers and am not an expert crossword (American
>> style) solver or creator. However, my guess is that those who do this
>> for a living follow this set of steps:
>>
>> ----
>> 1. Select a theme for the "long" entries.
>>
>> 2. Collect candidate long answers. This step may take days, weeks, or
>> months. It's the "wow" step of puzzle creation.
>>
>> 3. Sub-select long answers based on length (or other interesting feature).
>>
>> 4. Develop a compatible grid and insert long answers.
>>
>> 5. Now fill the rest in.
>>
>> If not successful, iterate steps 3 thru 5. If problems still remain, do
>> more of 2.
>> -----
>>
>> It's steps 1-3 that separate competent from inspired puzzles. Step 4
>> should radically reduce remaining generation time: there are more
>> constraints AKA less degrees of freedom.
>>
>> I can't swear this is how it's done by the experts but I'd bet a nickle
>> that it's close.
>>
> You're probably right. I'm British so I don't take an American newspaper.
> British crosswords rarely have themes, and they don't allow a square to
> be intersected by more than two words. Using my program, you can
> generate a blank "English-style" grid with a click, then fill it with another
> mouse click.
> So obviously American users will expect the same. But it's a lot harder
> to generate reasonable American-style grids at random. I resorted to
> stripping someone else's database and recycling the grids. (I hope it's
> all out of copyright, or that you can't copyright a blank grid).
> It's also a lot harder to fill an American-style grid. Whilst formally it's
> the same problem, the naive backtracking algorithm doesn't come
> back instantaneously with a fill the way it usually does with an English-
> style grid.
> I think most serious American constructors will do the theme first, as
> you say, then work around the short words. But if they are very serious,
> they will use paid-for software, and it's hard for a hobby project to
> compete with that. I'm aiming at schoolmasters or people who run
> church magazines, who will design the occasional crossword but can't
> justify a paid subscription.

Not much to add but I have an observation (that might be wrong)
different than yours: I think American style crosswords are easier to
solve because there is more redundancy. You get or guess a few small
entries and that provides clues about other entries. There are more
relatively easy starting places where you might "get lucky". The theme
in solving that is much like creation is moves to provide anchor points
and radically prune the search space.

Like I indicated above, I'm neither a good crossword creator or solver
but I do enjoy playing with them. In chess terms, I'm a duffer. My
relevant expertise is as an AI practitioner who has invented, analyzed,
and, applied search techniques - there the problem is always to discover
and get the constraints into the game as early as possible.

Another AI lesson from building expert systems is that the system
builder usually doesn't have sufficient expertise to provide the
knowledge or problem-solving heuristics necessary to build the system.
You will almost always do much better fining an interested expert in the
field and using him/her as your source and model of domain knowledge and
methods. This was true with virtually all successful systems that
achieved actual expert-level competence and performance. What we learned
in the earlier AI venture was that our place was to learn the field of
application well enough that we could apply our computer skills to hack
a series of systems; theses intermediate steps where improved using
feedback from the domain experts until things got good.

In other words, you would probably do better if you could acquire an
expert friend (i.e., a knowledgeable volunteer) who was interested in
seeing an interesting system developed. You could make the system
interesting, for example, by making it employ/discover themes or do
lexical tricks that occasionally appear in published puzzles. You would
need to include some cleverness in the proposed outcome to attract a
volunteer if, as you've said, commercial creator aids do exist.
--
Jeff Barnett

Re: Crossword filling

<57c3c665-40ae-4a20-8929-b245408b52d9n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=30031&group=comp.theory#30031

 copy link   Newsgroups: comp.theory
X-Received: by 2002:ad4:5cc3:0:b0:441:1959:cb45 with SMTP id iu3-20020ad45cc3000000b004411959cb45mr28497879qvb.93.1649702085804;
Mon, 11 Apr 2022 11:34:45 -0700 (PDT)
X-Received: by 2002:a0d:e2c6:0:b0:2ec:279b:c170 with SMTP id
l189-20020a0de2c6000000b002ec279bc170mr5342190ywe.302.1649702085584; Mon, 11
Apr 2022 11:34:45 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!1.us.feeder.erje.net!feeder.erje.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Mon, 11 Apr 2022 11:34:45 -0700 (PDT)
In-Reply-To: <t31oe4$p28$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:61e3:6326:3a3a:3cf0;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:61e3:6326:3a3a:3cf0
References: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
<t2v443$r7h$1@dont-email.me> <63d72533-6ee9-4636-8c35-84103db738e6n@googlegroups.com>
<t31oe4$p28$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <57c3c665-40ae-4a20-8929-b245408b52d9n@googlegroups.com>
Subject: Re: Crossword filling
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Mon, 11 Apr 2022 18:34:45 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 132
 by: Malcolm McLean - Mon, 11 Apr 2022 18:34 UTC

On Monday, 11 April 2022 at 18:27:35 UTC+1, Jeff Barnett wrote:
> On 4/11/2022 6:48 AM, Malcolm McLean wrote:
> > On Sunday, 10 April 2022 at 18:28:38 UTC+1, Jeff Barnett wrote:
> >> On 4/10/2022 7:21 AM, Malcolm McLean wrote:
> >>> I hope this post isn't too practical for comp.theory.
> >>>
> >>> As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. Version 1.6 is almost ready, and I have focused
> >>> on the user-interface side of things.
> >>>
> >>> But the heart of a crossword design program is the auto-fill algorithm. English-style grids, where each block of four squares is constrained to have at least one black square, usually fill almost instantaneously. American-style grids,
> >>> with a dense network of interlocking short words and only a few black
> >>> squares,a re far more challenging. Whilst I have had some successes,
> >>> usually the algorithm fails to complete before boredom sets in and I
> >>> terminate it.
> >>>
> >>> I've checked some papers, and the problem is NP-hard. Currently I use
> >>> a fairly naive backtracking algorithm. Another problem is that, to give
> >>> the algorithm a fighting chance, I give it a very large dictionary. But
> >>> really obscure words should be kept to a minimum.
> >>>
> >>> Work on a better way of doing American-style grids is pencilled in
> >>> for version 1.7.
> >>>
> >>> comp.theory readers might be interested in the first completed
> >>> American-style crossword. It's at
> >>> https://malcolmmclean.github.io/CrosswordDesigner/AmericanGrid1.html
> >>>
> >>> The project is on github
> >>> https://github.com/MalcolmMcLean/CrosswordDesigner
> >> I haven't read your papers and am not an expert crossword (American
> >> style) solver or creator. However, my guess is that those who do this
> >> for a living follow this set of steps:
> >>
> >> ----
> >> 1. Select a theme for the "long" entries.
> >>
> >> 2. Collect candidate long answers. This step may take days, weeks, or
> >> months. It's the "wow" step of puzzle creation.
> >>
> >> 3. Sub-select long answers based on length (or other interesting feature).
> >>
> >> 4. Develop a compatible grid and insert long answers.
> >>
> >> 5. Now fill the rest in.
> >>
> >> If not successful, iterate steps 3 thru 5. If problems still remain, do
> >> more of 2.
> >> -----
> >>
> >> It's steps 1-3 that separate competent from inspired puzzles. Step 4
> >> should radically reduce remaining generation time: there are more
> >> constraints AKA less degrees of freedom.
> >>
> >> I can't swear this is how it's done by the experts but I'd bet a nickle
> >> that it's close.
> >>
> > You're probably right. I'm British so I don't take an American newspaper.
> > British crosswords rarely have themes, and they don't allow a square to
> > be intersected by more than two words. Using my program, you can
> > generate a blank "English-style" grid with a click, then fill it with another
> > mouse click.
> > So obviously American users will expect the same. But it's a lot harder
> > to generate reasonable American-style grids at random. I resorted to
> > stripping someone else's database and recycling the grids. (I hope it's
> > all out of copyright, or that you can't copyright a blank grid).
> > It's also a lot harder to fill an American-style grid. Whilst formally it's
> > the same problem, the naive backtracking algorithm doesn't come
> > back instantaneously with a fill the way it usually does with an English-
> > style grid.
> > I think most serious American constructors will do the theme first, as
> > you say, then work around the short words. But if they are very serious,
> > they will use paid-for software, and it's hard for a hobby project to
> > compete with that. I'm aiming at schoolmasters or people who run
> > church magazines, who will design the occasional crossword but can't
> > justify a paid subscription.
> Not much to add but I have an observation (that might be wrong)
> different than yours: I think American style crosswords are easier to
> solve because there is more redundancy. You get or guess a few small
> entries and that provides clues about other entries. There are more
> relatively easy starting places where you might "get lucky". The theme
> in solving that is much like creation is moves to provide anchor points
> and radically prune the search space.
>
> Like I indicated above, I'm neither a good crossword creator or solver
> but I do enjoy playing with them. In chess terms, I'm a duffer. My
> relevant expertise is as an AI practitioner who has invented, analyzed,
> and, applied search techniques - there the problem is always to discover
> and get the constraints into the game as early as possible.
>
> Another AI lesson from building expert systems is that the system
> builder usually doesn't have sufficient expertise to provide the
> knowledge or problem-solving heuristics necessary to build the system.
> You will almost always do much better fining an interested expert in the
> field and using him/her as your source and model of domain knowledge and
> methods. This was true with virtually all successful systems that
> achieved actual expert-level competence and performance. What we learned
> in the earlier AI venture was that our place was to learn the field of
> application well enough that we could apply our computer skills to hack
> a series of systems; theses intermediate steps where improved using
> feedback from the domain experts until things got good.
>
> In other words, you would probably do better if you could acquire an
> expert friend (i.e., a knowledgeable volunteer) who was interested in
> seeing an interesting system developed. You could make the system
> interesting, for example, by making it employ/discover themes or do
> lexical tricks that occasionally appear in published puzzles. You would
> need to include some cleverness in the proposed outcome to attract a
> volunteer if, as you've said, commercial creator aids do exist.
>
There are quite a few options, both free and paid. The New York TImes
recommends CrossFire and Crossword Compiler. I'm not one of those
people who think that paid-for software is an affront to social justice,
on the other hand, I do think that simple tools should be free. You shouldn't
have to pay a lot of money to get the software to run a not-for profit
magazine.

I'm not really a crossword person either. It might be time to get a crossword
expert involved. It's the familiar chicken and egg problem, you need a
community of expert users who will contribute ideas to be taken seriously,
but until you are taken seriously, you can't attract those expert users.

I did write a crossword for my mother's bridge club magazine, using a
very early version of the program which just had manual editing. It
wasn't too difficult to create a bridge-themed crossword. However it was
a one off. It would be hard to do another one, because I'd run through
all the obvious puns on bridge the game, bridges the civil engineering
structures, and bridges of vessels.

I decided that focus for version 1.6 would be the user interface, to develop
a more polished look and feel. I'm nearly there. The question then is what to
do, whether to pause development for a while and focus on other things, or
to get a better auto-fill algorithm, or add more features.

Re: Crossword filling

<fb43ea9d-14e2-474f-8cf5-a74d0406ba11n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=30135&group=comp.theory#30135

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:620a:4510:b0:69c:54b4:399 with SMTP id t16-20020a05620a451000b0069c54b40399mr547880qkp.771.1649810930782;
Tue, 12 Apr 2022 17:48:50 -0700 (PDT)
X-Received: by 2002:a05:6902:84:b0:63d:4a3d:eb5 with SMTP id
h4-20020a056902008400b0063d4a3d0eb5mr27948094ybs.145.1649810930589; Tue, 12
Apr 2022 17:48:50 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Tue, 12 Apr 2022 17:48:50 -0700 (PDT)
In-Reply-To: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=93.41.99.122; posting-account=F3H0JAgAAADcYVukktnHx7hFG5stjWse
NNTP-Posting-Host: 93.41.99.122
References: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <fb43ea9d-14e2-474f-8cf5-a74d0406ba11n@googlegroups.com>
Subject: Re: Crossword filling
From: jul...@diegidio.name (Julio Di Egidio)
Injection-Date: Wed, 13 Apr 2022 00:48:50 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 49
 by: Julio Di Egidio - Wed, 13 Apr 2022 00:48 UTC

On Sunday, 10 April 2022 at 15:21:22 UTC+2, malcolm.ar...@gmail.com wrote:
> I hope this post isn't too practical for comp.theory.
>
> As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. Version 1.6 is almost ready, and I have focused
> on the user-interface side of things.
>
> But the heart of a crossword design program is the auto-fill algorithm. English-style grids, where each block of four squares is constrained to have at least one black square, usually fill almost instantaneously. American-style grids,
> with a dense network of interlocking short words and only a few black
> squares,a re far more challenging. Whilst I have had some successes,
> usually the algorithm fails to complete before boredom sets in and I
> terminate it.

But, pardon a question (I have never read about this problem before): I see you fill/compose the grid square by square, i.e. one letter in one position at a time, but had I had to approach this problem, I'd have worked differently: 1) design a grid; 2) fill the grid word by word from a given (finite and fixed) dictionary, with the only constraints of word length and how words cross each other; and that would be it and I wouldn't expect it to take particularly long to start printing out solutions (filled grids with their id, which here is simply some progressive relative to the brute-force search).

> I've checked some papers, and the problem is NP-hard.

Could you please link some? Would be nice to see how in the literature the problem is stated exactly.

> Currently I use
> a fairly naive backtracking algorithm. Another problem is that, to give
> the algorithm a fighting chance, I give it a very large dictionary. But
> really obscure words should be kept to a minimum.
>
> Work on a better way of doing American-style grids is pencilled in
> for version 1.7.
>
> comp.theory readers might be interested in the first completed
> American-style crossword. It's at
> https://malcolmmclean.github.io/CrosswordDesigner/AmericanGrid1.html
>
> The project is on github
> https://github.com/MalcolmMcLean/CrosswordDesigner

Julio

Re: Crossword filling

<f26e1724-751a-4eb3-8a10-4bc00f26ab0dn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31980&group=comp.theory#31980

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:6214:518d:b0:45a:933f:965d with SMTP id kl13-20020a056214518d00b0045a933f965dmr13186670qvb.94.1652102574948;
Mon, 09 May 2022 06:22:54 -0700 (PDT)
X-Received: by 2002:a81:7b46:0:b0:2e1:5ae7:5789 with SMTP id
w67-20020a817b46000000b002e15ae75789mr14631698ywc.61.1652102574717; Mon, 09
May 2022 06:22:54 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Mon, 9 May 2022 06:22:54 -0700 (PDT)
In-Reply-To: <fb43ea9d-14e2-474f-8cf5-a74d0406ba11n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:942c:ea35:908c:9324;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:942c:ea35:908c:9324
References: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com> <fb43ea9d-14e2-474f-8cf5-a74d0406ba11n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f26e1724-751a-4eb3-8a10-4bc00f26ab0dn@googlegroups.com>
Subject: Re: Crossword filling
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Mon, 09 May 2022 13:22:54 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
 by: Malcolm McLean - Mon, 9 May 2022 13:22 UTC

On Wednesday, 13 April 2022 at 01:48:51 UTC+1, ju...@diegidio.name wrote:
> On Sunday, 10 April 2022 at 15:21:22 UTC+2, malcolm.ar...@gmail.com wrote:
> > I hope this post isn't too practical for comp.theory.
> >
> > As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. Version 1.6 is almost ready, and I have focused
> > on the user-interface side of things.
> >
> > But the heart of a crossword design program is the auto-fill algorithm. English-style grids, where each block of four squares is constrained to have at least one black square, usually fill almost instantaneously. American-style grids,
> > with a dense network of interlocking short words and only a few black
> > squares,a re far more challenging. Whilst I have had some successes,
> > usually the algorithm fails to complete before boredom sets in and I
> > terminate it.
> But, pardon a question (I have never read about this problem before): I see you fill/compose the grid square by square, i.e. one letter in one position at a time, but had I had to approach this problem, I'd have worked differently: 1) design a grid; 2) fill the grid word by word from a given (finite and fixed) dictionary, with the only constraints of word length and how words cross each other; and that would be it and I wouldn't expect it to take particularly long to start printing out solutions (filled grids with their id, which here is simply some progressive relative to the brute-force search).
> > I've checked some papers, and the problem is NP-hard.
> Could you please link some? Would be nice to see how in the literature the problem is stated exactly.

https://arxiv.org/pdf/2109.11203.pdf

(Sorry for the delay. We've had Easter and a product launch, and I haven't had time for crosswords).

Re: Crossword filling

<4f1adc5a-674d-4eb7-b703-b47c3081bcafn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=32106&group=comp.theory#32106

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:620a:795:b0:69f:d074:6067 with SMTP id 21-20020a05620a079500b0069fd0746067mr15008831qka.527.1652185534901;
Tue, 10 May 2022 05:25:34 -0700 (PDT)
X-Received: by 2002:a0d:eb4b:0:b0:2f8:9089:3ad4 with SMTP id
u72-20020a0deb4b000000b002f890893ad4mr18933881ywe.65.1652185534741; Tue, 10
May 2022 05:25:34 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Tue, 10 May 2022 05:25:34 -0700 (PDT)
In-Reply-To: <f26e1724-751a-4eb3-8a10-4bc00f26ab0dn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=93.41.100.50; posting-account=F3H0JAgAAADcYVukktnHx7hFG5stjWse
NNTP-Posting-Host: 93.41.100.50
References: <9272f3e7-00fc-4e5f-8b0d-08022d3adf3fn@googlegroups.com>
<fb43ea9d-14e2-474f-8cf5-a74d0406ba11n@googlegroups.com> <f26e1724-751a-4eb3-8a10-4bc00f26ab0dn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <4f1adc5a-674d-4eb7-b703-b47c3081bcafn@googlegroups.com>
Subject: Re: Crossword filling
From: jul...@diegidio.name (Julio Di Egidio)
Injection-Date: Tue, 10 May 2022 12:25:34 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2016
 by: Julio Di Egidio - Tue, 10 May 2022 12:25 UTC

On Monday, 9 May 2022 at 15:22:56 UTC+2, malcolm.ar...@gmail.com wrote:
> On Wednesday, 13 April 2022 at 01:48:51 UTC+1, ju...@diegidio.name wrote:
> > On Sunday, 10 April 2022 at 15:21:22 UTC+2, malcolm.ar...@gmail.com wrote:
> > > I hope this post isn't too practical for comp.theory.
> > >
> > > As people who follow my posts on other newsgroups may know, I'm writing a program to design crosswords. [...]
> > > I've checked some papers, and the problem is NP-hard.
> >
> > Could you please link some? Would be nice to see how in the literature the problem is stated exactly.
> >
> https://arxiv.org/pdf/2109.11203.pdf
>
> (Sorry for the delay. We've had Easter and a product launch, and I haven't had time for crosswords).

Thanks very much, appreciated!

Julio

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor