Mathematical foundation behind Sudoku Puzzle in java

let’s dive into the mathematical foundation behind Sudoku so you can use it as a background theory for your Sudoku puzzle generator/solver is technical paper.

What is a Sudoku Puzzle?

A standard Sudoku is a 9×9 grid divided into nine 3×3 blocks, where the goal is to:

Fill the grid with numbers from 1 to 9
Such that each row, each column, and each 3×3 box contains all digits 1 to 9 exactly once

· This program solves a 9x9 Sudoku puzzle using the backtracking algorithm. It checks for valid placements and recursively fills the board.

Mathematical Background of Sudoku

1. Combinatorics and Permutations

Each row, column, and box must be a permutation of {1, 2, ..., 9}.

Ø Sudoku is essentially a Latin Square with additional 3×3 subgrid constraints.

2. Constraint Satisfaction Problem (CSP)

Sudoku can be modeled as a CSP:

Variables: Each cell (i, j) on the grid (total of 81)
Domain: {1, 2, ..., 9} for each variable
Constraints:

Row: ∀ row i, all values are unique
Column: ∀ column j, all values are unique
Subgrid: ∀ 3×3 block, all values are unique

Formal CSP Representation:

Let $x_{i,j} \in \{1, ..., 9\}$

Subject to:

$\forall i, \{x_{i,1}, x_{i,2}, ..., x_{i,9}\}$ are all different
$\forall j, \{x_{1,j}, x_{2,j}, ..., x_{9,j}\}$ are all different
$\forall (r, c) \in \{(0,0), (0,3), ..., (6,6)\}$, the 3×3 block starting at (r, c) has 9 unique values

3. Graph Theory View

Each cell is a node. An edge exists between two cells if they must not contain the same value (same row, column, or box).

This becomes a graph coloring problem where each node (cell) must be assigned a number (color) such that no adjacent node has the same color.
Min number of colors required = 9

4. Sudoku Grid as a Matrix

Let the Sudoku board be a matrix:

$$M = \begin{bmatrix} x_{1,1} & x_{1,2} & \cdots & x_{1,9} \\ x_{2,1} & x_{2,2} & \cdots & x_{2,9} \\ \vdots & \vdots & \ddots & \vdots \\ x_{9,1} & x_{9,2} & \cdots & x_{9,9} \\ \end{bmatrix}$$

Each:

Row: $M_{i,*}$ is a permutation of 1-9
Column: $M_{*,j}$ is a permutation of 1-9
Box: $M_{i:i+3, j:j+3}$ (with correct indexing) is a permutation of 1-9

5. Total Number of Valid Sudoku Grids

A fascinating combinatorics result:

The total number of valid 9×9 Sudoku solution grids is:

$6,670,903,752,021,072,936,960 \approx 6.67 \times 10^{21}$

And the number of minimal puzzles (with unique solution) is in the billions.

6. Java Program

import java.util.Random;

import java.util.Scanner;

public class SudokuGame {

private static final int SIZE = 9;

private static final int SUBGRID = 3;

private static final int EMPTY_CELLS = 40; // Number of cells to remove

private int[][] board = new int[SIZE][SIZE];

private Random random = new Random();

public SudokuGame() {

fillDiagonal();

fillRemaining(0, SUBGRID);

removeDigits();

}

private void fillDiagonal() {

for (int i = 0; i < SIZE; i += SUBGRID) {

fillSubGrid(i, i);

}

private void fillSubGrid(int row, int col) {

boolean[] used = new boolean[SIZE + 1];

for (int i = 0; i < SUBGRID; i++) {

for (int j = 0; j < SUBGRID; j++) {

int num;

do {

num = random.nextInt(SIZE) + 1;

} while (used[num]);

used[num] = true;

board[row + i][col + j] = num;

}

private boolean fillRemaining(int row, int col) {

if (col >= SIZE && row < SIZE - 1) {

row++; col = 0;

}

if (row >= SIZE && col >= SIZE) {

return true;

}

if (row < SUBGRID) {

if (col < SUBGRID) {

col = SUBGRID;

}

} else if (row < SIZE - SUBGRID) {

if (col == (row / SUBGRID) * SUBGRID) {

col += SUBGRID;

}

} else {

if (col == SIZE - SUBGRID) {

row++; col = 0;

if (row >= SIZE) {

return true;

}

for (int num = 1; num <= SIZE; num++) {

if (isSafe(row, col, num)) {

board[row][col] = num;

if (fillRemaining(row, col + 1)) {

return true;

}

board[row][col] = 0;

}

return false;

}

private boolean isSafe(int row, int col, int num) {

for (int x = 0; x < SIZE; x++) {

if (board[row][x] == num || board[x][col] == num) {

return false;

}

int startRow = row - row % SUBGRID, startCol = col - col % SUBGRID;

for (int i = 0; i < SUBGRID; i++) {

for (int j = 0; j < SUBGRID; j++) {

if (board[i + startRow][j + startCol] == num) {

return false;

}

return true;

}

private void removeDigits() {

int count = EMPTY_CELLS;

while (count != 0) {

int row = random.nextInt(SIZE);

int col = random.nextInt(SIZE);

if (board[row][col] != 0) {

board[row][col] = 0;

count--;

}

public void printBoard() {

for (int i = 0; i < SIZE; i++) {

for (int j = 0; j < SIZE; j++) {

System.out.print(board[i][j] + " ");

}

System.out.println();

}

public static void main(String[] args) {

SudokuGame game = new SudokuGame();

System.out.println("Generated Sudoku Puzzle:");

game.printBoard();

}

Mathematical foundation behind Sudoku Puzzle in java

Summary

Math Concept	Role in Sudoku
Latin Squares	Basic structure (rows/columns = permutations)
CSP (Constraint Satisfaction Problem)	Used to model solving logic
Graph Coloring	Avoiding value repetition in related cells
Matrix Theory	Representing and validating the grid
Combinatorics	Counting valid and unique grids