Depth First Search and Sudoku

Sudoku is a logic-based puzzle game that involves filling a 9x9 grid with numbers from 1 to 9. The grid is divided into 9 smaller 3x3 grids, and some of the cells are pre-filled with numbers. The objective is to fill in the empty cells with numbers in such a way that each row, column, and 3x3 grid contains all the numbers from 1 to 9 without repetition. Sudoku puzzles can vary in difficulty, with some requiring simple logic and deduction, while others may require more advanced techniques and strategies. The game has gained popularity around the world and is often featured in newspapers, magazines, and puzzle books.

Creating the game of sudoku is one challenge but to have a complete game we will need to provide the solution to each puzzle as well. We could manually do the solutions but this would limit the amount of puzzles and increase the complexity. So we need to be able to automatically solve the puzzles using code. One way that we can use code to solve a sudoku puzzle is with the Depth First Search algorithm. Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts from a given node in a graph and visits all its adjacent nodes first, filling in valid numbers as it goes. Once no valid numbers can be filled in it then visits the last correct node and changes its number, once changed it continues this process recursively until it reaches a dead end or the goal node, which in this case is the final block filled in with a valid number. DFS maintains a stack to keep track of the visited nodes and the order of their exploration. It uses the stack to backtrack and explore the unvisited branches of the graph until all nodes are visited or the goal node is found. DFS can be used to solve a variety of problems, including finding paths in a maze, determining connected components in a graph, and detecting cycles in a graph. However, DFS may not find the shortest path or optimal solution, as it explores each branch as far as possible before backtracking.

The puzzles are generated by placing a few random numbers which abide by the game rules and then using the Depth First Search algorithm to complete the puzzle, thus creating a valid puzzle. Numbers are then removed from the puzzle at random based on the difficulty level. This method can create millions of valid puzzles with relatively low complexity. The downside to this method is gauging the difficulty of each puzzle.
Below is a game of sudoku. Challenge yourself to complete a puzzle!

How to play:

• Click an empty square
• Type a number on your keyboard to enter it - Type the same number to remove it.
• All rows, columns and 3x3 squares should contain the numbers 1-9 with no duplicates
• If a number appears more than once in a row, colomn or 3x3 square it will be highlighted in red
• You can save a puzzle for later by saving the 'Seed' and entering it in the text box before pressing 'Generate'

Seed: