Sudoku Part I: Is the Board Valid?

Today's algorithm is the Valid Sudoku problem:

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

• Each row must contain the digits 1-9 without repetition.
• Each column must contain the digits 1-9 without repetition.
• Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition. The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

For example, let's say you were given this Sudoku board

As a two dimensional array, the input would be

  [
    ["5", "3", ".", ".", "7", ".", ".", ".", "."],
    ["6", ".", ".", "1", "9", "5", ".", ".", "."],
    [".", "9", "8", ".", ".", ".", ".", "6", "."],
    ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
    ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
    ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
    [".", "6", ".", ".", ".", ".", "2", "8", "."],
    [".", ".", ".", "4", "1", "9", ".", ".", "5"],
    [".", ".", ".", ".", "8", ".", ".", "7", "9"],
  ]

where each empty square is represented with a ".". We want to write a function which checks if this board is valid. By that, we want to be sure that there are no repeats of the numbers 1-9 in each column, row, and 3x3 square.

Whether you've never seen a Sudoku board before, or you love the game as much as I do, this is a fun algorithm because there are many ways to think about how to break up a 9x9 board. In this post, I'll be going over one way to approach this problem: by building a hash to store unique values.

Approaching the Valid Sudoku Problem

What's particularly tricky about this problem is you need a way to keep track of which values you've seen in the row, column, and squares that you're currently in. Since it's a 2D array, you could quickly check one row at a time to see if the values are unique (since each row is its own array), but that would still leave the problem of the columns and squares.

There's a few ways to deal with this, such as by creating a new set for each row and column, but in my solution I'll be making a hash, which stores unique values as they're seen, and will return false if a non-unique value is found. Using nested for loops, at each box we'll check the store to see if the box's the current row, current column, and current square already contain that box's value. If not, we can move on to check the next box.

Coding the Solution

We'll start the problem by creating a hash that'll store the values for each row, column, and square. What I mean by this is, working with the same Sudoku board as above, by the end of the problem, we'd want store to look like this:

{
  rows: {
    '0': [ '5', '3', '7' ],
    '1': [ '6', '1', '9', '5' ],
    '2': [ '9', '8', '6' ],
    '3': [ '8', '6', '3' ],
    '4': [ '4', '8', '3', '1' ],
    '5': [ '7', '2', '6' ],
    '6': [ '6', '2', '8' ],
    '7': [ '4', '1', '9', '5' ],
    '8': [ '8', '7', '9' ]
  },
  cols: {
    '0': [ '5', '6', '8', '4', '7' ],
    '1': [ '3', '9', '6' ],
    '2': [ '8' ],
    '3': [ '1', '8', '4' ],
    '4': [ '7', '9', '6', '2', '1', '8' ],
    '5': [ '5', '3', '9' ],
    '6': [ '2' ],
    '7': [ '6', '8', '7' ],
    '8': [ '3', '1', '6', '5', '9' ]
  },
  square: {
    '1-1': [ '5', '3', '6', '9', '8' ],
    '1-2': [ '7', '1', '9', '5' ],
    '1-3': [ '6' ],
    '2-1': [ '8', '4', '7' ],
    '2-2': [ '6', '8', '3', '2' ],
    '2-3': [ '3', '1', '6' ],
    '3-1': [ '6' ],
    '3-3': [ '2', '8', '5', '7', '9' ],
    '3-2': [ '4', '1', '9', '8' ]
  }
}

So, we can start by making the hash, and calling it store.

function isValidSudoku(board) {
  let store = {
    rows: {},
    cols: {},
    square: {},
  };
  //...
}

Now, in order to check each box, we should make nested for loops. The first for loop will have i go from 0 to 9, and will represent the current row we're checking. The second for loop will have j go from 0 to 9, and will represent the current column we're checking. Inside these for loops, we can also create a new variable called box, which will be the value of the current box we're on.

function isValidSudoku(board) {
  let store = {
    rows: {},
    cols: {},
    square: {},
  };
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const box = board[i][j];

      //...
    }
  }
  //...
}

We can start by checking the rows. We'll first want to check if the store already has a key for the row we're currently on. If it doesn't have the current row as a key, and if the value of the box is not ".", then we can instantiate an array representing the unique values in the row, and push the box to that array.

function isValidSudoku(board) {
  let store = {
    rows: {},
    cols: {},
    square: {},
  };
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const box = board[i][j];

      if (!store["rows"][i] && box !== ".") {
        store["rows"][i] = [];
        store["rows"][i].push(box);
      } 
      //...
      }
    }
  }
  //...
}

Now, if the rows in the store does already contain the row we're on, we should check if the array value at the row key has the box we're currently checking. If it doesn't have the box, we'll want to add it to the array.

