Background: Many years ago, while I was getting an MS in operations research, I took a class where the prof assigned, once per week or so, a combinatorial sort of problem. The intent was that students would spend a couple of hours finding the “trick” to transform the problem into one that could be solved manually. I found it was quicker in terms of student-time to write little programs to run through all possible solutions, or at least all possible interesting solutions. When the homework was handed back, the prof would make… comments. The comment he often made about my solution was, “And Mr. Cain, of course, used brute force on the computer [1] to get an answer.” To which my response was generally, “Yes, but I was clever about the brute force. Not only can my piece of code solve the problem we were given, but it can (a) tell you if there are multiple solutions, and (b) is fast enough to be used to solve similar non-toy problems.” Sometimeswith the prof’s response of, “Yes. Mr. Cain, the chalkboard is yours, to talk about clever use of brute force for a few minutes.” The division problems are well-suited to clever use of brute force.

Side note: Absent any constraints, any problem of this form has a “trivial” solution with all letters having the value zero, exploiting the fact that 0/0 is undefined, hence any damned thing you would like it to be.

Having said all that… in setting up conditions that a solution must satisfy, the most obvious in this case is

LAA * LLATT + LDDTR == LTRNNUI

This involves only eight of the variables. Running through the 100 million possible combinations of eight variables (following Mr. Schilling’s advice to assume nothing, but ignoring the all-zero solution because it’s boring) and testing against that condition takes some time (in Perl, on my Mac, with no serious effort to optimize the code, 19 minutes of processor time). Unsurprisingly, there are multiple possibilities.

However, if we’re clever about the order in which we examine possible solutions, that condition also gives us

(A * T + R – I) mod 10 == 0

that can be used to eliminate a lot of the possibilities earlier in the search, reducing the search time to about 2 minutes, and identifying exactly the same 50 partial solutions.

If we start working our way through other simple constraints in the larger problem, we immediately find that

(R + N) mod 10 == I and (T + N) mod 10 == U

can be incorporated using only the eight variables previously used and reduce the search time to about 1.2 seconds. More interestingly, at this point we find that there are no non-trivial results that satisfy the constraints.

My code is specific to the problem given. Generalizing it to handle any such division problem is left as a straightforward exercise for the student.

[1] Most students avoided even attempting brute-force solutions because we were provided with limited pseudo-funds to buy resources on the university’s computers. Over the course of time at two different universities, I was a living demonstration that there’s almost always a way to get computer time for free. God, I love having fast personal computers instead of having to steal computing resources.

I once wrote a Sudoko-solver in Java that was clever (I thought) brute force. The algorithm is

0. Call step 1. 1. Find the first empty square. If there isn’t one, return. If there is, set it to the smallest number that doesn’t break the rules. If there is such a number, call step 1. If not, return. 2. When the called function returns, check whether the puzzle is solved. If so, return. 3. If the puzzle isn’t solved and our value isn’t already 9, increment it and call step 1. 4. If the puzzle isn’t solved and our value is 9, empty out our square and return. 5. When the outermost call returns, the puzzle is either solved or unsolvable.

It solves any solvable puzzle in well under a second, though unsolvable ones can take considerably longer to report that they’re unsolvable.

Presumably if the goal were expanded to either find all possible solutions, or to show that a solution was unique, the code would have taken as long as it took to prove a problem had no solution. There’s a growing body of literature about solving Sudoku puzzles. The most common Sudoku puzzle — a 9×9 grid subdivided into 3×3 grids — has been shown to be NP-complete.

It’s a bit more complicated than that. How long it takes to determine there’s no solution depends on where the contradiction shows up. Worst case is terrible, best case is very quick, and I haven’t tried to figure out where average case is. Finding all possible solutions doesn’t necessarily take a long time, depending on how much the cells that start filled in constrain the set of possible solutions.

Zl vzzrqvngr nffhzcgvba jnf gung gur yrggre “ryy” jnf rdhny gb mreb, juvpu jbhyq trg zr gb n tbbq cynpr… hagvy V fnj NYRGV zvahf NNEYA jnf rdhny gb fbzrguvat. NY zvahf NN jbhyq abg or n cbfvgvir ahzore vs “ryy” jnf mreb.

In that case, here’s something to keep you busy. I stopped at the Seven-Eleven while I was out running errands today, and bought four items. When I took them to the front counter, the kid on duty did something with the cash register and said, “That’ll be $7.11.” As I’m naturally suspicious, I asked him how he got that figure and he told me that he had multiplied the four prices together. “That’s not the right way to do it, you have to add the prices.” So he did the thing with the cash register and said, “Still $7.11.” What were the prices of the four items? Assume no sales tax, and the prices are exact in cents.

