服务器之家

服务器之家 > 正文

java版数独游戏核心算法(一)

时间:2021-03-07 12:04     来源/作者:I-Awakening

之前学习javascript时用javascript写过一个数独游戏,最近看了一点java的内容,于是就心血来潮想搞一个java版的数独游戏。

现在将全部代码分享出来和大家学习交流,当然代码中有着各种各样的问题和不足之处,望各位朋友批评指点。

以下是生成数独地图的核心算法,算法不是很好,也是之前参考过网上的一些思想:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
package hlc.shudu.src;
 
/*
 * 数独的帮助类,里面提供数据所需的所有算法
 */
public class ShuduHelper {
 //数独地图数组
 private static int[][] maps = new int[9][9];
 //每个小九宫格可放置位置的数
 private static int[] canPutSum = new int[9];
 //用来存储之前放置过的位置
 static int[] used = new int[9];
 //是否已经完成地图的生成
 static boolean isOk = true;
 
 /*
  * 得到数独地图数组
  */
 public static int[][] getMap() {
 //判断是否已经完成地图的生成,要是没有完成就重新生成。
 //从这里就可以看出算法还有待优化,如果回溯的好的话就一直可以通过回溯来重新生成,而这里是通过重新执行生成算法来重新生成。希望感兴趣的朋友可以去实现以下。
  do{
   isOk = true;
   initMaps();
  }while(!isOk);
  return maps;
 }
 
 /*
  * 初始化maps
  */
 private static void initMaps() {
  // 初始化地图数组中没有填入任何数字
  for (int i = 0; i < 9; i++) {
   for (int j = 0; j < 9; j++) {
    maps[i][j] = -1;
   }
  }
 
  // 依次填入1~9
  for (int num = 1; num <= 9; num++) {
   for (int i = 0; i < 9; i++) {
    used[i] = -1;
    canPutSum[i] = -1;
   }
   // 遍历大九宫格中的每个小九宫格
   for (int i = 0; i < 9; i++) {
    if (canPutSum[i]==-1) {
     canPutSum[i] = getCanPutSum(i, num);
    }
    if (canPutSum[i]==1) {
     used[i] = -1;
    }
 
    if (canPutSum[i] == 0) {
     canPutSum[i] = -1;
     used[i] = -1;
     // 如果当前小九宫格中不能放入数字num,则回到前一个小九宫格
     if (i > 0) {
      // 将前一个九宫格中放num的位置清空
      if (used[i-1]!=-1) {
       //maps[(int) (Math.floor(used[i-1]/3)+Math.floor((i-1)/3)*3)][used[i-1]%3+((i-1)%3)*3]=-1;
       clearNum(i - 1, num);
      }
      // i回退一个,因为等会for循环灰给i加一,所以这里减2
      i -= 2;
      continue;
     } else {
      isOk = false;
      return;
     }
    } else {
     // 将num放入当前小九宫格中
     boolean flag = false;
     while (!flag) {
      int j = (int) (Math.random() * 9);
      // 当前小方格横坐标
      int ii = (i / 3) * 3 + j / 3;
      // 当前小方格纵坐标
      int jj = (i % 3) * 3 + j % 3;
      //System.out.println("num:"+num+"\tii:"+ii+"\tjj:"+jj);
      // 如果可以放置num则放置
      if (maps[ii][jj] == -1 && j!=used[i] && isCanPut(ii, jj, num)) {
       maps[ii][jj] = num;
       used[i] = j;
       canPutSum[i] -= 1;
       flag = true;
      }
 
     }
    }
 
   }
  }
 
 }
 
 /*
  * 清空第i个小九宫格中的num
  */
 private static void clearNum(int i, int num) {
  for (int j = 0; j < 9; j++) {
   // 当前小方格横坐标
   int ii = (i / 3) * 3 + j / 3;
   // 当前小方格纵坐标
   int jj = (i % 3) * 3 + j % 3;
   // 判断当前小方格是否可以放置
   if (maps[ii][jj] == num) {
    maps[ii][jj] = -1;
   }
  }
 
 }
 
 /*
  * 得到当前小九宫格可以放入数字num的位置数目
  */
 private static int getCanPutSum(int i, int num) {
  int sum = 0;
  // 遍历小九宫格
  for (int j = 0; j < 9; j++) {
   // 当前小方格横坐标
   int ii = (i / 3) * 3 + j / 3;
   // 当前小方格纵坐标
   int jj = i % 3 * 3 + j % 3;
   // 判断当前小方格是否可以放置
   if (maps[ii][jj] == -1 && isCanPut(ii, jj, num)) {
    ++sum;
   }
  }
 
  return sum;
 
 }
 
 /*
  * 指定横纵坐标点是否可以放置num
  */
 private static boolean isCanPut(int ii, int jj, int num) {
  // 判断指定坐标点的同行或同列是否有相同数字,要是有则为false
  for (int i = 0; i < 9; i++) {
   if (maps[ii][i] == num) {
    return false;
   }
   if (maps[i][jj] == num) {
    return false;
   }
  }
  return true;
 }
}

完整程序包可在GitHub上下载:https://github.com/houlongchao/s

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:http://blog.csdn.net/da_keng/article/details/47778921

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部