|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <iostream> #include <vector> const int SIZE = 9; // Size of the Sudoku grid // Function to print the Sudoku grid void printGrid(const std::vector<std::vector<int>>& grid) { for (const auto& row : grid) { for (int num : row) { std::cout << num << ' '; } std::cout << std::endl; } } // Function to check if placing num at grid[row][col] is valid bool isValid(const std::vector<std::vector<int>>& grid, int row, int col, int num) { // Check row for (int c = 0; c < SIZE; ++c) { if (grid[row][c] == num) return false; } // Check column for (int r = 0; r < SIZE; ++r) { if (grid[r][col] == num) return false; } // Check 3x3 subgrid int startRow = row - row % 3; int startCol = col - col % 3; for (int r = startRow; r < startRow + 3; ++r) { for (int c = startCol; c < startCol + 3; ++c) { if (grid[r][c] == num) return false; } } return true; } // Backtracking function to solve the Sudoku bool solveSudoku(std::vector<std::vector<int>>& grid) { for (int row = 0; row < SIZE; ++row) { for (int col = 0; col < SIZE; ++col) { if (grid[row][col] == 0) { // Find an empty cell for (int num = 1; num <= SIZE; ++num) { if (isValid(grid, row, col, num)) { grid[row][col] = num; if (solveSudoku(grid)) return true; grid[row][col] = 0; // Backtrack } } return false; // Trigger backtracking } } } return true; // All cells are filled } int main() { // Example Sudoku grid (0 represents empty cells) std::vector<std::vector<int>> 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} }; if (solveSudoku(grid)) { std::cout << "Sudoku solved successfully!" << std::endl; printGrid(grid); } else { std::cout << "No solution exists!" << std::endl; } return 0; } |
Explanation:
- Constants:
SIZE: Defines the size of the Sudoku grid (9×9).
- printGrid Function:
- Prints the Sudoku grid to the console, showing numbers and spaces.
- isValid Function:
- Checks if placing a number in a specific cell is valid:
- Row Check: Ensures the number is not already in the same row.
- Column Check: Ensures the number is not already in the same column.
- 3×3 Subgrid Check: Ensures the number is not already in the 3×3 subgrid.
- Checks if placing a number in a specific cell is valid:
- solveSudoku Function:
- Uses backtracking to solve the Sudoku puzzle:
- Finds an empty cell (represented by 0).
- Tries placing numbers (1 to 9) in the cell and recursively solves the rest of the grid.
- If placing a number leads to a solution, the function returns
true. - If no number is valid, it backtracks by resetting the cell to 0 and tries the next number.
- Uses backtracking to solve the Sudoku puzzle:
- main Function:
- Initializes a Sudoku grid with some cells empty (represented by 0).
- Calls
solveSudokuto solve the puzzle. - Prints the solved Sudoku grid if a solution is found, or an error message if no solution exists.
Compilation:
To compile the program, use:
Run the program with:1g++ sudoku_solver.cpp -o sudoku_solver
1./sudoku_solver