Sudoku validator in TypeScript - create and validate a sudoku game

Sudoku is a popular logic puzzle game that involves filling a 9x9 grid with digits from 1 to 9, such that each row, column, and 3x3 subgrid contains each digit exactly once. In this article, we will explore how to implement a simple sudoku validator using TypeScript. And as a bonus, we will implement a sudoku generator for creating valid sudoku games.

Types

Let's start with setting up some basic types for our program. We will use a Board type, that will be a multi dimensional array with numbers ranging from 1-9.

Range type

Let's start with setting up our Range type that will limit the consumer to put in wrong numbers:

type Enumerate<
  N extends number,
  Acc extends number[] = []
> = Acc["length"] extends N
  ? Acc[number]
  : Enumerate<N, [...Acc, Acc["length"]]>;

type Range<F extends number, T extends number> = Exclude<
  Enumerate<T>,
  Enumerate<F>
>;

And then, we will create and export our Board type:

export type Board = Range<1, 10>[][];

The above type will restrict the user to only use numbers between 1-9, which saves us some time during our implementation. Gotta love TypeScript, right? 😎 Note: I will explain further down how this can be solved in JavaScript if you are using plain vanilla JS.

SudokuSolver

Let's create our SudokuSolver.ts file. We will start with checking the length of the board, so that each row and column contains the correct amount of cells.

const checkLengths = (board: Board): boolean => {
  let result = true;
  if (board.length !== 9) {
    return false;
  }
  board.forEach((row, rowIndex) => {
    if (row.length !== 9) {
      result = false;
    }
  });
  return result;
};

Then, let's setup a helper function for checking duplicates in our arrays. This will be used in our main function that will check each row for duplicates.

const hasDuplicates = (values: number[]) => {
  const set = new Set<number>();
  let hasDuplicates = false;
  values.forEach((value) => {
    if (value && value !== 0 && set.has(value)) {
      hasDuplicates = true;
    }
    set.add(value);
  });
  return hasDuplicates;
};

There we go. And now, we will check each row and column for duplicates. We will need to loop through all our rows, and then check each of the cells on the same horizontal and vertical line.

Let's implement our checkRows function:

const checkRows = (allRows: number[][]) => {
  let result = true;
  allRows.forEach((row) => {
    row.forEach((_, columnIndex) => {
      const vertical = allRows.map((row) => row[columnIndex]);
      if (hasDuplicates(vertical) || hasDuplicates(row)) {
        result = false;
      }
    });
  });
  return result;
};

And as a last check, we also need to check each of the nine cells in the grid. So let's create a function for checking the cells.

const checkCells = (board: Board) => {
  const cells = getCells(board);
  cells.forEach((cell) => {
    if (hasDuplicates(cell)) {
      throw new Error("Invalid board. Duplicates found in cell");
    }
  });
};

const getCells = (board: Board) => {
  const cells: number[][] = [];
  for (let i = 0; i < 9; i += 3) {
    for (let j = 0; j < 9; j += 3) {
      const cell = [];
      for (let k = i; k < i + 3; k++) {
        for (let l = j; l < j + 3; l++) {
          cell.push(board[k][l]);
        }
      }
      cells.push(cell);
    }
  }
  return cells;
};

Above function, is creating a new multi dimensional array which represents the nine 3*3 grids in the grid 🤯

And then, we will export our "main" function that will execute our functions:

export const checkBoard = (board: Board): boolean => {
  return checkLengths(board) && checkRows(board) && checkCells(board);
};

Full implementation of the SudokuChecker

import { Board } from "./types";

export const checkBoard = (board: Board): boolean => {
  return checkLengths(board) && checkRows(board) && checkCells(board);
};

const checkRows = (allRows: number[][]) => {
  let result = true;
  allRows.forEach((row) => {
    row.forEach((_, columnIndex) => {
      const vertical = allRows.map((row) => row[columnIndex]);
      if (hasDuplicates(vertical) || hasDuplicates(row)) {
        result = false;
      }
    });
  });
  return result;
};

