July 13

Sudoku Solver with React

Hi again! So I was on a cabin trip this weekend, and after solving countless amount of Sudoku I thought: “Hey, I could port over one of my old Sudoku Solver projects to React!”. I made one previous in C#, but the interface was just a terminal (“Ew…” I know). With React being made for creating UIs this proved to be a perfect project!

Usually I create the blog post while I’m making the projects, but this time I made the application first. So I won’t be going so in-depth in this blog post on how to make it, but the code will however, as always, be available!

So this is how the “Sudoku Solver” looks like:

Just enter the unsolved Sudoku into the cells, hit the “Solve” button… and voila!

This is how I made it:


class App extends Component {

  constructor(props) {
    super(props)

    //Set our sudoku size
    this.width = 9;
    this.height = 9;

    this.state = {
      board: this.createBoard(this.width, this.height),     //Our sudoku board
      invalidSudoku: false                                  //If the sudoku in the board is valid
    }

  }

First making it so that the “App” has a state with two variables. One for the board (2D Array) and one for if the input Sudoku is valid (bool). “createBoard” just returns a 2D Array (an array with arrays) with 0’s.

Next I made a handler for when one of the numbers in a “Cell” (where the user can put in a number) changes:


  //Changes the value in the state board
  changeValue = (i, j, num) => {

    //Create a copy of our current board
    let newBoard = this.state.board;
    newBoard[i][j] = num;

    //Update our state with the new board
    this.setState({
      board: newBoard,
      invalidSudoku: false                  //Since the sudoku changed we can set invalid to be false
    }, () => {
      this.setState({ state: this.state }); //Force a re-render after it's done with setting the state
    });
  }

Here I take three vars. “i” and “j” to know which spot we are changing, and the “num” put in. When you change the state in React, you have to use the “setState” method, so that React knows that it has to re-render the component. “setState” is done async ,so to show the state change immediately after the change is done we have to use the “setState’s” second parameter to give it a callback function. Setting another “setState” in the callback function will force it to re-render the component after the previous state has been updated. An inefficient (since it re-renders twice now), but good enough trick for this project.

Now if the user clicks the “Submit” button I run this function through the clickHandler:


  solve = () => {

    //Create a solvedBoard from the Solver class. It either returns as an 2D-array or bool
    let solvedBoard = new Solver(this.state.board);

    //If it's an array then it should be a valid solution. Set it as the current board
    if (Array.isArray(solvedBoard)) {
      this.setState({
        board: solvedBoard,
      }, () => {
        this.setState({ state: this.state }); //Force re-render
      });
    }else{
      //If it's not a valid array, then it's not a valid sudoku.
      this.setState({
        invalidSudoku: true                   //Set it as an invalid sudoku          
      }, () => {
        this.setState({ state: this.state }); //Force re-render
      });
    }
  }

I haven’t shown the Solver yet (I will do that after the React stuff), but know that in the constructor it either returns false if it didn’t find a solution or the sudoku is invalid, or a board if it succeeds. If it succeeds then we update the state with the solved board, and force a re-render!

The App’s render function looks like this:


  render() {
    return (
      <div className="App">

        <h1>Sudoko Solver</h1>

        {/* Show a table that shakes if it's an invalid sudoku. Using date as an key so that it shakes every time it re-renders*/}
        <table className={this.state.invalidSudoku ? "shake" : ""} key={new Date()}> 
          <tbody>
            {
              // Loop through the board and render a Cell for every number
              this.state.board.map((row, i) => (
                <tr key={i * 9}>
                  {row.map((cell, j) => <td key={(i * 9) + j + 1}> <Cell changeValue={this.changeValue} i={i} j={j} value={this.state.board[i][j]} /> </td>)}
                </tr>
              ))
            }
          </tbody>
        </table>

        <button className="button-submit" onClick={() => this.solve()}>Solve!</button>

        {/* Render an error message if the sudoku is not valid */}
        {this.state.invalidSudoku ? <h4 key={new Date() + 1} className="text-error">Not a valid sudoku!</h4> : ''}

      </div>
    );
  }

I render the Sudoku board using a table with some CSS (also in the bottom of the post). For every number in the board, I render a Cell component to show and handle the number being changed. I also pass along the clickHandler function “changeValue” to the Cell components. Afterwards I show a “Solve” button and an error message if the Sudoku is not valid.

The “Cell” component looks like this:


import React, { Component } from 'react'
import './Cell.css'

class BtnNumber extends Component {

