Write a program in c++ to solve a Sudoku puzzle by filling the empty cells. A sudoku…
- 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.
- 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
solveSudokufunction 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
mainfunction initializes a Sudoku grid and calls thesolveSudokufunction to solve it. If a solution is found, it displays the solved Sudoku grid. Otherwise, it prints that no solution exists.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.