JS Tips #8: How To Validate Sudoku Solutions

The today’s problem is interesting because I have always wanted to understand how to solve it. We are in the field of JavaScript (obviously), of two-dimensional arrays and games. In simple terms, given a grid of numbers, we have to verify that each row, each column, and each block of 3x3 contains all the numbers from 1 to 9. It follows that there cannot be any repeated numbers and no different numbers. And since there are a myriad of possible combinations, we must necessarily solve the problem by using a fast algorithm. But before moving on to the solution, let’s see the problem.

The Problem: Sudoku Solution Validator

link to the kata

Sudoku Background

Sudoku is a game played on a 9x9 grid. The goal of the game is to fill all cells of the grid with digits from 1 to 9, so that each column, each row, and each of the nine 3x3 sub-grids (also known as blocks) contain all of the digits from 1 to 9. (More info at: Wikipedia - Sudoku)

Sudoku Solution Validator

Write a function validSolution() that accepts a 2D array representing a Sudoku board, and returns true if it is a valid solution, or false otherwise. The cells of the sudoku board may also contain 0’s, which will represent empty cells. Boards containing one or more zeroes are considered to be invalid solutions.

The board is always 9 cells by 9 cells, and every cell only contains integers from 0 to 9.

Examples

validSolution([
  [5, 3, 4, 6, 7, 8, 9, 1, 2],
  [6, 7, 2, 1, 9, 5, 3, 4, 8],
  [1, 9, 8, 3, 4, 2, 5, 6, 7],
  [8, 5, 9, 7, 6, 1, 4, 2, 3],
  [4, 2, 6, 8, 5, 3, 7, 9, 1],
  [7, 1, 3, 9, 2, 4, 8, 5, 6],
  [9, 6, 1, 5, 3, 7, 2, 8, 4],
  [2, 8, 7, 4, 1, 9, 6, 3, 5],
  [3, 4, 5, 2, 8, 6, 1, 7, 9],
]); // => true

validSolution([
  [5, 3, 4, 6, 7, 8, 9, 1, 2],
  [6, 7, 2, 1, 9, 0, 3, 4, 8],
  [1, 0, 0, 3, 4, 2, 5, 6, 0],
  [8, 5, 9, 7, 6, 1, 0, 2, 0],
  [4, 2, 6, 8, 5, 3, 7, 9, 1],
  [7, 1, 3, 9, 2, 4, 8, 5, 6],
  [9, 0, 1, 5, 3, 7, 2, 1, 4],
  [2, 8, 7, 4, 1, 9, 6, 3, 5],
  [3, 0, 0, 4, 8, 1, 1, 7, 9],
]); // => false

The Solution

I’m starting by immediately presenting my solution. It’s not one of the smartest on CodeWars, but I think it’s easy enough to understand.

const checkSum = (arr) => arr.reduce((r, x) => r + x, 0) === 45;
const checkZero = (arr) => arr.every((x) => x > 0);
const validateRow = (arr) => checkZero(arr) && checkSum(arr);

const rotate = (arr) => arr[0].map((_, i) => arr.map((_, j) => arr[j][i]));
const divide = (arr) =>
  arr.map((x) => [x.slice(0, 3), x.slice(3, 6), x.slice(6, 9)]);
const blocks = (arr) => divide(rotate(divide(arr))).flat();

const listSolutions = (arr) => [...arr, ...rotate(arr), ...blocks(arr)];

const validSolution = (board) =>
  listSolutions(board).every((x) => validateRow(x.flat()));

I’ve already said it before; I think it’s better to have a slightly longer solution that’s easy to read, compared to a short but cryptic one. After all, we might have to touch the code again in the future: it’s better to avoid leaving ourselves with a mystery to solve.

But let’s move on to the algorithm that we need.

First of all, we need a check function. We have two conditions to verify:

1. each section of the Sudoku must not have the number 0;
2. each section must have all the numbers from 1 to 9;

To check for the presence of zero, we can use the Array.includes() method:

const checkZero = (arr) => !arr.includes(0);

To check for the presence of all numbers, we have two options. We can create a new array and remove the duplicates (using Set()): if the new array contains 9 elements then we have 9 different numbers. Or we can simply check if the sum of all the elements in the array is equal to the sum of the numbers from 1 to 9. That is 45.

const checkSum = (arr) => arr.reduce((r, x) => r + x, 0) === 45;

The next step is understanding what are the sections of the Sudoku that we need to check.

Of course, I must check all the rows of the original schema:

const listSolutions = (arr) => [...arr];

Then I need the columns of the matrix. I can get them by rotating the matrix itself by 90 degrees. This way the columns become arrays in themselves:

const rotate = (arr) => arr[0].map((_, i) => arr.map((_, j) => arr[j][i]));
const listSolutions = (arr) => [...arr, ...rotate(arr)];

Finding the different quadrants of the Sudoku requires a different thinking. This problem can also be solved in different ways. We can create a loop:

const blocks = (arr) =>
  arr.map((_, x) =>
    arr.map((_, y) => arr[~~(x / 3) * 3 + ~~(y / 3)][(x % 3) * 3 + (y % 3)])
  );

