2

The puzzle: We have $3$ dice, each having $4$ sides. Every side of every dice has a single letter on it (rather than a number).
We want to be able to make each of the words CAT, SON, POD, RIG, PEG, TAP, DIN, APE by rolling all dice together and rearranging them in the right order.

Determine the symbols on each dice.

I need to use the logical formula (i.e. all the conditions the dice have to satisfy) to let an SMT solver solve the problem via Z3. I can't figure out how to translate this into a logical formula.

abus
  • 21
  • 1
    What's the question? Are you asking something like "is there a way to label the sides on the three dice such that each of these words is possible?" Something else? – lulu Dec 23 '22 at 12:02
  • @lulu each dice sides has different letters and they must be able to make the words indicated above – abus Dec 23 '22 at 12:05
  • Ok, so what have you tried? – lulu Dec 23 '22 at 12:06
  • @lulu I don't know where to start. – abus Dec 23 '22 at 12:11
  • Perhaps you should consider a smaller version of this puzzle, with just two letter words (one letter words with one dice is too easy). For example, suppose you wanted two dice so that the words $CA,SO,PO,RI,PE,TA,DI,AP$ are producible. Maybe do this : think first for just $CA,SO,PO,RI$. Then add one word at a time, increase the complexity. See where you stumble, if at all! Then see if you can do the three letter version. – Sarvesh Ravichandran Iyer Dec 23 '22 at 12:15
  • Problems like this are meant to be played with...starting with CAT, say, put the $C,A,T$ on three different dice. But then TAP shows that the P should be with the C and so on. I expect that sort of thing leads to a solution fairly quickly (assuming there is one). – lulu Dec 23 '22 at 12:33
  • @lulu It's not about solving the puzzle for me now, but about writing down the conditions that the dice must meet with variables (bool and/or integer), equality, 'and', 'or', 'not' etc – abus Dec 23 '22 at 12:40
  • @SarveshRavichandranIyer that makes it easier but then I still don't know how to write it down. What I have so far is this with your example: (¬(C ∧ A) ∧ ¬(S ∧ O) ∧ ¬(P ∧ O) ∧ ¬(R ∧ I)) – abus Dec 23 '22 at 13:05
  • @abus I'm sorry, I am unable to understand the question. I saw your translation, and I don't see why that's the formula. What does $\neg(C \wedge A)$ mean, for example? I think it means that $C$ and $A$ don't appear on the same dice. However, that's not true : $C$ and $A$ could appear on both dices and you'd still be able to make $CA$. What you should try to say is that "for some pair of dice, $C$ is on one of the dies, and $A$ is on the other". So for example, if the dice are $D_i,i=1,2,3,4$ then $\exists (i \neq j) (C \in D_i, A \in D_j)$ makes sense (then take the intersection). – Sarvesh Ravichandran Iyer Dec 23 '22 at 13:32
  • If this is completely unintelligible, then I'm sorry, because I tried my best to understand your question and perhaps remain some way off. As for solving it, it seems an answer has done that. – Sarvesh Ravichandran Iyer Dec 23 '22 at 13:33
  • @SarveshRavichandranIyer I meant that C and A can't both be on one die. Otherwise you can never make the word CA. You use each die per letter. Di,i=1,2,3,4 then ∃(i≠j)(C∈Di,A∈Dj) I think this is what I'm looking for but now for all the words. – abus Dec 23 '22 at 13:44
  • @abus I don't think the implication is correct. For example, if you want to create $CA$, then it's enough to have $C,A$ on one dice and $C,A$ on the other dice as well : this way too, you can create $CA$. So it's not true that to create $CA$, you can't have $C$ and $A$ on the same dice. It's true that there are two different dices, one of which has $C$ as a face and one of which has $A$ as a face. That's what I expressed : a dice $D_i$ which has $C$ as a face, and a different dice $D_j$ which has $A$ as a face. That's what $\exists i \neq j , C \in D_i, A \in D_j$ means. – Sarvesh Ravichandran Iyer Dec 23 '22 at 15:07
  • That is, $\in$ means "is one of the faces of" and the dices are numbered $D_1,D_2,D_3,D_4$ (say), so that $i,j$ belong to the set ${1,2,3,4}$. – Sarvesh Ravichandran Iyer Dec 23 '22 at 15:37
  • @SarveshRavichandranIyer thanks for the explanation. Di,i=1,2 then ∃(i≠j)(C∈Di,A∈Dj, S∈Di,O∈Dj, P∈Di,O∈Dj, R∈Di,I∈Dj ) So this is the answer for the smaller version of the puzzle, correct? – abus Dec 23 '22 at 15:38
  • @abus Not exactly, but you're almost there. The point is, we know that $C$ is on one dice and $A$ is on another dice. If you notice, you wrote that $C\in D_i,S \in D_i$ : but it's not necessary that $C,S$ come from the same dice because you're allowed to "rearrange in the right order". The right answer is very close though : you just "AND" all the words together. For example, $$(\exists i_1 \neq j_1 , C \in D_{i_1}, A \in D_{j_1})\wedge(\exists i_2 \neq j_2, S \in D_{i_2}, O \in D_{j_2}) \wedge (\exists i_3 \neq j_3, P \in D_{i_3}, O \in D_{j_3}) \wedge (\text{the last one is similar})$$ – Sarvesh Ravichandran Iyer Dec 23 '22 at 15:47
  • At THAT point, you can use the and, because you want to be able to form the words CA and SO and PO and RI, so the $\wedge$ comes in there. However, within each formation, there is no $\wedge$, because you need two different dice to exist for which those letters can be the faces. Also, while it will take some time to write, one can easily extend this to the large case ($3$ dice, $8$ words), which you can have a go at now. – Sarvesh Ravichandran Iyer Dec 23 '22 at 15:50
  • $i=1,2,3$ then $(∃i1≠j1≠k1,C∈Di1,A∈Dj1,T∈Dk1)∧(∃i2≠j2≠k2,S∈Di2,O∈Dj2,N∈Dk2)∧(∃i3≠j3≠k3,P∈Di3,O∈Dj3,D∈Dk3)$ (and so on.... ) Correct me if I'm wrong. – abus Dec 23 '22 at 21:42
  • Beware that $i\neq j\neq k$ does not imply that $i\neq k,$ which you also need. Moreover you need something to say that each die has only four letters on it. – David K Dec 23 '22 at 22:36
  • @abus you've got the hang of it, pretty much.just David's comment above and you are done. Thank you for participating in this back and forth – Sarvesh Ravichandran Iyer Dec 24 '22 at 03:06
  • @DavidK $∃¬(i1=j1∧i1=k1∧ j1=k1)$ now i ,j and k can't be the same, right? But at the moment I don't know how to prove that every dice has only 4 sides. Anyone have suggestions? What suddenly comes to my mind is that the variables j and k must also be 1, 2 or 3, should I also indicate that? Like this: j = 1,2,3 and k=1,2,3 – abus Dec 24 '22 at 15:11
  • @SarveshRavichandranIyer can you check my previous comment please. – abus Dec 29 '22 at 00:17

