more, please!
:max_bytes(150000):strip_icc():format(webp)/illustration-depicting-oliver-twist-asking-for-more-food-by-j--mahoney-517216578-59f93a010d327a0010b2dd78.jpg)
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!
Xi'an's Og 
February 27, 2021 at 12:59 am
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 [294]
9, 8, 3 [216]
9, 5, 3 [135]
7, 2, 7 [98]
8, 2, 7 [112]
7, 4, 3 [84]
5, 7, 7 [245]
8, 5, 1 [40]
(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:
February 27, 2021 at 1:02 am
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.
February 27, 2021 at 7:20 pm
Thanks for the code and the two hours, Bob!
February 26, 2021 at 8:11 am
[…] 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) […]