const checkCells = (board: Board) => {
  let result = true;
  const cells = getCells(board);
  cells.forEach((cell) => {
    if (hasDuplicates(cell)) {
      result = false;
    }
  });
  return result;
};

const getCells = (board: Board) => {
  const cells: number[][] = [];
  for (let i = 0; i < 9; i += 3) {
    for (let j = 0; j < 9; j += 3) {
      const cell = [];
      for (let k = i; k < i + 3; k++) {
        for (let l = j; l < j + 3; l++) {
          cell.push(board[k][l]);
        }
      }
      cells.push(cell);
    }
  }
  return cells;
};

const hasDuplicates = (values: number[]) => {
  const set = new Set<number>();
  let hasDuplicates = false;
  values.forEach((value) => {
    if (value && value !== 0 && set.has(value)) {
      hasDuplicates = true;
    }
    set.add(value);
  });
  return hasDuplicates;
};

const checkLengths = (board: Board): boolean => {
  let result = true;
  if (board.length !== 9) {
    return false;
  }
  board.forEach((row, rowIndex) => {
    if (row.length !== 9) {
      result = false;
    }
  });
  return result;
};

Test the program

I found some examples on Sudoku boards that were both valid and invalid online, so let's setup a test file that we can use to run our program.

In boards.ts, we add following:

import { Board } from "./types";

const validBoard: Board = [
  [8, 3, 5, 4, 1, 6, 9, 2, 7],
  [2, 9, 6, 8, 5, 7, 4, 3, 1],
  [4, 1, 7, 2, 9, 3, 6, 5, 8],
  [5, 6, 9, 1, 3, 4, 7, 8, 2],
  [1, 2, 3, 6, 7, 8, 5, 4, 9],
  [7, 4, 8, 5, 2, 9, 1, 6, 3],
  [6, 5, 2, 7, 8, 1, 3, 9, 4],
  [9, 8, 1, 3, 4, 5, 2, 7, 6],
  [3, 7, 4, 9, 6, 2, 8, 1, 5],
];

const invalidBoard1: Board = [
  [8, 3, 5, 4, 1, 6, 9, 2, 7],
  [2, 9, 6, 8, 5, 7, 4, 3, 1],
  [4, 1, 7, 2, 9, 3, 6, 5, 8],
  [5, 6, 9, 1, 3, 4, 7, 8, 2],
  [1, 2, 3, 6, 7, 8, 5, 4, 9],
  [7, 4, 8, 5, 2, 9, 1, 6, 3],
  [6, 9, 2, 7, 8, 1, 3, 5, 4], // Wrong in this row
  [9, 8, 1, 3, 4, 5, 2, 7, 6],
  [3, 7, 4, 9, 6, 2, 8, 1, 5],
];

const invalidBoard2: Board = [
  [8, 3, 5, 4, 1, 6, 9, 2, 7],
  [2, 9, 6, 8, 5, 7, 4, 3, 1],
  [4, 1, 7, 2, 9, 3, 6, 5, 8],
  [5, 6, 9, 2, 3, 4, 7, 8, 1], // Wrong in this row
  [1, 2, 3, 6, 7, 8, 5, 4, 9],
  [7, 4, 8, 5, 2, 9, 1, 6, 3],
  [6, 5, 2, 7, 8, 1, 3, 9, 4],
  [9, 8, 1, 3, 4, 5, 2, 7, 6],
  [3, 7, 4, 9, 6, 2, 8, 1, 5],
];

export { validBoard, invalidBoard1, invalidBoard2 };

And then, in our index.ts file, we run some tests:

import { checkBoard } from "./sudoku/SudokuSolver";
import { invalidBoard1, invalidBoard2, validBoard } from "./sudoku/boards";

const execute = (fn: () => boolean) => {
  if (fn()) {
    console.log("Board is valid");
  } else {
    console.log("Board is invalid");
  }
};

