Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

Write a program in c++ to solve a Sudoku puzzle by filling the empty cells. A sudoku…

  1. User

    Write a program in c++ to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules:

    Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the nine 3x3 sub-grids that compose the grid must contain all of the digits from 1 to 9. The program should return the completed Sudoku board.

  2. Assistant

    Here is a C++ program that solves a Sudoku puzzle using a backtracking algorithm:

    #include <iostream>
    using namespace std;
    
    #define UNASSIGNED 0
    #define N 9
    
    bool isSafe(int grid[N][N], int row, int col, int num) {
        // Check if 'num' is already placed in current row
        for (int i = 0; i < N; i++) {
            if (grid[row][i] == num) {
                return false;
            }
        }
        
        // Check if 'num' is already placed in current column
        for (int i = 0; i < N; i++) {
            if (grid[i][col] == num) {
                return false;
            }
        }
        
        // Check if 'num' is already placed in current 3x3 sub-grid
        int startRow = row - row % 3;
        int startCol = col - col % 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[startRow + i][startCol + j] == num) {
                    return false;
                }
            }
        }
        
        // If 'num' is not already placed in current row, column or sub-grid, it is safe to place 'num' in the current cell
        return true;
    }
    
    bool findEmptyCell(int grid[N][N], int& row, int& col) {
        // Find the first empty cell in the grid
        for (row = 0; row < N; row++) {
            for (col = 0; col < N; col++) {
                if (grid[row][col] == UNASSIGNED) {
                    return true;
                }
            }
        }
        
        // If no empty cell is found, it means the grid is solved
        return false;
    }
    
    bool solveSudoku(int grid[N][N]) {
        int row, col;
        
        // Check if all cells are filled
        if (!findEmptyCell(grid, row, col)) {
            return true;
        }
        
        // Try all possible numbers in the empty cell
        for (int num = 1; num <= 9; num++) {
            if (isSafe(grid, row, col, num)) {
                // Place the number in the current cell
                grid[row][col] = num;
                
                // Recur to solve the remaining grid
                if (solveSudoku(grid)) {
                    return true;
                }
                
                // If the current number doesn't lead to a solution, undo the current cell and try the next number
                grid[row][col] = UNASSIGNED;
            }
        }
        
        // If no number in the range [1, 9] leads to a solution, backtrack to the previous cell
        return false;
    }
    
    void displayGrid(int grid[N][N]) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cout << grid[i][j] << " ";
            }
            cout << endl;
        }
    }
    
    int main() {
        int grid[N][N] = {
            {3, 0, 6, 5, 0, 8, 4, 0, 0},
            {5, 2, 0, 0, 0, 0, 0, 0, 0},
            {0, 8, 7, 0, 0, 0, 0, 3, 1},
            {0, 0, 3, 0, 1, 0, 0, 8, 0},
            {9, 0, 0, 8, 6, 3, 0, 0, 5},
            {0, 5, 0, 0, 9, 0, 6, 0, 0},
            {1, 3, 0, 0, 0, 0, 2, 5, 0},
            {0, 0, 0, 0, 0, 0, 0, 7, 4},
            {0, 0, 5, 2, 0, 6, 3, 0, 0}
        };
        
        if (solveSudoku(grid)) {
            cout << "Sudoku solved.\n";
            displayGrid(grid);
        }
        else {
            cout << "No solution exists.\n";
        }
        
        return 0;
    }
    

    In this program, we define a solveSudoku function that uses a backtracking algorithm to solve the Sudoku puzzle. The function iterates over each empty cell and tries all possible numbers in that cell. It checks if the number is safe to place in the current row, column, and 3x3 sub-grid. If a number is found to be safe, it is placed in the cell and the function recursively calls itself to solve the remaining grid. If a solution is found, it returns true. Otherwise, it backtracks and tries the next number. If no number in the range [1, 9] leads to a solution, the function returns false.

    The main function initializes a Sudoku grid and calls the solveSudoku function to solve it. If a solution is found, it displays the solved Sudoku grid. Otherwise, it prints that no solution exists.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.