← Back to DSA Course | Chapter 8: Recursion & Backtracking | Lesson 6 of 7

Sudoku Solver कैसे बनाएँ

एक Sudoku solver एक number try करके एक puzzle grid भरने जैसा है, और अगर यह बाद में एक clash का कारण बने, इसे मिटाकर अगला try करता है।

In this page:

  1. Sudoku Basics
  2. Safe Cell
  3. Backtracking Solver
  4. Validation
  5. Practice
Syntax
markup 
def solve(board):
    cell = find_empty(board)
    if not cell:
        return True
    row, col = cell
    for digit in range(1, 10):
        if is_safe(board, row, col, digit):
            board[row][col] = digit
            if solve(board):
                return True
            board[row][col] = 0    # backtrack
    return False

Sudoku Basics

Sudoku एक 9x9 grid पर खेला जाता है जो नौ 3x3 boxes में बंटा है, और एक valid solution हर cell को digits 1 से 9 से इस तरह भरती है कि कोई digit किसी भी row, column, या box में न दोहराए। इसे algorithmically solve करना एक heavily constrained grid पर backtracking का direct application है।

उदाहरण: Sudoku Basics

#include <iostream>
using namespace std;
int main() {
	cout << "A 9x9 grid split into nine 3x3 boxes, digits 1-9, no repeats in any row/col/box";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("A 9x9 grid split into nine 3x3 boxes, digits 1-9, no repeats in any row/col/box");
	}
}
print("A 9x9 grid split into nine 3x3 boxes, digits 1-9, no repeats in any row/col/box")
#include <stdio.h>
int main() {
	printf("A 9x9 grid split into nine 3x3 boxes, digits 1-9, no repeats in any row/col/box");
	return 0;
}

Safe Cell

एक digit किसी cell में रखने के लिए सिर्फ तब safe है जब यह पहले से उस cell की row, उस cell के column, या उस cell के 3x3 box में कहीं और न दिखे — सभी तीन checks का pass होना ज़रूरी है इससे पहले कि एक digit को वहां valid माना जाए।

उदाहरण: Safe Cell

#include <iostream>
using namespace std;
bool isSafe(int grid[9][9], int row, int col, int num) {
	for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return false;
	int br = row - row % 3, bc = col - col % 3;
	for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
		if (grid[br + i][bc + j] == num) return false;
	return true;
}
int main() {
	int grid[9][9] = {0};
	grid[0][1] = 5;
	cout << (isSafe(grid, 0, 3, 5) ? "Safe" : "Not safe");
	return 0;
}
public class Main {
	static boolean isSafe(int[][] grid, int row, int col, int num) {
		for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return false;
		int br = row - row % 3, bc = col - col % 3;
		for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
			if (grid[br + i][bc + j] == num) return false;
		return true;
	}
	public static void main(String[] args) {
		int[][] grid = new int[9][9];
		grid[0][1] = 5;
		System.out.println(isSafe(grid, 0, 3, 5) ? "Safe" : "Not safe");
	}
}
def is_safe(grid, row, col, num):
    for i in range(9):
        if grid[row][i] == num or grid[i][col] == num:
            return False
    br, bc = row - row % 3, col - col % 3
    for i in range(3):
        for j in range(3):
            if grid[br + i][bc + j] == num:
                return False
    return True

grid = [[0] * 9 for _ in range(9)]
grid[0][1] = 5
print("Safe" if is_safe(grid, 0, 3, 5) else "Not safe")
#include <stdio.h>
int isSafe(int grid[9][9], int row, int col, int num) {
	for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return 0;
	int br = row - row % 3, bc = col - col % 3;
	for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
		if (grid[br + i][bc + j] == num) return 0;
	return 1;
}
int main() {
	int grid[9][9] = {0};
	grid[0][1] = 5;
	printf(isSafe(grid, 0, 3, 5) ? "Safe" : "Not safe");
	return 0;
}

Backtracking Solver

Solver अगली खाली cell के लिए scan करता है, इसके लिए हर safe digit try करता है, और बाकी grid भरने के लिए recurse करता है; अगर एक branch एक ऐसी state की ओर ले जाए जहां बाकी puzzle पूरा नहीं हो सकता, यह digit undo करता है और अगला try करता है। यह choose, recurse, undo के general backtracking pattern को mirror करता है।

उदाहरण: Backtracking Solver

#include <iostream>
using namespace std;
bool isSafe(int grid[9][9], int row, int col, int num) {
	for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return false;
	int br = row - row % 3, bc = col - col % 3;
	for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
		if (grid[br + i][bc + j] == num) return false;
	return true;
}
bool solve(int grid[9][9], int row, int col) {
	if (row == 9) return true;
	if (col == 9) return solve(grid, row + 1, 0);
	if (grid[row][col] != 0) return solve(grid, row, col + 1);
	for (int num = 1; num <= 9; num++) {
		if (isSafe(grid, row, col, num)) {
			grid[row][col] = num;
			if (solve(grid, row, col + 1)) return true;
			grid[row][col] = 0;
		}
	}
	return false;
}
int main() {
	int grid[9][9] = {0};
	cout << (solve(grid, 0, 0) ? "Solved" : "No solution");
	return 0;
}
public class Main {
	static boolean isSafe(int[][] grid, int row, int col, int num) {
		for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return false;
		int br = row - row % 3, bc = col - col % 3;
		for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
			if (grid[br + i][bc + j] == num) return false;
		return true;
	}
	static boolean solve(int[][] grid, int row, int col) {
		if (row == 9) return true;
		if (col == 9) return solve(grid, row + 1, 0);
		if (grid[row][col] != 0) return solve(grid, row, col + 1);
		for (int num = 1; num <= 9; num++) {
			if (isSafe(grid, row, col, num)) {
				grid[row][col] = num;
				if (solve(grid, row, col + 1)) return true;
				grid[row][col] = 0;
			}
		}
		return false;
	}
	public static void main(String[] args) {
		int[][] grid = new int[9][9];
		System.out.println(solve(grid, 0, 0) ? "Solved" : "No solution");
	}
}
def is_safe(grid, row, col, num):
    for i in range(9):
        if grid[row][i] == num or grid[i][col] == num:
            return False
    br, bc = row - row % 3, col - col % 3
    for i in range(3):
        for j in range(3):
            if grid[br + i][bc + j] == num:
                return False
    return True

def solve(grid, row, col):
    if row == 9:
        return True
    if col == 9:
        return solve(grid, row + 1, 0)
    if grid[row][col] != 0:
        return solve(grid, row, col + 1)
    for num in range(1, 10):
        if is_safe(grid, row, col, num):
            grid[row][col] = num
            if solve(grid, row, col + 1):
                return True
            grid[row][col] = 0
    return False

grid = [[0] * 9 for _ in range(9)]
print("Solved" if solve(grid, 0, 0) else "No solution")
#include <stdio.h>
int isSafe(int grid[9][9], int row, int col, int num) {
	for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return 0;
	int br = row - row % 3, bc = col - col % 3;
	for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
		if (grid[br + i][bc + j] == num) return 0;
	return 1;
}
int solve(int grid[9][9], int row, int col) {
	if (row == 9) return 1;
	if (col == 9) return solve(grid, row + 1, 0);
	if (grid[row][col] != 0) return solve(grid, row, col + 1);
	for (int num = 1; num <= 9; num++) {
		if (isSafe(grid, row, col, num)) {
			grid[row][col] = num;
			if (solve(grid, row, col + 1)) return 1;
			grid[row][col] = 0;
		}
	}
	return 0;
}
int main() {
	int grid[9][9] = {0};
	printf(solve(grid, 0, 0) ? "Solved" : "No solution");
	return 0;
}

Validation

एक properly completed Sudoku grid को एक साथ हर row, हर column, और हर 3x3 box में uniqueness satisfy करनी चाहिए — एक finished (या partially finished) grid validate करने का मतलब है यह मानने के बजाय कि solver ने इसे सही किया कि हर जगह यही तीन checks चलाना।

उदाहरण: Validation

#include <iostream>
using namespace std;
bool rowHasDuplicate(int row[9]) {
	bool seen[10] = {false};
	for (int i = 0; i < 9; i++) {
		if (row[i] != 0) {
			if (seen[row[i]]) return true;
			seen[row[i]] = true;
		}
	}
	return false;
}
int main() {
	int row[9] = {5, 3, 0, 0, 7, 0, 0, 0, 5};
	cout << (rowHasDuplicate(row) ? "Invalid row" : "Valid row");
	return 0;
}
public class Main {
	static boolean rowHasDuplicate(int[] row) {
		boolean[] seen = new boolean[10];
		for (int v : row) {
			if (v != 0) {
				if (seen[v]) return true;
				seen[v] = true;
			}
		}
		return false;
	}
	public static void main(String[] args) {
		int[] row = {5, 3, 0, 0, 7, 0, 0, 0, 5};
		System.out.println(rowHasDuplicate(row) ? "Invalid row" : "Valid row");
	}
}
def row_has_duplicate(row):
    seen = set()
    for v in row:
        if v != 0:
            if v in seen:
                return True
            seen.add(v)
    return False

row = [5, 3, 0, 0, 7, 0, 0, 0, 5]
print("Invalid row" if row_has_duplicate(row) else "Valid row")
#include <stdio.h>
int rowHasDuplicate(int row[9]) {
	int seen[10] = {0};
	for (int i = 0; i < 9; i++) {
		if (row[i] != 0) {
			if (seen[row[i]]) return 1;
			seen[row[i]] = 1;
		}
	}
	return 0;
}
int main() {
	int row[9] = {5, 3, 0, 0, 7, 0, 0, 0, 5};
	printf(rowHasDuplicate(row) ? "Invalid row" : "Valid row");
	return 0;
}

Practice

Sudoku इस course के पहले के तीन ideas को एक साथ जोड़ता है: choices try और undo करने के लिए recursive backtracking, invalid branches जल्दी prune करने के लिए constraint checking, और यह track करने के लिए careful bookkeeping कि हर row, column, और box में कौन से digits पहले से उपयोग हो चुके हैं।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Sudoku combines backtracking, constraint checking, and pruning to fill the grid";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Sudoku combines backtracking, constraint checking, and pruning to fill the grid");
	}
}
print("Sudoku combines backtracking, constraint checking, and pruning to fill the grid")
#include <stdio.h>
int main() {
	printf("Sudoku combines backtracking, constraint checking, and pruning to fill the grid");
	return 0;
}
Related Topics

N-Queens समस्या · Subset Generation कैसे करें · Backtracking परिचय · Tower of Hanoi समस्या

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. सिर्फ row और column जांचना और 3x3 box भूल जाना।
  2. Box start गलत compute करना, जैसे row / 3 के बजाय row - row % 3।
  3. एक guess fail होने पर cell को वापस 0 सेट न करना, इसलिए गलत digit grid पर रह जाता है।
🔒

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson N-Queens Problem Next Lesson → Subset Generation

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.