数独を解くプログラム3

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
よっぴー

数独を解くプログラム3

#1

投稿記事 by よっぴー » 4年前

久しぶりです。再び数独を解くプログラムの続きです。
またしても解けない問題が出てきたので質問しに来ました。
現在、基本テクニック(ルールによるもの)と単独候補数字、そしてn国同盟まで作りました。
ですが現在、このn国同盟は数字が2つならでき、3つ以上となるとできません。
temporaryFlag()がn国同盟のつもりです。当然ですがtemporaryFlag()の中の2を3や4にしてもできません。
完全にn国同盟ができるようご指摘ください。

おそらく、コードを読んだだけでは何をしているのかすらわからないかと思います。
遠慮なく質問なさってください。

またshow(true,任意の値)で呼び出すと任意の値の現在のフラグの状態を表示できます。

コード:

#include "stdafx.h"
#include "stdio.h"
#include <time.h>
#include <iostream>
using namespace std;

#define Size 9
#define dataSize 82

int ban[Size][Size];
int checkedTarget = 0;
bool flagban[Size][Size][Size + 1];//0は使わない
bool IsFill = false;//1箇所でも埋めたか

void resetBan(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            ban[Line][Column] = 0;
        }
    }
}

void resetFlag(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            for (int Number = 1; Number <= Size; Number++)
                flagban[Line][Column][Number] = true;//すべての数字の入る可能性をありにする
            flagban[Line][Column][0] = false;//0は使わない
        }
    }
}

void show(bool IsFlagType, int Num){//IsFlagTypeはデバッグ用
    cout << endl;
    cout << "   1 2 3   4 5 6   7 8 9" << endl;
    for (int Line = 0; Line < Size; Line++){
        cout << Line + 1 << "0";
        for (int Column = 0; Column < Size; Column++){
            if (Column == 3 || Column == 6)
                cout << " |";//マスの区切り表示
            if(IsFlagType && flagban[Line][Column][Num])
                cout << " o";
            else if(IsFlagType)
                cout << " x";
            else
                cout << " " << ban[Line][Column];//数字の表示
        }
        if (Line == 2 || Line == 5){
            cout << endl;
            cout << "   ------+-------+------";//マスの区切り表示
        }
        cout << endl;
    }
    cout << endl;
}

void showPlace(int Line, int Column, int Num){
    cout << "X:" << Column + 1 << " Y:" << Line + 1 << " <=" << Num << endl;//埋めた座標と数字を表示
    IsFill = true;
}


//input関連はいずれGUIを使うようものに変更する
void input(){
    int add = 0, data = 0;
    cout << "データを以下のように入力してください" << endl << "行:5 列:7 数値:8 => 857" << endl << "1000を入力すると終了" << endl;
    while (add != 1000){
        show(false,0);
        cout << "1000を入力すると終了" << endl << "データ:";
        cin >> add;  //入力
        if (add < 10 || add >Size * 100 + Size * 10 + Size){
            if (add != 1000)
                cout << "入力失敗しました" << endl << "正しく入力してください" << endl;
            continue;
        }
        data = add / 100;
        add = add % 100;
        ban[add / 10 - 1][add % 10 - 1] = data;   //マスに反映
    }
}

void input2(){
    char c_data[10];
    int data[10], ans;
    for (int i = 0; i < Size; i++){
        cout << i + 1 << "行目のデータを一括で入力してください" << endl << "空白は0を入力してください" << endl;
        cin >> c_data;
        for (int j = 0; j < Size; j++){
            data[j] = c_data[j] - '0';   //数字を数値に変換
            ban[i][j] = data[j];
        }
        show(false,0);
        cout << i + 1 << "行目のデータはこれで合っていますか?" << endl << "はい:0を入力, いいえ:0以外を入力" << endl << "Ans: ";
        cin >> ans;
        if (ans != 0)i--;
        else if (i == 8)continue;
    }
}

void readData(){
    FILE *fp;
    char c_data[dataSize];
    int Line = 0, Column = 0;
    fp = fopen("data.txt", "r");
    if (fp == NULL)
        cout << "FILE OPEN ERROR1" << endl;
    else{
        if (fgets(c_data, dataSize, fp) != NULL){
            for (int i = 0; i < dataSize - 1; i++){
                if (i != 0){
                    if (i % Size == 0){
                        Line++;
                        Column = 0;
                    }
                    else
                        Column++;
                }
                ban[Line][Column] = c_data[i] - '0';   //数字を数値に変換
            }
        }
        else
            cout << "FILE OPEN ERROR2" << endl;
        fclose(fp);
    }
    cout << "読み込んだファイルは以下のようになります" << endl;
    show(false,0);
}

void deleteNumFlag(int Line, int Column){
    int startLine = Line / 3 * 3;
    int startColumn = Column / 3 * 3;
    
    for (int Number = 1; Number <= Size; Number++){
        
        if (flagban[Line][Column][Number]){//チェックする必要がなければチェックしない
            
            for (int x = 0; x < Size; x++){//横方向のチェック
                if (Number == ban[Line][x])
                    flagban[Line][Column][Number] = false;//そのマスのNumberの可能性をなくす
            }
            
            for (int y = 0; y < Size; y++){//縦方向のチェック
                if (Number == ban[y][Column])
                    flagban[Line][Column][Number] = false;
            }
            
            for (int i = startLine; i < startLine + 3; i++){//ボックス内のチェック
                for (int j = startColumn; j < startColumn + 3; j++){
                    if (Number == ban[i][j])
                        flagban[Line][Column][Number] = false;
                }
            }
            
        }
        
    }
}

int retLineColumn(int Line, int Column, int Num){
    int CountX = 0, CountY = 0, CountBox = 0, possibleLine = 10, possibleColumn = 10;
    
    for (int x = 0; x < Size; x++){//横方向のチェック
        if (flagban[Line][x][Num]){
            possibleColumn = x;//一時的に記憶
            CountX++;
        }
    }
    
    if (CountX == 1){
        checkedTarget = 1;//横
        return possibleColumn;
    }
    else if (CountX == 0)
        return 99;
    
    for (int y = 0; y < Size; y++){//縦方向のチェック
        if (flagban[y][Column][Num]){
            possibleLine = y;//一時的に記憶
            CountY++;
        }
    }
    
    if (CountY == 1){
        checkedTarget = 2;//縦
        return possibleLine;
    }
    else if (CountY == 0)
        return 99;
    
    int startLine = Line / 3 * 3;
    int startColumn = Column / 3 * 3;
    
    for (int i = startLine; i < startLine + 3; i++){//ボックス内のチェック
        
        for (int j = startColumn; j < startColumn + 3; j++){
            
            if (flagban[i][j][Num]){
                possibleColumn = j;
                possibleLine = i;
                CountBox++;
            }
            
        }
        
    }
    
    if (CountBox == 1){
        checkedTarget = 3;//ボックス
        return possibleLine * 10 + possibleColumn;
    }
    else if (CountBox == 0)
        return 99;
    
    
    return 99;
}


void filledGrid(int Line, int Column, int Num, bool IsStart){//埋めたマスのx,yと埋めた数字を引数とする
    if (ban[Line][Column] != 0){//改めて空白でないか確認
        
        if(!IsStart)
            showPlace(Line, Column, Num);//埋めたマスについて表示
        
        for (int Number = 1; Number <= Size; Number++)//既に埋められたマスのすべての可能性をなくす
            flagban[Line][Column][Number] = false;
        
        for (int x = 0; x < Size; x++)//横方向のチェック
            flagban[Line][x][Num] = false;//埋めた数字の可能性をなくす
        
        for (int y = 0; y < Size; y++)//縦方向のチェック
            flagban[y][Column][Num] = false;//埋めた数字の可能性をなくす
        
        int startLine = Line / 3 * 3;
        int startColumn = Column / 3 * 3;
        
        for (int i = startLine; i < startLine + 3; i++)//ボックス内のチェック
            for (int j = startColumn; j < startColumn + 3; j++)
                flagban[i][j][Num] = false;//埋めた数字の可能性をなくす
        
    }
}

void startFlag(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column] != 0)
                filledGrid(Line, Column, ban[Line][Column], true);
        }
    }
}

