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. 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:

    $ clang++ -O3 -std=c++17 riddle.cpp
    
    $ time ./a.out
    
    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)
    
    real	0m0.236s
    user	0m0.055s
    sys	0m0.001s
    
    • 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 [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)
      
      real	0m0.058s
      user	0m0.056s
      sys	0m0.001s
      
  2. […] 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) […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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