The complete implementation process of Sudoku using JavaScript

Preface
How to solve Sudoku

Fill in the first box
Fill in the second box
Fill in the third box
Fill in the ninth box
In summary

Implemented through code

Dynamic display of the test process

Nine-grid style
Question logic

Summarize

Preface

Recently, I saw my wife playing Sudoku on her mobile phone every day. Suddenly, I remembered that when I was playing LeetCode N years ago, there was a similar algorithm problem (37. Solving Sudoku). Is it possible to visualize this algorithm?

Just do it, after an hour of practice, the final effect is as follows:

How to solve Sudoku

Before solving Sudoku, let's first understand the rules of Sudoku:

The numbers 1-9 can appear only once in each line.
The numbers 1-9 can appear only once in each column.
The numbers 1-9 can only appear once in each of the 3x3 grids separated by thick solid lines.

Next, what we need to do is fill in a number in each box and then determine whether this number violates the rules.

Fill in the first box

First, fill 1 in the first grid, and you will find that there is already a 1 in the first column. At this time, you need to erase the number 1 filled in previously, and then fill 2 in the grid. You will find that the numbers are not repeated in the rows, columns, and nine-square grids. Then the grid is filled successfully.

Fill in the second box

Let’s look at the second grid. Just like before, try filling in 1 first. If you find that there are no repeated numbers in the rows, columns, and grid, then this grid is also filled successfully.

Fill in the third box

Let’s take a look at the third box. Since we have already filled the first two boxes with numbers 1 and 2, we can start filling in number 3 directly. After filling in 3, I found that there was already a 3 in the first row. Then I filled in 4 in the grid and found that the number 4 was repeated in both the row and the grid. It was still unsuccessful. Then I tried to fill in the number 5. Finally, there were no repeated numbers, indicating that the filling was successful.

…

Keep filling...

Fill in the ninth box

Following this idea, fill in until the ninth square. At this point, you will find that the last number 9 conflicts in the nine-square grid. But 9 is already the last number, so there is no way to fill in other numbers here. I can only return to the previous grid and change the number in the seventh grid from 8 to 9, but I found that there is still a conflict in the nine-square grid.

At this time, you need to replace the number in the previous grid (the sixth grid). Until there is no conflict, so in this process, you not only have to fill in the numbers backwards, but also look back to see if there are any problems with the previous numbers, and keep trying.

In summary

Solving Sudoku is a process of continuous trial and error. Try the numbers 1-9 in each grid. If there is a conflict, erase the number until all the grids are filled.

Implemented through code

To reflect the above solution in the code, we need to implement it through recursion + backtracking.

Before writing the code, let’s take a look at how to represent Sudoku. Here is a reference to the question on LeetCode: 37. Solve Sudoku.

The previous question can be represented by a two-dimensional array. There are 9 arrays in the outermost array, representing the 9 rows of Sudoku. The 9 characters in each inner array correspond to the columns of the array, and the unfilled spaces are represented by characters ('.').

const sudoku = [
  ['.', '.', '.', '4', '.', '.', '.', '3', '.'],
  ['7', '.', '4', '8', '.', '.', '1', '.', '2'],
  ['.', '.', '.', '2', '3', '.', '4', '.', '9'],
  ['.', '4', '.', '5', '.', '9', '.', '8', '.'],
  ['5', '.', '.', '.', '.', '.', '9', '1', '3'],
  ['1', '.', '.', '.', '8', '.', '2', '.', '4'],
  ['.', '.', '.', '.', '.', '.', '3', '4', '5'],
  ['.', '5', '1', '9', '4', '.', '7', '2', '.'],
  ['4', '7', '3', '.', '5', '.', '.', '9', '1'],
]

Now that we know how to represent arrays, let's write code.

const sudoku = [……]
// The method accepts two parameters, row and column, to locate the grid of Sudoku function solve(row, col) {
  if (col >= 9) { 
   // Beyond the ninth column, it means that this row has ended and a new row needs to be started col = 0
    row += 1
    if (row >= 9) {
      // After starting a new line, if it exceeds the ninth line, the entire Sudoku has been completed and return true
    }
  }
  if (sudoku[row][col] !== '.') {
    // If the grid has been filled, fill the next grid return solve(row, col + 1)
  }
  // Try to fill in the number 1-9 in the grid
  for (let num = 1; num <= 9; num++) {
    if (!isValid(row, col, num)) {
      // If it is an invalid number, skip the number continue
    }
    // Fill in numbers sudoku[row][col] = num.toString()
    // Continue to fill in the following grids if (solve(row, col + 1)) {
      // If everything is OK until the end, then the number in this grid is OK return true
    }
    // If there is a problem, solve returns false
    // Indicates that this place needs to be refilled sudoku[row][col] = '.' // Erase the number }
  // The numbers 1-9 all failed to be filled in, indicating that there is a problem with the previous numbers // Return FALSE, backtrack, and re-fill the previous numbers return false
}

