## more, please! As The Riddler proposed for several weeks in a row a CrossProduct™ puzzle where 3 x n one-digit integers have to be deduced from their rowwise and columnwise products, I attempted writing an R solver by applying a few basic rules repeatedly, which worked for the first two puzzles, if not for the earlier one I solved by paper & pen (mostly) a few weeks ago, and again worked for the final one. The rules I used were to spot unique entries, forced entries by saturation, and forced digits (from the prime factor decomposition) again by saturation. Any further rule to add to the solver? (The R code is currently rather ugly!) Please, some more!

### 4 Responses to “more, please!”

1. Bob Carpenter Says:

I love these kinds of constraint satisfaction puzzles. I used to work on constraint satisfaction in the early 1990s. It also reminds me of the top tier Top Coder problems I used to do when I moved from academia to industry and needed to get a lot better at coding in a language like C++.

I’m appending some C++ code to solve your problem. It takes 0.06s to solve this one (O3 optimization with clang++ on an iMac Pro):

7, 7, 6 
9, 8, 3 
9, 5, 3 
7, 2, 7 
8, 2, 7 
7, 4, 3 
5, 7, 7 
8, 5, 1 
(8890560), (156800), (55566)

The algorithm is a simple backtracking algorithm, like one might learn in an intro algorithms class as a solution to the 8-queens puzzle. All it does is try to fill in from upper left one square at a time (by row), only extending with guesses by which the row and column products are divisible and for which completed rows have the right product. There would be a lot of ways to make this go much faster. For example, the last entry in a row is deterministic given the row products. Also, only the last entry added needs to be checked for consistency given the way the extension and backtracking work.

This is the same basic constraint resolution algorithm I used to build a Sudoku solver in Java after trying my hand at one on a flight.

As usual, I thought I could code this in 30m, but my index fiddling just isn’t what it was back in my Top Coder practice days, so I wound up whiling away 2 hours of my Friday afternoon on it.

```#include
#include
#include

using vec = std::vector;

bool divisible(int y, int x) {
return (y % x) == 0;
}

int index(int i, int j, int N) {
return i * N + j;
}

int row_product(const vec& guess, int i, int N) {
int prod = 1;
for (int j = 0; j < N; ++j)
prod *= guess[index(i, j, N)];
return prod;
}

int col_product(const vec& guess, int j, int M, int N) {
int prod = 1;
for (int i = 0; i < M; ++i)
prod *= guess[index(i, j, N)];
return prod;
}

void print_matrix(const vec& guess, const vec& rowprod, const vec& colprod) {
int M = rowprod.size();
int N = colprod.size();
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j)
std::cout << guess[index(i, j, N)] << (j < N - 1 ? ", " : "");
std::cout << " [" << rowprod[i] << "]" << std::endl;
}
for (int j = 0; j < N; ++j)
std::cout << "(" << colprod[j] << ")" << (j < N - 1 ? ", " : "");
std::cout < 0 && solution.back() == 9)
solution.pop_back();
if (solution.size() == 0)
throw std::runtime_error("unsolvable!\n");
++solution.back();
}

bool consistent(const vec& guess, const vec& rowprod, const vec& colprod) {
int M = rowprod.size();
int N = colprod.size();

// rowprod, colprod divisible by entries
int pos = 0;
for (int i = 0; pos < guess.size() && i < M; ++i)
for (int j = 0; pos < guess.size() && j < N; ++j, ++pos)
if (!divisible(rowprod[i], guess[pos])
|| !divisible(colprod[j], guess[pos]))
return false;

// correct row products for filled rows
int M_filled = guess.size() / N;
for (int i = 0; i < M_filled; ++i)
if (row_product(guess, i, N) != rowprod[i])
return false;
return true;
}

bool solved(const vec& guess, const vec& rowprod, const vec& colprod) {
int M = rowprod.size();
int N = colprod.size();
if (guess.size() != M * N)
return false;
for (int j = 0; j < N; ++j)
if (col_product(guess, j, M, N) != colprod[j])
return false;
for (int i = 0; i < M; ++i)
if (row_product(guess, i, N) != rowprod[i])
return false;
return true;
}

vec solve(const vec& rowprod, const vec& colprod) {
int M = rowprod.size();
int N = colprod.size();
int size = M * N;
vec guess;
while (!solved(guess, rowprod, colprod))
if (guess.size() < size && consistent(guess, rowprod, colprod))
extend(guess);
else
backtrack(guess);
return guess;
}

int main() {
vec rowprod{294, 216, 135, 98, 112, 84, 245, 40};   // {2, 12, 30};
vec colprod{8890560, 156800, 55566};                // {15, 48};

vec solution = solve(rowprod, colprod);
print_matrix(solution, rowprod, colprod);
}
```

And here’s what the run looks like:

```\$ clang++ -O3 -std=c++17 riddle.cpp

\$ time ./a.out

7, 7, 6 
9, 8, 3 
9, 5, 3 
7, 2, 7 
8, 2, 7 
7, 4, 3 
5, 7, 7 
8, 5, 1 
(8890560), (156800), (55566)

real	0m0.236s
user	0m0.055s
sys	0m0.001s
```
• Bob Carpenter Says:

After the program was primed, subsequent runs took 0.06s! Also, the editor ate all of my angle brackets. I forgot how unfriendly WordPress is to pre blocks. All the vectors are vector<int>, and includes are exception, iostream, and vector. Luckily, it didn’t eat the comparison < symbols.

```\$ time ./a.out
7, 7, 6 
9, 8, 3 
9, 5, 3 
7, 2, 7 
8, 2, 7 
7, 4, 3 
5, 7, 7 
8, 5, 1 
(8890560), (156800), (55566)

real	0m0.058s
user	0m0.056s
sys	0m0.001s
```
• xi'an Says:

Thanks for the code and the two hours, Bob!

2. more, please! | R-bloggers Says:

[…] article was first published on R – Xi'an's Og, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here) […]

This site uses Akismet to reduce spam. Learn how your comment data is processed.