以下是今天上課用的程式碼sudoku.c
改編自課本156頁
#include<stdio.h>
int place_number(int n, int sudoku[9][9]) // 現在位置在盤面的第n格
{
// 宣告變數
int i,j,k,conflict,row,col,block_row,block_col,try;
// 終止條件
if(n==81)
{
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
printf("%d ",sudoku[i][j]);
printf("\n");
}
return 1; // 告訴呼叫自己的人: 找到一組解
}
row=n/9;
col=n%9;
block_row=row/3;
block_col=col/3;
// 如果在"這一層"不需要決定 則直接問"下一層"是否有解
if(sudoku[row][col]!=0) return place_number(n+1,sudoku);
for(try=1;try<=9;try++) // 把"這一層"所有可能列舉出來
{
// 檢查這個方法到底能不能用(是否與之前幾層的決定相牴觸)
conflict = 0;
for(i=0;i<9 && !conflict;i++)
{
if( ((col!=i) && (sudoku[row][i]==try)) ||
((row!=i) && (sudoku[i][col]==try)) )
conflict=1;
}
for(i=0;i<3 && !conflict;i++)
for(j=0;j<3 && !conflict;j++)
if(sudoku[3*block_row+i][3*block_col+j]==try)
conflict=1;
// 如果可以用的話 就去問"下一層 "到底能不能用
if(!conflict)
{
sudoku[row][col]=try;
if(place_number(n+1,sudoku))
return 1;
sudoku[row][col]=0;
}
}
return 0;
}
int main()
{
int sudoku[9][9]={
{0,0,0,5,0,6,0,0,0},
{1,0,7,0,0,0,5,9,2},
{5,0,4,0,1,7,6,0,0},
{8,0,0,0,0,9,0,4,0},
{9,0,0,3,6,4,0,0,7},
{0,4,0,2,0,0,0,0,9},
{0,0,5,8,9,0,1,0,4},
{2,9,8,0,0,0,7,0,5},
{0,0,0,7,0,2,0,0,0},
};
place_number(0,sudoku);
scanf(" ");
return 0;
}