January 17, 2021
In a world of sudokus, KenKens and kakuros, Barbara Yew offers a different sort of number puzzle:
There are eight three-digit numbers — each belongs in a row of the table below, with one digit per cell. The products of the three digits of each number are shown in the rightmost column. Meanwhile, the products of the digits in the hundreds, tens, and ones places, respectively, are shown in the bottom row.
Can you find all eight three-digit numbers and complete the table? It’s a bit of a mystery, but I’m sure you have it within you to hunt down the answer!
Answer:
7 7 6 9 8 3 9 5 3 7 2 7 8 2 7 7 4 3 5 7 7 8 5 1
Explanation:
Prime factor the numbers on the right-hand column, and collect factors keeping only the combinations that are between 1 and 9, inclusive. After that, I used an exhaustive search algorithm balancing time spent shrinking the search set and the algorithm's actual search time. I did this by only considering the digits that are possible for each row and let the machine take care of the columns. Algorithm written in MATLAB:
%% Author: David Ding
% January 17, 2021
clear;
close all;
clc;
%% Start of solver
% For each row, we populate the only possible values
posValSet = {
[6, 7];
[3, 4, 6, 8, 9];
[3, 5, 9];
[2, 7];
[1, 2, 4, 7, 8];
[2, 3, 4, 6, 7];
[5, 7];
[1, 2, 4, 5, 8];
};
horizVals = [294; 216; 135; 98; 112; 84; 245; 40];
vertVals = [8890560, 156800, 55566];
% Exhaustive Search
finalAns = zeros(8, 3);
% Populate a guess using the allowed values only
searchValSet = cell(8, 1);
for k = 1:8
searchValSet{k} = popListOfPossibleAnswers(posValSet{k}, horizVals(k));
end
%% Search
for a = 1:length(searchValSet{1})
finalAns(1, :) = deal(searchValSet{1}(a, :));
for b = 1:length(searchValSet{2})
finalAns(2, :) = deal(searchValSet{2}(b, :));
for c = 1:length(searchValSet{3})
finalAns(3, :) = deal(searchValSet{3}(c, :));
for d = 1:length(searchValSet{4})
finalAns(4, :) = deal(searchValSet{4}(d, :));
for e = 1:length(searchValSet{5})
finalAns(5, :) = deal(searchValSet{5}(e, :));
for f = 1:length(searchValSet{6})
finalAns(6, :) = deal(searchValSet{6}(f, :));
for g = 1:length(searchValSet{7})
finalAns(7, :) = deal(searchValSet{7}(g, :));
for h = 1:length(searchValSet{8})
finalAns(8, :) = deal(searchValSet{8}(h, :));
fprintf('%d %d %d %d %d %d %d %d\n',...
a, b, c, d, e, f, g, h);
% Verify answer
if checkAnswer(finalAns, vertVals)
% We've found it!
disp('Got it!');
return;
end
end
end
end
end
end
end
end
end
finalAns
%% Populate answers row
function vecList = popListOfPossibleAnswers(posVals, desiredVal)
len = length(posVals);
vecList = NaN(len^3, 3);
k = 1;
for a = 1:len
for b = 1:len
for c = 1:len
% Horizontal check
prod = posVals(a) * posVals(b) * posVals(c);
if prod ~= desiredVal
continue;
end
vecList(k, 1) = posVals(a);
vecList(k, 2) = posVals(b);
vecList(k, 3) = posVals(c);
k = k + 1;
end
end
end
vecList = rmmissing(vecList);
end
%% Check answer helper function
function res = checkAnswer(finalAns, vertVals)
res = true;
% Vertical
for j = 1:3
prodVec = cumprod(finalAns(:, j));
prod = prodVec(end);
if prod ~= vertVals(j)
res = false;
return;
end
end
end
>> finalAns
finalAns =
7 7 6
9 8 3
9 5 3
7 2 7
8 2 7
7 4 3
5 7 7
8 5 1