第一種解法:
利用佇列解
我是參考書上寫的
不過這方法似乎只能解基本的數獨
因為他是將未填入數字的位置 存入佇列中
再一一拿出來做
因為有一些數獨是需要用判斷的才能解
所以這種解法可能無法適用於所有的題目
#include <stdio.h>
struct data_item{
int x,y,val;
};
struct sudoku_item{
int x,y;
int num;
int val[10];
int resVal;
};
sudoku_item sudoku[9][9];
int rear,front;
data_item *dataQ[9*9];
void createQueue(){
rear = front = 0;
}
void enque(data_item *dataItem){
dataQ[rear] = dataItem;
rear = (rear +1) % (9*9);
}
data_item *deque(){
data_item *dataItem = dataQ[front];
front = (front + 1)% (9*9);
return dataItem;
}
int isEmpty(){
return rear == front;
}
data_item *clrSudokuItem(int x, int y, int n){
data_item *dataItem;
int i;
if(sudoku[x][y].resVal == 0){
sudoku[x][y].num-= sudoku[x][y].val[n];
sudoku[x][y].val[n] = 0;
if(sudoku[x][y].num == 1)
for(i = 1; i < 10; i++)
if(sudoku[x][y].val[i] == 1){
sudoku[x][y].resVal = i;
dataItem = (data_item *) new data_item;
dataItem ->x = x;
dataItem ->y = y;
dataItem ->val = i;
return dataItem;
}
}
return NULL;
}
void preprocess(int dataArr[][9]){
data_item *dataItem;
int i,j,k;
createQueue();
for(i = 0; i < 9;i++){
for(j = 0; j< 9; j++){
printf("%d ",dataArr[i][j]);
if(dataArr[i][j] != 0){
sudoku[i][j].num = 1;
sudoku[i][j].resVal = dataArr[i][j];
dataItem = (data_item *) new data_item;
dataItem->x = i;
dataItem->y = j;
dataItem->val = dataArr[i][j];
enque(dataItem);
}else{
sudoku[i][j].x = i;
sudoku[i][j].y = i;
for(k = 1; k<10; k++)
sudoku[i][j].val[k] = 1;
sudoku[i][j].num = 9;
sudoku[i][j].resVal = 0;
}
}
printf("\n");
}
}
void processSudoku(){
data_item *dataItem,*retData;
int i,j;
while(!isEmpty()){
int x,y,val;
dataItem = deque();
x =dataItem->x;
y =dataItem->y;
val = dataItem->val;
for(i = 0; i<9; i++){
if(i != y){
retData = clrSudokuItem(x,i,val);
if(retData != NULL)
enque(retData);
}
if(i != x){
retData = clrSudokuItem(i,y,val);
if(retData != NULL)
enque(retData);
}
}
for(i = 0; i<3; i++)
for(j = 0; j<3; j++){
int m = x/3 *3 +i;
int n = y/3 *3 +j;
if(m!=x && n != y){
retData = clrSudokuItem(m,n,val);
if(retData != NULL)
enque(retData);
}
}
}
}
void output(){
int i,j;
printf("Answer:\n");
for(i = 0; i<9; i++){
for(j = 0; j<9; j++)
printf("%d ",sudoku[i][j].resVal);
printf("\n");
}
}
int main(){
int data[9][9] = {
{3,0,1,0,0,9,0,5,0},
{0,9,0,0,0,4,1,8,0},
{0,0,0,6,2,0,9,0,4},
{1,0,0,0,4,0,0,6,0},
{0,5,0,0,6,0,0,4,0},
{0,8,0,9,7,0,5,0,2},
{0,0,5,0,3,2,0,0,0},
{0,2,9,0,0,0,0,0,5},
{0,6,0,5,9,0,4,0,0}};
preprocess(data);
processSudoku();
output();
getchar();
return 0;
}
第二種解法:
第二次我是利用遞迴讓所有可能性直接跑完(直到有答案)
相信大家都知道遞迴的缺點 浪費時間,空間
不過我還沒想到可以縮短執行時間,空間的方法
若有 歡迎指教
#include "stdafx.h"
struct local_mark{
int x[9];
int y[9];
int z[9];
};
struct point{
int x;
int y;
};
local_mark *Number_Place_set(int [][9]);
bool Number_Place_game(int [][9], local_mark *);
int local_val(int, int);
int bitcount(int );
void print_data(int [][9]);
int main(){
int data[9][9] = {
{3,0,1,0,0,9,0,5,0},
{0,9,0,0,0,4,1,8,0},
{0,0,0,6,2,0,9,0,4},
{1,0,0,0,4,0,0,6,0},
{0,5,0,0,6,0,0,4,0},
{0,8,0,9,7,0,5,0,2},
{0,0,5,0,3,2,0,0,0},
{0,2,9,0,0,0,0,0,5},
{0,6,0,5,9,0,4,0,0}};
printf("Subject:\n");
print_data(data);
local_mark *mark = Number_Place_set(data);
printf("Answer:\n");
if(Number_Place_game(data,mark)){
print_data(data);
}else{
printf("No solution!\n");
}
getchar();
return 0;
}
local_mark *Number_Place_set(int data[][9]){
local_mark *mark = (local_mark*) new local_mark;
for(int i = 0; i < 9; i++ )
mark -> x[i] = mark -> y[i] = mark -> z[i] = 0;
for(int i = 0; i < 9; i++ )
for(int j = 0; j < 9; j++)
if(data[i][j]){
mark -> x[j] |= (1 << data[i][j]-1);
mark -> y[i] |= (1 << data[i][j]-1);
mark -> z[local_val(i,j)] |= (1 << data[i][j]-1);
}
return mark;
}
bool Number_Place_game(int data[][9], local_mark *mark){
point *p = (point*) new point;
int m , max = 0 , count = 0;
for(int i = 0; i < 9; i++ )
for(int j = 0; j < 9; j++)
if(!data[i][j]){
count++;
m = mark->x[j] | mark->y[i] | mark->z[local_val(i,j)];
if(bitcount(m) > bitcount(max)){
max = m;
p -> x = j;
p -> y = i;
}
}
if(count == 0)
return true;
for(int i = 0; i < 9; i++)
if(max != (max | (1 << i))){
data[ p->y ][ p->x ] = i+1;
mark -> x[ p->x ] |= (1 << i);
mark -> y[ p->y ] |= (1 << i);
mark -> z[ local_val( p->y , p->x ) ] |= (1 << i);
if(Number_Place_game(data,mark)){
return true;
}else{
data[ p->y ][ p->x ] = 0;
mark -> x[ p->x ] &= ~(1 << i);
mark -> y[ p->y ] &= ~(1 << i);
mark -> z[ local_val( p->y , p->x ) ] &= ~(1 << i);
}
}
return false;
}
int local_val(int x,int y){
return y/3+(x/3)*3;
}
int bitcount(int x){
int b;
for(b = 0; x; x &= x-1)
++b;
return b;
}
void print_data(int data[][9]){
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++)
printf("%d ",data[i][j]);
printf("\n");
}
}
