现在的位置: 首页 > 综合 > 正文

数独问题的解法/程序实现

2013年08月08日 ⁄ 综合 ⁄ 共 790字 ⁄ 字号 评论 1 条
30元程序员衣装优惠券,仅剩3天!点击领取

基本思路就是搜索,建立每行、每列和每个分区块的限定数组,对每一个点寻找符合条件的解。
代码见下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int arr[9][9];
int xflag[9][10];
int yflag[9][10];
int pflag[9][10];
bool find_result;
 
int get_part_id(int x, int y) {
  return (x / 3) * 3 + (y / 3) + 1;
}
 
void print_arr() {
  for (int i = 0; i < 9; ++i) {
    if (i == 3 || i == 6) {
      printf("\n");
    }
    printf("%d", arr[i][0]);
    for (int j = 1; j < 9; ++j) {
      if (j == 3 || j == 6) {
        printf(" ");
      }
      printf(" %d", arr[i][j]); 
    }
    printf("\n");
  }
}
 
void search(int x, int y) {
  if (x >= 9) {
    printf("\nfind result:\n");
    print_arr();
    find_result = true;
    return;
  }
  if (find_result){return;}
 
  int next_x, next_y;
  next_y = y + 1;
  if (next_y == 9) {
    next_x = x + 1;
    next_y = 0;
  } else {
    next_x = x;
  }
  int part_id = get_part_id(x, y);
 
  if (arr[x][y] > 0) {
    return search(next_x, next_y);
  }
 
  for (int i = 1; i <= 9; ++i) {
    if (xflag[x][i] == 0 && yflag[y][i] == 0 && pflag[part_id][i] == 0) {
      arr[x][y] = i;
      xflag[x][i] = 1, yflag[y][i] = 1, pflag[part_id][i] = 1;
      search(next_x, next_y);
      arr[x][y] = 0;
      xflag[x][i] = 0, yflag[y][i] = 0, pflag[part_id][i] = 0;
    }
  }
}
 
int main() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  int part_id;
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      scanf("%d", arr[i] + j);
      if (arr[i][j] > 0) {
        xflag[i][arr[i][j]] = 1;
        yflag[j][arr[i][j]] = 1;
        pflag[get_part_id(i, j)][arr[i][j]] = 1;
      }
    }
  }
 
  print_arr(); 
  find_result = false;
  search(0, 0);
 
  return 0;
}
30元程>序员衣装优惠券,仅剩3天!点击领取

目前有 1 条留言    访客:1 条, 博主:0 条

  1. sunshine945 2013年08月09日 下午2:33  Δ-49楼

    赞啊!