//このtemporaryFlagがn国同盟のつもりです。
void temporaryFlag(int Line, int Column){//一時的にフラグを折る
    int flagCount[Size + 1] = {0,0,0,0,0,0,0,0,0,0};
    int startLine = Line / 3 * 3;
    int startColumn = Column / 3 * 3;
    int ngPosX[Size + 1][2];
    int ngPosY[Size + 1][2];
    
    for (int num = 1; num <= Size; num++){
        for (int i = startLine; i < startLine + 3; i++){
            for (int j = startColumn; j < startColumn + 3; j++){
                if (flagban[i][j][num]){
                    flagCount[num]++;
                    if (flagCount[num] <= 2){
                        ngPosX[num][flagCount[num] - 1] = j;
                        ngPosY[num][flagCount[num] - 1] = i;
                    }
                }
            }
        }
    }
    
    for (int first = 1; first <= Size; first++){
        for (int second = 1; second <= Size; second++){
            if (first != second && flagCount[first] == 2 && flagCount[second] == 2){
                if (flagban[ngPosY[first][0]][ngPosX[first][0]][second] && flagban[ngPosY[first][1]][ngPosX[first][1]][second]){
                    for (int k = 1; k <= Size; k++){
                        if(k != first && k != second){
                            flagban[ngPosY[first][0]][ngPosX[first][0]][k] = false;
                            flagban[ngPosY[first][1]][ngPosX[first][1]][k] = false;
                        }
                    }
                }
            }
        }
        
    }
    
}

void solve() {
    int Num, possibleNumCount = 0;
    
    for (int Line = 0; Line < Size; Line++){
        
        for (int Column = 0; Column < Size; Column++){
            
            if (ban[Line][Column] == 0){//空白である
                
                resetFlag();
                
                startFlag();
                
                deleteNumFlag(Line, Column);//入る可能性のある数字を減らす
                
                temporaryFlag(Line, Column);
                
                deleteNumFlag(Line, Column);//入る可能性のある数字を減らす
                
                possibleNumCount = 0;//マスごとに初期化
                
                for (Num = 1; Num <= Size; Num++){
                    
                    if (flagban[Line][Column][Num])//入る可能性を発見
                        possibleNumCount++;//カウントする
                }
                
                if (possibleNumCount == 1){//そのマスにおいて入る可能性のある数字が一つならば
                    
                  
                    
                    for (Num = 1; Num <= Size; Num++){
                        
                        if (flagban[Line][Column][Num]){//その唯一可能性のある数字を
                            cout << "outPut-onlyNum" << endl;
                            ban[Line][Column] = Num;//代入
                            filledGrid(Line, Column, Num, false);
                        }
                        
                    }
                    
                }
                
                for (Num = 1; Num <= Size; Num++){
                    
                    int pos = retLineColumn(Line, Column, Num);
                    
                    if (pos != 99){//99は発見できなかったとき
                        
                        if (checkedTarget == 3){//対象がボックス
                            cout << "outPut-Box" << endl;
                            ban[pos / 10][pos % 10] = Num;
                            filledGrid(pos / 10, pos % 10, Num, false);
                        }
                        else if (checkedTarget == 2){//縦
                            cout << "outPut-Column" << endl;
                            ban[pos][Column] = Num;
                            filledGrid(pos, Column, Num, false);
                        }
                        else if (checkedTarget == 1){//横
                            cout << "outPut-Line" << endl;
                            ban[Line][pos] = Num;
                            filledGrid(Line, pos, Num, false);
                        }
                        
                    }
                }

                
            }
        }
    }
}


bool IsEnd(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column] == 0)//空白を発見
                return false;//続行
        }
    }
    return true;
}

void setStart(){
    char mode;
    bool isOK = false;
    cout << "| ナンプレ・数独解読プログラム |" << endl;
    cout << "入力の仕方を選択してください" << endl;
    do{
        cout << "aを入力: 番地・数値入力モード(空白の多いとき推奨)" << endl;
        cout << "bを入力: 行一括入力モード(空白の少ないとき推奨)" << endl;
        cout << "fを入力: ファイルから読み込み" << endl << "入力モード :";
        cin >> mode;
        if (mode == 'a'){
            input();
            isOK = true;
        }
        else if (mode == 'b'){
            input2();
            isOK = true;
        }
        else if (mode == 'f'){
            readData();
            isOK = true;
        }
        else
            cout << "正しく入力してください" << endl;
    } while (!isOK);
}

int _tmain(int argc, const char * argv[]) {
    
    resetBan();
    
    resetFlag();
    
    setStart();
    
    do{//解く
        
        IsFill = false;
        
        solve();
        
        if (!IsFill)
            cout << "結果:盤への代入はありませんでした" << endl;

        show(false,0);
        
        cin.sync();//syncとgetで入力待ち
        cin.get();//getが1回だとバグが起こることがある
        cin.get();
        
    } while (!IsEnd());
    cout << "---------答え----------" << endl;
    show(false,0);
    return 0;
}

たいちう
記事: 418
登録日時: 9年前

Re: 数独を解くプログラム3

#2

投稿記事 by たいちう » 4年前

今回は私がやっときましたが、前スレと「n国同盟」とやらを説明するサイトへのリンクを貼りましょう。

前スレ
数独を解くプログラム2
参考サイト
ナンバープレース、数独 解法まとめ

それと、現在「n国同盟」が正しく実装されたら解けると考えている問題も、
ソースコードに埋め込んでもらえると、デバッグしやすいです。
酒を飲み始めてしまったので、今日はここまでです。

よっぴー

Re: 数独を解くプログラム3

#3

投稿記事 by よっぴー » 4年前

前スレとn国同盟説明のリンクは貼るべきですね。以後気をつけます。
問題は以下のようになります。

6 0 0 | 0 8 0 | 0 0 0
0 0 8 | 7 0 6 | 0 0 1
0 0 0 | 0 0 5 | 6 0 8
----+-----+----
8 4 0 | 0 0 2 | 0 9 3
0 0 0 | 8 4 3 | 0 0 0
0 2 0 | 5 0 0 | 0 8 4
----+----+-----
0 0 4 | 2 5 0 | 0 0 0
5 0 2 | 0 0 8 | 3 0 0
0 0 0 | 3 1 0 | 0 0 2
↓ファイル用
600080000008700001000005600840002090000803000020500084004200000500008300000010002

もしかすると、n国同盟以前の問題なのかもしれませんが
どのみち解けていません。ご指摘お願いします。

たいちう
記事: 418
登録日時: 9年前

Re: 数独を解くプログラム3

#4

投稿記事 by たいちう » 4年前

前スレを読み返してみたけど、デバッグするようにさんざん指摘していますね。
今回も同じことです。

後で時間が取れたときに見るかもしれませんが、
それを待つよりもご自分でデバッグした方が早いかもしれないし、
何より建設的ではないですか?

(問題として間違っていなければ)数独が必ず解けるのと同じように、
この種類の不具合は必ず原因を突き止められます。
何故しないのですか?

よっぴー

Re: 数独を解くプログラム3

#5

投稿記事 by よっぴー » 4年前

たいちう さんが書きました:前スレを読み返してみたけど、デバッグするようにさんざん指摘していますね。
今回も同じことです。
この種類の不具合は必ず原因を突き止められます。
何故しないのですか?
デバッグとしてフラグの状態を表示してみましたが、何もつかめません。
ですが、問題の続きは以下のようにして見つけることができることだけはわかりました。
(別の方に聞きました。プログラムはわからない方です)

-----------------------------------------------------------------
6 0 0 | 0 8 0 | 0 0 0
0 0 8 | 7 0 6 | 0 0 1
0 0 0 | 0 0 5 | 6 0 8
----+-----+----
8 4 D | M N 2 | 0 9 3
0 C 0 | 8 4 3 | 0 A B
0 2 E | 5 L 0 | 0 8 4
----+-----+----
K 0 4 | 2 5 0 | 0 0 0
5 H 2 | I J 8 | 3 0 0
G 0 F | 3 1 0 | 0 0 2

中段右ブロックで6が入るのはABしかないので、
横並びのCには6が入らないため、
中段左ブロックで6が入るのはDEだけになります。
従って、縦並びのFには6が入らず、Fに入るのは7と9だけとなります。
Gに入るのは元々7と9だけです。
GとFで7と9が使われるので、
下段左ブロックに注目すると、Hには1または6が入ることになります。
下段中央ブロックで6が入るのはIJしかないので、
横並びのHには6が入らないため、
Hに1が確定します。
-----------------------------------------------------------------

ただ、上のようにしてHに1が確定することはわかりますがプログラムにできません。
そもそもこの解き方はn国同盟と関係あるのでしょうか?それすらわかってません。
何をどうデバッグして、何を見たらよいのでしょうか?

たいちう
記事: 418
登録日時: 9年前

Re: 数独を解くプログラム3

#6

投稿記事 by たいちう » 4年前

> ただ、上のようにしてHに1が確定することはわかりますがプログラムにできません。
> そもそもこの解き方はn国同盟と関係あるのでしょうか?それすらわかってません。
> 何をどうデバッグして、何を見たらよいのでしょうか?

Hが確定する理由は判りました。
一方、「n国同盟」という用語は定義が曖昧な印象を感じていますので、
この解法が「n国同盟」なのかは判断付きません。多分違うと思いますが。


「n国同盟」という解法も万能ではないでしょうから、
解けなかったからといって不具合があるとは限りません。
n国同盟が正しく実装できれば、「このマスのこのフラグはクリアされるはず」、
というマスを探し、予想通りにクリアされるか確認しましょう。

