题目: 解数独

分析

解数独可以采用回溯法进行数字的摆放。

题解

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public void solute(List<List<Integer>> board) {
        List<List<Integer>> coordinateList = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            List<Integer> integerList = board.get(i);
            for (int j = 0; j < 9; j++) {
                Integer integer = integerList.get(j);
                if (integer == 0) {
                    List<Integer> coordinate = new ArrayList<>();
                    coordinate.add(i);
                    coordinate.add(j);
                    coordinateList.add(coordinate);
                }
            }
        }
        int size = coordinateList.size();
        for (int i = 0; i < size; ) {
            List<Integer> coordinate = coordinateList.get(i);
            int x = coordinate.get(0);
            int y = coordinate.get(1);
            List<Integer> integerList1 = board.get(x);
            int j = integerList1.get(y) + 1;
            for (; j < 10; j++) {
                boolean flag = true;
                for (int k = 0; k < 9; k++)
                    if (integerList1.get(k) == j) {
                        flag = false;
                        break;
                    }
                if (!flag) continue;
                for (int k = 0; k < 9; k++)
                    if (puzzle.get(k).get(y) == j) {
                        flag = false;
                        break;
                    }
                if (!flag) continue;
                int block = x / 3 * 3 + y / 3;
                int xStart = block / 3 * 3;
                int yStart = (block - xStart) * 3;
                for (int k = xStart; k < xStart + 3; k++) {
                    List<Integer> integerList2 = puzzle.get(k);
                    for (int l = yStart; l < yStart + 3; l++)
                        if (integerList2.get(l) == j) {
                            flag = false;
                            break;
                        }
                    if (!flag) break;
                }
                if (!flag) continue;
                integerList1.set(y, j);
                break;
            }
            if (j == 10) {
                integerList1.set(y, 0);
                i--;
            } else {
                integerList1.set(y, j);
                i++;
            }
        }
    }
}