Finding the block using row and column indices - Sudoku Scala

Finding the Sudoku Block Using Row and Column Indices in Scala

Learn how to programmatically determine the 3x3 block a cell belongs to in a Sudoku grid using its row and column indices in Scala.

In Sudoku, the 9x9 grid is divided into nine 3x3 subgrids, often referred to as 'blocks' or 'boxes'. When developing a Sudoku solver or validator, a common requirement is to identify which of these nine blocks a given cell (specified by its row and column indices) belongs to. This article will guide you through a simple and efficient method to achieve this in Scala, providing clear explanations and a practical code example.

Understanding Sudoku Block Structure

A standard 9x9 Sudoku grid has rows and columns indexed from 0 to 8 (or 1 to 9, depending on convention). The nine 3x3 blocks are also typically indexed, often from 0 to 8, starting from the top-left block and proceeding row by row. For instance, the top-left block might be block 0, the top-middle block block 1, and so on, down to the bottom-right block which would be block 8.

graph TD
    subgraph Sudoku Grid (9x9)
        A["Cell (row, col)"]
    end

    subgraph Block Calculation
        R["Row Index (0-8)"]
        C["Column Index (0-8)"]
        R --> R_DIV_3{"row / 3"}
        C --> C_DIV_3{"col / 3"}
        R_DIV_3 --> R_BLOCK["Row Block Index (0-2)"]
        C_DIV_3 --> C_BLOCK["Col Block Index (0-2)"]
        R_BLOCK --> BLOCK_NUM["Block Number = (Row Block Index * 3) + Col Block Index"]
        C_BLOCK --> BLOCK_NUM
    end

    A --> R
    A --> C
    BLOCK_NUM --> B["Determined Block (0-8)"]

Flowchart illustrating the logic to determine a Sudoku block number from row and column indices.

The Calculation Logic

The key to finding the block index lies in integer division. Since each block is 3x3, dividing the row index by 3 will tell us which 'row of blocks' the cell is in (0, 1, or 2). Similarly, dividing the column index by 3 will tell us which 'column of blocks' the cell is in (0, 1, or 2).

Let's denote:

• row: The 0-indexed row of the cell (0-8)
• col: The 0-indexed column of the cell (0-8)

1. Determine the block's row position: blockRow = row / 3 (integer division)
2. Determine the block's column position: blockCol = col / 3 (integer division)

These blockRow and blockCol values will range from 0 to 2. To get a single block index (0-8), we can use the formula:

blockIndex = (blockRow * 3) + blockCol

This formula effectively flattens the 3x3 grid of blocks into a single 0-indexed sequence.

object SudokuUtils {

  /**
   * Calculates the 0-indexed block number (0-8) for a given cell in a Sudoku grid.
   *
   * @param row The 0-indexed row of the cell (0-8).
   * @param col The 0-indexed column of the cell (0-8).
   * @return The 0-indexed block number (0-8).
   * @throws IllegalArgumentException if row or col are outside the 0-8 range.
   */
  def getBlockIndex(row: Int, col: Int): Int = {
    require(row >= 0 && row <= 8, s"Row index must be between 0 and 8, but got $row")
    require(col >= 0 && col <= 8, s"Column index must be between 0 and 8, but got $col")

    val blockRow = row / 3 // Integer division
    val blockCol = col / 3 // Integer division

    (blockRow * 3) + blockCol
  }

  def main(args: Array[String]): Unit = {
    // Test cases
    println(s"Cell (0,0) is in block: ${getBlockIndex(0, 0)}") // Expected: 0
    println(s"Cell (0,3) is in block: ${getBlockIndex(0, 3)}") // Expected: 1
    println(s"Cell (2,8) is in block: ${getBlockIndex(2, 8)}") // Expected: 2
    println(s"Cell (3,0) is in block: ${getBlockIndex(3, 0)}") // Expected: 3
    println(s"Cell (4,4) is in block: ${getBlockIndex(4, 4)}") // Expected: 4
    println(s"Cell (8,8) is in block: ${getBlockIndex(8, 8)}") // Expected: 8

    // Example of invalid input
    try {
      getBlockIndex(9, 0)
    } catch {
      case e: IllegalArgumentException => println(s"Error: ${e.getMessage}")
    }
  }
}

Scala function to calculate the Sudoku block index and example usage.

Example Walkthrough

Let's trace an example: finding the block for cell (row=4, col=5).

1. blockRow = 4 / 3 = 1 (integer division)
2. blockCol = 5 / 3 = 1 (integer division)
3. blockIndex = (1 * 3) + 1 = 3 + 1 = 4

So, the cell at (4,5) belongs to block 4. If you visualize a Sudoku grid, block 4 is indeed the center 3x3 block.