1. Runtime Distribution

2. Submission Details

3. Description

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

4. Example

5. Explanation

1. We could replace '.' one by one with a digit that is compatible, if we can't find a compatible digit for a cube, we backtrace to a cube and fill it with another compatible digit. if we have replace all '.' with a compatible digit, we get a solution
2. The key point is which '.' should we replace first? we should first replace intuitively a '.' which has the fewest compatible digit. why? let‘s say，we chosed a digit for the first '.' and finally we find it is a wrong digit, we have to traceback to this first '.', it would be painfully inefficient, so, we should first replace a '.' which we are most likely choose a right digit for it. The fewer compatible digits the '.' has, the more likely we can choose a right digits for it.

6. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C 0ms" active="active"]

#define MASK 0x01FF

typedef struct record 
{
	int row, col, block;
} record;

typedef struct bitMark 
{
	int row, col, block;
} bitMark;

record rec[81];
bitMark marks[9];
int num = 0;

int findNextToBeHandledPoint(int index)
{
	int min = INT_MAX, tobeHandle = index;
	for (int i = index; i < num; i++)
	{
		int possible = marks[rec[i].row].row & marks[rec[i].col].col & marks[rec[i].block].block;
		int bitCount = 0;
		for (; possible; possible &= possible - 1, bitCount++);
		if (bitCount < min)
		{
			min = bitCount;
			tobeHandle = i;
		}
	}
	return tobeHandle;
}

bool solve(char **board, int index)
{
	if (index >= num)
	{
		return true;
	}
	int tobeHandle = findNextToBeHandledPoint(index);

	record tmp = rec[tobeHandle];
	rec[tobeHandle] = rec[index];
	rec[index] = tmp;

	int possible = marks[rec[index].row].row & marks[rec[index].col].col & marks[rec[index].block].block;
	while (possible)
	{
		int valbit = possible & -possible;
		int reverseValbit = ~valbit;

		possible &= reverseValbit;
		marks[rec[index].row].row &= reverseValbit;
		marks[rec[index].col].col &= reverseValbit;
		marks[rec[index].block].block &= reverseValbit;

		board[rec[index].row][rec[index].col] = log2(valbit) + '1';

		if (solve(board, index + 1))
		{
			return true;
		}
		marks[rec[index].row].row |= valbit;
		marks[rec[index].col].col |= valbit;
		marks[rec[index].block].block |= valbit;
	}

	board[rec[index].row][rec[index].col] = '.';
	return false;
}

void solveSudoku(char **board, int m, int n)
{
	for (int i = 0; i < 9; i++)
	{
		marks[i].row = MASK;
		marks[i].col = MASK;
		marks[i].block = MASK;
	}
	num = 0;
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			if (board[i][j] == '.')
			{
				rec[num].row = i;
				rec[num].col = j;
				rec[num++].block = i / 3 * 3 + j / 3;
			}
			else
			{
				int mark = ~(1 << board[i][j] - '1');
				marks[i].row &= mark;
				marks[j].col &= mark;
				marks[i / 3 * 3 + j / 3].block &= mark;
			}
		}
	}
	solve(board, 0);
}

[/restab]
[restab title="C 13ms"]

#include

bool isValid(char** board, int row, int colum, char num)
{
	int subCubeStartRow = 3 * (row / 3), subCubeStartColum = 3 * (colum / 3);
	for (int i = 0; i < 9; i++) {
		if (board[row][i] == num || board[i][colum] == num)
		{
			return false;
		}
		if (board[subCubeStartRow + i / 3][subCubeStartColum + i % 3] == num) return false;
	}
	return true;
}

bool solver(char** board, int row, int column)
{
	if (row == 9) return true;
	if (board[row][column] != '.') return solver(board, column + 1 == 9 ? row + 1 : row, (column + 1) % 9);
	for (char a = '1'; a <= '9'; a++)
	{
		if (isValid(board, row, column, a))
		{
			board[row][column] = a;
			if (solver(board, column + 1 == 9 ? row + 1 : row, (column + 1) % 9)) return true;
			board[row][column] = '.';
		}
	}
	return false;
}
void solveSudoku1(char** board, int rSize, int cSize)
{
	solver(board, 0, 0);
}

[/restab]
[/restabs]

7.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

#include 
#include 
#include 
#include 

#define MASK 0x01FF

typedef struct record 
{
	int row, col, block;
} record;

typedef struct bitMark 
{
	int row, col, block;
} bitMark;

record rec[81];
bitMark marks[9];
int num = 0;

int findNextToBeHandledPoint(int index)
{
	int min = INT_MAX, tobeHandle = index;
	for (int i = index; i < num; i++)
	{
		int possible = marks[rec[i].row].row & marks[rec[i].col].col & marks[rec[i].block].block;
		int bitCount = 0;
		for (; possible; possible &= possible - 1, bitCount++);
		if (bitCount < min)
		{
			min = bitCount;
			tobeHandle = i;
		}
	}
	return tobeHandle;
}

bool solve(char **board, int index)
{
	if (index >= num)
	{
		return true;
	}
	int tobeHandle = findNextToBeHandledPoint(index);

	record tmp = rec[tobeHandle];
	rec[tobeHandle] = rec[index];
	rec[index] = tmp;

	int possible = marks[rec[index].row].row & marks[rec[index].col].col & marks[rec[index].block].block;
	while (possible)
	{
		int valbit = possible & -possible;
		int reverseValbit = ~valbit;

		possible &= reverseValbit;
		marks[rec[index].row].row &= reverseValbit;
		marks[rec[index].col].col &= reverseValbit;
		marks[rec[index].block].block &= reverseValbit;

		board[rec[index].row][rec[index].col] = log2(valbit) + '1';

		if (solve(board, index + 1))
		{
			return true;
		}
		marks[rec[index].row].row |= valbit;
		marks[rec[index].col].col |= valbit;
		marks[rec[index].block].block |= valbit;
	}

	board[rec[index].row][rec[index].col] = '.';
	return false;
}

void solveSudoku(char **board, int m, int n)
{
	for (int i = 0; i < 9; i++)
	{
		marks[i].row = MASK;
		marks[i].col = MASK;
		marks[i].block = MASK;
	}
	num = 0;
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			if (board[i][j] == '.')
			{
				rec[num].row = i;
				rec[num].col = j;
				rec[num++].block = i / 3 * 3 + j / 3;
			}
			else
			{
				int mark = ~(1 << board[i][j] - '1');
				marks[i].row &= mark;
				marks[j].col &= mark;
				marks[i / 3 * 3 + j / 3].block &= mark;
			}
		}
	}
	solve(board, 0);
}

int main()
{
	char board[][9] = 
	{
		{ "53..7...." },
		{ "6..195..." },
		{ ".98....6." },
		{ "8...6...3" },
		{ "4..8.3..1" },
		{ "7...2...6" },
		{ ".6....28." },
		{ "...419..5" },
		{ "....8..79" }
	};
	solveSudoku(board, 9, 9);
	for(int i = 0; i< 9; i++)
	{
		for(int j =0; j < 9; j++)
		{
			printf("%c", board[i][j]);
		}
		printf("\n");
	}
	system("pause");
	return 0;
}

[/restab]
[/restabs]