execute(() => checkBoard(validBoard));
execute(() => checkBoard(invalidBoard1));
execute(() => checkBoard(invalidBoard2));

And in our console, we should see something like:

Board is valid
Board is invalid
Board is invalid

There we go, our own Sudoku checker 🍾

Bonus - implement a sudoku creator

Now we will implement a sudoku creator. This will generate a finished game for us. Create a new file called SudokuCreator.ts.

We start with creating a new type that allows undefined to be added to our arrays

export type BaseBoard = (number | undefined)[][];

Then, we will add a function for creating our empty board:

const COLUMN_SIZE = 9;

const createDefaultBoard = (): BaseBoard => {
  const board: BaseBoard = [];
  for (let i = 0; i < COLUMN_SIZE; i++) {
    board.push([]);
    for (let j = 0; j < COLUMN_SIZE; j++) {
      board[i].push(undefined);
    }
  }
  return board;
};

Then, we will create a little function for getting the next value to add to a cell (1-9):

const getNextEligible = (cur: number): number => {
  if (cur === 9) {
    return 1;
  }
  return cur + 1;
};

And at last, our main function that will do the logic:

export const createBoard = (): Board => {
  const board: BaseBoard = createDefaultBoard();
  board.forEach((_, rowIndex) => {
    let next = 0;
    let counter = 0;
    while (counter < COLUMN_SIZE) {
      next = getNextEligible(next);
      board[rowIndex][counter] = next;
      if (!checkBoard(board as Board)) {
        board[rowIndex][counter] = undefined;
      } else {
        counter++;
      }
    }
  });
  return board as Board;
};

Or, if we want it to be a little bit "random", we can specify a starting number. Change signature to:

export const createBoard = (startValue?: Range<1, 10>): Board () => {}

And the let next = 0 to:

let next = startValue || 0;

Generate a game

And then, call it like this:

import { createBoard } from "./sudoku/SudokuCreator";

createBoard();
createBoard(5);

and we will now get a correct sudoku game.

Remove entries to make it playable

As the above code is all good and dandy, we can't really do anything with it, right? The puzzle is already solved. So let's fix that, and make our generator able to generate a sudoku that we could use for solving - in other words, let's eliminate some entries based on a skill level. So now we will expand our SudokuCreator.ts.

Let's start with our typings. We will have three levels - easy, medium and hard.

export type SudokuLevel = "easy" | "medium" | "hard";

Then, we will create our function for removing entries in our board.

const removeCells = (board: Board, eliminate: number): Board => {
  board.forEach((row) => {
    for (let i = 0; i < eliminate; i++) {
      const randomIndex = Math.floor(Math.random() * 8);
      row[randomIndex] = undefined as any;
    }
  });
  return board;
};

Cool, and now it's time to create our main function that we will export.

export const generateBoard = (level: SudokuLevel): Board => {
  const random = Math.floor(Math.random() * 8 + 1) as Range<1, 10>;
  const board = createBoard(random);
  switch (level) {
    case "easy":
      return removeCells(board, 3);
    case "medium":
      return removeCells(board, 5);
    case "hard":
      return removeCells(board, 7);
  }
};

And there we go. We are using a random number for our generation, and also eliminating a fixed number based on the level of skill that we choose. This could of course be much improved to be more random in the removal etc. But this article is just made for giving inspiration (and for fun 🤓).

Consume the function as below:

import { generateBoard } from "./sudoku/SudokuCreator";

generateBoard("easy")
generateBoard("medium")
generateBoard("hard")

Summary

In this article, we created a sudoku validator in TypeScript, that checks if a sudoku solution is correct or not. TypeScript is quite neat when it comes to typing (obviously), and as mentioned above, we create a Range type that forced us to use numbers between 1-9 for example. Otherwise we would need to do this check ourselves, preferably in our checkRows function where we would need to check if the value is >= 1 && <= 9 for example. Not a big deal, but less code is always great 😃 As a bonus, we added functionality for creating a complete Sudoku game as well.

Hope you enjoyed this one, and have a great day!