More than 1 year has passed since last update.

C++で数独を解いてみた！

Last updated at 2023-11-15Posted at 2019-03-04

数独(sudoku)を解く

最近勉強し始めたC++とアルゴリズムを使って数独を解くコードを書きました。~~懸賞問題を自動で解きたい~~数独大好きなので

深さ優先探索(DFS)
を使って、全探索していきます。

大まかな手順

空欄を0として左上から1~9を順に当てはめる
bool solve_sudoku()
それが数独のルールを満たすかを確認する
bool check_vertically()
bool check_horizontally()
bool check_mass()
int change_num()

※細かい説明などはコード内コメントに書いておきました。

--1--


bool solve_sudoku(vector< vector<int> >& arr, int x, int y)//x:0~8、横方向,y:0~8、縦方向
//深さ優先探索
{
    if(y>8){
        return true;
    }else if(x>8){
        if(solve_sudoku(arr, 0, y+1)==1){
            return true;
        }
    }else if(arr[y][x]!=0){
        if(solve_sudoku(arr, x+1, y)==1){
            return true;
        }
    }else{
        for(int i=1; i<=9; i++){//iを当てはめていく
            int tmp=change_num(arr, x, y, i);
            if(tmp!=0){
                if(solve_sudoku(arr, x+1, y)==1){
                    return true;
                }
            }
        }
        arr[y][x]=0;
    }
    return false;
}

--2--


bool check_vertically(vector< vector<int> >& arr, int x, int n)//縦の確認
{
    for(int i=0; i<9; i++){
        if(arr[i][x]==n){
            return false;
        }
    }
    return true;
}
bool check_horizontally(vector< vector<int> >& arr, int y, int n)//横の確認
{
    for(int i=0; i<9; i++){
        if(arr[y][i]==n){
            return false;
        }
    }
    return true;
}
bool check_mass(vector< vector<int> >& arr, int x, int y, int n)//3*3マスでの確認
{
    int x_base=(x/3)*3;
    int y_base=(y/3)*3;
    for(int i=x_base; i<x_base+3; i++){
        for(int j=y_base; j<y_base+3; j++){
            if(arr[j][i]==n){
                return false;
            }
        }
    }
    return true;
}
int change_num(vector< vector<int> >& arr, int x, int y, int n)//n:1~9での置き換えを試みるダメなら0を返す
{
    if(check_vertically(arr, x, n)==1 && check_horizontally(arr, y, n)==1 && check_mass(arr, x, y, n)==1){
        return arr[y][x]=n;
    }else{
        return 0;
    }
}

main()関数

int_main()


#include <iostream>
#include <vector>
#include <chrono>
using namespace std;

int main()
{
    vector< vector<int> > arr;
    arr.resize(9);
    for(int i=0; i<9; i++){
        char* buf=new char[10];
        cin >> buf;
        for(int j=0; j<9; j++){
            arr[i].push_back(int(buf[j])-48);//int('0')==48
        }
        delete[]buf;
    }

    chrono::system_clock::time_point  start, end;//時間計測
    start = std::chrono::system_clock::now();

    if(solve_sudoku(arr, 0, 0)==1){
        cout << "--解けました!!--" << endl;
        for(int i=0; i<9; i++){
            cout << '|';
            for(int j=0; j<8; j++){
                cout << arr[i][j] << ',';
            }
            cout << arr[i][8];
            cout << '|' << endl;
        }
    }else{
        cout << "--解けませんでした…--" << endl;
    }
    
    end = std::chrono::system_clock::now();
    double elapsed = chrono::duration_cast<chrono::milliseconds>(end-start).count();
    cout << "かかった時間は" << elapsed << "μsです。\n";
    return 0;
}

入出力


//入力
850002400
720000009
004000000
000107002
305000900
040000000
000080070
017000000
000036040
//出力

--解けました!!--
|8,5,9,6,1,2,4,3,7|
|7,2,3,8,5,4,1,6,9|
|1,6,4,3,7,9,5,2,8|
|9,8,6,1,4,7,3,5,2|
|3,7,5,2,6,8,9,1,4|
|2,4,1,5,9,3,7,8,6|
|4,3,2,9,8,1,6,7,5|
|6,1,7,4,2,5,8,9,3|
|5,9,8,7,3,6,2,4,1|
かかった時間は157msです。

今回は「Pythonで数独を解く」を参考にほぼ同じコードを書きました。
環境にもよりますが、同じ問題を同じようなコードでPythonだと23秒かかるらしいので、C++の160msは早いですね…100倍くらい？

最後に〜

「本当に解ける人いるの？　フィンランド人数学者が作った “世界一難しい数独” が発表される」
を解いてみました。
まずは自分で…20分経っても1マスも埋まらない
ということでやってみる


--解けました!!--
|8,1,2,7,5,3,6,4,9|
|9,4,3,6,8,2,1,7,5|
|6,7,5,4,9,1,2,8,3|
|1,5,4,2,3,7,8,9,6|
|3,6,9,8,4,5,7,2,1|
|2,8,7,1,6,9,5,3,4|
|5,2,1,9,7,4,3,6,8|
|4,3,8,5,2,6,9,1,7|
|7,9,6,3,1,8,4,5,2|
かかった時間は28msです。

グッジョブ

参考

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up