例えば、説明ページの最初の図をデータとして与えれば、
「n国同盟」の処理を終えたとき、2つめの図の状態になるはずです。
このような確認をするのが「テスト」です。
期待通りの結果が得られなければ、「デバッグ」して原因を見つけましょう。


「n国同盟」を一旦忘れ、Hを確定する方法を実装しても良いでしょう。
長い手順は分割します。最初の説明は、
「中段右ブロックで6が入るのはABしかないので、
横並びのCには6が入らないため、」ですので、
まずはこれだけを考えましょう。できそうですか?

よっぴー

Re: 数独を解くプログラム3

#7

投稿記事 by よっぴー » 4年前

たいちう さんが書きました: 「中段右ブロックで6が入るのはABしかないので、
横並びのCには6が入らないため、」ですので、
まずはこれだけを考えましょう。できそうですか?
このことだけを考え、temporaryFlag関数内に幾つか追加しました。
結果からいうときちんとA,Bの6のフラグを調べた時、Cの6のフラグが折れるようになっていました。
ですが、まだ1は代入できませんでした。プログラムの改善点等々についてご指摘ください。

コード:

// ConsoleApplication5.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//
//#include "stdafx.h"
#include "stdio.h"
#include <time.h>
#include <iostream>
using namespace std;

#define Size 9
#define dataSize 82

int ban[Size][Size];
int answer[Size][Size];
int checkedTarget = 0;
bool flagban[Size][Size][Size + 1];//0は使わない
bool IsFill = false;//1箇所でも埋めたか
bool IsDebug = true;//デバッグ用(代入ごとに答え合わせをする)

void resetBan(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            ban[Line][Column] = 0;
        }
    }
}

void resetFlag(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            for (int Number = 1; Number <= Size; Number++)
                flagban[Line][Column][Number] = true;//すべての数字の入る可能性をありにする
        }
    }
}

void show(bool IsFlagType,int num){
    int Line, Column;
    cout << endl;
    cout << "   1 2 3   4 5 6   7 8 9" << endl;
    for (Line = 0; Line < Size; Line++){
        cout << Line + 1 << "0";
        for (Column = 0; Column < Size; Column++){
            if (Column == 3 || Column == 6)
                cout << " |";//マスの区切り表示
            if(IsFlagType && flagban[Line][Column][num])
                cout << " o";
            else if(IsFlagType && !flagban[Line][Column][num])
                cout << " x";
            else
                cout << " " << ban[Line][Column];//数字の表示
        }
        if (Line == 2 || Line == 5){
            cout << endl;
            cout << "   ------+-------+------";//マスの区切り表示
        }
        cout << endl;
    }
    cout << endl;
}

void showPlace(int Line, int Column, int Num){
    cout << "X:" << Column + 1 << " Y:" << Line + 1 << " <=" << Num;//埋めた座標と数字を表示
    if (IsDebug){
        if (answer[Line][Column] == Num)
            cout << ":ok" << endl;
        else
            cout << "wrong" << endl;
    }
    else
        cout << endl;
    IsFill = true;
}

//input関連はいずれGUIを使うようものに変更する
void input(){
    int add = 0, data = 0;
    cout << "データを以下のように入力してください" << endl << "行:5 列:7 数値:8 => 857" << endl << "1000を入力すると終了" << endl;
    while (add != 1000){
        show(false,0);
        cout << "1000を入力すると終了" << endl << "データ:";
        cin >> add;  //入力
        if (add < 10 || add >Size * 100 + Size * 10 + Size){
            if (add != 1000)
                cout << "入力失敗しました" << endl << "正しく入力してください" << endl;
            continue;
        }
        data = add / 100;
        add = add % 100;
        ban[add / 10 - 1][add % 10 - 1] = data;   //マスに反映
    }
}

void input2(){
    char c_data[10];
    int data[10], ans;
    for (int i = 0; i < Size; i++){
        cout << i + 1 << "行目のデータを一括で入力してください" << endl << "空白は0を入力してください" << endl;
        cin >> c_data;
        for (int j = 0; j < Size; j++){
            data[j] = c_data[j] - '0';   //数字を数値に変換
            ban[i][j] = data[j];
        }
        show(false,0);
        cout << i + 1 << "行目のデータはこれで合っていますか?" << endl << "はい:0を入力, いいえ:0以外を入力" << endl << "Ans: ";
        cin >> ans;
        if (ans != 0)i--;
        else if (i == 8)continue;
    }
}

void readData(bool anserType){
    FILE *fp;
    char c_data[dataSize];
    int Line = 0, Column = 0;
    fp = fopen("data.txt", "r");
    if (anserType)
        fp = fopen("answer.txt", "r");
    if (fp == NULL)
        cout << "FILE OPEN ERROR1" << endl;
    else{
        if (fgets(c_data, dataSize, fp) != NULL){
            for (int i = 0; i < dataSize - 1; i++){
                if (i != 0){
                    if (i % Size == 0){
                        Line++;
                        Column = 0;
                    }
                    else
                        Column++;
                }
                if(!anserType)
                    ban[Line][Column] = c_data[i] - '0';   //数字を数値に変換
                else
                    answer[Line][Column] = c_data[i] - '0';   //数字を数値に変換
            }
        }
        else
            cout << "FILE OPEN ERROR2" << endl;
        fclose(fp);
    }
    if (!anserType){
        cout << "読み込んだファイルは以下のようになります" << endl;
        show(false,0);
    }
}

void deleteNumFlag(int Line, int Column){
    int startLine = Line / 3 * 3;
    int startColumn = Column / 3 * 3;
    for (int Number = 1; Number <= Size; Number++){
        if (flagban[Line][Column][Number]){//チェックする必要がなければチェックしない
            for (int x = 0; x < Size; x++){//横方向のチェック
                if (Number == ban[Line][x])
                    flagban[Line][Column][Number] = false;//そのマスのNumberの可能性をなくす
            }
            for (int y = 0; y < Size; y++){//縦方向のチェック
                if (Number == ban[y][Column])
                    flagban[Line][Column][Number] = false;
            }
            for (int i = startLine; i < startLine + 3; i++){//ボックス内のチェック
                for (int j = startColumn; j < startColumn + 3; j++){
                    if (Number == ban[i][j])
                        flagban[Line][Column][Number] = false;
                }
            }
        }
    }
}

void temporaryFlag(int Line, int Column){
    int flagCount[Size + 1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    int startLine = Line / 3 * 3;
    int startColumn = Column / 3 * 3;
    int ngPosX[Size + 1][2] = { 0, 0 };
    int ngPosY[Size + 1][2] = { 0, 0 };
    for (int num = 1; num <= Size; num++){
        for (int i = startLine; i < startLine + 3; i++){
            for (int j = startColumn; j < startColumn + 3; j++){
                if (flagban[i][j][num]){
                    flagCount[num]++;//box内である数字の入る可能性を数える
                    if (flagCount[num] <= 2){//2マス以内なら座標を記憶(3マス以上となると破棄)
                        ngPosX[num][flagCount[num] - 1] = j;
                        ngPosY[num][flagCount[num] - 1] = i;
                    }
                }
            }
        }
    }
    //あるbox内で2マスしか可能性のない2つの数字の座標を比べ、同じ2マスならその2マス以外の可能性をなくす
    for (int num = 1; num <= Size; num++){
        for (int second = 1; second <= Size; second++){
            if (num != second && flagCount[num] == 2 && flagCount[second] == 2){
                if (flagban[ngPosY[num][0]][ngPosX[num][0]][second] && flagban[ngPosY[num][1]][ngPosX[num][1]][second]){
                    for (int k = 1; k <= Size; k++){
                        flagban[ngPosY[num][0]][ngPosX[num][0]][k] = false;
                        flagban[ngPosY[num][1]][ngPosX[num][1]][k] = false;
                    }
                }
            }
        }
        
        if (flagCount[num] == 2){//box内である数字の入る可能性が2マスしかないとき
            //横
            if(ngPosX[num][0] + 1 == ngPosX[num][1] || ngPosX[num][0] - 1 == ngPosX[num][1]){//ngPosX[num][0]と[1]が隣か
                for (int k = 1; k <= Size; k++){
                    if (k != ngPosX[num][0] && k != ngPosX[num][1]){
                        flagban[ngPosY[num][0]][k][num] = false;
                        flagban[ngPosY[num][1]][k][num] = false;
                    }
                }
                if(num == 6 && ngPosY[6][0] == 4){
                    show(true,6);//ここで成り立つことを調べている(デバッグ)
                }
            }
            //縦
            if(ngPosY[num][0] + 1 == ngPosY[num][1] || ngPosY[num][0] - 1 == ngPosY[num][1]){//ngPosY[num][0]と[1]が隣か
                for (int k = 1; k <= Size; k++){
                    if (k != ngPosY[num][0] && k != ngPosY[num][1]){
                        flagban[k][ngPosX[num][0]][num] = false;
                        flagban[k][ngPosX[num][1]][num] = false;
                    }
                }
            }
        }
        
    }
}

int retLineColumn(int Line, int Column, int Num){
    int CountX = 0, CountY = 0, CountBox = 0, possibleLine = 10, possibleColumn = 10;
    for (int x = 0; x < Size; x++){//横方向のチェック
        if (flagban[Line][x][Num]){
            possibleColumn = x;//一時的に記憶
            CountX++;
        }
    }
    if (CountX == 1){
        checkedTarget = 1;//横
        return possibleColumn;
    }
    else if (CountX == 0)
        return 99;
    for (int y = 0; y < Size; y++){//縦方向のチェック
        if (flagban[y][Column][Num]){
            possibleLine = y;//一時的に記憶
            CountY++;
        }
    }
    if (CountY == 1){
        checkedTarget = 2;//縦
        return possibleLine;
    }
    else if (CountY == 0)
        return 99;
    int startLine = Line / 3 * 3;
    int startColumn = Column / 3 * 3;
    for (int i = startLine; i < startLine + 3; i++){//ボックス内のチェック
        for (int j = startColumn; j < startColumn + 3; j++){
            if (flagban[i][j][Num]){
                possibleColumn = j;
                possibleLine = i;
                CountBox++;
            }
        }
    }
    if (CountBox == 1){
        checkedTarget = 3;//ボックス
        return possibleLine * 10 + possibleColumn;
    }
    else if (CountBox == 0)
        return 99;
    
    return 99;
}

void filledGrid(int Line, int Column, int Num, bool IsStart){//埋めたマスのx,yと埋めた数字を引数とする
    if (ban[Line][Column] != 0){//改めて空白でないか確認
        if(!IsStart)
            showPlace(Line, Column, Num);//埋めたマスについて表示
        for (int Number = 1; Number <= Size; Number++)//既に埋められたマスのすべての可能性をなくす
            flagban[Line][Column][Number] = false;
        for (int x = 0; x < Size; x++)//横方向のチェック
            flagban[Line][x][Num] = false;//埋めた数字の可能性をなくす
        for (int y = 0; y < Size; y++)//縦方向のチェック
            flagban[y][Column][Num] = false;//埋めた数字の可能性をなくす
        int startLine = Line / 3 * 3;
        int startColumn = Column / 3 * 3;
        for (int i = startLine; i < startLine + 3; i++)//ボックス内のチェック
            for (int j = startColumn; j < startColumn + 3; j++)
                flagban[i][j][Num] = false;//埋めた数字の可能性をなくす
    }
}

void startFill(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column] != 0)
                filledGrid(Line, Column, ban[Line][Column], true);
        }
    }
}

