fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. #define N 9
  6.  
  7. bool isSafe(int grid[N][N], int row, int col, int num) {
  8.     for (int i = 0; i < N; i++) {
  9.         if (grid[row][i] == num || grid[i][col] == num)
  10.             return false;
  11.     }
  12.  
  13.     int startRow = row - row % 3;
  14.     int startCol = col - col % 3;
  15.     for (int i = 0; i < 3; i++) {
  16.         for (int j = 0; j < 3; j++) {
  17.             if (grid[i + startRow][j + startCol] == num)
  18.                 return false;
  19.         }
  20.     }
  21.  
  22.     return true;
  23. }
  24.  
  25. bool findEmptyLocation(int grid[N][N], int &row, int &col) {
  26.     for (row = 0; row < N; row++) {
  27.         for (col = 0; col < N; col++) {
  28.             if (grid[row][col] == 0) 
  29.                 return true;
  30.         }
  31.     }
  32.     return false; 
  33. }
  34.  
  35. bool solveSudoku(int grid[N][N]) {
  36.     int row, col;
  37.  
  38.     // If there is no empty cell, puzzle is solved
  39.     if (!findEmptyLocation(grid, row, col))
  40.         return true;
  41.  
  42.     for (int num = 1; num <= 9; num++) {
  43.         if (isSafe(grid, row, col, num)) {
  44.             grid[row][col] = num;
  45.  
  46.             if (solveSudoku(grid))
  47.                 return true;
  48.  
  49.             grid[row][col] = 0;
  50.         }
  51.     }
  52.  
  53.     return false;
  54. }
  55.  
  56. void printGrid(int grid[N][N]) {
  57.     for (int row = 0; row < N; row++) {
  58.         for (int col = 0; col < N; col++)
  59.             cout << grid[row][col] << " ";
  60.         cout << endl;
  61.     }
  62. }
  63.  
  64. int main() {
  65.     int grid[N][N];
  66.  
  67.     cout << "Enter the initial Sudoku puzzle (use 0 for empty cells):\n";
  68.     for (int row = 0; row < N; row++) {
  69.         for (int col = 0; col < N; col++) {
  70.             cin >> grid[row][col];
  71.         }
  72.     }
  73.  
  74.     if (solveSudoku(grid))
  75.         printGrid(grid);
  76.     else
  77.         cout << "No solution exists" << endl;
  78.  
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
stdout
copy 
Enter the initial Sudoku puzzle (use 0 for empty cells):
1 2 3 4 5 6 7 8 9 
4 5 6 7 8 9 1 2 3 
7 8 9 1 2 3 4 5 6 
2 1 4 3 6 5 8 9 7 
3 6 5 8 9 7 2 1 4 
8 9 7 2 1 4 3 6 5 
5 3 1 6 4 2 9 7 8 
6 4 2 9 7 8 5 3 1 
9 7 8 5 3 1 6 4 2
https://ideone.com/g6E5T7
language:
C++ (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!