Building a React app to solve every Sudoku puzzle.

Introduction

Peter Norvig, the legendary Google mogul and AI titan, wrote a python essay to solve every Sudoku puzzle 10 years ago. Back then, he may not have expected that his code will inspire so many other posts and to be ported to so many different languages. For JavaScript, the latest version of the solver that I found was @einaregilsson/sudoku from 2014 .

I thought it would be interesting to create a react app that uses Peter Norvig's solver ideas and adds some learning layers to the UI.

Here are some details from the design document that I used to create the app. Let's start.

If you want to check it out before reading, go to the LIVE DEMO

or the github repo jsolano/react-sudoku-solver

Plan and Scope

1. Designing and implementing a HTML/JS/CSS Web app using React (with hooks).
2. Designing and implementing an algorithm that solves Sudoku puzzles in JavaScript. (From easy to extra heavy-hard levels)

Goals and non-goals

Goals:

1. Build a HTML/JavaScript application that solves a given Sudoku puzzle.
2. Use React components and React hooks.
3. Cover aesthetics and usability.
4. Support entering puzzle strings in the format described in Peter Norvig's article.
5. Cover Performance of the algorithm (Easy, Medium, Hard, Expert).
6. Display time taken to solve a puzzle.
7. Cover Unit testing.

Non-Goals:

1. UI level automation-tests.
2. Generate new unsolved puzzle.
3. Print a Sudoku.
4. Storage any session data (local or remote).
5. Accept user solutions to the puzzle.
6. Make the solver stop in a specific step.

The Initial Design

The idea was to create a sense of flow in the UI, where users can easily understand how to use it.

System Context Diagram

There are two main modules of the app:

First, I made a raw version of the basic JS components and utilities:

Then, I started working on the solver service using JEST for testing.

Later, I implemented the react components for the board, modal, messages and buttons, and then integrated with the solver service using react hooks.

The Learning Layer.

Here's when things started to get interesting. On one side, the UI learning column helped me understand how the solver was working and how to improve the implementation. But, after I ported Peter Norvig's algorithm, which uses a backtracking search strategy and solves ALL SUDOKUS, I realized the learning column was useless because in the search of a solution, it created temp steps that were not valid. I needed to change my approach.

The Turning Point

I could've just removed the learning feature and lived with just a simple solver but instead, I chose to implement other solving strategies that provided the detailed solutions.

I did my research about Sudoku solving strategies, and there were more than 38 options. I was totally hooked. See more here

But all of these strategies come with a caveat: you can work on many lines of code while trying to implement some of these strategies and still not solve all the puzzles. (I learned this the hard way). So, I found a solution:

Creating a react app that uses human solving strategies (for learning purposes and for fun), and only applying Backtracking Search as the last resort.

So now, the app will apply this strategies :

1. Hidden Singles
2. Naked Pairs/Triples
3. Pointing Pairs
4. And as a last option: Backtracking Search

Also, it comes with a prevention for infinity loops and a spinner while it's solving the puzzle.

Update #1:

• Added Pick Just One link to load a random puzzle. (Thanks Andre for the suggestion!)

Update #2:

• Added a message when the entered board is solve in the parsing moment. (Thanks Andre for the hint!) This could happens after filtering for cell possible values and all cell get solved. (not common, but possible e.g.: ..6.....2.81.4293.25...34..4.8.1..76..2...8..17..6.3.9..35...94.9732.51.5.....7.. )

Update #3:

• Added responsive layout for mobile

Update #4:

• Changed the useState hook for useReducer to decouple the state management from the component and also added localStorage persistence.

If you are a Sudoku fan and want to collaborate, take a look of the github repo. Join me in implementing the other 34 strategies!

/JP

The enemies of people who work with ideas are not the people with the opposing ideas. They're those who want to ban the discussion altogether. -Paul Graham

Comments

[Andre]

Really well done! A suggestion would be to make inputting a new board easier. I feel like the current process is quite tedious. Maybe randomized boards too! Other than that, this is really great

[J.P. Solano]

That's correct Andre, thank you for the feedback, I'll add the randomized option soon..

[J.P. Solano]

Hi Andre, I just updated the repo and the online demo with your suggestion, I hope you will enjoy it. /JP

[Andre]

I just tried it out and it's really cool! One more bug I found was when inputting a sudoku string (ex. ..6.....2.81.4293.25...34..4.8.1..76..2...8..17..6.3.9..35...94.9732.51.5.....7..) it solves it in the first column instantly rather than the second.

[J.P. Solano]

Great! Thank you for take a look. I tested your sudoku string and it's not a bug, what's happening is when you load a new puzzle, the parseGrid method apply strategy 1 and to 2 (assign(values, square, digit) Solver.js, line 148) to generate the possible values for the cell. In this case, resolve the complete puzzle. May be need a message explaining what happens.

[J.P. Solano]

Hi Andre, I updated (repo and live) with a message when the board is solved in the load state. Thank you for sharing your feedback.

[Ruben Vitt]

Well done! 👏 How long did you work for it?

[J.P. Solano]

Thank you Ruben. The initial push was like 10hours spaced in 1 week, couple hours every day.

[acm1812]

Extremely well written article! Well done! 👍

[J.P. Solano]

Thank you!