void solve() {
    int Num, possibleNumCount;
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column] == 0){//空白である
                
                startFill();
                deleteNumFlag(Line, Column);//入る可能性のある数字を減らす
                temporaryFlag(Line, Column);
                possibleNumCount = 0;//マスごとに初期化
                for (Num = 1; Num <= Size; Num++){
                    if (flagban[Line][Column][Num])//入る可能性を発見
                        possibleNumCount++;//カウントする
                }
                if (possibleNumCount == 1){//そのマスにおいて入る可能性のある数字が一つならば
                    
                    for (Num = 1; Num <= Size; Num++){
                        if (flagban[Line][Column][Num]){//その唯一可能性のある数字を
                            ban[Line][Column] = Num;//代入
                            filledGrid(Line, Column, Num, false);
                        }
                    }
                }
                for (Num = 1; Num <= Size; Num++){
                    int pos = retLineColumn(Line, Column, Num);
                    if (pos != 99){//99は発見できなかったとき
                        if (checkedTarget == 3){//対象がボックス
                            ban[pos / 10][pos % 10] = Num;
                            filledGrid(pos / 10, pos % 10, Num, false);
                        }
                        else if (checkedTarget == 2){//縦
                            ban[pos][Column] = Num;
                            filledGrid(pos, Column, Num, false);
                        }
                        else if (checkedTarget == 1){//横
                            ban[Line][pos] = Num;
                            filledGrid(Line, pos, Num, false);
                        }
                    }
                }
                resetFlag();
            }
        }
    }
}

bool IsEnd(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column] == 0)//空白を発見
                return false;//続行
        }
    }
    return true;
}

void setStart(){
    char mode;
    bool isOK = false;
    cout << "| ナンプレ・数独解読プログラム |" << endl;
    cout << "入力の仕方を選択してください" << endl;
    do{
        cout << "aを入力: 番地・数値入力モード(空白の多いとき推奨)" << endl;
        cout << "bを入力: 行一括入力モード(空白の少ないとき推奨)" << endl;
        cout << "fを入力: ファイルから読み込み" << endl << "入力モード :";
        cin >> mode;
        if (mode == 'a'){
            input();
            isOK = true;
        }
        else if (mode == 'b'){
            input2();
            isOK = true;
        }
        else if (mode == 'f'){
            readData(false);
            if(IsDebug)
                readData(true);//デバッグ用
            isOK = true;
        }
        else
            cout << "正しく入力してください" << endl;
    } while (!isOK);
}

int _tmain(int argc, const char * argv[]) {
    resetBan();
    resetFlag();
    setStart();
    do{//解く
        IsFill = false;
        cin.sync();//syncとgetで入力待ち
        cin.get();//getが1回だとバグが起こることがある
        cin.get();
        solve();
        if (!IsFill)
            cout << "盤への代入はありませんでした" << endl;
        show(false,0);
    } while (!IsEnd());
    cout << "---------答え----------" << endl;
    show(false,0);
    return 0;
}

たいちう
記事: 418
登録日時: 9年前

Re: 数独を解くプログラム3

#8

投稿記事 by たいちう » 4年前

次はこれですね。

> 中段左ブロックで6が入るのはDEだけになります。
> 従って、縦並びのFには6が入らず、Fに入るのは7と9だけとなります。

Fのタテヨコとブロックを見ると、6・7・9の可能性がありましたが、
中段左ブロックの6の入るマスがD・Eのみになったことから、
Fから6の可能性がなくなりました。

判定の原理は「Cに6が入らない」を導いたのと同じはずです。
順々にやっていって、どこまでコーディングとテストができますか?


# プログラムに無駄は多そうですが、できればまず完成させましょう。
# あれこれ効率を考えて未完成よりは、冗長でも完成させた方が、
# よほど価値があります。
# とはいえ、無駄に複雑になりすぎて完成させられないこともあるので、
# にっちもさっちもいかなくなったら質問してください。

よっぴー

Re: 数独を解くプログラム3

#9

投稿記事 by よっぴー » 4年前

たいちう さんが書きました: Fのタテヨコとブロックを見ると、6・7・9の可能性がありましたが、
中段左ブロックの6の入るマスがD・Eのみになったことから、
Fから6の可能性がなくなりました。
このことを実装する際に大きなことに気づき、以下のように対処し、結果を得ました。

・resetFlagの位置がおかしい。このままだとせっかくフラグを折っても意味がない。
 →結局、どこが正しいのかわからないまま。模索中。

・temporaryFlagは一つのboxしか見ていない。せっかく中央右のブロックから中央左の6の可能をD,Eのみに絞ったにもかかわらず、中央左のboxを調べずに解こうとしている。
→Line,Columnを渡すのではなく2重のfor文を使いすべてのboxを一回のtemporaryFlagで一巡するように変更
 →誤入力が生まれてしまった

・上のままではすべてのboxを一度調べるが、一巡だとflagを折ってもそれよりも前のマスに影響されない
→do~while文を使い、flagを折る限りループ
 →無限ループした

正直、なんにも進んでおりません。
上の3点について「必要ない、間違いだ」と思いましたらそうおっしゃってください。
逆に、「これは必要。ただし〜のように変更すべき」と思いましたらどのように変更すべきなのかヒントをください。

よろしくお願いします。

よっぴー

Re: 数独を解くプログラム3

#10

投稿記事 by よっぴー » 4年前

プログラムを以下のように書き換えました。色々とスッキリさせ、その上でtemporaryFlagを大幅に変更したのですが、「数独を解く」という点では全く進歩がありません。temporaryFlagをループさせることで6のフラグを折ったときのようなことを連続してできるようにし、結果的にどこかのマスのフラグを1つに絞れるつもり(今なら6より7,9。7,9より1のみになる)なのですが、代入まで持っていくことができません。プログラム、アルゴリズムに関するご指摘お待ちしております。

コード:

// ConsoleApplication5.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

#include "stdafx.h"
#include "stdio.h"
#include <time.h>
#include <iostream>
using namespace std;

#define Size 9
#define dataSize 82

int ban[Size][Size];
int answer[Size][Size];
int checkedTarget = 0;
bool flagban[Size][Size][Size + 1];//0は使わない
bool IsFill = false;//1箇所でも埋めたか
bool IsDebug = true;//デバッグ用(代入ごとに答え合わせをする)