3 Answers3

3

If there is a logical formula, it's going to be very long, because you have $12$ different locations to be filled with $12$ different letters.

Moreover, in terms of actually solving the problem, merely translating it into a logical formula is not necessarily going to make it any easier to solve, because the problem of satisfying a proposition in Boolean logic is one of the famous NP-complete problems. Informally you can take this as an indication that you might end up having to just brute-force the solution by very tedious trial and error.

But in this case there is almost a deterministic algorithm to solve the problem. Very little trial-and-error is really required.

Try making a grid of eight rows by four columns. Put the words you have to make in the first column. The letters to put on the dice will go in the other three columns, where each column contains all the letters that are on one die.

Since the columns can be exchanged without affecting what words can be made, we might as well start by filling in one of the words, say CAT, in the last three columns. So we start out like this:

\begin{array}{|c|c|c|c|}\hline CAT & C & A & T \\ \hline SON & & & \\ \hline POD & & & \\ \hline RIG & & & \\ \hline PEG & & & \\ \hline TAP & & & \\ \hline DIN & & & \\ \hline APE & & & \\ \hline \end{array}

Now since there are $12$ different letters that must fit on the $12$ sides of the three dice, we know that whenever a letter appears in a column, that letter must appear again in the same column on every row where that letter is used in the word in the first column. Doing this for the letters C, A, T, we get this result:

\begin{array}{|c|c|c|c|}\hline CAT & C & A & T \\ \hline SON & & & \\ \hline POD & & & \\ \hline RIG & & & \\ \hline PEG & & & \\ \hline TAP & & A & T \\ \hline DIN & & & \\ \hline APE & & A & \\ \hline \end{array}

Another simple rule is that whenever we have just one empty cell in a given row, that cell must be filled with the remaining letter of the word that has not yet been written on that row:

\begin{array}{|c|c|c|c|}\hline CAT & C & A & T \\ \hline SON & & & \\ \hline POD & & & \\ \hline RIG & & & \\ \hline PEG & & & \\ \hline TAP & P & A & T \\ \hline DIN & & & \\ \hline APE & & A & \\ \hline \end{array}

Write the additional copies of the new letter where they must occur:

\begin{array}{|c|c|c|c|}\hline CAT & C & A & T \\ \hline SON & & & \\ \hline POD & P & & \\ \hline RIG & & & \\ \hline PEG & P & & \\ \hline TAP & P & A & T \\ \hline DIN & & & \\ \hline APE & P & A & \\ \hline \end{array}

Continue applying these two simple rules. The next step is to write the remaining letter of APE, namely E, in the blank cell in that row, then write copies of E in the row for PEG; this leaves only one blank cell in the PEG row, which you fill with G, which you then copy in the RIG row. At this point the grid looks like this:

\begin{array}{|c|c|c|c|}\hline CAT & C & A & T \\ \hline SON & & & \\ \hline POD & P & & \\ \hline RIG & & G & \\ \hline PEG & P & G & E \\ \hline TAP & P & A & T \\ \hline DIN & & & \\ \hline APE & P & A & E \\ \hline \end{array}

At this point all the letters in the grid have been copied wherever they can be, and there are no rows with only one blank cell, so we have to try something else.

We have six remaining letters to put in ten remaining empty cells. Four of the letters, D, I, N, and O, get written twice each, and the remaining two letters, R and S, get written once each. Three of the doubled letters occur in rows where there are only two empty cells, so if we choose one of these letters there are only two possible ways to fill that letter in the grid. Try each way an continue solving as before; only one of the attempts will work.

That's a little trial and error, but not much.

As an alternative to trial and error, let's start over with a new word. There is one word, DIN, that contains three of the doubled letters left over from the first stage of the solution. If we fill these letters into the grid (not using any of the letters we used before), we get this:

\begin{array}{|c|c|c|c|}\hline CAT & & & \\ \hline SON & & & \\ \hline POD & & & \\ \hline RIG & & & \\ \hline PEG & & & \\ \hline TAP & & & \\ \hline DIN & D & I & N \\ \hline APE & & & \\ \hline \end{array}

Copy the letters of DIN where they need to be copied:

\begin{array}{|c|c|c|c|}\hline CAT & & & \\ \hline SON & & & N \\ \hline POD & D & & \\ \hline RIG & & I & \\ \hline PEG & & & \\ \hline TAP & & & \\ \hline DIN & D & I & N \\ \hline APE & & & \\ \hline \end{array}

There is one remaining doubled letter, O, which has to be written in the rows for SON and POD, in the same column both times. Only the second column is empty in these two rows, so O goes there:

\begin{array}{|c|c|c|c|}\hline CAT & & & \\ \hline SON & & O & N \\ \hline POD & D & O & \\ \hline RIG & & I & \\ \hline PEG & & & \\ \hline TAP & & & \\ \hline DIN & D & I & N \\ \hline APE & & & \\ \hline \end{array}

We can now fill in the remaining letters of SON and POD. Let's do this and then compare the grid we have so far (derived from DIN) side by side with the grid we derived earlier from CAT:

$$ \begin{array}{|c|c|c|c|}\hline CAT & & & \\ \hline SON & S & O & N \\ \hline POD & D & O & P \\ \hline RIG & & I & \\ \hline PEG & & & \\ \hline TAP & & & \\ \hline DIN & D & I & N \\ \hline APE & & & \\ \hline \end{array} \qquad \begin{array}{|c|c|c|c|}\hline CAT & C & A & T \\ \hline SON & & & \\ \hline POD & P & & \\ \hline RIG & & G & \\ \hline PEG & P & G & E \\ \hline TAP & P & A & T \\ \hline DIN & & & \\ \hline APE & P & A & E \\ \hline \end{array} $$

Somehow we have to be able to reconcile these two grids into a third grid. Obviously we cannot just copy the letters of the grid on the left to the grid on the right, because some copied letters would conflict with letters already written in the grid, but remember that the sequence of columns was arbitrary. So we can shuffle columns of the left-hand grid to make it "fit" the right-hand grid.

Clearly the P of POD has to be in the same column in each grid, so let's take column $3$ of the left grid and put it before the other two columns. Now we have

