Python Sudoku Solver

Introduction

Sudoku is a logic-based, combinatorial number-placement puzzle. In classic sudoku, the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called “boxes”, “blocks”, or “regions”) contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

Mathematics of Sudoku

The general problem of solving Sudoku puzzles on grids of blocks is known to be NP-complete. Many computer algorithms, such as backtracking and dancing links can solve most 9×9 puzzles efficiently, but combinatorial explosion occurs as n increases, creating limits to the properties of Sudokus that can be constructed, analyzed, and solved as n increases. A Sudoku puzzle can be expressed as a graph coloring problem. The aim is to construct a 9-coloring of a particular graph, given a partial 9-coloring. The number of classic 9×9 Sudoku solution grids is 6,670,903,752,021,072,936,960 (sequence A107739 in the OEIS), or around . This is roughly times the number of 9×9 Latin squares.

Python Implementation

The code below is referred from here.

grid = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0], 
    [6, 0, 0, 1, 9, 5, 0, 0, 0], 
    [0, 9, 8, 0, 0, 0, 0, 6, 0], 
    [8, 0, 0, 0, 6, 0, 0, 0, 3], 
    [4, 0, 0, 8, 0, 3, 0, 0, 1], 
    [7, 0, 0, 0, 2, 0, 0, 0, 6], 
    [0, 6, 0, 0, 0, 0, 2, 8, 0], 
    [0, 0, 0, 4, 1, 9, 0, 0, 5], 
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

def possible(x, y, n, grid):
    for i in range(9):
        if grid[i][x] == n:
            return False
    for i in range(9):
        if grid[y][i] == n:
            return False
    x0 = (x//3) * 3
    y0 = (y//3) * 3
    for i in range(3):
        for j in range(3):
            if grid[y0+i][x0+j] == n:
                return False
    return True

def solve(grid):
    for x in range(9):
        for y in range(9):
            if grid[y][x] == 0:
                for n in range(1, 10):
                    if possible(x, y, n, grid):
                        grid[y][x] = n
                        solve(grid)
                        grid[y][x] = 0
                return
    print(np.matrix(grid))
    input("More?")

solve(grid)

Sudoku Solver

Enter the numbers of the puzzle you want to solve in the grid.

Solve Validate Board Reset

Conclusion

Sudoku is a ‘brain game’ that requires a variety of cognitive skills, such as quick decision making, spotting patterns, and applying logical reasoning. Sudoku is a nice escape from the little challenges of daily life – we can solve a Sudoku puzzle and point to it as a tangible example of what we can achieve with our minds.

Reference

1. https://www.youtube.com/watch?v=G_UYXzGuqvM&list=PLCZeVeoafktVGu9rvM9PHrAdrsUURtLTo&index=59&t=454s&ab_channel=Computerphile
2. https://en.wikipedia.org/wiki/Sudoku
3. https://sudoku.com/
4. https://codereview.stackexchange.com/questions/239248/sudoku-game-in-javascript
5. https://sudokuspoiler.azurewebsites.net/
6. https://www.sudoku-solutions.com/