void resetBan(){
    for (int Line = 0; Line < Size; Line++){
        
        for (int Column = 0; Column < Size; Column++){
            
            ban[Line][Column] = 0;
            
        }
        
    }
    
}

void resetFlag(){
    
    for (int Line = 0; Line < Size; Line++){
        
        for (int Column = 0; Column < Size; Column++){
            
            for (int Number = 1; Number <= Size; Number++)
                flagban[Line][Column][Number] = true;//すべての数字の入る可能性をありにする
        }
        
    }
    
}

void show(bool IsFlagType, int num){
    
    int Line, Column;
    
    cout << endl;
    cout << "   1 2 3   4 5 6   7 8 9" << endl;
    
    for (Line = 0; Line < Size; Line++){
        
        cout << Line + 1 << "0";
        
        for (Column = 0; Column < Size; Column++){
            
            if (Column == 3 || Column == 6)
                cout << " |";//マスの区切り表示
            
            if (IsFlagType && flagban[Line][Column][num])
                cout << " o";
            
            else if (IsFlagType && !flagban[Line][Column][num])
                cout << " x";
            
            else
                cout << " " << ban[Line][Column];//数字の表示
        }
        
        if (Line == 2 || Line == 5)
            cout << endl << "   ------+-------+------";//マスの区切り表示
        
        cout << endl;
        
    }
    
    cout << endl;
    
}

void showPlace(int Line, int Column, int Num){
    
    cout << "X:" << Column + 1 << " Y:" << Line + 1 << " <=" << Num;//埋めた座標と数字を表示
    
    if (IsDebug){
        
        if (answer[Line][Column] == Num)
            cout << ":ok" << endl;
        else
            cout << "wrong" << endl;
    }
    else
        cout << endl;
    
    IsFill = true;
    
}

void input(){
    
    int add = 0, data = 0;
    
    cout << "データを以下のように入力してください" << endl << "行:5 列:7 数値:8 => 857" << endl << "1000を入力すると終了" << endl;
    
    while (add != 1000){
        
        show(false, 0);
        
        cout << "1000を入力すると終了" << endl << "データ:";
        
        cin >> add;  //入力
        
        if (add < 10 || add >Size * 100 + Size * 10 + Size){
            
            if (add != 1000)
                cout << "入力失敗しました" << endl << "正しく入力してください" << endl;
            
            continue;
        }
        
        data = add / 100;
        
        add = add % 100;
        
        ban[add / 10 - 1][add % 10 - 1] = data;   //マスに反映
        
    }
    
}

void input2(){
    
    char c_data[10];
    
    int data[10], ans;
    
    for (int i = 0; i < Size; i++){
        
        cout << i + 1 << "行目のデータを一括で入力してください" << endl << "空白は0を入力してください" << endl;
        
        cin >> c_data;
        
        for (int j = 0; j < Size; j++){
            
            data[j] = c_data[j] - '0';   //数字を数値に変換
            
            ban[i][j] = data[j];
            
        }
        
        show(false, 0);
        
        cout << i + 1 << "行目のデータはこれで合っていますか?" << endl << "はい:0を入力, いいえ:0以外を入力" << endl << "Ans: ";
        
        cin >> ans;
        
        if (ans != 0)i--;
        
        else if (i == 8)continue;
        
    }
    
}

void readData(bool anserType){
    
    FILE *fp;
    char c_data[dataSize];
    int Line = 0, Column = 0;
    
    fp = fopen("data.txt", "r");
    
    if (anserType)
        fp = fopen("answer.txt", "r");
    
    if (fp == NULL)
        cout << "FILE OPEN ERROR1" << endl;
    
    else{
        
        if (fgets(c_data, dataSize, fp) != NULL){
            
            for (int i = 0; i < dataSize - 1; i++){
                
                if (i != 0){
                    
                    if (i % Size == 0){
                        
                        Line++;
                        
                        Column = 0;
                        
                    }
                    else
                        Column++;
                    
                }
                
                if (!anserType)
                    ban[Line][Column] = c_data[i] - '0';   //数字を数値に変換
                
                else
                    answer[Line][Column] = c_data[i] - '0';   //数字を数値に変換
            }
            
        }
        else
            cout << "FILE OPEN ERROR2" << endl;
        
        fclose(fp);
        
    }
    
    if (!anserType){
        
        cout << "読み込んだファイルは以下のようになります" << endl;
        
        show(false, 0);
        
    }
    
}

void deleteNumFlag(){
    
    for (int Line = 0; Line < Size; Line++){
        
        for (int Column = 0; Column < Size; Column++){
            
            int startLine = Line / 3 * 3;
            int startColumn = Column / 3 * 3;
            
            for (int Number = 1; Number <= Size; Number++){
                
                if (flagban[Line][Column][Number]){//チェックする必要がなければチェックしない
                    
                    for (int x = 0; x < Size; x++){//横方向のチェック
                        
                        if (Number == ban[Line][x])
                            flagban[Line][Column][Number] = false;//そのマスのNumberの可能性をなくす
                    }
                    
                    for (int y = 0; y < Size; y++){//縦方向のチェック
                        
                        if (Number == ban[y][Column])
                            flagban[Line][Column][Number] = false;
                    }
                    
                    for (int i = startLine; i < startLine + 3; i++){//ボックス内のチェック
                        
                        for (int j = startColumn; j < startColumn + 3; j++){
                            
                            if (Number == ban[i][j])
                                flagban[Line][Column][Number] = false;
                            
                        }
                        
                    }
                    
                }
                
            }
        }
        
    }
    
}

int retLineColumn(int Line, int Column, int Num){
    int CountX = 0, CountY = 0, CountBox = 0, possibleLine = 10, possibleColumn = 10;
    for (int x = 0; x < Size; x++){//横方向のチェック
        if (flagban[Line][x][Num]){
            possibleColumn = x;//一時的に記憶
            CountX++;
        }
    }
    if (CountX == 1){
        checkedTarget = 1;//横
        return possibleColumn;
    }
    else if (CountX == 0)
        return 99;
    for (int y = 0; y < Size; y++){//縦方向のチェック
        if (flagban[y][Column][Num]){
            possibleLine = y;//一時的に記憶
            CountY++;
        }
    }
    if (CountY == 1){
        checkedTarget = 2;//縦
        return possibleLine;
    }
    else if (CountY == 0)
        return 99;
    int startLine = Line / 3 * 3;
    int startColumn = Column / 3 * 3;
    for (int i = startLine; i < startLine + 3; i++){//ボックス内のチェック
        for (int j = startColumn; j < startColumn + 3; j++){
            if (flagban[i][j][Num]){
                possibleColumn = j;
                possibleLine = i;
                CountBox++;
            }
        }
    }
    if (CountBox == 1){
        checkedTarget = 3;//ボックス
        return possibleLine * 10 + possibleColumn;
    }
    else if (CountBox == 0)
        return 99;
    
    return 99;
}

void filledGrid(int Line, int Column, int Num, bool IsStart){//埋めたマスのx,yと埋めた数字を引数とする
    if (ban[Line][Column] != 0){//改めて空白でないか確認
        if (!IsStart)
            showPlace(Line, Column, Num);//埋めたマスについて表示
        for (int Number = 1; Number <= Size; Number++)//既に埋められたマスのすべての可能性をなくす
            flagban[Line][Column][Number] = false;
        for (int x = 0; x < Size; x++)//横方向のチェック
            flagban[Line][x][Num] = false;//埋めた数字の可能性をなくす
        for (int y = 0; y < Size; y++)//縦方向のチェック
            flagban[y][Column][Num] = false;//埋めた数字の可能性をなくす
        int startLine = Line / 3 * 3;
        int startColumn = Column / 3 * 3;
        for (int i = startLine; i < startLine + 3; i++)//ボックス内のチェック
            for (int j = startColumn; j < startColumn + 3; j++)
                flagban[i][j][Num] = false;//埋めた数字の可能性をなくす
    }
}

void startFill(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column] != 0)
                filledGrid(Line, Column, ban[Line][Column], true);
        }
    }
}

void temporaryFlag(){
    
    int hitPosX[Size + 1][2];
    int hitPosY[Size + 1][2];
    int startPos[3] = { 0, 3, 6 };
    int flagCount[Size + 1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    int loopCount = 0;
    
    do{
        
        loopCount++;
        
        for (int index = 1; index <= Size; index++)
            flagCount[index] = 0;
        
        for (int Num = 1; Num <= Size; Num++){
            
            for (int boxPosY = 0; boxPosY < 3; boxPosY++){
                
                for (int boxPosX = 0; boxPosX < 3; boxPosX++){
                    
                    int startLine = startPos[boxPosY];
                    int startColumn = startPos[boxPosX];
                    
                    for (int i = startLine; i < startLine + 3; i++){
                        
                        for (int j = startColumn; j < startColumn + 3; j++){
                            
                            if (flagban[i][j][Num]){
                                
                                flagCount[Num]++;//box内である数字の入る可能性を数える
                                
                                if (flagCount[Num] <= 2){//2マス以内なら座標を記憶(3マス以上となると破棄)
                                    
                                    hitPosX[Num][flagCount[Num] - 1] = j;
                                    hitPosY[Num][flagCount[Num] - 1] = i;
                                }
                                
                            }
                            
                        }
                        
                    }
                }
            }
            
            if (flagCount[Num] == 2){
                
                //あるbox内で2マスしか可能性のない2つの数字の座標を比べ、同じ2マスならその2つの数字以外の可能性をなくす
                for (int num = 1; num <= Size; num++){
                    
                    for (int second = 1; second <= Size; second++){
                        
                        if (num != second && flagCount[num] == 2 && flagCount[second] == 2){
                            
                            if (flagban[hitPosY[num][0]][hitPosX[num][0]][second] && flagban[hitPosY[num][1]][hitPosX[num][1]][second]){
                                
                                for (int k = 1; k <= Size; k++){
                                    
                                    flagban[hitPosY[num][0]][hitPosX[num][0]][k] = false;
                                    flagban[hitPosY[num][1]][hitPosX[num][1]][k] = false;
                                    
                                }
                                
                            }
                            
                        }
                        
                    }
                    
                }
                
                for (int num = 1; num <= Size; num++){
                    
                    if (hitPosY[num][0] == hitPosY[num][1]){//左右の関係
                        
                        for (int k = 1; k <= Size; k++){
                            
                            if (k != hitPosX[num][0] && k != hitPosX[num][1]){
                                
                                flagban[hitPosY[num][0]][k][num] = false;
                                
                            }
                            
                        }
                        
                    }
                    
                    if (hitPosX[num][0] == hitPosX[num][1]){//上下の関係
                        
                        for (int k = 1; k <= Size; k++){
                            
                            if (k != hitPosY[num][0] && k != hitPosY[num][1]){
                                
                                flagban[k][hitPosX[num][0]][num] = false;
                            }
                            
                        }
                        
                    }
                    
                }
                
            }
            else if (flagCount[Num] == 1){
                cout << "--break--" << endl;
                return;
            }
            
        }
        
    } while (loopCount >= 5);
    
}



void solve() {
    
    int Num = 0, num = 0, possibleNumCount = 0;
    
    startFill();
    
    deleteNumFlag();
    
    temporaryFlag();
    
    for (int Line = 0; Line < Size; Line++){
        
        for (int Column = 0; Column < Size; Column++){
            
            if (ban[Line][Column] == 0){//空白である
                
                possibleNumCount = 0;//マスごとに初期化
                
                for (Num = 1; Num <= Size; Num++){
                    
                    if (flagban[Line][Column][Num]){//入る可能性を発見
                        
                        possibleNumCount++;//カウントする
                        
                        num = Num;//その数字を記憶
                    }
                    
                    int pos = retLineColumn(Line, Column, Num);
                    
                    if (pos != 99){//99は発見できなかったとき
                        
                        if (checkedTarget == 3){//対象がボックス
                            
                            
                            ban[pos / 10][pos % 10] = Num;
                            
                            cout << "box --- ";
                            
                            filledGrid(pos / 10, pos % 10, Num, false);
                            
                        }
                        
                        else if (checkedTarget == 2){//縦
                            
                            ban[pos][Column] = Num;
                            
                            cout << "column --- ";
                            
                            filledGrid(pos, Column, Num, false);
                            
                        }
                        
                        else if (checkedTarget == 1){//横
                            
                            ban[Line][pos] = Num;
                            
                            cout << "line --- ";
                            
                            filledGrid(Line, pos, Num, false);
                            
                        }
                        
                    }
                    
                }//Num
                
                if (possibleNumCount == 1){//そのマスにおいて入る可能性のある数字が一つならば
                    
                    ban[Line][Column] = num;//代入
                    
                    cout << "only --- ";
                    
                    filledGrid(Line, Column, num, false);
                    
                }

            }//空白
            
        }//column
        
    }//line
    
    resetFlag();
    
}

bool IsEnd(){
    
    for (int Line = 0; Line < Size; Line++){
        
        for (int Column = 0; Column < Size; Column++){
            
            if (ban[Line][Column] == 0)//空白を発見
                return false;//続行
        }
        
    }
    
    return true;
    
}

void setStart(){
    
    char mode;
    bool isOK = false;
    
    cout << "| ナンプレ・数独解読プログラム |" << endl;
    cout << "入力の仕方を選択してください" << endl;
    
    do{
        cout << "aを入力: 番地・数値入力モード(空白の多いとき推奨)" << endl;
        cout << "bを入力: 行一括入力モード(空白の少ないとき推奨)" << endl;
        cout << "fを入力: ファイルから読み込み" << endl << "入力モード :";
        cin >> mode;
        
        if (mode == 'a'){
            
            input();
            
            isOK = true;
            
        }
        
        else if (mode == 'b'){
            
            input2();
            
            isOK = true;
            
        }
        
        else if (mode == 'f'){
            
            readData(false);
            
            if (IsDebug)
                readData(true);//デバッグ用
            
            isOK = true;
        }
        
        else
            cout << "正しく入力してください" << endl;
        
    } while (!isOK);
    
}

int _tmain(int argc, const char * argv[]) {

    resetBan();
    
    resetFlag();
    
    setStart();
    
    do{//解く
        
        IsFill = false;
        
        cin.sync();//syncとgetで入力待ち
        cin.get();//getが1回だとバグが起こることがある
        cin.get();
        
        solve();
        
        if (!IsFill)
            cout << "盤への代入はありませんでした" << endl;
        
        show(false, 0);
        
    } while (!IsEnd());
    
    cout << "---------答え----------" << endl;
    
    show(false, 0);
    
    return 0;
    
}

たいちう
記事: 418
登録日時: 9年前

Re: 数独を解くプログラム3

#11

投稿記事 by たいちう » 4年前

時間がないのでNo.10のプログラムはちゃんと見ていません。
No.7のプログラムで致命的な点を2つ見つけていたのですが、
どうやらそれは修正されたようですね。


> 結果的にどこかのマスのフラグを1つに絞れるつもり(今なら6より7,9。7,9より1のみになる)なのですが、
> 代入まで持っていくことができません。

予想と結果が違うんですよね?
結果は突然湧いて出てくるわけではなく、途中経過を経て結果が導かれます。
プログラムを作るときに予想していた途中経過は、どこまで予想通りでしたか?
それをちゃんと確認しましょう。

# もしかして、すごく原始的な開発環境なのですか?
# Break Pointとか、Step実行とか、使えませんか?
# 要所要所でcoutで出力する方法でも十分デバッグ可能ですが、
# 強力なデバッガを使うのも良いかも。
# 例えば、フリーのVisual Studio Express Editionなどが定番です。

# ついでに、張り付けたソースコードに無駄な空白行が多いと思いませんか?

たいちう
記事: 418
登録日時: 9年前

Re: 数独を解くプログラム3

#12

投稿記事 by たいちう » 4年前

「GとFで7と9が使われるので、下段左ブロックに注目すると、Hには1または6が入ることになります。」

言い換えると、

「GとFで7と9が使われるので、同じブロックのHには7と9は入りません。」

この処理が抜けていませんか?

よっぴー

Re: 数独を解くプログラム3

#13

投稿記事 by よっぴー » 4年前

返信ありがとうございます。

まず、環境についての質問にお答えします。
私は学校と家とで別々の環境を使っています。
学校ではWindows8,VisualStudio2013であり、家ではOS X Yosemite 10.10.3,Xcode6です。
プログラムはメールで直接送っています。(_tmainやstdafx.hは随時変更してます)
強力なデバッガーを使ったら?とのことですが、残念ながらデバッガーの知識を持ち合わせておりません。
今後も必要になるので知識をつけるべきもしれませんが・・・

肝心のプログラムですが
たいちう さんが書きました: 「GとFで7と9が使われるので、同じブロックのHには7と9は入りません。」
この処理が抜けていませんか?
おっしゃている通り、この処理は抜けていました。
この処理の実装を含めたtemporaryFlag()を再び大幅に変更しました。

結果はというと、誤入力が大幅に減りました。
ですが、実際に埋めて、それが正解というのも増えていません。
条件を厳しくしたからだと思います。なんとか6月中には完成させたいです。
プログラム、アルゴリズムに対するご指摘よろしくお願いします。

コード:

// ConsoleApplication5.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

#include "stdafx.h"
#include "stdio.h"
#include <time.h>
#include <iostream>
using namespace std;

#define Size 9
#define dataSize 82

int ban[Size][Size];
int answer[Size][Size];
int checkedTarget = 0;
bool flagban[Size][Size][Size + 1];//0は使わない
bool IsFill = false;//1箇所でも埋めたか
bool IsDebug = true;//デバッグ用(代入ごとに答え合わせをする)

void resetBan(){
    for (int Line = 0; Line < Size; Line++){
        
        for (int Column = 0; Column < Size; Column++){
            
            ban[Line][Column] = 0;
            
        }
        
    }
    
}

void resetFlag(){
    
    for (int Line = 0; Line < Size; Line++){
        
        for (int Column = 0; Column < Size; Column++){
            
            for (int Number = 1; Number <= Size; Number++)
                flagban[Line][Column][Number] = true;//すべての数字の入る可能性をありにする
        }
        
    }
    
}

void show(bool IsFlagType, int num){
    
    int Line, Column;
    
    cout << endl;
    cout << "   1 2 3   4 5 6   7 8 9" << endl;
    
    for (Line = 0; Line < Size; Line++){
        
        cout << Line + 1 << "0";
        
        for (Column = 0; Column < Size; Column++){
            
            if (Column == 3 || Column == 6)
                cout << " |";//マスの区切り表示
            
            if (IsFlagType && flagban[Line][Column][num])
                cout << " o";
            
            else if (IsFlagType && !flagban[Line][Column][num])
                cout << " x";
            
            else
                cout << " " << ban[Line][Column];//数字の表示
        }
        
        if (Line == 2 || Line == 5)
            cout << endl << "   ------+-------+------";//マスの区切り表示
        
        cout << endl;
        
    }
    
    cout << endl;
    
}

void showPlace(int Line, int Column, int Num){
    
    cout << "X:" << Column + 1 << " Y:" << Line + 1 << " <=" << Num;//埋めた座標と数字を表示
    
    if (IsDebug){
        
        if (answer[Line][Column] == Num)
            cout << ":ok" << endl;
        else
            cout << "wrong" << endl;
    }
    else
        cout << endl;
    
    IsFill = true;
    
}

void input(){
    
    int add = 0, data = 0;
    
    cout << "データを以下のように入力してください" << endl << "行:5 列:7 数値:8 => 857" << endl << "1000を入力すると終了" << endl;
    
    while (add != 1000){
        
        show(false, 0);
        
        cout << "1000を入力すると終了" << endl << "データ:";
        
        cin >> add;  //入力
        
        if (add < 10 || add >Size * 100 + Size * 10 + Size){
            
            if (add != 1000)
                cout << "入力失敗しました" << endl << "正しく入力してください" << endl;
            
            continue;
        }
        
        data = add / 100;
        
        add = add % 100;
        
        ban[add / 10 - 1][add % 10 - 1] = data;   //マスに反映
        
    }
    
}

void input2(){
    
    char c_data[10];
    
    int data[10], ans;
    
    for (int i = 0; i < Size; i++){
        
        cout << i + 1 << "行目のデータを一括で入力してください" << endl << "空白は0を入力してください" << endl;
        
        cin >> c_data;
        
        for (int j = 0; j < Size; j++){
            
            data[j] = c_data[j] - '0';   //数字を数値に変換
            
            ban[i][j] = data[j];
            
        }
        
        show(false, 0);
        
        cout << i + 1 << "行目のデータはこれで合っていますか?" << endl << "はい:0を入力, いいえ:0以外を入力" << endl << "Ans: ";
        
        cin >> ans;
        
        if (ans != 0)i--;
        
        else if (i == 8)continue;
        
    }
    
}

void readData(bool anserType){
    
    FILE *fp;
    char c_data[dataSize];
    int Line = 0, Column = 0;
    
    fp = fopen("data.txt", "r");
    
    if (anserType)
        fp = fopen("answer.txt", "r");
    
    if (fp == NULL)
        cout << "FILE OPEN ERROR1" << endl;
    
    else{
        
        if (fgets(c_data, dataSize, fp) != NULL){
            
            for (int i = 0; i < dataSize - 1; i++){
                
                if (i != 0){
                    
                    if (i % Size == 0){
                        
                        Line++;
                        
                        Column = 0;
                        
                    }
                    else
                        Column++;
                    
                }
                
                if (!anserType)
                    ban[Line][Column] = c_data[i] - '0';   //数字を数値に変換
                
                else
                    answer[Line][Column] = c_data[i] - '0';   //数字を数値に変換
            }
            
        }
        else
            cout << "FILE OPEN ERROR2" << endl;
        
        fclose(fp);
        
    }
    
    if (!anserType){
        
        cout << "読み込んだファイルは以下のようになります" << endl;
        
        show(false, 0);
        
    }
    
}

void deleteNumFlag(){
    
    for (int Line = 0; Line < Size; Line++){
        
        for (int Column = 0; Column < Size; Column++){
            
            int startLine = Line / 3 * 3;
            int startColumn = Column / 3 * 3;
            
            for (int Number = 1; Number <= Size; Number++){
                
                if (flagban[Line][Column][Number]){//チェックする必要がなければチェックしない
                    
                    for (int x = 0; x < Size; x++){//横方向のチェック
                        
                        if (Number == ban[Line][x])
                            flagban[Line][Column][Number] = false;//そのマスのNumberの可能性をなくす
                    }
                    
                    for (int y = 0; y < Size; y++){//縦方向のチェック
                        
                        if (Number == ban[y][Column])
                            flagban[Line][Column][Number] = false;
                    }
                    
                    for (int i = startLine; i < startLine + 3; i++){//ボックス内のチェック
                        
                        for (int j = startColumn; j < startColumn + 3; j++){
                            
                            if (Number == ban[i][j])
                                flagban[Line][Column][Number] = false;
                            
                        }
                        
                    }
                    
                }
                
            }
        }
        
    }
    
}

int retLineColumn(int Line, int Column, int Num){
    
    int CountX = 0, CountY = 0, CountBox = 0, possibleLine = 10, possibleColumn = 10;
    int startLine = Line / 3 * 3;
    int startColumn = Column / 3 * 3;
    
    for (int x = 0; x < Size; x++){//横方向のチェック
        
        if (flagban[Line][x][Num]){
            
            possibleColumn = x;//一時的に記憶
            CountX++;
            
        }
        
    }
    
    if (CountX == 1){
        checkedTarget = 1;//横
        return possibleColumn;
    }
    else if (CountX == 0)
        return 99;
    
    for (int y = 0; y < Size; y++){//縦方向のチェック
        
        if (flagban[y][Column][Num]){
            
            possibleLine = y;//一時的に記憶
            CountY++;
        }
        
    }
    
    if (CountY == 1){
        checkedTarget = 2;//縦
        return possibleLine;
    }
    else if (CountY == 0)
        return 99;
    
    for (int i = startLine; i < startLine + 3; i++){//ボックス内のチェック
        
        for (int j = startColumn; j < startColumn + 3; j++){
            
            if (flagban[i][j][Num]){
                
                possibleColumn = j;
                possibleLine = i;
                CountBox++;
            }
            
        }
        
    }
    
    if (CountBox == 1){
        checkedTarget = 3;//ボックス
        return possibleLine * 10 + possibleColumn;
    }
    else if (CountBox == 0)
        return 99;
    
    
    return 99;
}

void filledGrid(int Line, int Column, int Num, bool IsStart){//埋めたマスのx,yと埋めた数字を引数とする
    
    if (ban[Line][Column] != 0){//改めて空白でないか確認
        
        if (!IsStart)
            showPlace(Line, Column, Num);//埋めたマスについて表示
        
        for (int Number = 1; Number <= Size; Number++)//既に埋められたマスのすべての可能性をなくす
            flagban[Line][Column][Number] = false;
        
        for (int x = 0; x < Size; x++)//横方向のチェック
            flagban[Line][x][Num] = false;//埋めた数字の可能性をなくす
        
        for (int y = 0; y < Size; y++)//縦方向のチェック
            flagban[y][Column][Num] = false;//埋めた数字の可能性をなくす
        
        int startLine = Line / 3 * 3;
        int startColumn = Column / 3 * 3;
        
        for (int i = startLine; i < startLine + 3; i++)//ボックス内のチェック
            for (int j = startColumn; j < startColumn + 3; j++)
                flagban[i][j][Num] = false;//埋めた数字の可能性をなくす
    }
}

void startFill(){
    
    for (int Line = 0; Line < Size; Line++){
        
        for (int Column = 0; Column < Size; Column++){
            
            if (ban[Line][Column] != 0)
                filledGrid(Line, Column, ban[Line][Column], true);
            
        }
        
    }
    
}

void temporaryFlag(){
    
    int hitPosX[Size + 1][2];
    int hitPosY[Size + 1][2];
    int startPos[3] = { 0, 3, 6 };
    int flagCount[Size][Size + 1];
    int loopCount = 0;
    
    do{
        
        loopCount++;
        
        for (int index = 0; index < Size; index++){
            for (int num = 1; num <= Size; num++){
                flagCount[index][num] = 0;
            }
        }
        
        for(int boxIndex = 0; boxIndex < Size; boxIndex++){
            
            int startLine = startPos[boxIndex / 3];//index番目のboxにおける左上の座標を求める
            int startColumn = startPos[boxIndex % 3];
            
            for (int Num = 1; Num <= Size; Num++){
                    
                for (int i = startLine; i < startLine + 3; i++){
                        
                    for (int j = startColumn; j < startColumn + 3; j++){
                            
                        if (flagban[i][j][Num]){
                                
                            flagCount[boxIndex][Num]++;//数字の入る可能性を数える
                                
                            if (flagCount[boxIndex][Num] <= 2){//2マス以内なら座標を記憶(3マス以上となると破棄)
                                
                                hitPosX[Num][flagCount[boxIndex][Num] - 1] = j;
                                hitPosY[Num][flagCount[boxIndex][Num] - 1] = i;
                            }
                                
                        }
                            
                    }//startColumn
                        
                }//startLine
            
            }//Num
            
        }//boxIndex

        for (int index = 0; index < Size; index++){//boxのindex(左上から右下へ)
            
            for (int Num = 1; Num <= Size; Num++){
                
                if (flagCount[index][Num] == 2){
                    
                    //あるbox内で2マスしか可能性のない2つの数字の座標を比べ、同じ2マスなら
                    
                    for (int second = 1; second <= Size; second++){
                        
                        if (Num != second && flagCount[index][Num] == 2 && flagCount[index][second] == 2){
                            
                            if (flagban[hitPosY[Num][0]][hitPosX[Num][0]][second] && flagban[hitPosY[Num][1]][hitPosX[Num][1]][second]){
                                
                                //2マスにおけるその2つの数字以外の可能性をなくす
                                for (int k = 1; k <= Size; k++){
                                    
                                    if (k != Num && k != second){
                                        
                                        flagban[hitPosY[Num][0]][hitPosX[Num][0]][k] = false;
                                        flagban[hitPosY[Num][1]][hitPosX[Num][1]][k] = false;
                                        
                                    }
                                    
                                }
                                
                                //その2マス以外の2つの数字の可能性をなくす
                                int startLine = startPos[index / 3];
                                int startColumn = startPos[index % 3]; 
                                
                                for (int i = startLine; i < startLine + 3; i++){
                                    
                                    for (int j = startColumn; j < startColumn + 3; j++){
                                        
                                        if (!(hitPosY[Num][0] == i && hitPosX[Num][0] == j) && !(hitPosY[Num][1] == i && hitPosX[Num][1] == j)){
                                            
                                            flagban[i][j][Num] = false;
                                            flagban[i][j][second] = false;
                                            
                                        }
                                        
                                    }
                                    
                                }
                                
                            }
                            
                        }
                        
                    }
                    
                    if (hitPosY[Num][0] == hitPosY[Num][1]){//左右の関係
                        
                        for (int k = 1; k <= Size; k++){
                            
                            if (k != hitPosX[Num][0] && k != hitPosX[Num][1]){
                                flagban[hitPosY[Num][0]][k][Num] = false; 
                            }
                            
                        }
                        
                    }
                    
                    if (hitPosX[Num][0] == hitPosX[Num][1]){//上下の関係
                        
                        for (int k = 1; k <= Size; k++){
                            
                            if (k != hitPosY[Num][0] && k != hitPosY[Num][1]){
                                flagban[k][hitPosX[Num][0]][Num] = false;
                            }
                        }
                        
                    }
                    
                }else if (flagCount[index][Num] == 1){
                    cout << "EndBreak---loopCout: " << loopCount << " Index: " << index << " Num: " << Num << endl;
                    return;
                }
                
            }//Num
            
        }//index
        
    } while (loopCount < 5);//無限ループしないようループは5回まで
    
    cout << "EndLoop---loopCount: " << loopCount << endl;
    
}

void solve() {
    
    int Num = 0, num = 0, possibleNumCount = 0;
    
    resetFlag();
    
    startFill();
    
    //deleteNumFlag();//おそらくあってもなくても同じ
    
    temporaryFlag();
    
    /*for (int num = 1; num <= Size; num++){
     cout << "Num: " << num << endl;
     show(true,num);
     }*/
    
    for (int Line = 0; Line < Size; Line++){
        
        for (int Column = 0; Column < Size; Column++){
            
            if (ban[Line][Column] == 0){//空白である
                
                possibleNumCount = 0;//マスごとに初期化
                
                for (Num = 1; Num <= Size; Num++){
                    
                    if (flagban[Line][Column][Num]){//入る可能性を発見
                        
                        possibleNumCount++;//カウントする
                        
                        num = Num;//その数字を記憶
                    }
                }
                
                if (possibleNumCount == 1){//そのマスにおいて入る可能性のある数字が一つならば
                    
                    ban[Line][Column] = num;//代入
                    
                    cout << "only --- ";
                    
                    filledGrid(Line, Column, num, false);
                    
                }
                
                for (Num = 1; Num <= Size; Num++){
                    
                    int pos = retLineColumn(Line, Column, Num);
                    
                    if (pos != 99){//99は発見できなかったとき
                        
                        if (checkedTarget == 3){//対象がボックス
                            
                            
                            ban[pos / 10][pos % 10] = Num;
                            
                            cout << "box --- ";
                            
                            filledGrid(pos / 10, pos % 10, Num, false);
                            
                        }
                        
                        else if (checkedTarget == 2){//縦
                            
                            ban[pos][Column] = Num;
                            
                            cout << "column --- ";
                            
                            filledGrid(pos, Column, Num, false);
                            
                        }
                        
                        else if (checkedTarget == 1){//横
                            
                            ban[Line][pos] = Num;
                            
                            cout << "line --- ";
                            
                            filledGrid(Line, pos, Num, false);
                            
                        }
                        
                    }
                    
                }
                
            }
            
        }
        
    }
    
}

bool IsEnd(){
    
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column] == 0)//空白を発見
                return false;//続行
        }
    }
    
    return true;
    
}

