forked from piaohua/mjalgorism
-
Notifications
You must be signed in to change notification settings - Fork 0
/
AgariBacktrack.java
207 lines (167 loc) · 4.16 KB
/
AgariBacktrack.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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
public class AgariBacktrack {
static final int MAN = 0;
static final int MAN1 = 0;
static final int MAN2 = 1;
static final int MAN3 = 2;
static final int MAN4 = 3;
static final int MAN5 = 4;
static final int MAN6 = 5;
static final int MAN7 = 6;
static final int MAN8 = 7;
static final int MAN9 = 8;
static final int PIN = 9;
static final int PIN1 = 9;
static final int PIN2 = 10;
static final int PIN3 = 11;
static final int PIN4 = 12;
static final int PIN5 = 13;
static final int PIN6 = 14;
static final int PIN7 = 15;
static final int PIN8 = 16;
static final int PIN9 = 17;
static final int SOU = 18;
static final int SOU1 = 18;
static final int SOU2 = 19;
static final int SOU3 = 20;
static final int SOU4 = 21;
static final int SOU5 = 22;
static final int SOU6 = 23;
static final int SOU7 = 24;
static final int SOU8 = 25;
static final int SOU9 = 26;
static final int TON = 27;
static final int NAN = 28;
static final int SHA = 29;
static final int PEI = 30;
static final int HAK = 31;
static final int HAT = 32;
static final int CHU = 33;
static final int[] n_zero;
static {
n_zero = new int[34];
Arrays.fill(n_zero, 0);
}
// 牌の種類ごとの個数を求める
static int[] analyse(int[] hai) {
for (int i : n_zero) {
System.out.printf("%d ", i);
}
System.out.print("\n");
int[] n = n_zero.clone();
for (int i : hai) {
n[i]++;
}
for (int i : n) {
System.out.printf("%d ", i);
}
System.out.print("\n");
return n;
}
// バックトラック法で雀頭と面子の組み合わせを求める
static List<Integer[][]> agari(int[] n) {
List<Integer[][]> ret = new ArrayList<Integer[][]>();
for (int i = 0; i < 34; i++) {
for (int kotsu_first = 0; kotsu_first < 2; kotsu_first++) {
Integer[] janto = new Integer[1];
ArrayList<Integer> kotsu = new ArrayList<Integer>();
ArrayList<Integer> shuntsu = new ArrayList<Integer>();
int[] t = n.clone();
if (t[i] >= 2) {
// 雀頭をはじめに取り出す
t[i] -= 2;
janto[0] = i;
if (kotsu_first == 0) {
// 刻子を先に取り出す
for (int j = 0; j < 34; j++) {
if (t[j] >= 3) {
t[j] -= 3;
kotsu.add(j);
}
}
// 順子を後に取り出す
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 7;) {
if (t[9*a+b] >= 1 &&
t[9*a+b+1] >= 1 &&
t[9*a+b+2] >= 1) {
t[9*a+b]--;
t[9*a+b+1]--;
t[9*a+b+2]--;
shuntsu.add(9*a+b);
} else {
b++;
}
}
}
} else {
// 順子を先に取り出す
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 7;) {
if (t[9*a+b] >= 1 &&
t[9*a+b+1] >= 1 &&
t[9*a+b+2] >= 1) {
t[9*a+b]--;
t[9*a+b+1]--;
t[9*a+b+2]--;
shuntsu.add(9*a+b);
} else {
b++;
}
}
}
// 刻子を後に取り出す
for (int j = 0; j < 34; j++) {
if (t[j] >= 3) {
t[j] -= 3;
kotsu.add(j);
}
}
}
// 和了の形か調べる
if (Arrays.equals(t, n_zero)) {
ret.add(new Integer[][] {janto, kotsu.toArray(new Integer[0]), shuntsu.toArray(new Integer[0])});
}
}
}
}
return ret;
}
public static void main(String[] args) {
int[] hai = {
MAN1, MAN1, MAN1,
MAN2, MAN3, MAN4,
MAN6, MAN7, MAN8,
TON, TON, TON,
SHA, SHA
};
int[] n = null;
List<Integer[][]> ret = null;
long time = System.currentTimeMillis();
// for (int i = 0; i < 100000; i++) {
// n = analyse(hai);
// ret = agari(n);
// }
n = analyse(hai);
ret = agari(n);
//for (int i : n) {
// System.out.printf("%d ,", i);
//}
System.out.print("\n");
System.out.println(System.currentTimeMillis() - time);
for (Integer[][] r : ret) {
System.out.print("雀頭=");
System.out.println(r[0][0]);
for (Integer kotsu : r[1]) {
System.out.print("刻子=");
System.out.println(kotsu);
}
for (Integer shuntsu : r[2]) {
System.out.print("順子=");
System.out.println(shuntsu);
}
}
}
}