The above code only implements the recursion and backtracking parts, and there is an isValid method that has not been implemented. This method mainly performs a verification according to the rules of Sudoku.

const sudoku = [……]
function isValid(row, col, num) {
  // Check if the row is repeated for (let i = 0; i < 9; i++) {
    if (sudoku[row][i] === num) {
      return false
    }
  }
  // Check if there is a duplicate in the column for (let i = 0; i < 9; i++) {
    if (sudoku[i][col] === num) {
      return false
    }
  }
  // Determine whether the nine-square grid is repeated const startRow = parseInt(row / 3) * 3
  const startCol = parseInt(col / 3) * 3
  for (let i = startRow; i < startRow + 3; i++) {
    for (let j = startCol; j < startCol + 3; j++) {
      if (sudoku[i][j] === num) {
        return false
      }
    }
  }
  return true
}

With the above code, we can solve a Sudoku.

const sudoku = [
  ['.', '.', '.', '4', '.', '.', '.', '3', '.'],
  ['7', '.', '4', '8', '.', '.', '1', '.', '2'],
  ['.', '.', '.', '2', '3', '.', '4', '.', '9'],
  ['.', '4', '.', '5', '.', '9', '.', '8', '.'],
  ['5', '.', '.', '.', '.', '.', '9', '1', '3'],
  ['1', '.', '.', '.', '8', '.', '2', '.', '4'],
  ['.', '.', '.', '.', '.', '.', '3', '4', '5'],
  ['.', '5', '1', '9', '4', '.', '7', '2', '.'],
  ['4', '7', '3', '.', '5', '.', '.', '9', '1']
]
function isValid(row, col, num) {……}
function solve(row, col) {……}
solve(0, 0) // Solve from the first grid console.log(sudoku) // Output the result

Dynamic display of the test process

With the above theoretical knowledge, we can apply the problem-solving process to react and dynamically display the problem-solving process, which is the Gif at the beginning of the article.

Here we use create-react-app scaffolding to quickly start a project

npx create-react-app sudoku
cd sudoku

Open App.jsx and start writing code.

import React from 'react';
import './App.css';

class App extends React.Component {
  state = {
    // Configure a Sudoku two-dimensional array in state sudoku: [
      ['.', '.', '.', '4', '.', '.', '.', '3', '.'],
      ['7', '.', '4', '8', '.', '.', '1', '.', '2'],
      ['.', '.', '.', '2', '3', '.', '4', '.', '9'],
      ['.', '4', '.', '5', '.', '9', '.', '8', '.'],
      ['5', '.', '.', '.', '.', '.', '9', '1', '3'],
      ['1', '.', '.', '.', '8', '.', '2', '.', '4'],
      ['.', '.', '.', '.', '.', '.', '3', '4', '5'],
      ['.', '5', '1', '9', '4', '.', '7', '2', '.'],
      ['4', '7', '3', '.', '5', '.', '.', '9', '1']
    ]
  }

 // TODO: Solve SudokusolveSudoku = async () => {
    const { sudoku } = this.state
  }

  render() {
    const { sudoku } = this.state
    return (
      <div className="container">
        <div className="wrapper">
          {/* Traverse the two-dimensional array and generate a nine-square grid*/}
          {sudoku.map((list, row) => (
            {/* div.row corresponds to the row of Sudoku*/}
            <div className="row" key={`row-${row}`}>
              {list.map((item, col) => (
              {/* span corresponds to each grid of Sudoku*/}
                <span key={`box-${col}`}>{ item !== '.' && item }</span>
              ))}
            </div>
          ))}
          <button onClick={this.solveSudoku}>Start solving the problem</button>
        </div>
      </div>
    );
  }
}

Nine-grid style

Add a dotted border to each grid to make it look like a nine-grid.

.row {
  display: flex;
  direction: row;
  /* Center the elements in the row */
  justify-content: center;
  align-content: center;
}
.row span {
  /*Each grid has the same width and height*/
  width: 30px;
  min-height: 30px;
  line-height: 30px;
  text-align: center;
  /* Set the dotted border */
  border: 1px dashed #999;
}

You can get a graph like this:

