Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ///****************
- const int n = 9, bn = 3;
- int sudokuGrid[n + 2][n + 2];
- bool usedInRow(int row, int num) {
- for (int i = 0; i < n; i++)
- if (sudokuGrid[row][i] == num)
- return true;
- return false;
- }
- bool usedInCol(int col, int num) {
- for (int i = 0; i < n; i++)
- if (sudokuGrid[i][col] == num)
- return true;
- return false;
- }
- bool usedInBox(int bsRow, int bsCol, int num) {
- for (int i = bsRow; i < bsRow + bn; i++)
- for (int j = bsCol; j < bsCol + bn; j++) {
- if (sudokuGrid[i][j] == num) {
- return true;
- }
- }
- return false;
- }
- bool isSafe(int row, int col, int num) {
- bool e = !usedInRow(row, num);
- e = e && !usedInCol(col, num);
- e = e && !usedInBox(row - row % bn,
- col - col % bn,
- num);
- return e;
- }
- bool findEmptyPlace(int &row, int &col) {
- for (row = 0; row < n; row++)
- for (col = 0; col < n; col++)
- if (!sudokuGrid[row][col])
- return true;
- return false;
- }
- bool solveSudoku() {
- int row, col;
- if (!findEmptyPlace(row, col))
- return true;
- for (int num = 1; num <= n; num++) {
- if (isSafe(row, col, num)) {
- sudokuGrid[row][col] = num;
- if (solveSudoku())
- return true;
- sudokuGrid[row][col] = 0;
- }
- }
- return false;
- }
- void read() {
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- cin >> sudokuGrid[i][j];
- }
- void display(bool ok) {
- if (!ok) {
- puts("IMPOSSIBLE!");
- return;
- }
- cout << string(17, '-') << endl;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++)
- cout << sudokuGrid[i][j] << ' ';
- puts("");
- }
- }
- int main()
- {
- read();
- display(solveSudoku());
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement