[練習] 數獨程式

用NXT做的數獨機器人

前面比較繁瑣的工作是判斷位置

以及掃描出數字

將9*9表格讀入機器後就可以開始進行運算

藉此機會

就來研究看看解數獨的程式該如何寫吧

首先要瞭解規則

在1~9行內絕對只有1~9的數字 且不重複

在1~9列內絕對只有1~9的數字 且不重複

以每9格(正方) 為單位  9格內也只有1~9的數字 且不重複

例如:

1 2 3 4 5 6 7 8 9

4 5 6 7 8 9 1 2 3

7 8 9 1 2 3 4 5 6

2 3 4 5 6 7 8 9 1

5 6 7 8 9 1 2 3 4

8 9 1 2 3 4 5 6 7

3 4 5 6 7 8 9 1 2

這就算是一個數獨的答案

然而數獨的每個題目  永遠都只會有一個答案(如果有很多答案就沒什麼好玩了)

第一種解法:
利用佇列解
我是參考書上寫的
不過這方法似乎只能解基本的數獨
因為他是將未填入數字的位置 存入佇列中
再一一拿出來做

因為有一些數獨是需要用判斷的才能解
所以這種解法可能無法適用於所有的題目

#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");
 }
}