LightOJ 1397 ( Sudoku Solver )

Problem link: http://www.lightoj.com/volume_showproblem.php?problem=1397

In this problem we have to solve a Sudoku with the given data. It can be solved in naive way by adding a little optimization.

What we do first for solving a Sudoku in newspapers or in any game ? We search for the 3×3 box, a row or a column in which maximum data is given. Then we continue assuming values form there. It reduces recursion call with wrong assumption which can’t make solution. In FindPos() function I have checked which empty cell contains less valid value, that means less probability of facing wrong path to solution.

Code:

	#include <bits/stdc++.h>
	using namespace std;
	int box[9][9];
	void print()
	{
	for (int row = 0; row < 9; row++)
	{
	for (int col = 0; col < 9; col++)
	{
	printf("%d",box[row][col]);
	}
	printf("\n");
	}
	}
	bool isSafe(int row,int col, int num)
	{
	if(box[row][col]!=0)
	return false;
	for (int i = 0; i < 9; i++)
	{
	if (box[row][i] == num || box[i][col] == num)
	{
	return false;
	}
	}
	int start_row=(row/3)*3,start_col=(col/3)*3;
	for (int i = 0; i < 3; i++)
	{
	for (int j = 0; j < 3; j++)
	{
	if (box[start_row + i][start_col + j] == num)
	{
	return false;
	}
	}
	}
	return true;
	}
	bool FindPos(int &row, int &col)
	{
	int mn=100000,cnt=0;
	for (int i = 0; i < 9; i++)
	{
	for (int j = 0; j < 9; j++)
	{
	if(box[i][j]!=0)
	continue;
	cnt=0;
	for(int k=1;k<=9;k++)
	{
	if (isSafe(i,j,k))
	cnt++;
	}
	if(cnt<mn)
	{
	mn=cnt;
	row=i;
	col=j;
	}
	}
	}
	if(mn<10)
	return true;
	return false;
	}
	bool call()
	{
	int row, col,mx=100,cnt=0;
	if (!FindPos(row, col))
	return true;
	for (int num = 1; num <= 9; num++)
	{
	if (isSafe(row, col, num))
	{
	box[row][col] = num;
	if (call())
	return true;
	box[row][col] = 0;
	}
	}
	return false;
	}
	int main()
	{
	int t,id=1,i,n,m,j;
	scanf("%d",&t);
	char ch;
	while(id<=t)
	{
	for (int i = 0; i < 9; ++i)
	{
	for (int j = 0; j < 9; ++j)
	{
	cin >> ch;
	if (ch == '.')
	box[i][j] = 0;
	else {
	box[i][j] = ch -48;
	}
	}
	}
	call();
	printf("Case %d:\n",id++);
	print();
	}
	return 0;
	}

view raw lightoj1397.cpp hosted with ❤ by GitHub

“For every complex problem there is an answer that is clear, simple, and wrong“

— H. L. Mencken