Sudoku: Exact Cover Matrix

2020, Jun 06
Link to project here.

In computer science, the exact cover problem is a decision problem to determine if an exact cover exists, and Donald Knuth's Algorithm X is an algorithm for finding all solutions to the problems.

After a lot of googling, reading and trial and error, I can finally generate my own exact cover matrix dynamically based on the size of the Sudoku puzzle. The idea that got me to this point is basically:

"It's a matrix where the rows represent each possible move, and every column represents a constraint that needs to be satisfied"

However, I'd be lying if I said I can comfortably explain the overall concept to myself, let alone anybody else. So here are some links to resources I found very helpful:

  1. Gareth Rees, Zendoku puzzle generation
  2. Andy G, Solving Sudoku, Revisited
  3. Baeldung, Create a Sudoku Solver in Java

Implementation

In essence, this is a Javascript translation of Baeldung's Java implementation. On top of it however, I took extra care in trying to understand the reasoning behind every line of code as most examples seemed to brush past explaining what everything does and why certain values are used.

Just so we are on the same page, here are some of the terms I will be using:

  • matrix = the exact cover matrix
  • row, col = exact cover matrix row and col
  • grid = the grid containing the Sudoku puzzle
  • i, j, b (or block) = grid row, col and block
  • v = value (or symbol) at grid[i,j]
  • row progression = how the values [i,j,v] that each row represents changes sequentially
  • column progression = how the constraints and the value combinations ([i,j]..., [i,v]..., [j,v]...) that each col represents changes sequentially
  • marking a column = replacing the value 0 of a column with a 1, meaning the row it is on satisfies the constraint of that column

getRowIndex

In my eyes, this is the most important function in the set. It guarantees we can always find the correct row to while constructing the columns of the exact cover matrix, allowing us to only have to focus on the column progression.

const getRowIndex = (i, j, v, grid) => {
  // Returns the index of the row in the EC matrix for the grid state [i,j,v]
  // This is the most important function that allows me to assign 1s to rows out of order
  const matrix = grid.get("matrix")
  const symbols = grid.get("symbols")
  // for every cycle of v, j will increase. For every cycle of j, i will increase
  const iOffset = i * matrix.count() * symbols.count()
  const jOffset = j * symbols.count()
  // Thankfully the order of values in the an Immutable.Set is stable
  const vOffset = symbols.toList().indexOf(v) 
  return iOffset + jOffset + vOffset
}

Based on the given i, j, v and grid, it calculates the row index of this particular combination of values in the exact cover matrix. The expectation is every time the symbols cycle, it increments the column by 1, and every time columns finish cycling, it increments rows by 1. Just like how starting from 0, if you add 1 (a symbol) enough times, the number ticks over to 10 (columns), and adding enough sets of 10 causes the number to tick over into 100 (rows) before continuing the process. Another way of representing it would be:

const getRowIndex = (i, j, v, grid) => { // Very inefficient
  let rowInd = 0
  for (let i2=0; i2<grid.get("matrix").count(); i2++) {
    for (let j2=0; j2<grid.get("matrix").get(0).count(); j2++) {
      symbols.forEach(v2 => {
        if(i==i2 && j==j2 && v==v2) return rowInd
        rowInd++
      })
    }
  }
}

To get a view of the row progression check out this ASCII Exact Cover Matrix.

Initializing an Empty Matrix

The approach taken in creating the exact cover matrix is basically to initialize an empty matrix and then filling it in progressively. In order to initialize the empty matrix, we need to know its dimensions, and this section dives into how it is calculated.

Number of Rows

Like I said earlier, the rows represent every possible move in Sudoku. For every cell [i,j], there is a value v, thus the total number of rows can be calculated as ni * nj * nv.

// One row for every value in every grid[i,j]
const nRows = gMatrix.count() * gMatrix.get(0).count() * symbols.count()

If a grid has 4 rows, and 5 columns with 6 possible values for each cell, then there will be 4 * 5 * 6 = 120 rows in the exact cover matrix.

Number of Columns

The columns in the exact cover matrix represent the constraints that need to be satisfied.

This first constraint is the one where every grid cell must contain a value (Cell Constraint). So the number of columns in this section is equal to the number of cells in the grid, ni * nj.

// Cell constraint (each grid[i,j] must contain a v)
// One col for every grid[i,j]
// This constraint is satisfied when a grid[i,j] contains any valid value
const nCellConCols = gMatrix.count() * gMatrix.get(0).count()

The second constraint is where every grid row must contain exactly one of each value (Row Constraint). So the number of columns in this section is equal to the number of i-v combinations, ni * nv. You can also think of it as every cell in i must be filled with a unique value v.

// Row constraint (Each i must contain every v)
// One col for every possible (i,v) pair
// This constraint is satisfied when a v exists in a given i. 
const nRowConCols = gMatrix.count() * symbols.count()

The third constraint is where every grid column must contain exactly one of each value (Column Constraint). So the number of columns in this section is equal to the number of j-v combinations , nj * nv.

// Col constraint (Each j must contain every v)
// One col for every possible (j,v) pair
// This constraint is satisfied when a v exists in a given j. 
const nColConCols = gMatrix.get(0).count() * symbols.count()

The final constraint is where every grid block must contain exactly one of each value (Block Constraint). So the number of columns in this section is equal to the number of b-v combinations , nb * nv.

// Block constraint (Each b must contain every v)
// One col for every possible (b,v) pair
// This constraint is satisfied when a v exists in a given b.
const nBlocksInGrid = gMatrix.count()
const nBlockConCols = nBlocksInGrid * symbols.count()

