Using matrix operations to solve the Einstein's riddle. Part II.

In the previous part of this article we formulated the Einstein's riddle in terms of matrices, and presented three matrix operations that will be the base for an algorithm to solve the riddle. In this part we'll be talking about this algorithm, and a JavaScript implementation which will allow solving this riddle and any other grid riddle similar to this one.

Rules based on the use of the matrix operators

The algorithm is pretty straightforward, and it's based on three rules (the use of the operators defined previously, has been highlighted):

1. If a hint matrix has a common value with other hint matrix then: If both matrices can be merged (no matter if new rows should be added to the first matrix), then merge both hints, otherwise reject.

2. If the riddle matrix has a common value with a hint matrix then: If the hint matrix can be merged into the riddle matrix without the need to add new rows to the riddle matrix, then merge the hint matrix into the riddle matrix, otherwise reject.

3. If for a specific blank cell in the riddle matrix located on column C, there exists one and only one hint which matrix contains a row, where the cell on column C is not blank and the it can be merged into the riddle matrix using that cell as the point of merger and without the need to add new rows to the riddle matrix, then merge the hint matrix into the riddle matrix.

The two first rules are very intuitive, the third one is a little more complex, but it makes sense when none of the hint matrices can be merged between them or into the riddle matrix.

The algorithm

The algorithm can be described using the following pseudo code:

1. Get the start matrix (riddle matrix) and the set of hints (hint matrices)

2. While the riddle matrix has empty cells do

• Check rule 1 for every pair of hint matrices, and repeat the process until no pair of matrices can be merged. If a rejection occurs then the problem doesn't have solution for the set of hints.

• Check rule 2 for every hint matrix. If a rejection occurs then the problem doesn't have solution for the set of hints.

• If none of the hints was able to be merged into the previous two steps, check rule 3 for every blank cell in the riddle matrix.

Note that if the problem is not well defined, the algorithm could iterate infinitely, so it's a good idea to use another stop condition based on the amount of iterations.

When there are options in any of the hints, people don't consider the idea to generate all possible combinations of hints, instead of that, they try to find the right option in every hint while trying to solve the puzzle; but for the purpose of the algorithm we described, several options result in different sets of hints. The algorithm will test each set of hints, which gives the possibility to find all the possible solutions, as it happens in one of the riddles we chose at the end of this article.

JavaScript Implementation

There are some programming languages as Prolog, designed to work with logic facts, where you can deal with logical problems in a natural way. By using the matrix formulation we can use any programming language to deal with this kind of riddles. Here we provide the implementation, in JavaScript, of the matrix object with the three basic operators used to solve the riddles. The selection of JavaScript is not arbitrary, it allows to show the effectiveness of the algorithm in this same post.

<script type="text/javascript">
var stringMatrix = function(m)
{
  this.values = m;
}

stringMatrix.prototype.totalRows = function(){
  return this.values.length;
}

stringMatrix.prototype.totalColumns = function(){
  return this.values[0].length;
}

stringMatrix.prototype.hasCommonValue = function(matrix){
  for (var i = 1 - matrix.totalRows(); i < this.totalRows(); i++){
    for (var k = 0; k < matrix.totalRows(); k++){
      for (var j = 0; j < this.totalColumns(); j++){
        if ((i + k) >= 0 && (i + k) < this.totalRows()){
          if (this.values[i + k][j] != '' && this.values[i + k][j] == matrix.values[k][j]){
            return {
              found: true,
              rowIndex: i + k,
              externalMatrixRowIndex: k,
              columnIndex: j
            };
          }
        }
      }
    }
  }
  return { found: false };
}

stringMatrix.prototype.canBeMerged = function(rowIndex, matrix, matrixRowIndex, failIfGoBeyond){
  if (failIfGoBeyond && ((rowIndex + matrix.totalRows() - matrixRowIndex > this.totalRows()) || (matrixRowIndex - rowIndex > 0))){
    return false;
  }

  var leftSteps = Math.min(rowIndex, matrixRowIndex);
  var totalRows = leftSteps + Math.min(this.totalRows() - rowIndex, matrix.totalRows() - matrixRowIndex);
  var minIndex = rowIndex - leftSteps;
  var minMatrixIndex = matrixRowIndex - leftSteps;

  for (var i=0; i<totalRows; i++){
    for (var j = 0; j < this.totalColumns(); j++){
      if (this.values[minIndex + i][j] != '' && matrix.values[minMatrixIndex + i][j] != '' && this.values[minIndex + i][j] != matrix.values[minMatrixIndex + i][j]){
        return false;
      }
    }
  }

  return true;
}

stringMatrix.prototype.newRow = function(){
  var newRow = new Array(this.totalColumns());
  for (var i=0; i < newRow.length; i++){
    newRow[i] = '';
  }
  return newRow;
}

stringMatrix.prototype.merge = function(rowIndex, matrix, matrixRowIndex){
  if (this.totalRows() < rowIndex + matrix.totalRows() - matrixRowIndex){
    for (var i = this.totalRows(); i < rowIndex + matrix.totalRows() - matrixRowIndex; i++){
      this.values.push(this.newRow());
    }
  }

  if (matrixRowIndex - rowIndex > 0){
    for (var i = 0; i < matrixRowIndex - rowIndex; i++){
      this.values.unshift(this.newRow());
    }
    rowIndex = matrixRowIndex
  }

  var i = rowIndex - matrixRowIndex;
  for (var k = 0; k < matrix.totalRows(); k++){
    for (var j = 0; j < this.totalColumns(); j++){
      if (matrix.values[k][j] != ''){
        this.values[i + k][j] = matrix.values[k][j];
      }
    }
  }
}
</script>

You can download the whole script here: riddle-solver.js

You only need to call the function: solveRiddle(riddle, elementId), where the riddle parameter is the JSON object containing all the necessary info (see below) and elementId is the id of a div where you want to display the solution.

Solving grid riddles

We chose 6 different grid riddles, including the Einstein's riddle, to show the algorithm's effectiveness:

1. Neighbours (Einstein's riddle)
2. Ships puzzle
3. Meeting the challenge
4. Soccer Problem
5. Who lives in the city?
6. Who stole the Ginger cookie from cookie jar?

For riddle number 5, note that the algorithm finds two different valid solutions.

In all cases, when selecting the riddle, you can see the riddle description.

If you want to see the steps and rules used at every step, just check the Detailed Solution box.

The edit box "JSON" shows how the problem is defined for the algorithm be able to understand the matrix and hints. It uses a JSON object that requires 4 attributes:

header: An array with the header of the columns

startMatrix: The start matrix used to solve the problem. It should contain values on at least one of its columns, depending on the problem. The amount of columns in this matrix should be the same as the length of the header array.

hints: It's a four-dimension matrix, where each entry should correspond to a hint in the verbal formulation. When the hint can be expressed as a single submatrix, then the entry on the four-dimension matrix will be a three-dimension matrix containing only one entry (the submatrix), but if the hint derived in more than one option, then the entry will be a three-dimension matrix containing as many submatrices as options derived from the hint.

singleHints: This is Boolean value to specify if the rows of each submatrix representing a hint, should be considered as single rows or as a submatrix itself. For example, in the Einstein's riddle the hint 6 is considered as a submatrix itself, because both rows must always remain together, on the other hand if you check hints from riddle Meeting the challenge, there is one hint that states: Pamela and her husband borrowed the book that Mr and Mrs Zajac brought; this hint involves two rows, but it doesn't mean the rows should be one after the other.

If you are familiar with JSON, you could use the edit box to introduce new problems when selecting "My own grid riddle".

If you want to share any idea, please leave a comment or write to us.