数独を解くプログラム

　別記事〔数独を自動で解くプログラム〕で、自作プログラムでは、簡単な数独の問題しか解けないので、ただ今改良中だと書かせていただきました。

　数独の解法を無視した力技で、自動で解くプログラムを作ってしまいました。

　作っておいて言うのは変ですが、数独（ナンバープレース）はやっぱり自分の頭で考えて解くべきです。今回紹介するプログラムでは、問題が適切なものかどうかは無関係に、入力された部分にマッチする解を無理やり総当り方式で解いてしまいます。なんだか、ちょっと後味が悪いのですが…

（by　心如）

───〔出力例〕───────────────────────────

───〔プログラム例〕───────────────────────────
// NumPlace.cpp
//
// 2012.04.25 ───── coded by 心如

#include <iostream>
#include <string>
#include <fstream>
using namespace std;

const Mxn = 9;

// 数独の定義
class NumPlace{
    int data[Mxn][Mxn];
    int bupd[Mxn][Mxn];
    int search(int, int);
public:
    NumPlace(){
        clear();
        backup();
    }
    void clear();
    void backup();
    void swap();
    void print();
    void input();
    void set(string);
    int chkSet(int, int, int);
    void analyze();
    void read();
    void save();
};

// 数独データの消去
void NumPlace::clear(){
    for(int i = 0; i < Mxn; i++){
        for(int j = 0; j < Mxn; j++){
            data[i][j] = 0;
        }
    }
}

// 数独データのバックアップ
void NumPlace::backup(){
    for(int i = 0; i < Mxn; i++){
        for(int j = 0; j < Mxn; j++){
            bupd[i][j] = data[i][j];
        }
    }
}

// 数独データの交換
void NumPlace::swap(){
    for(int i = 0; i < Mxn; i++){
        for(int j = 0; j < Mxn; j++){
            int w = data[i][j];
            data[i][j] = bupd[i][j];
            bupd[i][j] = w;
        }
    }
}

// 数独データの表示
void NumPlace::print(){
    cout << "/:_1_2_3__4_5_6__7_8_9:x" << endl;
    for(int y = 0; y < Mxn; y++){
        cout << y + 1 << "|";
        for(int x = 0; x < Mxn; x++){
            cout << " ";
            if(data[y][x] == 0) cout << " ";
            else cout << data[y][x];
            if(x % 3 == 2) cout << "|";
        }
        cout << endl;
        if(y == 2 || y == 5){
            cout << " |------+------+------|" << endl;
        }
    }
    cout << "y+------+------+------+" << endl;
}

// 数独データの入力
void NumPlace::input(){
    string w;
    backup();
    while(1){
        cout << "input<yxv>(000:中止)?>";
        cin >> w;
        if(w == "000")break;
        set(w);
        print();
    }
}

// 数独データの設定
void NumPlace::set(string w){
    if(w.size() != 3){
        cerr << ">不正なデータです!?\n";
        return;
    }
    int y = atoi(w.substr(0, 1).c_str());
    int x = atoi(w.substr(1, 1).c_str());
    int v = atoi(w.substr(2, 1).c_str());
    if(x >= 1 && x <= 9 && y >= 1 && y <= 9 && v >= 0 && v <= 9){
        if(chkSet(x-1, y-1, v)){
            data[y-1][x-1] = v;
        }
        else{
            cerr << w << ">この値は設定できません！\n";
        }
    }
    else{
        cerr << w << ">不正な入力です！\n";
    }
}

// 数独データの確認
int NumPlace::chkSet(int x, int y, int n){
    if(n == 0) return 1;
    for(int i = 0; i < Mxn; i++){
        if(i != y && data[i][x] == n) return 0;
        if(i != x && data[y][i] == n) return 0;
    }
    int bx = x / 3;
    int by = y / 3;
    for(int i = 0;i < 3;i++){
        for(int j = 0; j < 3; j++){
            int wx = bx * 3 + j;
            int wy = by * 3 + i;
            if(x != wx && y != wy && data[wy][wx] == n) return 0;
        }
    }
    return 1;
}

// 数独データの検索
int NumPlace::search(int x, int y){
    while(data[y][x] != 0){
        x++;
        if(x == Mxn){
            x = 0;
            y++;
            if(y == Mxn){
                return 1;
            }
        }
    }
    for(int n = 1; n <= Mxn; n++){
        if(chkSet(x, y, n)){
            data[y][x] = n;
            if(search(x, y)){
                return 1;
            }
            data[y][x] = 0;
        }
    }
    return 0;
}

// 数独データの解析
void NumPlace::analyze(){
    cout << "解析開始･･･";
    backup();
    int kekka = search(0, 0);
    if(kekka){
        cout << "･･･完了！\n";
    }
    else{
        cout << "･･･失敗!?\n";
        cout << "解が存在しないと思われますが…\n";
    }
}

// ファイルから数独データを読み込む
void NumPlace::read(){
    string fname;
    cout << "読み込むファイル名の指定>";
    cin >> fname;
    ifstream f(fname.c_str());
    if(f == NULL){
        cerr << fname << "がオープンできません!?\n";
        return;
    }
    backup();
    clear();
    string s;   //ファイルからデータを受け取るstring
    while(1){
        f >> s;
        if(s =="zzz" || s.size() == 0) break;
        set(s);
    }
}

// 数独データをファイルに書き出す
void NumPlace::save(){
    string fname;
    cout << "書き出すファイル名の指定>";
    cin >> fname;
    ofstream f(fname.c_str());
    if(f == NULL){
        cerr << fname << "がオープンできません!?\n";
        return;
    }
    int n;
    for(int i = 0; i < Mxn; i++){
        for(int j = 0; j < Mxn; j++){
            if(data[i][j] != 0){
                f << i+1 << j+1 << data[i][j] << endl;
            }
        }
    }
    f << "zzz" << endl;
}

// メイン・ルーチン
int main(){
    int cmd;
    NumPlace nm;
    srand((unsigned)time(NULL));
    while(1){
        nm.print();
        cout << "<0:消去,1:入力,2:読込,3:解析,5:保存,8:訂正,9:終了>\n";
        cout << "次に何をしますか? ";
        cin >> cmd;
        switch(cmd){
        case 0:
            cout << "消去しますか（99:yes）?";
            cin >> cmd;
            if(cmd == 99){
                nm.clear();
            }
            break;
        case 1:
            nm.input();
            break;
        case 2:
            nm.read();
            break;
        case 3:
            nm.analyze();
            break;
        case 5:
            nm.save();
            break;
        case 8:
            nm.swap();
            break;
        case 9:
            cout << "お疲れ様でした…^^;" << endl;
            return 0;
        default:
            cerr << "その命令は未定義です!!" << endl;
            break;
        }
    }
}

 

タグ：数独 パズル ナンプレ