Dimensions

The final dimensions for our exact cover matrix are as follows:

  • Rows : ni * nj * nv
  • Columns : (ni * nj) + (ni * nv) + (nj * nv) + (nb * nv)

Filling the Matrix

Because we implemented getRowIndex() earlier, we don't have worry about iterating through the rows of the exact cover matrix in the correct order. Instead, we just need to make sure we get every combination of values with respect to the constraint and mark the corresponding rows.

For example, in a 9x9 grid, we already know that the Cell Constraint has 81 columns (ni * nj), and we also know that every v we put into the cell [i,j] will satisfy the same constraint column, so we must mark every row where i and j are the same, and v is any value before moving on to another column:

const _setCellConstraints = (mutable, grid, col) => {
  // col represents the starting index for a particular section of constraints
  // Usually it means that it is the sum on the number of column for each section
  // that has come before it
  const gMatrix = grid.get("matrix")
  const symbols = grid.get("symbols")
  // For each grid[i,j]
  for (let i=0; i<gMatrix.count(); i++) {
    for (let j=0; j<gMatrix.get(0).count(); j++) {
      // and every possible value for each cell
      symbols.forEach(v => {
        // Mark the current col at the row that represents [i,j,v]
        const row = exactCover.getRowIndex(i, j, v, grid)
        mutable.setIn([row, col], 1)
      })
      // ** Go to next col after every row that satisfies 
      // the same constraint has been marked **
      col++
    }
  }
}

We will apply the same logic to Row Constraints, where there are also 81 columns (ni * nv), and every j will satisfy the same constraint:

const _setRowConstraints = (mutable, grid, col) => {
  const gMatrix = grid.get("matrix")
  const symbols = grid.get("symbols")
  // For each i
  for (let i=0; i<gMatrix.count(); i++) {
    // and every v that needs to be in the i
    symbols.forEach(v => {
      for (let j=0; j<gMatrix.count(); j++) {
        // Mark the current col at the row that represents [i,j,v]
        const row = exactCover.getRowIndex(i, j, v, grid)
        mutable.setIn([row, col], 1)
      }
      // Go to next col after every row that satisfies 
      // the same constraint has been marked
      col++
    })
  }
},

In Column Constraints, where there are also 81 columns (nj * nv), and every i will satisfy the same constraint:

const _setColConstraints = (mutable, grid, col) => {
    const gMatrix = grid.get("matrix")
    const symbols = grid.get("symbols")
    // For each j
    for (let j=0; j<gMatrix.count(); j++) {
      // and every v that needs to be in the j
      symbols.forEach(v => {
        for (let i=0; i<gMatrix.count(); i++) {
          // Mark the current col at the row that represents [i,j,v]
          const row = exactCover.getRowIndex(i, j, v, grid)
          mutable.setIn([row, col], 1)
        }
        // Go to next col after every row that satisfies 
        // the same constraint has been marked
        col++
      })
    }
  }

While seemingly more complicated, the Block Constraints also follow the same logic. There are 9 blocks in the grid, and each block must contain 9 values resulting in 81 columns. The goal of the code is to mark all cells [i,j] that are part of the same block and have the same v.

const _setBlockConstraints = (mutable, grid, col) => {
  const gMatrix = grid.get("matrix")
  const symbols = grid.get("symbols")
  const blockLen = fnGrid.getBlockLen(grid) // block per row or col
  // For every block in the grid
  for (let iOffset=0; iOffset<gMatrix.count(); iOffset+=blockLen) {
    for (let jOffset=0; jOffset<gMatrix.count(); jOffset+=blockLen) {
      // and every value that needs to be in each block
      symbols.forEach(v => {
        // For every grid[i,j] in the block
        for (let i = 0; i < blockLen; i++) {
          for (let j = 0; j < blockLen; j++) {
              // Mark the current col at the row that represents [i,j,v]
              const row = exactCover.getRowIndex(iOffset+i, jOffset+j, v, grid)
              mutable.setIn([row, col], 1)
            }
          }
        // Go to next col after every row that satisfies 
        // the same constraint has been marked
        col++
      })
    }
  }
}

To simplify the code, it should basically be this:

For every block in the grid:
  For every possible value:
    Mark the same constraint column for every cell in the block
    Go to next constraint column

Bringing It All Together

Using what we have, we can finally get our desired exact cover matrix:

const cellConStartCol = 0
const rowConStartCol = nCellConCols
const colConStartCol = nCellConCols + nRowConCols
const blockConStartCol = nCellConCols + nRowConCols + nColConCols

return fnMatrix.mkFill(nRows, nCellConCols + nRowConCols + nColConCols + nBlockConCols, 0)
  .withMutations(mutable => {
    exactCover._setCellConstraints(mutable, grid, cellConStartCol)
    exactCover._setRowConstraints(mutable, grid, rowConStartCol)
    exactCover._setColConstraints(mutable, grid, colConStartCol)
    exactCover._setBlockConstraints(mutable, grid, blockConStartCol)
  })

fnMatrix.mkFill() is just a simple helper function that makes a 2D matrix of a specified size and fills it with a specified value. You may have noticed that all our _setXConstraints() functions took an extra col argument, this allows us to specify the column index each function should begin at.

Conclusion

Now I can actually try out Algorithm X (Without Dancing Links). This took way too long to figure out. If you actually understood my borderline incoherent ramblings, good job. I'm going to go pass out now.

So Tired