Demo entry 6623993

suduko

   

Submitted by anonymous on Jun 12, 2017 at 17:32
Language: C. Code size: 3.5 kB.

#include<stdio.h>
#include<stdlib.h>
int getSudoku[9][9] ={
	{0,4,0,7,0,0,0,0,0},
	{9,2,0,0,0,0,6,0,7},
	{8,3,0,0,0,5,4,0,0},
	{0,1,0,0,0,3,0,0,0},
	{0,0,0,2,0,1,0,0,0},
	{0,0,0,5,0,0,0,4,0},
	{0,0,4,9,0,0,0,7,1},
	{3,0,5,0,0,0,0,9,4},
	{0,0,0,0,0,8,0,6,0}
};
int prt() //´òÓ¡Êý×é״̬
{
	int i = 0, j = 0;
	for (; i < 9; i++)
	{
		for (; j < 9; j++)
		{
			printf("%d ", getSudoku[i][j]);
		}
		printf("\n");
	}
	//getchar();
}
int getAllSovle(int i, int j, int a[9]) //»ñÈ¡Ò»¸öλÖõ±Ç°µÄËùÓпÉÄܽâ
{
	int s[9] = { 1,2,3,4,5,6,7,8,9 };
	int row, col, k;
	for (col = 0; col < 9; col++)
	{
		k = getSudoku[i][col];  //ɾ³ýµ±Ç°ÐÐÖÐÒѳöÏÖµÄÖµ
		if (k != 0)
		{
			s[k - 1] = 0;
		}
	}
	for (row = 0; row < 9; row++) //ɾ³ýµ±Ç°ÁÐÖÐÒѳöÏÖµÄÖµ
	{
		k = getSudoku[row][j];
		if (k != 0)
		{
			s[k - 1] = 0;
		}
	}
	row = (i / 3) * 3; //ɾ³ýµ±Ç°¾Å¹¬¸ñÖÐÒѳöÏÖµÄÖµ
	col = (j / 3) * 3;
	for (i = row; i < (row + 3); i++)
	{
		for (j = col; j < (col + 3); j++)
		{
			k = getSudoku[i][j];
			if (k != 0)
			{
				s[k - 1] = 0;
			}
		}
	}
	for (k = 0, i = 0; k < 9; k++)
	{
		if (s[k] != 0)
		{
			a[i++] = s[k];
		}
	}
	return i;
}
int checkRow(int i, int num) //Åжϵ±Ç°ÐÐÊÇ·ñºÏ·¨
{
	int j;
	for (j = 0; j < 9; j++)
	{
		if (getSudoku[i][j] == num)
		{
			return 0;
		}
	}
}
int checkCol(int j, int num) //Åжϵ±Ç°ÁÐÊÇ·ñºÏ·¨
{
	int i;
	for (i = 0; i < 9; i++)
	{
		if (getSudoku[i][j] == num)
		{
			return 0;
		}
	}
}
int checkBlock(int i, int j, int num) //Åжϵ±Ç°¾Å¹¬¸ñÊÇ·ñºÏ·¨
{
	int row = (i / 3) * 3;
	int col = (j / 3) * 3;
	int k = 0;
	int l = 0;
	for (k = row; k < (row + 3); k++)
	{
		for (l = col; l < (col + 3); l++)
		{
			if (getSudoku[k][l] == num)
			{
				return 0;
			}
		}
	}
	return 1;
}
int tryOneSolution(int i, int j, int num) //³¢ÊÔÒ»¸ö½â
{
	if (checkRow(i, num) && checkCol(j, num) && checkBlock(i, j, num))
	{
		getSudoku[i][j] = num;
		return 1;
	}
	return 0;
}
int getNextSolution(int *pi, int *pj) //»ñÈ¡ÏÂÒ»¸öÒªÌî¿ÕµÄλÖÃ
{
	int i = *pi;
	int j = *pj;
	int row = i;
	int col = 0;
	j++;
	for (; row < 9; row++)
	{
		for (col = j; col < 9; col++)
		{
			if (getSudoku[row][col] == 0)
			{
				*pi = row;
				*pj = col;
				return; //Í˳öº¯Êý
			}
		}
		j = 0;
	}
	if (row == 9)
		return 0;
	*pi = row;
	*pj = col;
	return 1;
}
int finish() //Óнâ´òÓ¡Êý¶À½á¹û
{
	printf("find the solution:\n");
	prt();
}
int doOnePosition(int i, int j) //´¦ÀíÒ»¸öλÖÃ
{
	int row = i;
	int col = j;
	int n = 0;
	int k = 0;
	int a[9] = { 0 };
	if (getSudoku[row][col] != 0)
	{
		if (getNextSolution(&row, &col))
		{
			doOnePosition(row, col);//¶ÔÏÂһλÖýøÐеݹé²Ù×÷
		}
		else
			finish(); //¶¼Óнâ¾Í´òÓ¡
		return;
	}
	else //µ±Ç°Î»ÖÃÎÞ½â
	{
		n = getAllSovle(i, j, a); //»ñÈ¡µ±Ç°Î»ÖõÄËùÓпÉÄܽâ
		for (k = 0; k < n; k++)   //³¢ÊÔËùÓпÉÄܽâ
		{
			if (tryOneSolution(i, j, a[k]))
			{
				row = i;
				col = j;
				if (getNextSolution(&row, &col)) //´ËλÖÃÓн⣬ÏÂÒ»¸ö
				{
					doOnePosition(row, col);
				}
				else //µ±Ç°Î»ÖÃÒÑÓнâÇÒûÓÐÏÂÒ»¸ö£¬½áÊø
				{
					finish();
				}
			}
		}
		getSudoku[i][j] = 0; //ÈôÏòÇ°»ØËÝ,ÔòÕâ¸öλÖÃÕÒµ½µÄ½âÎÞЧ,»ØËÝÇ°Çå0
		return;
	}
}
int main()
{
	/*printf("ÊäÈëÒ»¸ö9*9Êý¶À\n");
	int i = 0, j = 0;
	for (; i < 9; i++)
		for (; j < 9; j++)
			scanf("%d", getSudoku[i][j]);*/
	doOnePosition(0, 0);
	return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).