void setStart(){
    
    char mode;
    bool IsOK = false;
    
    cout << "| ナンプレ・数独解読プログラム |" << endl;
    cout << "入力の仕方を選択してください" << endl;
    
    do{
        cout << "aを入力: 番地・数値入力モード(空白の多いとき推奨)" << endl;
        cout << "bを入力: 行一括入力モード(空白の少ないとき推奨)" << endl;
        cout << "fを入力: ファイルから読み込み" << endl << "入力モード :";
        cin >> mode;
        
        if (mode == 'a'){
            input();
            IsOK = true;
        }
        
        else if (mode == 'b'){
            input2();
            IsOK = true;
        }
        
        else if (mode == 'f'){
            readData(false);
            if (IsDebug)
                readData(true);//デバッグ用
            IsOK = true;
        }
        
        else
            cout << "正しく入力してください" << endl;
        
    } while (!IsOK);
    
}

int _tmain(int argc, const char * argv[]) {
    
    resetBan();
    
    resetFlag();
    
    setStart();
    
    do{//解く
        
        IsFill = false;
        
        cin.sync();//syncとgetで入力待ち
        cin.get();//getが1回だとバグが起こることがある
        cin.get();
        
        solve();
        
        if (!IsFill)
            cout << "盤への代入はありませんでした" << endl;
        
        show(false, 0);
        
    } while (!IsEnd());
    
    cout << "---------答え----------" << endl;
    
    show(false, 0);
    
    return 0;
    
}