Unlike Jaybird, I’m not irritated, I’m fascinated. So, a simple yes-or-no question: are all of the following statements simultaneously true? I use + in the standard way.

A > 0 L > 0 ALETI, AARLN, and LDDTR are all > 0 LDDTR + AARLN = ALETI

To wrap this one up, the trick is that the problem is in base -10 (that is, negative 10). You don’t come across negative bases a lot, but they work pretty much as you’d expect: the rightmost digit is 1’s, the next one over -10’s, the next one 100s, and so on. So, for instance, in base -10, 127 – 134 = 193, which in base regular 10 comes out as 87 – 74 = 13.

The digits in the division problem are

0123456789
ILNATCUERD

which is “inturlaced” interlaced (the misspelling was necessary to avoid duplicate ‘e’s.) That makes the problem

Hmmm…

Background: Many years ago, while I was getting an MS in operations research, I took a class where the prof assigned, once per week or so, a combinatorial sort of problem. The intent was that students would spend a couple of hours finding the “trick” to transform the problem into one that could be solved manually. I found it was quicker in terms of student-time to write little programs to run through all possible solutions, or at least all possible interesting solutions. When the homework was handed back, the prof would make… comments. The comment he often made about my solution was, “And Mr. Cain, of course, used brute force on the computer [1] to get an answer.” To which my response was generally, “Yes, but I was

cleverabout the brute force. Not only can my piece of code solve the problem we were given, but it can (a) tell you if there are multiple solutions, and (b) is fast enough to be used to solve similar non-toy problems.” Sometimeswith the prof’s response of, “Yes. Mr. Cain, the chalkboard is yours, to talk about clever use of brute force for a few minutes.” The division problems are well-suited to clever use of brute force.Side note: Absent any constraints, any problem of this form has a “trivial” solution with all letters having the value zero, exploiting the fact that 0/0 is undefined, hence any damned thing you would like it to be.

Having said all that… in setting up conditions that a solution must satisfy, the most obvious in this case is

LAA * LLATT + LDDTR == LTRNNUI

This involves only eight of the variables. Running through the 100 million possible combinations of eight variables (following Mr. Schilling’s advice to assume nothing, but ignoring the all-zero solution because it’s boring) and testing against that condition takes some time (in Perl, on my Mac, with no serious effort to optimize the code, 19 minutes of processor time). Unsurprisingly, there are multiple possibilities.

However, if we’re clever about the order in which we examine possible solutions, that condition also gives us

(A * T + R – I) mod 10 == 0

that can be used to eliminate a lot of the possibilities earlier in the search, reducing the search time to about 2 minutes, and identifying exactly the same 50 partial solutions.

If we start working our way through other simple constraints in the larger problem, we immediately find that

(R + N) mod 10 == I and

(T + N) mod 10 == U

can be incorporated using only the eight variables previously used and reduce the search time to about 1.2 seconds. More interestingly, at this point we find that there are no non-trivial results that satisfy the constraints.

My code is specific to the problem given. Generalizing it to handle any such division problem is left as a straightforward exercise for the student.

[1] Most students avoided even attempting brute-force solutions because we were provided with limited pseudo-funds to buy resources on the university’s computers. Over the course of time at two different universities, I was a living demonstration that there’s almost always a way to get computer time for free. God, I love having fast personal computers instead of having to steal computing resources.

Michael CainQuote Link

Report

I once wrote a Sudoko-solver in Java that was clever (I thought) brute force. The algorithm is

0. Call step 1.

1. Find the first empty square. If there isn’t one, return. If there is, set it to the smallest number that doesn’t break the rules. If there is such a number, call step 1. If not, return.

2. When the called function returns, check whether the puzzle is solved. If so, return.

3. If the puzzle isn’t solved and our value isn’t already 9, increment it and call step 1.

4. If the puzzle isn’t solved and our value is 9, empty out our square and return.

5. When the outermost call returns, the puzzle is either solved or unsolvable.

It solves any solvable puzzle in well under a second, though unsolvable ones can take considerably longer to report that they’re unsolvable.

Mike SchillingQuote Link

Report

Presumably if the goal were expanded to either find all possible solutions, or to show that a solution was unique, the code would have taken as long as it took to prove a problem had no solution. There’s a growing body of literature about solving Sudoku puzzles. The most common Sudoku puzzle — a 9×9 grid subdivided into 3×3 grids — has been shown to be NP-complete.

Michael CainQuote Link

Report

It’s a bit more complicated than that. How long it takes to determine there’s no solution depends on where the contradiction shows up. Worst case is terrible, best case is very quick, and I haven’t tried to figure out where average case is. Finding all possible solutions doesn’t necessarily take a long time, depending on how much the cells that start filled in constrain the set of possible solutions.

Mike SchillingQuote Link

Report

