Sanjul - Profile SanjulAll Blogs
Switch off light

Let's make a sudoku solver - Part 1 - Representation & Validation

October 02, 2021

In this brief article, we’ll set the stage for a Sudoku Solver program using Dart.

To quote from Wikipedia:

A standard Sudoku contains 81 cells, in a 9×9 grid, and has 9 boxes, each box being the intersection of the first, middle, or last 3 rows, and the first, middle, or last 3 columns. Each cell may contain a number from one to nine, and each number can only occur once in each row, column, and box. A Sudoku starts with some cells containing numbers (clues), and the goal is to solve the remaining cells.

Let’s assemble the parts together like little legos

1. Representation

A standard sudoku puzzle is the one with a 9 x 9 grid with only valid digits 1 to 9 that can be filled in the cells. For example, let’s look at a typical sudoku puzzle:

537619598686348317266284195879

One easy way to represent this puzzle in the code is using a two dimensional array ( just a fancy array of arrays ). We can use 0 to represent the empty cell since it’s not a valid digit.

// Simple two dimensional array representation
// of above sudoku puzzle
// let's put it in a variable `board`


var board = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9],
];

2. Validation

Before we actually go about building a solution. It might help to understand what qualifies as a correct solution.

Let’s explore if the sudoku puzzle that we’re going to deal with is actually valid to begin with. Also, once we figured the ‘algorithm’ to solve the puzzle, it’ll be important that we have way to determine if the puzzle is really solved.

1. To verify if a puzzle is VALID

We can perform following checks to verify if a given sudoku puzzle is valid.

  1. Check all columns and verify no repeated digits:

    537619598686348317266284195879

  2. Check all rows and verify no repeated digits

    537619598686348317266284195879

  3. Verify all the 3x3 grids ( Let’s call it a ‘Box’) and make sure no digits are repeated within these boxes.

    537619598686348317266284195879

We may simplify the above validations by looking at it from the perspective of a single cell. We’re NOT really trying to optimize, but this way, it will be easier to wrap our heads around it!

Let’s dig into some code.

First of all, let’s start by declaring some useful constants:

// size of the sudoku puzzle ( Since it's a standard puzzle it's 9)
const int SIZE = 9;


// size of the internal grid ('Box') (we have a 3x3 grid, it'll be 3)
const int BOXSIZE = 3;

Now, let’s write a function to check for a given cell in sudoku ( specified using row and column index of our two dimensional array with the name board) is valid according to above validations :

/// A function to verify if the value at given
/// row and column is valid
/// will return `true` if valid, otherwise `false`
bool checkIfCellIsValid(int row, int col) {


  int val = board[row][col]; // get the digit at given row and column




  if(val != 0){ // do the below checks if it's not empty cell


    // SECTION 1 :  check if cell is unique in Row
    if(!isUniqueInRow(row, col, val)){
      return false;
    }


    // SECTION 2: check if cell is unique in Column
    if(!isUniqueInColumn(row, col, val)){
      return false;
    }


    // SECTION 3: check if cell is unique in Box
    if(!isUniqueInBox(row, col, val)){
      return false;
    }
  }


  // if none of the above checks has returned `false` so far,
  // It has to be valid, so return true
  return true;


}

Now, let’s try implementing each sections.

  • SECTION 1: check if the val is unique in a given ROW :

    bool isUniqueInRow(int row, int col, int val){
      // check val is unique in given ROW
      // by going through all columns in that row
      for (int c = 0; c < SIZE; c++) {
    

        if (c == col) continue; // don't compare with itself
    

        int _otherCellVal = board[row][c];
        if (_otherCellVal != 0 && _otherCellVal == val) {
          return false;
        }
      }
    

      return true;
    

    }

  • SECTION 2: check if the val is unique in a given COLUMN

    bool isUniqueInColumn(int row, int col, int val){
    

      // check val is uniuqe in given COLUMN
      // by going through all rows in that column
      for (int r = 0; r < SIZE; r++) {
        if (r == row) continue; // don't compare with itself
    

        int _otherCellVal = board[r][col];
        if (_otherCellVal != 0 && _otherCellVal == val) {
          return false;
        }
      }
      return true;
    }

  • SECTION 3: check if the val is unique in a given ‘Box’

    bool isUniqueInBox(int row, int col, int val){
    

    int bxRowStart = row - row % BOXSIZE;
    int bxColStart = col - col % BOXSIZE;
    

    // check if val is unique in BOX
    // by going through all rows and columns in the
    // given 'BOX'
    for (int r = bxRowStart; r < bxRowStart + BOXSIZE; r++) {
      for (int c = bxColStart; c < bxColStart + BOXSIZE; c++) {
        if (r == row && c == col) continue; // don't compare with itself
    

        int _otherCellVal = board[r][c];
        if (_otherCellVal != 0 && _otherCellVal == val) {
          return false;
        }
      }
    }
    

    return true;
    }

2. Verify if the puzzle is SOLVED

It’ll be very useful to know if the puzzle is solved already, and done so correctly.

Now that we know how to check if the cells in a sudoku puzzle are valid, verifying if the puzzle is solved is much simpler:

  1. Use the above steps to verify if the puzzle is valid ( Ie, all the cells are valid)
  2. Make sure no empty cells left (that is, no more zeroes in our 2D array)

The code for which would look something like this :

bool isSolved(){


  // go through all the cells in the puzzle
  for(int r = 0; r < SIZE; r++){
    for(int c = 0; c < SIZE; c++){


      int val = board[r][c];


      if(val == 0){
        // found an empty cell,
        // so it's not solved
        return false;
      }


      if(!checkIfCellIsValid(r,c)){
        // found an invalid cell
        // so it's not solved
        return false;
      }
    }
  }


  // no empty cells left and
  // all cells are valid, so puzzle is solved
  return true;
}

That’s it for the first part of this series!

In next one, we’ll explore how we can come up with an ‘algorithm’ to actually solve the puzzle!

See you in the next one!

        
© 2021, Sanjul