文章目录
九宫格一共有多少种解法缘起解题思路代码运行结果
九宫格一共有多少种解法
缘起
今天同事和我讨论了九宫格的回溯问题，说实话，我之前玩过一款游戏叫“九阴真经”，里面有一个副本第二关开启就要解一个九宫格。我一直认为有很多种解法，至少得有百八十种吧。但是用回溯解完之后，发现，我太天真了。
解题
思路
不就是1-9的数字放到九个框框里面么？我把所有的可能都回溯出来，再看看满不满足九宫格的条件不就得了，至于需要判断多少遍，不多，也就9!遍（准确的说，一共<362880>次）。
当然这个绝对是可以优化的，比如说同一行已经有9和6了那就不用继续了。优化这件事，以后有时间再做。。。
代码
/**
* @program: algorithm_code
* @description: 九宫格
* @author: YangHang
* @create: 2019-08-26 19:27
**/
public class JiuGongGe {
public static int count = 0;
public static void main(String[] args) {
int[] arr = new int[9];
long startTime = System.currentTimeMillis();
set(0, arr);
System.out.println("一共<" + count + ">次");
long endTime = System.currentTimeMillis();
System.out.println((endTime - startTime) + "ms");
}
public static void set(int n, int[] arr) {
if (n == 9) {
count++;
if (ok(arr, 15, 3)) {
System.out.println(Arrays.toString(arr));
}
return;
}
A:
for (int i = 1; i < 10; i++) {
for (int j = 0; j < n; j++) {
if (arr[j] == i) {
continue A;
}
}
arr[n] = i;
set(n + 1, arr);
}
}
private static boolean ok(int[] arr, int sum, int jie) {
int sum_;
for (int i = 0; i < jie; i++) {
sum_ = Arrays.stream(arr, i * jie, i * jie + jie).reduce(Integer::sum).orElse(0);
if (sum_ != sum) {
return false;
}
int i_ = i;
sum_ = IntStream.range(0, jie).mapToObj(item -> arr[item * jie + i_]).reduce(Integer::sum).orElse(0);
if (sum_ != sum) {
return false;
}
}
sum_ = IntStream.range(0, jie).mapToObj(item -> arr[item * jie + item]).reduce(Integer::sum).orElse(0);
if (sum_ != sum) {
return false;
}
sum_ = IntStream.range(0, jie).mapToObj(item -> arr[(item + 1) * (jie - 1)]).reduce(Integer::sum).orElse(0);
if (sum_ != sum) {
return false;
}
return true;
}
}
运行结果