之前寫過的程式,不過個人覺得寫得很爛.....
所以重新再度重寫了!
結合著新的想法跟現在的知識,新寫出來的程式比較整潔。
雖然程式又大了100KB......- -|||
正文
使用C語言實作。
AC (0ms, 368KB)
說明:
數獨的特性為每一行、列、小九宮內,有1~9之數字,且不重複。
使用乘法將其區塊內的數字相乘,即可得到9!(階乘)的數字。
因其數字限定在1~9間,故可使用階乘做為判定條件,只要有任一數字錯誤,判定區塊所得到的數值就不等於1*2*3*4*5*6*7*8*9。
程式碼如下:/*a016數獨(SUDOKU)*/
#include <stdio.h>
typedef enum
{
HORIZONTAL, /* 水平 */
VERTICAL, /* 垂直 */
JIUGONGGE /* 九宮格 */
}QueryType;/* 查詢方式 */
/* 查詢函數 */
int Query(QueryType type, int SUDOKU[9][9], int i, int j);
/* 數獨判定 */
int Factorial(int SUDOKU[9][9], QueryType type);
int main()
{
int data[9][9];
while (scanf("%d", &data[0][0])!=EOF)
{
int i, j, answer = 1, factorial = 1;
/* 資料輸入 */
for(i = 0; i < 9; i++)
{
for(j = (i==0)? 1 : 0; j< 9; j++)
{
scanf("%d",&data[i][j]);
}
}
/* 如不為0,則為數獨 */
answer = Factorial(data, HORIZONTAL) /* 水平方向判定 */
* Factorial(data, VERTICAL) /* 垂直方向判定 */
* Factorial(data, JIUGONGGE); /* 小九宮判定 */
printf("%s\n", (answer)? "yes" : "no");
}
return 0;
}
/* 查詢函數 */
int Query(QueryType type, int SUDOKU[9][9], int i, int j)
{
switch(type)
{
case HORIZONTAL:
return SUDOKU[i][j];
case VERTICAL:
return SUDOKU[j][i];
case JIUGONGGE:
return SUDOKU[(i / 3) * 3 + j/ 3][(i % 3) * 3 + j % 3];
}
}
/* 數獨判定 */
int Factorial(int SUDOKU[9][9], QueryType type)
{
const int FACTORIAL_9 = 1*2*3*4*5*6*7*8*9;
int i, j, factorial = 1;
for(i = 0; i < 9; i++, factorial = 1)
{
for(j = 0; j < 9; j++)
{
factorial *= Query(type,SUDOKU, i, j);
}
if(factorial != FACTORIAL_9)/* 不為9!(階乘)之數值 */
return 0;
}
return 1;
}