More interestingly, at this point we find that there are no non-trivial results that satisfy the constraints.So, what assumptions have you made that you’ve just shown to be false?

Mike SchillingQuote Link

Report

I’m already irritated.

JaybirdQuote Link

Report

Zl vzzrqvngr nffhzcgvba jnf gung gur yrggre “ryy” jnf rdhny gb mreb, juvpu jbhyq trg zr gb n tbbq cynpr… hagvy V fnj NYRGV zvahf NNEYA jnf rdhny gb fbzrguvat. NY zvahf NN jbhyq abg or n cbfvgvir ahzore vs “ryy” jnf mreb.

JaybirdQuote Link

Report

Of course, once you start multiplying, that flies out the window.

JaybirdQuote Link

Report

Nsgre V tbg qbar orngvat vg gb qrngu jvgu n pbzchgre, V nyfb fgnegrq sebz NYRGV >= NNEYA. Gung pna bayl or gehr vs YRGV >= NEYA, gb nibvq gur arrq gb obeebj sebz gung yrnqvat N. Urapr Y vf vaqrrq mreb. Ohg abj YRGV >= NEYA jvgu Y == 0 zrnaf gung N zhfg nyfb or mreb, juvpu cebivqrf n *ybg* bs vasbezngvba.

Michael CainQuote Link

Report

Then my work here is done.

Mike SchillingQuote Link

Report

In that case, here’s something to keep you busy. I stopped at the Seven-Eleven while I was out running errands today, and bought four items. When I took them to the front counter, the kid on duty did something with the cash register and said, “That’ll be $7.11.” As I’m naturally suspicious, I asked him how he got that figure and he told me that he had multiplied the four prices together. “That’s not the right way to do it, you have to

addthe prices.” So he did the thing with the cash register and said, “Still $7.11.” What were the prices of the four items? Assume no sales tax, and the prices are exact in cents.Michael CainQuote Link

Report

This one is a pain in the ass.

ChrisQuote Link

Report

Hint:

The ten different letters in the puzzle represent the digits 0-9 in the usual way, that is, each digit is represented by one and only one letter.

The usual rules for writing numbers apply, so neither L nor A is zero.

Mike SchillingQuote Link

Report

Unlike Jaybird, I’m not irritated, I’m fascinated. So, a simple yes-or-no question: are all of the following statements simultaneously true? I use + in the standard way.

A > 0

L > 0

ALETI, AARLN, and LDDTR are all > 0

LDDTR + AARLN = ALETI

Michael CainQuote Link

Report

YOU WILL BE

JaybirdQuote Link

Report

It is driving me crazy! I keep running into contradictions. I hate contradictions. This is evil!

ChrisQuote Link

Report

I don’t understand how L + A can equal A if L is 1 or greater.

JaybirdQuote Link

Report

L is on drugs.

ChrisQuote Link

Report

All true.

Mike SchillingQuote Link

Report

Fb, artngvir onfr 10 nevguzrgvp. VYANGPHREQ.

Michael CainQuote Link

Report

Very nice. Now, for the grand prize, what do those letters spell?

Mike SchillingQuote Link

Report

How about “cruel trial?” Which I’m sure some of the others are thinking about now.

Michael CainQuote Link

Report

Pretty good, but the answer isn’t an anagram; it’s more tightly determined than that.

Mike SchillingQuote Link

Report

Which makes no sense. I’m much worse at anagrams than I am at numbers.

Michael CainQuote Link

Report

Trarenyvmvat gur oehgr-sbepr nccebnpu gb unaqyr n artngvir onfr vf fgenvtugsbejneq. Qvq lbh ernyyl rkcrpg crbcyr gb pehapu guebhtu vg ol ybtvp nybar va n artngvir onfr?

Michael CainQuote Link

Report

Vg’f qbnoyr. Sbe vafgnapr, bapr lbh svther bhg vg’f onfr artngvir gra, vg’f boivbhf gung Y vf bar naq gung gur gjb qvtvgf bs gur dhbgvrag gbgny gra.

Mike SchillingQuote Link

Report

I saw the explanation in the Logic thread and I immediately ran here to see if there was a similar explanation.

JaybirdQuote Link

Report

To wrap this one up, the trick is that the problem is in base -10 (that is, negative 10). You don’t come across negative bases a lot, but they work pretty much as you’d expect: the rightmost digit is 1’s, the next one over -10’s, the next one 100s, and so on. So, for instance, in base -10, 127 – 134 = 193, which in base regular 10 comes out as 87 – 74 = 13.

The digits in the division problem are

which is “inturlaced” interlaced (the misspelling was necessary to avoid duplicate ‘e’s.) That makes the problem

Mike SchillingQuote Link

Report

JaybirdQuote Link

Report