A while ago, someone online claimed to have solved the hardest 数独 or something, and a crowd cheered below. I looked at the so-called problem—it was nothing more than an ordinary 9×9 puzzle, something a machine can easily brute-force. It feels incredible—in this information age, anything a computer can easily brute-force doesn't count as a hard problem. It's fine as a casual pastime, but presenting it as an academic achievement to show off is a bit... like sitting in a well looking at the sky.

While working on my real task, debugging was frustrating, so I casually wrote a Sudoku solver to restore my mental and physical health.

The rules of Sudoku are as follows:

  • In the 9*9 empty cells, fill in one of the nine digits 1–9
  • The nine digits in each row and each column must not repeat.
  • Divide the 9*9 area into 3*3 regions of 3*3 cells each; digits within each region must not repeat.

Implementation is as follows:

1. No duplicates in each row

During initialization, unfilled positions are 0, so they won't affect other data.

Then keep the row coordinate fixed and try the column coordinates one by one; if none match, it means the value can be used.

C
int Horizontal(int a[9][9],int abscissa,int ordinate,int test)
{
	int i;
	for(i=0;i<9;i++)
		if(a[abscissa][i] == test)return 0;
	return 1;
}

2. No duplicates in each column

No duplicates in each column is actually similar to no duplicates in each row; the only difference is that one keeps the row coordinate fixed and the other keeps the column coordinate fixed.

C
int Vertical(int a[9][9],int abscissa,int ordinate,int test)
{
	int i;
	for(i=0;i<9;i++)
		if(a[i][ordinate] == test) return 0;
	return 1;
}

3. No duplicates in the small region

First, check the region where the cell to be tested is located (essentially 3 regions horizontally and 3 regions vertically).

Then compare, same as the previous two checks.

C
int Area(int a[9][9],int abscissa,int ordinate,int test)
{
	int i,j;
	int absMin = (abscissa/3)*3;
	int absMax = (abscissa/3+1)*3;
	int ordMin = (ordinate/3)*3;
	int ordMax = (ordinate/3+1)*3;
	for(i=absMin;i<absMax;i++)
		for(j=ordMin;j<ordMax;j++)
			if(test == a[i][j]) return 0;
	return 1;
}

4. Recursive trial

The input is a half-filled array and an offset. The offset ranges from 0 to 80, for a total of 81 positions. If it exceeds this, it means we've perfectly finished; otherwise, continue checking.

If it's non-zero, recursively call itself to fill the next offset; otherwise, try each digit from 1 to 9 to see if it can be placed. If it can, fill it in; otherwise, clear the current cell and test the next digit. Continue until a valid digit is found or it's finally determined that this path won't work, then return true or false.

C
inline int AllDone(int a[9][9],int abscissa,int ordinate,int test)
{
	if(!Horizontal(a,abscissa,ordinate,test)) return 0;
	if(!Vertical(a,abscissa,ordinate,test)) return 0;
	if(!Area(a,abscissa,ordinate,test)) return 0;
	return 1;
}

int nextData(int a[9][9],int offset)
{
	if(offset >= 81) return 1;
	int i;
	int abs = offset/9;
	int ord = offset%9;
	if(a[abs][ord]!=0)
	{
		return nextData(a,offset+1);
	}
	for(i=1;i<10;i++)
	{
		if(AllDone(a,abs,ord,i))
		{
			a[abs][ord] = i;
			if(nextData(a,offset+1))
			{
				return 1;
			}
		}
		a[abs][ord] = 0;
	}
	return 0;
}

5. Output

As stated. The output is just simple console output.

Print 9 numbers per line, for 9 lines.

C
int output(int a[9][9])
{
	int i,j;
	for(i=0;i<9;i++)
	{
		for(j=0;j<9;j++)
			printf("%d ",a[i][j]);
		printf("\n");
	}
	return 1;		
}

6. main function

The main function reads 9×9 numbers, then starts the recursion.

If it can't be solved, display no solution; otherwise, display the solution.

C
int main()
{
	int a[9][9];
	int i;
	int j;
	memset(a,0,sizeof(a));
	for(i=0;i<9;i++)
	{
		for(j=0;j<9;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	if(nextData(a,0))
	{
		printf("get result:\n");
		output(a);
	}else
	{
		printf("no result.\n");
	}
	return 0;
}

Of course, some parameters in the parameter list are unused; I'll fix that later, since this isn't the real work I'm doing anyway.

Output Test

Bash
[yu@argcandargv-com Sudoku]$ make run 
INPUT:
0 0 0 0 0 0 4 5 0
0 0 7 0 0 0 3 0 0
1 0 9 0 6 0 0 0 0
3 0 0 0 0 0 0 0 0
5 0 0 4 0 0 0 0 0
0 0 0 0 7 0 0 0 9
0 0 1 2 0 0 0 0 0
0 0 0 3 0 0 0 0 0
0 0 6 0 0 0 0 0 7
OUTPUT:
get result:
8 6 3 7 9 2 4 5 1 
2 5 7 1 8 4 3 9 6 
1 4 9 5 6 3 8 7 2 
3 9 8 6 2 1 7 4 5 
5 7 2 4 3 9 6 1 8 
6 1 4 8 7 5 2 3 9 
9 8 1 2 4 7 5 6 3 
7 2 5 3 1 6 9 8 4 
4 3 6 9 5 8 1 2 7 

CORRECT?

The project is located here:

[github_widget repo="yuikns/Sudoku"]

If anyone is interested, feel free to take it and play around.

It should be noted that this is purely brute-force. There are many easy ways to optimize it, but I simply didn't do so.

In addition, LeetCode also has a problem about Sudoku, and I've prepared a solution for it here.