LeetCode 解答 #37. Sudoku Solver プログラミング練習

問題：

難易度:　hard
入力:　character型array
目的: 入力された数独パズルの解を探せ
出力:　なし

皆さんお馴染みの数独ゲームの問題です。
解らない人もいると思うのでルールとしては:
9*9の盤面をもらい、縦が1-9、横も1-9、更に9個のsub-box（3*3）もすべて1-9の重複なしの数字で埋めるゲームです。
なので一列、一行、一箱に同じ数字が存在してはなりません。

前回は入力された盤面が有効かどうか判断する問題でしたが、
今回はそのパズルを解く問題です。
出力がなしと言うのは関数の出力のことで、
入力されたArrayを直接動かす事になります。
難易度はhard。
でも馴染みのある問題なので解いていて楽しいですよ（笑）
必ず解がある入力なのでボーダーケースを考えないでいいのは楽ですね

注意すべき事:　

• 入力された盤面には唯一の解が必ず存在する。

• 未入力部分は'.'で表されている。

• 盤面は常に9＊9

以下回答です。

class Solution {
    public void solveSudoku(char[][] board) {
        backtracking(board);
    }
    
    public boolean backtracking(char[][] board) {
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                if (board[i][j] == '.') {
                    for (char c='1'; c<='9'; c++) {
                        if (check(board, i, j, c)) {
                            board[i][j] = c;
                            if (backtracking(board)) { 
                                return true;
                            }
                            else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    public boolean check(char[][] board, int i, int j, char c) {
        for (int k = 0; k < 9; k++) {
            if (board[k][j] == c) return false;
            if (board[i][k] == c) return false;
            int m = 3 * (i / 3) + k / 3;
            int n = k % 3 + 3 * (j / 3);
            if (board[m][n] == c) return false;
        }
        return true;
    }
}

今回はバックトラッキング方を使わせてもらいました。
以前8queenの問題を某企業の面接で回答したことがありますが、
考え方としては全く同じです。
パズル系には強いアルゴリズムです。
所謂全体探索をしているのであまり効率のいいアルゴリズムではありませんが...
一つずつ試して、法則に合っていたらそのまま次の未入力部分に進み、
合わなかったら前の状態に戻って違う数字を試し繰り返すやり方ですね。
注意すべきはcheckの部分。
ブロック部分の変換は前回の問題と全く同じなので、
解らない人は#36問を参考にしてください。

今日は以上。
よいプログラミング生活を！