$$ \begin{array}{|c|c|c|c|}\hline CAT & & & \\ \hline SON & N & S & O \\ \hline POD & P & D & O \\ \hline RIG & & & I \\ \hline PEG & & & \\ \hline TAP & & & \\ \hline DIN & N & D & I \\ \hline APE & & & \\ \hline \end{array} \qquad \begin{array}{|c|c|c|c|}\hline CAT & C & A & T \\ \hline SON & & & \\ \hline POD & P & & \\ \hline RIG & & G & \\ \hline PEG & P & G & E \\ \hline TAP & P & A & T \\ \hline DIN & & & \\ \hline APE & P & A & E \\ \hline \end{array} $$

It is also clear that the last two columns of the left-hand grid have to be copied in the order shown above, because if we swapped them then the left-hand grid would have an I in column $2$ and this would conflict with the G of RIG in the right-hand grid.

Copying the letters from one grid to the other, we get

\begin{array}{|c|c|c|c|}\hline CAT & C & A & T \\ \hline SON & N & S & O \\ \hline POD & P & D & O \\ \hline RIG & & G & I \\ \hline PEG & P & G & E \\ \hline TAP & P & A & T \\ \hline DIN & N & D & I \\ \hline APE & P & A & E \\ \hline \end{array}

There's only one cell left and only one way to fill it:

\begin{array}{|c|c|c|c|}\hline CAT & C & A & T \\ \hline SON & N & S & O \\ \hline POD & P & D & O \\ \hline RIG & R & G & I \\ \hline PEG & P & G & E \\ \hline TAP & P & A & T \\ \hline DIN & N & D & I \\ \hline APE & P & A & E \\ \hline \end{array}

Read off the unique letters from each column:

\begin{array}{c} CNPR \\ ASDG \\ TOIE \end{array}

Those are the letters on each die.

David K
  • 98,388
  • Thanks for your answer. I am not going to solve the puzzle myself via a logical formula. I need to use the logical formula (i.e. all the conditions the dice have to satisfy) to let an SMT solver solve the problem via Z3. – abus Dec 23 '22 at 21:02
  • 2
    Details like that (using an MST solver) are absolutely essential to put in the question itself. You can edit the question to fix this. While you are doing that, I recommend to add any other information that might be relevant, such as where the problem came from, what tools you are supposed to use (name of solver) -- be specific and name names. Assume that the person who might have the answer you want will not read any of the comments, so everything to evoke that answer has to be in the main question. – David K Dec 23 '22 at 22:18
  • We don't have 12 different locations to be filled with 12 different letters, we have only 3 locations, the three dice. In your tabular format, that's the three columns, because the rows are not something we get to choose. – MJD Dec 24 '22 at 15:17
  • @MJD In each row you have only $3$ letters for $3$ locations. But also each die has four sides. That's $12$ sides altogether. If there were $13$ distinct letters among all the words we would know right away there is no solution. If there were only $11$ distinct sides then the rule "whenever a letter appears in a column, that letter must appear again in the same column on every row where that letter is used" would not hold, because we could have another copy of the letter on another die and therefore it could occur in two different columns. – David K Dec 24 '22 at 15:33
1

There are 12 unique letters, so each must appear exactly once. answer set = {ASDG, TOIE, CNPR}

Arrange the words in a grid like so and then tally the unique contents of each column. Where a letter appears in more than one column, swap columns. This can happen recursively.

AngleWyrm
  • 11
  • Thanks for you explanation, but I'm looking for the logical formula of this puzzle. – abus Dec 23 '22 at 13:11
  • @abus To the best of my knowledge, the problem must be solved by an iterative process, as described in this answer. If my surmise is correct, then there is no closed form solution. Obviously, I could be mistaken. – user2661923 Dec 23 '22 at 13:37
1

Let $c_1, c_2, c_3$ be the statements that letter C is on die #1, #2, or #3 respectively. It must be at least one, so

$$c_1\lor c_2\lor c_3$$

and it can't be on more than one, so

$$(c_1\land\lnot c_2)\\ (c_1\land\lnot c_3)\\\vdots$$

We want CAT so these three letters must be on different dice:

$$(c_1\land a_2\land t_3)\lor\\ (c_1\land a_3\land t_2)\lor\\\vdots$$

Maybe you can take it from there. As has been pointed out elsewhere, you can abbreviate this somewhat by arbitrarily assuming that $c_1, a_2, t_3$ are all true and simplifying the formulas accordingly.

MJD
  • 65,394
  • 39
  • 298
  • 580