Building a Sudoku Puzzle Generator Using Vanilla JavaScript

Coding a generator can be a lot of work. There are a ton of factors that you need to consider. Here’s how I did it using vanilla JavaScript.

Sudoku Board

What is Sudoku?

Before I begin explaining how to generate unique Sudoku puzzles, it is important to review the rules of Sudoku.

Sudoku is played on a 9x9 grid, sectioned off by rows, columns, and 3x3 ‘boxes’. The ‘cells’ in each row, column, and box need to be filled out with the numbers 1–9, without repeating numbers. In order for a Sudoku puzzle to be valid, it must only have 1 unique solution. In other words, every cell on the board has a predetermined value that will be revealed as the puzzle is being solved. If a cell has 2 or more values that would lead to a solution, the puzzle is not valid.

Background

Coding a generator can be a lot of work. There are a ton of factors that you need to consider, such as grading the puzzles that you generate (assigning a difficulty) and ensuring that generated puzzles have unique solutions.

Grading the puzzles is an exceptionally difficult problem because of the variety of techniques humans use when solving. While it would certainly be an interesting foray into computer science and human psychology, I found that building a generator from scratch would be particularly unnecessary for most use cases. Instead, I decided to ‘cheat’ by manipulating existing matrices (puzzles) without affecting the integrity of the puzzle, as defined above.

Coding the Generator

I began this process by curating a list of existing puzzles that have already been graded, and copying them down into a javascript file as 2-D arrays (matrices) to use as seeds, with null values mapped to 0. You can represent the null values as null or undefined, I just prefer 0, because it’s easier to read the output when testing. You can then keep the variables representing the matrices in arrays labeled ‘easy’, ‘medium’, ‘hard’, etc. You end up with something like: const easy = [easySeed1, easySeed2, ...]. Next, I perform a random series of transformations on a random seed whenever I need to generate a puzzle. The transformations that you can do to any valid puzzle are:

1. Rotate the matrix between 0 and 3 times
2. Map all of the numbers to other numbers
3. Shuffle any 2–3 rows or columns that span the same 3 boxes.

Rotate Matrix

Imagine that you were holding a piece of paper that contained a sudoku puzzle. Now rotate that piece of paper 90 degrees, and orient the numbers so that they aren’t sideways. The puzzle would look different, but it is obviously still valid. In fact, if you were playing Sudoku online or on an app, and you were given the same exact sudoku, only rotated 90 degrees, you probably wouldn’t notice. And that is exactly the point. You don’t need to generate entirely ‘unique’ puzzles, just ‘unique’ enough that they go unnoticed. Anyways, the code to do this is as follows:

const rotateMatrix = (array) => {
  const n = array.length  
  
  // Create a temporary matrix of size n x n
  let t = Array.from(Array(n), () => Array.from(Array(n)))
  
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      
      // basically array[i][j] gets moved to [j][n - (i + 1)]
      // e.g. array[0][0] => array[0][8] assuming 9x9 matrix
      let ele = array[i][j];
      let idx = n - (i + 1)
      
      t[j][idx] = ele
    }
  }
  return t
}

Map Numbers

You can also map any number group to any other number group, and the puzzle remains the same. For example, you can map the numbers so that ‘1’s become ‘3’s, ‘3’s become ‘9’s and so forth… 1 => 3, 3 => 9. We can do this by first shuffling an array of numbers 1–9 using the Fisher-Yates method, and setting a conversion object such that:

const conversion = {}
// i + 1 bc we want 1-9 as keys and arrays start at index 0 
shuffled.forEach((e, i) => conversion[i + 1] = e)

Once you have your conversion object, you can simply iterate across the matrix and map every number to the value of the conversion, making sure that you account for your null values:

arr[i][j] = conversion[[arr[i][j]] || 0

Shuffle Rows and Columns

This is by far the coolest method for transforming the seed puzzles, and the one that I believe truly changes the puzzle. Reference the image at the top of this article for a minute. If you were to take the first row (the one that is highlighted green), and switch it with the second or third row, the puzzle would still be valid. To generalize the rule, the order of rows in groups (1, 2, 3), (4, 5, 6), and (7, 8, 9) does not matter, but you can’t swap rows between the groups. The same goes for the columns. If you don’t believe me, check out Sudoku Solutions and simply copy the puzzle from the image at the top of the page to their interface. Click ‘check puzzle’. Now simply swap the first and second rows, and continue to do this with the rows and columns until you are convinced. Assuming you already have a shuffle function from above, you can shuffle the rows very easily:

const shuffleRows = (array) => {
  return [
   shuffle(array.slice(0, 3)),
   shuffle(array.slice(3, 6)),
   shuffle(array.slice(6)
  ].flat() // flat by default flattens array by one level

In order to shuffle the columns, first rotate the matrix once, then use the same shuffleRows function, and then rotate the matrix 3 more times, back to its original orientation.

Conclusion

I was inspired to make a puzzle generator because the packages I tried to use to generate puzzles were not generating valid puzzles, and I did not want to rely on an external API to fetch puzzles.

While not technically a ‘true’ puzzle generator, I have found that this method works well enough for my own personal projects. Of course, the more puzzle seeds you provide to the generator, the better it will be at fooling people into believing they are solving truly unique puzzles.

I tried to test it on my roommates, but they got bored before I had any conclusive data. Hope you enjoyed the article, thanks for reading!

More content at plainenglish.io