    changeValue = (event) => {
        //Prevents user from entering a non-number
        if (!Number(event.target.value) && event.target.value !== "") return;

        //Changes the board value
        this.props.changeValue(this.props.i, this.props.j, Number(event.target.value));

    }

    render() {
        return (
            <div>
                {/* Renders the cell. Shows 0 as nothing */}
                <input className='component-btn-number' value={(this.props.value === 0) ? ' ' : this.props.value} onChange={event => this.changeValue(event)} />
            </div>
        )
    }
}

export default BtnNumber

I use an “input” element as a way to both show the number and receive input from the user. I only show a number as long as it’s not zero since empty fields in the Sudoku board is set to be 0. In the “changeValue” I make sure the input can only be a number by simply not setting the value unless it’s a number.

Now for the Solver. To solve an Sudoku I use the “Backtracking algorithm”. Basically what happens is that the app starts in the top-left and tries every number, making sure that it’s valid, until it reaches the bottom-right. The trick about a backtracking algorithm is that if it reaches a dead end, it will track back to a previous state and try a different number.

File:Sudoku solved by bactracking.gif
A visual representation on how backtracking works. Credits to Wikipedia for the gif

We can achieve this by using a “recursive method”. A recursive method is a method that calls itself! I started making my own implementation for the backtracking method, but after some time I decided to reuse the code from my old C# project, since I wanted this project to be about learning about React, not algorithms. The code originally comes from the website https://www.geeksforgeeks.org/sudoku-backtracking-7/ and is made by 29AjayKumar. I won’t go in-depth about the solver, but know that the “solve” function and half of the “isValid” function was made by 29AjayKumar!



class solver {

    constructor(board) {
        this.board = board;

        if (this.isValidSudoku(this.board)) {                       //Check first if the sudoku is valid
            if (this.solve(this.board, this.board.length)) {        //Start the solving process.
                return this.board;                                  //If "solve" returns true, then return the solved board
            } else {
                return false;                                       //Else return false
            }
        }else{
            return false;                                           //If it's not a valid sudoku, return false
        }
    }

    //Original code by 29AjayKumar. Found on https://www.geeksforgeeks.org/sudoku-backtracking-7/
    solve(board, n) {

        let row = -1;
        let col = -1;
        let isEmpty = true;

        //Checks if there's any empty spot left
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (this.board[i][j] === 0) {
                    row = i;
                    col = j;

                    isEmpty = false;
                    break;
                }
            }
            if (!isEmpty) {
                break;
            }
        }

        // no empty space left 
        if (isEmpty) {
            return true;
        }

        // else for each-row backtrack 
        for (let num = 1; num <= n; num++) {
            if (this.isValid(board, row, col, num)) {
                this.board[row][col] = num;
                if (this.solve(board, n)) {
                    return true;
                }
                else {
                    // replace it
                    this.board[row][col] = 0;
                }
            }
        }

        return false;
    }

    isValid(board, col, row, num) {
        //Check rows
        for (let i = 0; i < board.length; i++) {
            if (i !== col) { //Dont check own number
                if (board[i][row] === num) return false;
            }
        }

        //Check Y Axis
        for (let i = 0; i < board.length; i++) {
            if (i !== row) { //Dont check own number
                if (board[col][i] === num) return false;
            }
        }

        //Check box. Also by 29AjayKumar
        let sqrt = Number(Math.sqrt(board.length));
        let boxRowStart = col - col % sqrt;
        let boxColStart = row - row % sqrt;

        for (let i = boxRowStart; i < boxRowStart + sqrt; i++) {
            for (let j = boxColStart; j < boxColStart + sqrt; j++) {
                if (i !== col &#038;&#038; j !== row) {
                    if (board[i][j] === num) {
                        return false;
                    }
                }
            }
        }
        
        return true; //Else it must be valid
    }

    isValidSudoku(board) {
        for (let i = 0; i < board.length; i++) {
            for (let j = 0; j < board.length; j++) {
                if (board[i][j] !== 0 &#038;&#038; !this.isValid(board, i, j, board[i][j])) return false;
            }
        }

        return true;
    }

}



export default solver;


And that’s it! I’m really happy about how this project went! I learned more about how to deal with states and props, and just React in general.

Link to the project Github: https://github.com/atle517/React-SudokuSolver



Copyright 2020. All rights reserved.

Posted July 13, 2020 by Atle in category "ReactJS

Leave a Reply

Your email address will not be published. Required fields are marked *