function isValidSudoku(board) {
  let store = {
    rows: {},
    cols: {},
    square: {},
  };
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const box = board[i][j];

      if (!store["rows"][i] && box !== ".") {
        store["rows"][i] = [];
        store["rows"][i].push(box);
      } else if (box !== "." && !store["rows"][i].includes(box)) {
        store["rows"][i].push(box);
      } 
        //...
      }
    }
  }
  //...
}

Otherwise, if that value already is in the array, then we know there's been a repeated number, and it's not a valid Sudoku board. So, we can just return false.

function isValidSudoku(board) {
  let store = {
    rows: {},
    cols: {},
    square: {},
  };
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const box = board[i][j];

      if (!store["rows"][i] && box !== ".") {
        store["rows"][i] = [];
        store["rows"][i].push(box);
      } else if (box !== "." && !store["rows"][i].includes(box)) {
        store["rows"][i].push(box);
      } else if (store["rows"][i] && store["rows"][i].includes(box)) {
        return false;
      }

      //...
    }
  }
  //...
}

At this point in the code, with the same Sudoku board that we started with, this is what store looks like:

{
  rows: {
    '0': [ '5', '3', '7' ],
    '1': [ '6', '1', '9', '5' ],
    '2': [ '9', '8', '6' ],
    '3': [ '8', '6', '3' ],
    '4': [ '4', '8', '3', '1' ],
    '5': [ '7', '2', '6' ],
    '6': [ '6', '2', '8' ],
    '7': [ '4', '1', '9', '5' ],
    '8': [ '8', '7', '9' ]
  },
  cols: {},
  square: {}
}

Now we'll want to move onto the columns. The way we'll approach checking each column is very similar to how we checked each row. We'll start by checking if cols in store already has seen that column, and if the box's value is not blank. If that's the case, we'll initialize an empty array as the value for that column's key, and push to box to the array.

function isValidSudoku(board) {
  let store = {
    rows: {},
    cols: {},
    square: {},
  };
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const box = board[i][j];

      if (!store["rows"][i] && box !== ".") {
        store["rows"][i] = [];
        store["rows"][i].push(box);
      } else if (box !== "." && !store["rows"][i].includes(box)) {
        store["rows"][i].push(box);
      } else if (store["rows"][i] && store["rows"][i].includes(box)) {
        return false;
      }

      if (!store["cols"][j] && box !== ".") {
        store["cols"][j] = [];
        store["cols"][j].push(box);
      } 
      //...
    }
  }
  //...
}

If that column already is a key in the store, and the value array does not include the box we're currently on, then we can add the box to the array. Otherwise, if the box we're currently on has already been seen, then we know it's not a valid Sudoku, and we can return false.

function isValidSudoku(board) {
  let store = {
    rows: {},
    cols: {},
    square: {},
  };
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const box = board[i][j];

      if (!store["rows"][i] && box !== ".") {
        store["rows"][i] = [];
        store["rows"][i].push(box);
      } else if (box !== "." && !store["rows"][i].includes(box)) {
        store["rows"][i].push(box);
      } else if (store["rows"][i] && store["rows"][i].includes(box)) {
        return false;
      }

      if (!store["cols"][j] && box !== ".") {
        store["cols"][j] = [];
        store["cols"][j].push(box);
      } else if (box !== "." && !store["cols"][j].includes(box)) {
        store["cols"][j].push(box);
      } else if (store["cols"][j] && store["cols"][j].includes(box)) {
        return false;
      }

      //...
    }
  }
  //...
}

At this point in our solution, and using the same Sudoku board as before, the store would look like this:

{
  rows: {
    '0': [ '5', '3', '7' ],
    '1': [ '6', '1', '9', '5' ],
    '2': [ '9', '8', '6' ],
    '3': [ '8', '6', '3' ],
    '4': [ '4', '8', '3', '1' ],
    '5': [ '7', '2', '6' ],
    '6': [ '6', '2', '8' ],
    '7': [ '4', '1', '9', '5' ],
    '8': [ '8', '7', '9' ]
  },
  cols: {
    '0': [ '5', '6', '8', '4', '7' ],
    '1': [ '3', '9', '6' ],
    '2': [ '8' ],
    '3': [ '1', '8', '4' ],
    '4': [ '7', '9', '6', '2', '1', '8' ],
    '5': [ '5', '3', '9' ],
    '6': [ '2' ],
    '7': [ '6', '8', '7' ],
    '8': [ '3', '1', '6', '5', '9' ]
  },
  square: {}
}

Now we're onto the squares, and this is where it gets super tricky. What we need to do is keep track of each square, and therefore each value in that square, and so we need a way to identify which square we're on.

