1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
|
#include <iostream>
using namespace std;
void print_board (int board[][10]);
bool isFinished (int board[][10]);
bool isNumValid (int board[][10], int row, int col, int num);
int main()
{
// Initialize "board" array
int board[10][10] = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 7, 9, 6, 0, 0, 0, 3, 0, 0},
{0, 0, 0, 0, 0, 0, 6, 9, 0, 0},
{0, 8, 0, 0, 0, 3, 0, 0, 7, 6},
{0, 0, 0, 0, 0, 0, 5, 0, 0, 2},
{0, 0, 0, 5, 4, 1, 8, 7, 0, 0},
{0, 4, 0, 0, 7, 0, 0, 0, 0, 0},
{0, 6, 1, 0, 0, 9, 0, 0, 0, 8},
{0, 0, 0, 2, 3, 0, 0, 0, 0, 0},
{0, 0, 0, 9, 0, 0, 0, 1, 5, 4}};
int numValidAnswers, validNum;
do {
for (int i = 1; i <= 9; i++)
{
for (int j = 1; j <= 9; j++)
{
if (board[i][j] == 0) // Empty spot; find a valid number
{
numValidAnswers = 0;
for (int k = 1; k <= 9; k++)
{
if (isNumValid(board, i, j, k))
{
numValidAnswers++;
validNum = k;
}
}
if (numValidAnswers == 1)
{
board[i][j] = validNum;
}
}
}
}
}
while (!isFinished(board));
// Print board
print_board(board);
}
// Prints board according to array "board[10][10]"
void print_board (int board[][10])
{
for(int i = 1; i < 10; i++)
{
for(int j = 1; j < 10; j++)
{
if (board[i][j] == 0) cout << " ";
else cout << board[i][j];
if (j == 3 || j == 6) cout << " | ";
}
cout << endl;
if (i == 3 || i == 6) cout << "---------------" << endl;
}
}
// Check if the board is finished or not
bool isFinished (int board[][10])
{
for (int i = 1; i < 10; i++)
{
for (int j = 1; j < 10; j++)
{
if (board[i][j] == 0) return false;
}
}
return true;
}
// Check if the current number is a valid number
bool isNumValid (int board[][10], int row, int col, int num)
{
// Check row first
for (int i = 1; i < 10; i++)
{
if (board[row][i] == num) return false;
}
// Check column next
for (int i = 1; i < 10; i++)
{
if (board[i][col] == num) return false;
}
// Check subgroup
// Get top row in this subgroup
int topRow = row - ((row - 1) % 3);
int topCol = col - ((row - 1) % 3);
for (int i = topRow; i <= topRow + 2; i++)
{
for (int j = topCol; j <= topCol + 2; j++)
{
if (board[i][j] == num) return false;
}
}
return true;
}
|