Objectives:
- 2-dimensional array
- Writing a popular game solver (albeit using a very simple algorithm on a mini version of the game)
Task:
Sudoku is a popular logic-based number placement puzzle. The 9×9 board has 9 rows, 9 columns and 9 sections of 3×3 cells. The objective is to fill the board so that each row, each column and each section contains the digits from 1 to 9. There is only one unique solution. Figure 1 below, taken from Wikipedia: Sudoku, shows a Sudoku puzzle and its solution.
Figure 1. A Sudoku puzzle and its solution.
In this exercise, we shall solve mini-Sudoku puzzles on a 4×4 board. The board consists of digits from 0 to 4 where 0 represents a blank cell. The solver needs to replace all the 0s with the correct values (1 - 4).
These puzzles are such that at any time, there is at most one blank cell (0) in a certain row, a column, or a 2×2 section. Hence, you are able to fill in the blank cells progressively until the whole board is filled.
One very simple algorithm for solve() is described below. We shall call it algorithm A.
Repeat until no more blank cells can be filled:For each row, check whether there is a single 0. If so, replace that 0 with the obvious value.
For each column, check whether there is a single 0. If so, replace that 0 with the obvious value.
For each 2×2 section, check whether there is a single 0. If so, replace that 0 with the obvious value.
We will use an example to illustrate algorithm A. Figure 2a below shows a puzzle with seven blank cells, labelled from A to G for easy reference.
 |  |  |  |
| Figure 2a. A Sudoku puzzle. | Figure 2b. | Figure 2c. | Figure 2d. The solution. |
After examining each row, we cannot fill in any blank cell as none of the rows has a single blank cell.
We proceed to examine every column. In the first column, we find that we can fill E with 2, and in the fourth column, B with 4, as shown in Figure 2b.
We proceed to examine every 2×2 section. We find that we can fill D with 1, F with 1, and G with 4. See Figure 2c.
The puzzle is still not solved, so we repeat the process. As we examine the rows this time, we find that we are able to fill A with 2, and C with 4. This gives the solution as shown in Figure 2d.
Sample runs:
Sample run using interactive input (user's input shown in blue; output shown in bold purple). Note that the first two lines (in green below) are commands issued to compile and run your program on UNIX.
$ gcc -Wall sudoku.c -o sudoku $ sudoku Enter board (0 for blank cell): 1 0 3 0 3 0 0 2 4 3 2 1 0 0 0 3 Sudoku puzzle solved: 1 2 3 4 3 4 1 2 4 3 2 1 2 1 4 3
Second sample run:
$ sudoku Enter board (0 for blank cell): 0 1 3 2 2 0 1 0 1 0 0 3 3 4 2 1 Sudoku puzzle solved: 4 1 3 2 2 3 1 4 1 2 4 3 3 4 2 1
Solution:
#include <stdio.h>
#define SIZE 4
void readBoard(int [][SIZE]);
void printBoard(int [][SIZE]);
void solve(int [][SIZE]);
int anotherRound(int [][SIZE]);
void checkBox(int [][SIZE], int, int, int, int);
int main(void) {
int board[SIZE][SIZE];
printf("Enter board (0 for blank cell):\n");
readBoard(board);
solve(board); // solve the puzzle now!
printf("Sudoku puzzle solved:\n");
printBoard(board);
return 0;
}
// To read a 4x4 integer array from user.
void readBoard(int board[][SIZE]) {
int r, c;
for (r = 0; r < SIZE; r++) {
for(c = 0; c < SIZE; c++)
scanf("%d", &board[r][c]);
}
}
// To print the 4x4 Sudoku board.
void printBoard(int board[][SIZE]) {
int r, c;
for (r = 0; r < SIZE; r++) {
for (c = 0; c < SIZE; c++)
printf("%d ", board[r][c]);
printf("\n");
}
}
// Solving a Sudoku puzzle using a very simple
// algorithm (algorithm A in the write-up).
// It only solves the simplest puzzles.
void solve(int board[][SIZE]) {
int blankCellFound; // indicate whether there is still some blank cell
do {
blankCellFound = anotherRound(board);
} while (blankCellFound);
}
// Apply loop body of algorithm A and return 1 if there are still
// blank cells, or 0 if there is no more blank cell.
int anotherRound(int board[][SIZE]) {
int r, c,
sum, // Sum of elements in a row or column
countZero; // Number of zeroes in a row or column
// Check every row
for (r = 0; r < SIZE; r++) {
sum = 0;
countZero = 0;
for (c = 0; c < SIZE; c++) {
if (board[r][c] == 0)
countZero++;
else
sum += board[r][c];
}
if (countZero == 1) { // A single zero is present
for (c = 0; c < SIZE; c++) { // To find the position of the single zero
if (board[r][c] == 0) {
board[r][c] = 10 - sum; // Replace the single zero with the obvious value
break;
}
}
}
}
// Check every column
for (c = 0; c < SIZE; c++) {
sum = 0;
countZero = 0;
for (r = 0; r < SIZE; r++) {
if (board[r][c] == 0)
countZero++;
else
sum += board[r][c];
}
if (countZero == 1) { // A single zero is present
for (r = 0; r < SIZE; r++) { // To find the position of the single zero
if (board[r][c] == 0) {
board[r][c] = 10 - sum; // Replace the single zero with the obvious value
break;
}
}
}
}
// Check every box
checkBox(board, 0, 2, 0, 2);
checkBox(board, 0, 2, 2, 4);
checkBox(board, 2, 4, 0, 2);
checkBox(board, 2, 4, 2, 4);
// Check if there are any blank cells
for (r = 0; r < SIZE; r++) {
for (c = 0; c < SIZE; c++) {
if (board[r][c] == 0) // Blank cell found
return 1;
}
}
return 0; // No blank cell
}
// This function checks a 2X2 box if there is a single zero.
// If so, it replaces the zero with the obvious value.
// Precond: lrow <= urow, lcol <= ucol, 0 <= lrow, urow, lcol, ucol <= SIZE
void checkBox(int board [][SIZE], int lrow, int urow, int lcol, int ucol) {
int r, c,
sum = 0, // Sum of elements in the 2X2 box
countZero = 0; // Number of zeroes in the 2X2 box
for (r = lrow; r < urow; r++) { // lrow and urow are the lower and upper limits of the rows
for (c = lcol; c < ucol; c++) { // lcol and ucol are the lower and upper limits of the columns
if (board[r][c] == 0)
countZero++;
else
sum += board[r][c];
}
}
if (countZero == 1) { // A single zero is present
for (r = lrow; r < urow; r++) {
for (c = lcol; c < ucol; c++) { // To find the position of the single zero
if (board[r][c] == 0) {
board[r][c] = 10 - sum; // Replace the single zero with the obvious value
break;
}
}
}
}
}
