白俊-2239号(斯多庫)

21230 ワード
baekjoon テキストリンク
質問元:https://www.acmicpc.net/problem/2239
質問する
  • 数独は簡単なデジタルパズルです.9×9個のサイズの回路基板を有する場合、行毎、列毎、9個の3×3サイズのボードに1～9の数字を記入すると、繰り返されません.例:

  • 上図は本当に謎解きのいい例だ.1行あたり1～9の数字は重複しません.列あたり1～9の数字は重複しません.行あたり3×3の方形(9個、上は色で表す)では、1から9の数字は繰り返されないからです.

  • ハダマンスド・クーパーにあげるときは、完成したプログラムを書いてください.
    • import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static List<int[]> target;
    private static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int[][] sudoku = new int[9][9];

        target = new ArrayList<>();

        for (int i = 0; i < 9; i++) {
            char[] temp = reader.readLine().toCharArray();

            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = temp[j] - '0';
                if (sudoku[i][j] == 0) target.add(new int[] { i, j });
            }
        }

       dfs(sudoku, 0);

        System.out.println(sb);
    }

    private static void dfs(int[][] sudoku, int idx) {
        if (sb != null) return;

        if (idx == target.size()) {
            sb = new StringBuilder();

            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(sudoku[i][j]);
                }
                sb.append("\n");
            }

            return;
        }

        int y = target.get(idx)[0];
        int x = target.get(idx)[1];

        boolean[] temp = new boolean[10];

        checkCross(sudoku, temp, y, x);
        checkInner(sudoku, temp, y / 3 * 3, x / 3 * 3);

        for (int k = 1; k < 10; k++) {
            if (!temp[k]) {
                sudoku[y][x] = k;
                dfs(sudoku, idx + 1);
                sudoku[y][x] = 0;
            }
        }
    }

    // 가로, 세로 체크
    private static void checkCross(int[][] sudoku, boolean[] temp, int r, int c) {
        for (int i = 0; i < 9; i++) {
            if (sudoku[r][i] != 0) temp[sudoku[r][i]] = true;

            if (sudoku[i][c] != 0) temp[sudoku[i][c]] = true;
        }
    }

    // 내부 3x3 사각형 체크
    private static void checkInner(int[][] sudoku, boolean[] temp, int r, int c) {
        for (int i = r; i < r + 3; i++) {
            for (int j = c; j < c + 3; j++) {
                if (sudoku[i][j] != 0) temp[sudoku[i][j]] = true;
            }
        }
    }

}
  • はかなり長い時間をかけてやっと問題を解いた.
  • が最初に解決した方法は、メモリと時間が想像以上のレベルにあることです.
  • は特に,dfsがこれまで継続できなかった場合,他の場所へ行く目的にのみ用いられていることを認識し,他の値で埋める方法も可能であることを改めて知った.
  • は、さまざまな不要なルールを考慮するのに多くの時間を費やし、より系統的に論理を確立する練習が必要であるようだ.
    • Remember Me
    Web開発ログ-第2週2日目(JQ入門)