Javaインプリメンテーション:解数独

6158 ワード

タイトル
埋め込まれたスペースで数独の問題を解決するプログラムを作成します.
数独の解法は、次のルールに従う必要があります.
  • 数字1-9は、行ごとに1回しか表示されません.
  • 数字1-9は、列ごとに1回しか表示されません.
  • 数字1-9は、太い実線で区切られた3x3の子宮内で1回しか現れない.

  • 空白格は'.'で表される.
     
    アルゴリズム#アルゴリズム#
    再帰アルゴリズムを用いると、まず最初に充填すべき位置、すなわち行と列を取得し、複雑度が指数関数的に増加する場合、優先処理候補値が比較的少ないため、効率が向上する.充填完了後、正しいか否かを判断し、正しくない場合は空に戻る.
    import java.util.HashSet;
    import java.util.Set;
    
    /**
     * Created by GuanDS on 2018/8/28.
     */
    public class Test {
    
        public static void main(String[] args) {
            char[][] board = {
                    {8, '.', '.', '.', '.', '.', '.', '.', '.'},
                    {'.', 7, '.', '.', 9, '.', 2, '.', '.'},
                    {'.', '.', 3, 6, '.', '.', '.', '.', '.'},
                    {'.', 5, '.', '.', '.', 7, '.', '.', '.'},
                    {'.', '.', '.', '.', 4, 5, 7, '.', '.'},
                    {'.', '.', '.', 1, '.', '.', '.', 3, '.'},
                    {'.', '.', 1, '.', '.', '.', '.', 6, 8},
                    {'.', '.', 8, 5, '.', '.', '.', 1, '.'},
                    {'.', 9, '.', '.', '.', '.', 4, '.', '.'}
            };
    
            board = fill(board);
            if (board == null) {
                System.out.println("    ");
                return;
            }
            System.out.printf("[");
            for (int j = 0; j < board.length; j++) {
                System.out.printf("[\"");
                for (int i = 0; i < board[0].length; i++) {
                    System.out.print((int) board[j][i] + (i == board.length - 1 ? "\"]" : "\", \""));
                }
                if (j != board.length - 1) {
                    System.out.printf(", ");
                }
            }
            System.out.printf("]");
        }
    
        //       
        private static char[][] fill(char[][] board) {
            int[] index = fillIndex(board);
            int i = index[0], j = index[1];
            if (i < 0 || j < 0) {
                return board;
            }
    
            //         
            Set setX = new HashSet<>();
            Set setY = new HashSet<>();
            for (int m = 0; m < board.length; m++) {
                if (board[j][m] != '.' && !setX.add(board[j][m])) {
                    return null;
                }
            }
            for (int n = 0; n < board.length; n++) {
                if (board[n][i] != '.' && !setY.add(board[n][i])) {
                    return null;
                }
            }
    
            //             ,         
            setX.addAll(setY);
            if (setX.size() >= board.length) {
                return null;
            }
            for (int k = 1; k < board.length + 1; k++) {
                //             
                if (!setX.contains((char) k)) {
                    char[][] temp = copy(board);
                    temp[j][i] = (char) k;
                    char[][] result = fill(temp);
                    if (result != null) {
                        return result;
                    }
                }
            }
            return null;
        }
    
        //              ,     ,     
        private static int[] fillIndex(char[][] array) {
            int max = 0, maxI = -1, maxJ = -1;
            for (int j = 0; j < array.length; j++) {
                for (int i = 0; i < array.length; i++) {
                    if (array[j][i] != '.') {
                        continue;
                    }
                    Set set = new HashSet<>();
                    for (int m = 0; m < array.length; m++) {
                        if (array[m][i] != '.') {
                            set.add(array[m][i]);
                        }
                    }
                    for (int n = 0; n < array.length; n++) {
                        if (array[j][n] != '.') {
                            set.add(array[j][n]);
                        }
                    }
                    if (set.size() > max) {
                        max = set.size();
                        maxI = i;
                        maxJ = j;
                    }
    
                    if (max == array.length - 1) {
                        return new int[]{i, j};
                    }
                }
            }
            return new int[]{maxI, maxJ};
        }
    
        //     
        private static char[][] copy(char[][] array) {
            char[][] result = new char[array.length][array[0].length];
            for (int m = 0; m < array.length; m++) {
                for (int n = 0; n < array[0].length; n++) {
                    result[m][n] = array[m][n];
                }
            }
            return result;
        }
    
    }
    

    結果
    [["8", "3", "7", "2", "1", "6", "9", "4", "5"], ["1", "7", "4", "3", "9", "8", "2", "5", "6"], ["9", "8", "3", "6", "2", "1", "5", "7", "4"], ["3", "5", "2", "4", "6", "7", "1", "8", "9"], ["2", "1", "6", "8", "4", "5", "7", "9", "3"], ["4", "6", "9", "1", "5", "2", "8", "3", "7"], ["5", "2", "1", "9", "7", "4", "3", "6", "8"], ["7", "4", "8", "5", "3", "9", "6", "1", "2"], ["6", "9", "5", "7", "8", "3", "4", "2", "1"]]