たいちう
記事: 418
登録日時: 9年前

Re: 数独を解くプログラム3

#14

投稿記事 by たいちう » 4年前

> 結果はというと、誤入力が大幅に減りました。
> ですが、実際に埋めて、それが正解というのも増えていません。
> 条件を厳しくしたからだと思います。なんとか6月中には完成させたいです。
> プログラム、アルゴリズムに対するご指摘よろしくお願いします。

結構プログラムは書けていると思いますが、根本的な考え方が間違っていると思います。
数独の解き方についてではなく、プログラムの作り方についてです。

誤入力が減ったとありますが、誤入力することが一度でもあるならば、それはバグです。
条件を厳しくしたから正解が増えていないと推測していますが、
条件には正しい条件と間違った条件しかありません。
いい塩梅の厳しさを調整するものではありません。

解けない場合で現段階で許されているのは、
「実装済みの方法では手詰まり」という場合だけです。


> おっしゃている通り、この処理は抜けていました。

どうしたら、このようなことを自分で気づけるようになりますか?
私は気合で見つけたわけではありませんよ。
今までのデバッグについての私の指摘では足りないですか?

よっぴー

Re: 数独を解くプログラム3

#15

投稿記事 by よっぴー » 4年前

誤入力が減っても存在する限り、バグがある。
(超複雑なシステムなどはともかく)バグは1つでもあってはいけない。
バグがある限り、デバッグを繰り返し、自力で間違いを見つける。そうですよね。

人に頼ろうとし過ぎでした。本当に申し訳ありません。
もう少し自力でどこまで直せるのか試してみようと思います。

閉鎖

“C言語何でも質問掲示板” へ戻る