Riddler Express: February 12, 2021

David Ding

February 12, 2021

Mystery Sudoku Mini Part 2

It’s the second week in our four weeks of CrossProduct™ puzzles!

This time around, there are six 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.

sudokugridTable

Can you find all six three-digit numbers and complete the table?

Answer:

7     6     5
9     8     2
3     9     2
5     9     3
1     4     1
7     1     7
	

Explanation:

Prime factor the numbers on the right-hand column, and collect factors keeping only the possible 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. That is, I do the work on the rows, and MATLAB handles the rest with the columns. 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
% February 15, 2021
clear;
close all;
clc;

%% Start of solver
% For each row, we populate the only possible values
posValSet = {
    [5, 6, 7];
    [2, 3, 4, 6, 8, 9];
    [1, 2, 3, 6, 9];
    [3, 5, 9];
    [1, 2, 4];
    [1, 7, 7];
};

horizVals = [210; 144; 54; 135; 4; 49];
vertVals = [6615, 15552, 420];

% Exhaustive Search
rows = length(horizVals);
finalAns = zeros(rows, 3);

% Populate a guess using the allowed values only
searchValSet = cell(rows, 1);
for k = 1:rows
    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, :));
                        fprintf('%d %d %d %d %d %d\n',...
                                        a, b, c, d, e, f);
                        % Verify answer
                        if checkAnswer(finalAns, vertVals)
                            % We've found it!
                            disp('Got it!');
                            finalAns %#ok
                            return;
                        end
                    end
                end
            end
        end
    end
end

%% 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     6     5
     9     8     2
     3     9     2
     5     9     3
     1     4     1
     7     1     7
		

For explanation on how I populated the list of possible values, please see my last week's post.