Or we can take it one step at a time.

Since I know that each quadrant is composed of 3 rows of 3 elements each, we can make this type of reasoning. I divide each row of the array into 3 parts. Then I rotate the entire schema. And I find myself with three different arrays on each row. By merging them, I get 9 rows again, but each row contains a block of 3x3 elements. But it’s easier to put things in JavaScript:

const rotate = (arr) => arr[0].map((_, i) => arr.map((_, j) => arr[j][i]));

const divide = (arr) =>
  arr.map((x) => [x.slice(0, 3), x.slice(3, 6), x.slice(6, 9)]);

const blocks = (arr) => {
  const a = divide(arr);
  const b = rotate(a);
  const c = divide(b);
  const d = c.map((x) => x.map((y) => y.flat())).flat();
  return d;
};

Now, finally, I have all the rows to check:

const listSolutions = (arr) => [...arr, ...rotate(arr), ...blocks(arr)];

By combining the various pieces, I finally obtain a solution for the problem:

const checkZero = (arr) => !arr.includes(0);
const checkSum = (arr) => arr.reduce((r, x) => r + x, 0) === 45;

const rotate = (arr) => arr[0].map((_, i) => arr.map((_, j) => arr[j][i]));

const divide = (arr) =>
  arr.map((x) => [x.slice(0, 3), x.slice(3, 6), x.slice(6, 9)]);

const blocks = (arr) => {
  const a = divide(arr);
  const b = rotate(a);
  const c = divide(b);
  const d = c.map((x) => x.map((y) => y.flat())).flat();
  return d;
};

const listSolutions = (arr) => [...arr, ...rotate(arr), ...blocks(arr)];

const validSolution = (board) => {
  const list = listSolutions(board);
  const result = list.map((x) => checkZero(x) && checkSum(x));

  return !result.includes(false);
};

But it’s still not a good solution. Or, better, I can simplify the code a bit. First, I rewrite the blocks function so as to eliminate the variables:

const blocks = (arr) =>
  divide(rotate(divide(arr)))
    .map((x) => x.map((y) => y.flat()))
    .flat();

I can also simplify validSolution:

const validSolution = (board) =>
  !listSolutions(board)
    .map((x) => checkZero(x) && checkSum(x))
    .includes(false);

However, if I look at the code closely, I realize two things. The first: I’m not taking into account the presence of any negative numbers. I can rewrite checkZero like this:

const checkZero = (arr) => arr.every((x) => x > 0);

Or like

const checkZero = (arr) => arr.every((x) => x > 0 && x <= 9);

In this way, I use the Array.every() method to verify that every element present in the array is between 1 and 9.

The second thing is that I can use Array.every also to check the different solutions simplifying the code even more :

const validSolution = (board) =>
  listSolutions(board).every((x) => checkZero(x) && checkSum(x));

In this way, we don’t need an additional .map().includes(false) and this also directly returns true or false based on the check of all solutions using Array.every method.

const checkSum = (arr) => arr.reduce((r, x) => r + x, 0) === 45;
const checkZero = (arr) => arr.every((x) => x > 0 && x <= 9);
const validateRow = (arr) => checkZero(arr) && checkSum(arr);

const rotate = (arr) => arr[0].map((_, i) => arr.map((_, j) => arr[j][i]));
const divide = (arr) =>
  arr.map((x) => [x.slice(0, 3), x.slice(3, 6), x.slice(6, 9)]);
const blocks = (arr) => divide(rotate(divide(arr))).flat();

const listSolutions = (arr) => [...arr, ...rotate(arr), ...blocks(arr)];

const validSolution = (board) =>
  listSolutions(board).every((x) => validateRow(x.flat()));

If we want, we can also modify the blocks function (using the double bitwise NOT (~) operator) and eliminate the divide function.

const checkSum = (arr) => arr.reduce((r, x) => r + x, 0) === 45;
const checkZero = (arr) => arr.every((x) => x > 0 && x <= 9);
const validateRow = (arr) => checkZero(arr) && checkSum(arr);

const rotate = (arr) => arr[0].map((_, i) => arr.map((_, j) => arr[j][i]));

const blocks = (arr) =>
  arr.map((_, x) =>
    arr.map((_, y) => arr[~~(x / 3) * 3 + ~~(y / 3)][(x % 3) * 3 + (y % 3)])
  );

const listSolutions = (arr) => [...arr, ...rotate(arr), ...blocks(arr)];

const validSolution = (board) =>
  listSolutions(board).every((x) => validateRow(x.flat()));

Finally, I can write an even more compact solution:

const validSolution = (board) =>
  [
    ...board,
    ...board[0].map((_, i) => board.map((_, j) => board[j][i])),
    ...board.map((_, x) =>
      board.map(
        (_, y) => board[~~(x / 3) * 3 + ~~(y / 3)][(x % 3) * 3 + (y % 3)]
      )
    ),
  ].every(
    (a) =>
      a.flat().reduce((x, y) => x + y, 0) === 45 &&
      a.flat().every((x) => x > 0 && x <= 9)
  );

But, as I said before, perhaps this solution is a bit too cryptic. In any case, it is a valid and functioning solution.