C++で数独の有効性を判定するアルゴリズムを解説

9×9の行列で表される数独（Sudoku）が与えられたとします。この課題の目的は、与えられた数独の配置が有効かどうかを判定することです。

一般的な数独の盤面は次のようになります。

数独のルール

• 各行には1〜9の範囲の数字が入る
• 各列には1〜9の範囲の数字が入る
• 各3×3のブロックには重複のない数字が入る
• 同じ行に同じ数字が現れることはできない
• 同じ列に同じ数字が現れることはできない

入出力の例

入力例：

sudoku[]=
    [["3","5",".",".","2",".",".",".","."]
    ,["7",".",".","1","6","5",".",".","."]
    ,[".","9","8",".",".",".",".","6","."]
    ,["8",".",".",".","6",".",".",".","3"]
    ,["4",".",".","5",".","4",".",".","1"]
    ,["7",".",".",".","2",".",".",".","6"]
    ,[".","6",".",".",".",".","2","8","."]
    ,[".",".",".","4","1","9",".",".","5"]
    ,[".",".",".",".","8",".",".","7","9"]]

出力： True

解説： 数独行列内のすべての数字が有効な数独のパターンに従っているため、出力は True になります。なお、「.」は空のマス（未入力のセル）を表し、空のマスは判定の対象外となります。

解決のためのアプローチ

まず、与えられた数独盤面の各列に重複した数字がないかを確認します。次に各行をチェックし、さらに各3×3ブロック内で数字がすべて一意であるかを確認します。ブロックの行と列を順に走査し、重複する数字が1つでも見つかれば false を返し、すべてのチェックを通過すれば true を返します。

具体的な手順は以下の通りです。

• 数独盤面を2次元配列として入力として受け取る
• 行内の要素が一意であるかを判定するブール関数を用意する
• 列内の要素が一意であるかを判定するブール関数を用意する
• 3×3ブロック内の要素が一意であるかを判定するブール関数を用意する

C++での実装例

#include<bits/stdc++.h>
using namespace std;
bool validSudoku(vector<vector<char>>& sudoku) {
    int row = 0, col = 0, i = 0, block = 0;
    int count[9];
    // 各行のチェック
    for (row = 0; row < 9; ++row){
        memset(count, 0, 9 * sizeof(int));
        for (col = 0; col < 9; ++col){
            if (sudoku[row][col] != '.')
                ++count[sudoku[row][col]-'1'];
        }
        for (i = 0; i < 9; ++i)
            if (count[i] > 1)
                return false;
    }
    // 各列のチェック
    for (col = 0; col < 9; ++col){
        memset(count, 0, 9 * sizeof(int));
        for (row = 0; row < 9; ++row){
            if (sudoku[row][col] != '.')
                ++count[sudoku[row][col]-'1'];
        }
        for (i = 0; i < 9; ++i)
            if (count[i] > 1)
                return false;
    }
    // 各3×3ブロックのチェック
    int block_row = 0, block_col = 0;
    for (block = 0; block < 9; ++block){
        block_row = (block / 3) * 3, block_col = (block % 3) * 3;
        memset(count, 0, 9 * sizeof(int));
        for (row = block_row; row < (block_row + 3); ++row)
        for (col = block_col; col < (block_col + 3); ++col)
            if (sudoku[row][col] != '.')
                ++count[sudoku[row][col] - '1'];
        for (i = 0; i < 9; ++i)
            if (count[i] > 1)
                return false;
    }
    return true;
}
int main(){
    vector<vector<char> > sudoku= {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };
    bool ans= validSudoku(sudoku);
    if(ans){
        cout<<"True"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    return 0;
}

実行結果

True

アルゴリズムのポイント

この実装では、出現回数を記録する配列 count[9] を用意し、memset で毎回初期化することで、行・列・ブロックごとに独立したカウントを実現しています。文字 '1' からのオフセットをインデックスとして使うことで、数字 '1'〜'9' を配列の添字 0〜8 にマッピングしています。

計算量は盤面が固定サイズ（9×9）であるため O(1) ですが、一般化すると O(N²) の時間計算量、O(N) の空間計算量となります。空きマス「.」はスキップされるため、未完成の数独盤面に対しても有効性の判定が可能です。