Next, you need to add a solid line border to the outer border and each nine-square grid. The specific code is as follows:

/* Add a border to the top of line 1*/
.row:nth-child(1) span {
  border-top: 3px solid #333;
}
/* Add borders to the bottom of rows 3, 6, and 9*/
.row:nth-child(3n) span {
  border-bottom: 3px solid #333;
}
/* Add a border to the left of the first column*/
.row span:first-child {
  border-left: 3px solid #333;
}

/* Add borders to the right of columns 3, 6, and 9*/
.row span:nth-child(3n) {
  border-right: 3px solid #333;
}

Here you will find that the right border of the third and sixth columns and the left border of the fourth and seventh columns overlap a little. The bottom border of the third and sixth rows and the top border of the fourth and seventh rows will also have this problem. Therefore, we also need to hide the left border of the fourth and seventh columns and the bottom border of the third and sixth rows.

.row:nth-child(3n + 1) span {
  border-top: none;
}
.row span:nth-child(3n + 1) {
  border-left: none;
}

Question logic

After the style is written, you can continue to improve the logic of answering the questions.

class App extends React.Component {
  state = {
    // Configure a Sudoku two-dimensional array in state sudoku: [...]
  }

  solveSudoku = async () => {
    const { sudoku } = this.state
    // Check whether the entered number is valid. Refer to the above code and will not be repeated here const isValid = (row, col, num) => {
      …
    }
    // Solve the problem using recursion + backtracking const solve = async (row, col) => {
      if (col >= 9) { 
        col = 0
        row += 1
        if (row >= 9) return true
      }
      if (sudoku[row][col] !== '.') {
        return solve(row, col + 1)
      }
      for (let num = 1; num <= 9; num++) {
        if (!isValid(row, col, num)) {
          continue
        }
 
        sudoku[row][col] = num.toString()
        this.setState({ sudoku }) // After filling in the grid, you need to synchronize to the state

        if (solve(row, col + 1)) {
          return true
        }

        sudoku[row][col] = '.'
        this.setState({ sudoku }) // After filling in the grid, you need to synchronize to the state
      }
      return false
    }
    // Solve the problem solve(0, 0)
  }

  render() {
    const { sudoku } = this.state
    return (……)
  }
}

Compared with the previous logic, here we just call this.setState to synchronize sudoku to the state after filling in the two-dimensional array of Sudoku.

function solve(row, col) {
   …
   sudoku[row][col] = num.toString()
+ this.setState({ sudoku })
  …
   sudoku[row][col] = '.'
+ this.setState({ sudoku }) // After filling in the grid, you need to synchronize to the state
}

After calling solveSudoku, it is found that there is no dynamic effect, but the result is synchronized to the view in one step.

This is because setState is a pseudo-asynchronous call. In an event task, all setState calls will be merged into one. If we need to see the dynamic process of answering questions, we need to put each setState operation outside the event flow, that is, put it in setTimeout. For more questions about setState asynchrony, please refer to my previous article: Is setState in React a macro task or a micro task?

solveSudoku = async () => {
  const { sudoku } = this.state
  // Check whether the entered number is valid. Refer to the above code and will not be repeated here const isValid = (row, col, num) => {
    …
  }
  // Depart from the event flow and call setState
  const setSudoku = async (row, col, value) => {
    sudoku[row][col] = value
    return new Promise(resolve => {
      setTimeout(() => {
        this.setState({
          sudoku
        }, () => resolve())
      })
    })
  }
  // Solve the problem using recursion + backtracking const solve = async (row, col) => {
    …
    for (let num = 1; num <= 9; num++) {
      if (!isValid(row, col, num)) {
        continue
      }

   await setSudoku(row, col, num.toString())

      if (await solve(row, col + 1)) {
        return true
      }

   await setSudoku(row, col, '.')
    }
    return false
  }
  // Solve the problem solve(0, 0)
}

The final effect is as follows:

Summarize

This is the end of this article about using JavaScript to do Sudoku. For more relevant JavaScript Sudoku content, please search 123WORDPRESS.COM's previous articles or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!

You may also be interested in:

Javascript implementation of Sudoku algorithm web page example
Javascript implementation of Sudoku solution
javascript sudoku Sudoku puzzle game generation code
JS implementation of valid Sudoku algorithm example
Summary of the main ideas for solving Sudoku problems through JavaScript traversal

<<: Alibaba Cloud ECS Server Getting Started Process (Must-Read Tutorial for Newbies)

>>: After installing Navicat in MySQL, 2059 appears, Authentication plugin and local link virtual machine docker, remote link server