Problem Statement
The task involves writing a program that can solve a Sudoku puzzle by correctly filling in all the empty cells, represented by the character '.'. The solution must adhere to the standard rules of Sudoku in which:
- Each number from
1to9must appear exactly once in each row. - Each number from
1to9must appear exactly once in each column. - Each number from
1to9must appear exactly once in each of the nine3x3sub-boxes of the 9x9 game board.
The goal is to transform a provided board with several empty cells into a completely filled board where each row, column, and 3x3 sub-box contains all numbers from 1 to 9 exactly once.
Examples
Example 1
Input:
board = [["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]Output:
[["5","3","4","6","7","8","9","1","2"], ["6","7","2","1","9","5","3","4","8"], ["1","9","8","3","4","2","5","6","7"], ["8","5","9","7","6","1","4","2","3"], ["4","2","6","8","5","3","7","9","1"], ["7","1","3","9","2","4","8","5","6"], ["9","6","1","5","3","7","2","8","4"], ["2","8","7","4","1","9","6","3","5"], ["3","4","5","2","8","6","1","7","9"]]
Explanation:
The input board is partially filled. The output represents the only valid Sudoku solution.
Constraints
board.length == 9board[i].length == 9board[i][j]is a digit'1'-'9'or'.'.- It is guaranteed that the input board has only one solution.
Approach and Intuition
To solve this problem, a classic backtracking technique is highly suitable due to its nature of trial and error with the ability to revert decisions. Here's how:
Track Empty Cells: Identify and record all cells that are initially empty (
'.').Recursive Backtracking:
For each empty cell, attempt inserting digits
1to9.Before insertion, validate whether the digit complies with Sudoku rules:
- Not already present in the same row, column, or
3x3box.
- Not already present in the same row, column, or
If valid, place the digit and move to the next empty cell.
If none of the digits work, backtrack (reset the cell) and try a different digit in the previous step.
Base Case: When all cells are filled, a valid solution has been found.
This algorithm is efficient enough given the constraints and the guarantee of a unique solution. It leverages recursion depth proportional to the number of empty cells and avoids unnecessary recomputation by validating moves on-the-fly.
Solutions
- C++
- Java
- C
- JavaScript
- Python
class SudokuSolver {
int boxSize = 3;
int gridSize = boxSize * boxSize;
int **rowConstraints;
int **columnConstraints;
int **boxConstraints;
vector<vector<char>> sudokuBoard;
bool isSolved = false;
public:
bool canPlace(int value, int row, int col) {
int boxIndex = (row / boxSize) * boxSize + col / boxSize;
return rowConstraints[row][value] + columnConstraints[col][value] + boxConstraints[boxIndex][value] == 0;
}
void placeValue(int value, int row, int col) {
int boxIndex = (row / boxSize) * boxSize + col / boxSize;
rowConstraints[row][value]++;
columnConstraints[col][value]++;
boxConstraints[boxIndex][value]++;
sudokuBoard[row][col] = (char)(value + '0');
}
void removeValue(int value, int row, int col) {
int boxIndex = (row / boxSize) * boxSize + col / boxSize;
rowConstraints[row][value]--;
columnConstraints[col][value]--;
boxConstraints[boxIndex][value]--;
sudokuBoard[row][col] = '.';
}
void continueSearch(int row, int col) {
if ((col == gridSize - 1) && (row == gridSize - 1)) {
isSolved = true;
} else {
if (col == gridSize - 1) solveFrom(row + 1, 0);
else solveFrom(row, col + 1);
}
}
void solveFrom(int row, int col) {
if (sudokuBoard[row][col] == '.') {
for (int num = 1; num <= 9; num++) {
if (canPlace(num, row, col)) {
placeValue(num, row, col);
continueSearch(row, col);
if (!isSolved) removeValue(num, row, col);
}
}
} else continueSearch(row, col);
}
void solveSudoku(vector<vector<char>> &board) {
sudokuBoard = board;
rowConstraints = new int *[gridSize];
columnConstraints = new int *[gridSize];
boxConstraints = new int *[gridSize];
for (int i = 0; i < gridSize; i++) {
rowConstraints[i] = new int[gridSize + 1]();
columnConstraints[i] = new int[gridSize + 1]();
boxConstraints[i] = new int[gridSize + 1]();
}
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridSize; j++) {
char num = board[i][j];
if (num != '.') {
int digit = num - '0';
placeValue(digit, i, j);
}
}
}
solveFrom(0, 0);
board = this->sudokuBoard;
}
};
Implementing a Sudoku solver in C++ involves creating the SudokuSolver class that encapsulates the logic for solving Sudoku puzzles. The solution strategy used is typically known as the backtracking algorithm, which explores possible solutions recursively until the correct one is found or all are deemed unworkable. The key components of the solution are as follows:
Data Members:
boxSize,gridSize: Define the dimensions of the Sudoku puzzle, standard being 3x3 boxes in a 9x9 grid.rowConstraints,columnConstraints,boxConstraints: Arrays to track constraints on each row, column, and 3x3 box respectively to avoid placing duplicate numbers.sudokuBoard: Holds the current state of the board during solution.isSolved: A flag indicating whether the board has been successfully solved.
Member Functions:
canPlace(int value, int row, int col): Checks if a value can be placed at a specific position without violating Sudoku rules.placeValue(int value, int row, int col): Places a value on the board and updates constraints.removeValue(int value, int row, int col): Removes a value from the board and updates constraints, typically used during backtracking.continueSearch(int row, int col): Moves to the next cell in processing the Sudoku board.solveFrom(int row, int col): Recursive function that attempts to solve the Sudoku starting from a certain position.solveSudoku(vector<vector<char>> &board): Initializes the Sudoku board, constraints, and begins the solving process from the top-left corner.
The solution follows these outlined steps:
- Initialize constraints and board from the provided unsolved Sudoku puzzle.
- Begin the solving procedure from (0, 0).
- For each position, check if a placement is possible through
canPlace(). If yes, place the number usingplaceValue(). - Continue to the next cell using
continueSearch(). - If a conflict arises (a number cannot be placed anywhere in a cell), use backtracking by removing the last placed number with
removeValue()and trying the next possible number. - Once all cells are filled correctly, set
isSolvedto true. - The
solveSudoku()function will update the original Sudoku board passed by reference to reflect the solved puzzle.
This approach ensures that every step and backtrack is logical and progresses towards a solution, or proves that the puzzle is unsolvable with the current configuration and inputs.
class SudokuSolver {
int blockSize = 3;
int boardSize = blockSize * blockSize;
int[][] rowTracker = new int[boardSize][boardSize + 1];
int[][] colTracker = new int[boardSize][boardSize + 1];
int[][] boxTracker = new int[boardSize][boardSize + 1];
char[][] sudokuBoard;
boolean isSolved = false;
public boolean canPlace(int number, int row, int col) {
int boxIndex = (row / blockSize) * blockSize + col / blockSize;
return rowTracker[row][number] + colTracker[col][number] + boxTracker[boxIndex][number] == 0;
}
public void putNumber(int number, int row, int col) {
int boxIndex = (row / blockSize) * blockSize + col / blockSize;
rowTracker[row][number]++;
colTracker[col][number]++;
boxTracker[boxIndex][number]++;
sudokuBoard[row][col] = (char) (number + '0');
}
public void removeNumber(int number, int row, int col) {
int boxIndex = (row / blockSize) * blockSize + col / blockSize;
rowTracker[row][number]--;
colTracker[col][number]--;
boxTracker[boxIndex][number]--;
sudokuBoard[row][col] = '.';
}
public void findNextNumbers(int row, int col) {
if ((col == boardSize - 1) && (row == boardSize - 1)) {
isSolved = true;
} else {
if (col == boardSize - 1) backtrack(row + 1, 0);
else backtrack(row, col + 1);
}
}
public void backtrack(int row, int col) {
if (sudokuBoard[row][col] == '.') {
for (int num = 1; num <= 9; num++) {
if (canPlace(num, row, col)) {
putNumber(num, row, col);
findNextNumbers(row, col);
if (!isSolved) removeNumber(num, row, col);
}
}
} else findNextNumbers(row, col);
}
public void solveSudoku(char[][] board) {
sudokuBoard = board;
for (int i = 0; i < boardSize; i++) {
for (int j = 0; j < boardSize; j++) {
char num = board[i][j];
if (num != '.') {
int number = Character.getNumericValue(num);
putNumber(number, i, j);
}
}
}
backtrack(0, 0);
}
}
This Java program efficiently solves a Sudoku puzzle using the backtracking algorithm, optimized with additional tracking for rows, columns, and boxes to quickly check the feasibility of placing a number. Here's a concise overview of its execution:
- Initializes trackers for rows, columns, and 3x3 boxes, as well as the Sudoku board itself.
- Provides methods for checking if a number can be placed (
canPlace), placing a number on the board (putNumber), and removing a number (removeNumber). - Includes a recursive function (
backtrack) that attempts to place every number from 1 to 9 in each empty cell.- After placing a number, it moves to the next cell and continues until the board is either solved or needs backtracking.
- If a number doesn't lead to a solution, it reverts the last placed number and tries the next option.
- The
solveSudokumethod sets up the board and initializes the solution process from the top-left corner of the grid.
This structured approach, which includes using separate tracking arrays for each dimension of the grid, allows the program to quickly skip over invalid numbers, leading to an efficient solution process. This is especially effective for larger, more complex puzzles, ensuring that the solution can scale up as needed.
#define BOARD_SIZE 9
#define SUBGRID_SIZE 3
int **rowConstraints;
int **colConstraints;
int **boxConstraints;
char **sudokuBoard;
bool isSolved;
bool canPlace(int digit, int row, int col) {
int boxIndex = (row / SUBGRID_SIZE) * SUBGRID_SIZE + col / SUBGRID_SIZE;
return rowConstraints[row][digit] + colConstraints[col][digit] + boxConstraints[boxIndex][digit] == 0;
}
void placeDigit(int digit, int row, int col) {
int boxIndex = (row / SUBGRID_SIZE) * SUBGRID_SIZE + col / SUBGRID_SIZE;
rowConstraints[row][digit]++;
colConstraints[col][digit]++;
boxConstraints[boxIndex][digit]++;
sudokuBoard[row][col] = (char)(digit + '0');
}
void removeDigit(int digit, int row, int col) {
int boxIndex = (row / SUBGRID_SIZE) * SUBGRID_SIZE + col / SUBGRID_SIZE;
rowConstraints[row][digit]--;
colConstraints[col][digit]--;
boxConstraints[boxIndex][digit]--;
sudokuBoard[row][col] = '.';
}
void traverse(int row, int col);
void proceedToNextCell(int row, int col) {
if ((col == BOARD_SIZE - 1) && (row == BOARD_SIZE - 1)) {
isSolved = true;
} else {
if (col == BOARD_SIZE - 1)
traverse(row + 1, 0);
else
traverse(row, col + 1);
}
}
void traverse(int row, int col) {
if (sudokuBoard[row][col] == '.') {
for (int digit = 1; digit <= 9; digit++) {
if (canPlace(digit, row, col)) {
placeDigit(digit, row, col);
proceedToNextCell(row, col);
if (!isSolved) removeDigit(digit, row, col);
}
}
} else {
proceedToNextCell(row, col);
}
}
void solveSudoku(char **inputBoard, int boardDimension, int *boardColSizes) {
sudokuBoard = inputBoard;
rowConstraints = malloc(BOARD_SIZE * sizeof(int *));
colConstraints = malloc(BOARD_SIZE * sizeof(int *));
boxConstraints = malloc(BOARD_SIZE * sizeof(int *));
isSolved = false;
for (int i = 0; i < BOARD_SIZE; i++) {
rowConstraints[i] = calloc(10, sizeof(int));
colConstraints[i] = calloc(10, sizeof(int));
boxConstraints[i] = calloc(10, sizeof(int));
}
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
char num = sudokuBoard[i][j];
if (num != '.') {
int digit = num - '0';
placeDigit(digit, i, j);
}
}
}
traverse(0, 0);
for (int i = 0; i < BOARD_SIZE; i++) {
free(rowConstraints[i]);
free(colConstraints[i]);
free(boxConstraints[i]);
}
free(rowConstraints);
free(colConstraints);
free(boxConstraints);
}
The supplied C code represents a solution for solving a standard 9x9 Sudoku puzzle through a backtracking algorithm. Below is a concise summary of the approach and methodology used in this code:
Initialization and Constraint Setup:
- Before the actual Sudoku board can be processed, memory allocations are carried out for tracking constraints in three different scopes:
- Row-wise constraints.
- Column-wise constraints.
- Sub-grid (box) constraints.
- These constraints help to keep track of the number placements and ensure that the rules of Sudoku are adhered to.
- Before the actual Sudoku board can be processed, memory allocations are carried out for tracking constraints in three different scopes:
Functions and Their Roles:
canPlacechecks if a digit can be legally placed in a given cell by ensuring the digit has not been already placed in the corresponding row, column, and sub-grid.placeDigitandremoveDigitmanage the placement and removal of digits on the Sudoku board, also updating the constraints.proceedToNextCellmoves the traversal to the next cell in the Sudoku board, handling the transition between rows.traverseis the core recursive function that attempts to place every number in a vacant spot and recurses into the next cell. If a contradiction is reached, it backtracks by removing the placed digit and tries the next possibility.
Overall Sudoku Solving Flow:
- Begins with filling out the board constraints based on the initial numbers present in the input board.
- Through the
traversefunction, the algorithm applies backtracking, trying all possible numbers in empty spots and moving forward consistently by storing the state of partial solutions. - Once the end of the board is reached without contradictions, the board is considered solved.
Performance and Memory Management:
- Significant attention is paid to proper memory management by allocating and freeing memory; a crucial aspect given the recursive nature of the algorithm which can become memory intensive.
Completion and Cleanup:
- After successfully solving the Sudoku or exhausting all possibilities, memory allocated for the constraints is freed to prevent memory leaks.
This solution effectively employs the backtracking technique characterized by its recursive nature to explore multiple configurations, withdrawing decisions that lead to contradictions. Such an approach guarantees exploration of the entire solution space and ensures that the solution, if one exists, will be found.
var sudokuSolver = function (grid) {
const gridSize = 9;
let rowMaps = Array.from({ length: gridSize }, () => new Map());
let columnMaps = Array.from({ length: gridSize }, () => new Map());
let boxMaps = Array.from({ length: gridSize }, () => new Map());
let solved = false;
function getBoxIndex(r, c) {
return Math.floor(r / 3) * 3 + Math.floor(c / 3);
}
function canPlace(num, r, c) {
let possible = !(
rowMaps[r].has(String(num)) ||
columnMaps[c].has(String(num)) ||
boxMaps[getBoxIndex(r, c)].has(String(num))
);
return possible;
}
function placeNum(num, r, c) {
rowMaps[r].set(
String(num),
rowMaps[r].has(String(num)) ? rowMaps[r].get(String(num)) + 1 : 1,
);
columnMaps[c].set(
String(num),
columnMaps[c].has(String(num)) ? columnMaps[c].get(String(num)) + 1 : 1,
);
boxMaps[getBoxIndex(r, c)].set(
String(num),
boxMaps[getBoxIndex(r, c)].has(String(num))
? boxMaps[getBoxIndex(r, c)].get(String(num)) + 1
: 1,
);
grid[r][c] = String(num);
}
function removeNum(num, r, c) {
rowMaps[r].delete(String(num), rowMaps[r].get(String(num)) - 1);
columnMaps[c].delete(String(num), columnMaps[c].get(String(num)) - 1);
boxMaps[getBoxIndex(r, c)].delete(
String(num),
boxMaps[getBoxIndex(r, c)].get(String(num)) - 1,
);
grid[r][c] = ".";
}
function placeNext(r, c) {
if (c === gridSize - 1 && r === gridSize - 1) solved = true;
else {
if (c === gridSize - 1) solveNext(r + 1, 0);
else solveNext(r, c + 1);
}
}
function solveNext(r = 0, c = 0) {
if (grid[r][c] === ".") {
for (let num = 1; num <= 9; num++) {
if (canPlace(num, r, c)) {
placeNum(num, r, c);
placeNext(r, c);
if (!solved) removeNum(num, r, c);
}
}
} else placeNext(r, c);
}
for (let r = 0; r < gridSize; r++)
for (let c = 0; c < gridSize; c++)
if (grid[r][c] !== ".") placeNum(parseInt(grid[r][c]), r, c);
solveNext();
};
The JavaScript solution for the Sudoku Solver problem involves setting up a function sudokuSolver which takes a grid as an argument, representing the 9x9 Sudoku board. This implementation employs backtracking and efficient look-up techniques using maps to keep track of available numbers for each row, column, and 3x3 box.
Here's how the function and its auxiliary components operate:
Initialization:
- The grid size is set to 9.
- Three arrays of maps (
rowMaps,columnMaps,boxMaps) are created to monitor the numbers used in each row, column, and box.
Helper Functions:
getBoxIndex(r, c): Calculates which of the 9 boxes a cell belongs to.canPlace(num, r, c): Checks if a number can be legally placed in a given cell.placeNum(num, r, c): Places a number in the grid and updates the corresponding maps.removeNum(num, r, c): Removes a number from the grid and updates the maps if a placement is found to be incorrect on further moves.placeNext(r, c): Moves to the next cell in the grid, handling row transitions and marking the puzzle as solved when the end is reached.solveNext(r, c): Attempts to solve the puzzle by trying to place every possible number in the current empty cell.
Process Flow:
- Initially, populate the maps with the numbers already present in the grid.
- Begin the recursive solution process starting from the top-left corner of the grid using
solveNext.
This technique not only systematically attempts all possible placements (backtracking) but also ensures that any move made does not violate Sudoku rules, utilizing checking mechanisms that provide O(1) time complexity due to the use of maps. Once the end of the grid is reached and all cells are correctly filled, the puzzle is marked as solved.
from collections import defaultdict
class SudokuSolver:
def solve(self, grid):
def is_valid(number, r, c):
return not (
number in row_track[r]
or number in col_track[c]
or number in box_track[get_box_index(r, c)]
)
def put_number(number, r, c):
row_track[r][number] += 1
col_track[c][number] += 1
box_track[get_box_index(r, c)][number] += 1
grid[r][c] = str(number)
def remove_number(number, r, c):
row_track[r][number] -= 1
col_track[c][number] -= 1
box_track[get_box_index(r, c)][number] -= 1
if row_track[r][number] == 0:
del row_track[r][number]
if col_track[c][number] == 0:
del col_track[c][number]
if box_track[get_box_index(r, c)][number] == 0:
del box_track[get_box_index(r, c)][number]
grid[r][c] = "."
def place_next(r, c):
if c == N - 1 and r == N - 1:
solution_found[0] = True
elif c == N - 1:
search(r + 1, 0)
else:
search(r, c + 1)
def search(r=0, c=0):
if grid[r][c] == ".":
for num in range(1, 10):
if is_valid(num, r, c):
put_number(num, r, c)
place_next(r, c)
if solution_found[0]:
return
remove_number(num, r, c)
else:
place_next(r, c)
n = 3
N = n * n
get_box_index = lambda r, c: (r // n) * n + c // n
row_track = [defaultdict(int) for _ in range(N)]
col_track = [defaultdict(int) for _ in range(N)]
box_track = [defaultdict(int) for _ in range(N)]
for i in range(N):
for j in range(N):
if grid[i][j] != ".":
num = int(grid[i][j])
put_number(num, i, j)
solution_found = [False]
search()
This code implements a Sudoku Solver in Python 3 using a backtracking algorithm, which is a type of depth-first search. Key features include checking the validity of a number in a given position, placing and removing numbers, and navigating through the grid for a solution. Here is a breakdown of the main components and their functionalities:
Checking Validity (
is_validfunction): This function checks whether placing a certain number in a specified row and column violates Sudoku rules. It ensures the number isn't already present in the same row, column, or the corresponding 3x3 box.Placing and Removing Numbers (
put_numberandremove_numberfunctions): These functions handle adding and removing numbers from the grid. When adding, numbers are updated in the 'grid' and tracked using dictionaries (row_track,col_track, andbox_track) to efficiently check for conflicts in future placements. Removing a number reverses this process and also handles the cleanup of tracking dictionaries for numbers that drop to a count of zero.Navigation Through Grid (
place_nextandsearchfunctions):place_nextdecides the next cell to attempt to fill, moving rightward across rows and downward at the end of rows. Thesearchfunction uses recursion to try each number (1-9) in empty cells and proceeds viaplace_next. If a dead-end is reached where no numbers are valid, it backtracks by removing the last placed number throughremove_number.Initialization: Before starting the backtracking process, the grid is prepared by initializing tracking dictionaries one for each row, column, and box. These dictionaries track counts of each number to quickly assess placement validity during the search. The solver function initializes this process after setting up initial known values from the provided 'grid'.
This solver functionally decomposes the problem into manageable parts, integrating backtracking for a comprehensive solution to the Sudoku puzzle. The strategy focuses on systematic trial and error, leveraging the constraints of Sudoku to efficiently prune the search space and find the solution.
No comments yet.