Sudoku Solver Gaming Project in C++

Projects Inventory

3 months ago

#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;
}

#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.
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.
main Function:
- Initializes a Sudoku grid with some cells empty (represented by 0).
- Calls solveSudoku to 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:
  
  C++
  
  g++ sudoku_solver.cpp -o sudoku_solver
  
  1
  
  g++ sudoku_solver.cpp -o sudoku_solver
  
  Run the program with:
  
  C++
  
  ./sudoku_solver
  
  1
  
  ./sudoku_solver

Explanation:

Compilation:

Related Posts: