Is this a Boggle pad?

11

1

Given a list of case-insensitive ASCII letter strings ("words"), output whether the entire list can be found on some four-by-four configuration ("board") of letter squares, in which no square can be used more than once in a word, and in which words are formed by moving from any square to any adjacent square including diagonally.

You do not need to worry that the combination of squares that would allow for the list actually appears in a Boggle game. The words need not be actual words in any language. You should assume that if Q appears on the board, it's on a square of its own (unlike in actual Boggle).

Standard loopholes are banned, standard I/O rules apply, and you're golfing.


In the examples below, a slash signifies a newline.

Truthy examples

  • auuuuooiiaaoiee, euiaaiueeuua, ooouuueee, eueueuoaoa — All are on the board auii/euoa/ueoa/euio
  • swiop, byteba, ceropl, qoiz, aeis, lqoep — All are on the board abcb/rety/poiw/lqzs

Falsy examples

  • swiop, byteba, ceropl, qoiz, aeis, lqoep, wybez — There are fifteen distinct letters (abceilopqrstwyz) and a single word has two bs, so that's the sixteenth square. Thus there's only one e. But the e has nine distinct letters (abcioprtz) adjacent to it, which is impossible.
  • hskcbnzvgfa, lajdnzvfhgs, kajfbmxvshd, ldgckvbsanx — There are sixteen distinct letters (abcdfghjklmnsvxz). Of those, s is adjacent to all of abghkv, v is adjacent to all of bfgksxz, b is adjacent to all of cfmnsv, a is adjacent to all of fjklns, and f is adjacent to all of abghjv. But on an actual board only four squares are adjacent to more than five squares apiece.

msh210

Posted 2018-04-28T23:17:36.623

Reputation: 3 094

6I can understand the challenge clearly and unambiguously. If anyone disagree (and VTC as unclear), consider leaving a comment. – user202729 – 2018-04-29T02:02:11.497

1

I wonder if it would be better suited for fastest-code or fastest-algorithm. As code-golf, it may lead to brute-force solutions that run forever and never actually return anything.

– Arnauld – 2018-04-29T10:30:14.320

(Or you may consider adding a time limit if you decide to keep it as code-golf.) – Arnauld – 2018-04-29T10:31:59.477

@Arnauld, I don't like fastest-code challenges, personally, and don't know enough compsci to understand or judge fastest-algorithm challenges. That said, I'm considering making a note in the challenge that no brute-force answer will get the checkmark, even if it's shortest in its language. – msh210 – 2018-04-29T11:25:02.003

1You'd need to define what brute-force exactly means. But even so, I'm not sure it's a good idea. A very clever answer may still use brute-force in some way. – Arnauld – 2018-04-29T11:39:13.113

4Besides that, I too think that the challenge is clearly defined. So, people that have VTC really should share their thoughts. – Arnauld – 2018-04-29T11:42:39.900

@msh Not accepting any answer is an option. – user202729 – 2018-04-30T02:33:23.337

@Arn Both codegolf and fastestcode are interesting in their own way. You can post fastestcode if you want. – user202729 – 2018-04-30T02:34:08.110

3As far as I can see, in general this is a subgraph problem, which is NP complete, so all non-magical answers will need some degree of brute force. – Phil H – 2018-05-01T11:32:55.173

I haven't VTC, but the question didn't make sense to me until I read up on what Boggle was and what its rules were. Perhaps a short description that would make sense to someone who doesn't know Boggle, and better formatting of the board (auii/euoa/ueoa/euio) in 2D, would help clarify the challenge. – sundar - Reinstate Monica – 2018-06-16T14:14:02.093

No answers