A Sudoku board has nine "squares":

There are a few ways we could label each square, but I decided to see the board as having three square rows and three square columns. Therefore, each 3x3 square could be called "squareRowId"-"squareColumnId":

In our code, therefore, we'd want to create variables for squareRowId and squareColId, and then use string interpolation to get the name of each squareId. I used Math.ceil() and added 1 to the current row and column before dividing by 3, in order to make three rows and three columns, each numbered from 1 to 3.

function isValidSudoku(board) {
  let store = {
    rows: {},
    cols: {},
    square: {},
  };
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const box = board[i][j];

      if (!store["rows"][i] && box !== ".") {
        store["rows"][i] = [];
        store["rows"][i].push(box);
      } else if (box !== "." && !store["rows"][i].includes(box)) {
        store["rows"][i].push(box);
      } else if (store["rows"][i] && store["rows"][i].includes(box)) {
        return false;
      }

      if (!store["cols"][j] && box !== ".") {
        store["cols"][j] = [];
        store["cols"][j].push(box);
      } else if (box !== "." && !store["cols"][j].includes(box)) {
        store["cols"][j].push(box);
      } else if (store["cols"][j] && store["cols"][j].includes(box)) {
        return false;
      }

      const squareRowId = Math.ceil((i + 1) / 3);
      const squareColId = Math.ceil((j + 1) / 3);
      const squareId = `${squareRowId}-${squareColId}`;

      //...
    }
  }
  //...
}

Now, the logic at this point is the same as with the rows and columns. If square in the store has not already seen that square id, and the current box is not blank, then we should initiate a new key-value pair for that square id, pushing the box to the array value. If square does have that square id, but the box's value is not already in it, we should push the box to the array. Finally, if the box has already been seen in the square, we can return false.

function isValidSudoku(board) {
  let store = {
    rows: {},
    cols: {},
    square: {},
  };
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const box = board[i][j];

      if (!store["rows"][i] && box !== ".") {
        store["rows"][i] = [];
        store["rows"][i].push(box);
      } else if (box !== "." && !store["rows"][i].includes(box)) {
        store["rows"][i].push(box);
      } else if (store["rows"][i] && store["rows"][i].includes(box)) {
        return false;
      }

      if (!store["cols"][j] && box !== ".") {
        store["cols"][j] = [];
        store["cols"][j].push(box);
      } else if (box !== "." && !store["cols"][j].includes(box)) {
        store["cols"][j].push(box);
      } else if (store["cols"][j] && store["cols"][j].includes(box)) {
        return false;
      }

      const squareRowId = Math.ceil((i + 1) / 3);
      const squareColId = Math.ceil((j + 1) / 3);
      const squareId = `${squareRowId}-${squareColId}`;

      if (!store["square"][squareId] && box !== ".") {
        store["square"][squareId] = [];
        store["square"][squareId].push(box);
      } else if (box !== "." && !store["square"][squareId].includes(box)) {
        store["square"][squareId].push(box);
      } else if (
        store["square"][squareId] &&
        store["square"][squareId].includes(box)
      ) {
        return false;
      }
    }
  }
  //...
}

If, after all of these checks, false has never been returned, then we can return true, giving us the final code for this solution:

function isValidSudoku(board) {
  let store = {
    rows: {},
    cols: {},
    square: {},
  };
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const box = board[i][j];

      if (!store["rows"][i] && box !== ".") {
        store["rows"][i] = [];
        store["rows"][i].push(box);
      } else if (box !== "." && !store["rows"][i].includes(box)) {
        store["rows"][i].push(box);
      } else if (store["rows"][i] && store["rows"][i].includes(box)) {
        return false;
      }

      if (!store["cols"][j] && box !== ".") {
        store["cols"][j] = [];
        store["cols"][j].push(box);
      } else if (box !== "." && !store["cols"][j].includes(box)) {
        store["cols"][j].push(box);
      } else if (store["cols"][j] && store["cols"][j].includes(box)) {
        return false;
      }

      const squareRowId = Math.ceil((i + 1) / 3);
      const squareColId = Math.ceil((j + 1) / 3);
      const squareId = `${squareRowId}-${squareColId}`;

      if (!store["square"][squareId] && box !== ".") {
        store["square"][squareId] = [];
        store["square"][squareId].push(box);
      } else if (box !== "." && !store["square"][squareId].includes(box)) {
        store["square"][squareId].push(box);
      } else if (
        store["square"][squareId] &&
        store["square"][squareId].includes(box)
      ) {
        return false;
      }
    }
  }
  return true;
}

--

Please let me know you have any questions or comments about checking for a valid Sudoku board!