数独を解くプログラム2

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

数独を解くプログラム2

#1

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

以前、数独を解くプログラムに関する質問をさせていただいたものです。再び数独を解くプログラムを作っております。
理由としましては、前回のプログラムはバックトラック法を使用した力技であり、本来の目的である人工知能とは遠くかけ離れていてからです。そのため改めて人間に近いアルゴリズムに沿って解くプログラムを作成することにしました。

現在、非常に簡単な問題であれば解ける具合です。現在のやり方としては、
1:入れたい数字を決める
2:入れたい数字と同じ数字の行、列、箱(3*3の部分)にフラグを立てる
3:空白をみつける 
4:3のマスのフラグが立っていないか確かめる 
5:箱ないでフラグが立っていないところが1つか確かめる 
6;4、5を満たすのであれば実際に代入
7:1へもどる
といった具合になっております。(むしろ、これだけです)

ですが、難しい問題になってくると5番を満たすことができず、無限ループのようになってしまいます。
ここからどういったやり方で難しい問題を解けるようにできるのでしょうか?
たくさんの意見お待ちしております。

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

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

#2

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

よっぴーさん自身は、難しい問題を解くときにどうしていますか?
その方法を忠実にコーディングしたら、人間に近いアルゴリズムになりませんか?

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

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

#3

投稿記事 by みけCAT » 8年前

よっぴー さんが書きました:ですが、難しい問題になってくると5番を満たすことができず、無限ループのようになってしまいます。
数独の仕様だと思います。
例えば「入る可能性がある数字」(入れてもすぐルール違反にならない数字)の数が一番少ないマスを選んで、
そこに順番に「入る可能性がある数字」を入れてバックトラック、などでしょうか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

yoko
記事: 24
登録日時: 13年前

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

#4

投稿記事 by yoko » 8年前

自分も数独のプログラムは作成したことがありますが、
次のように作りました。

1.問題読み込み
2.取り合えす空白部分にすべての数字のフラグを立てる
3.空白マスを上から順に見ていき、縦、横、同じブロック(3×3)にある数字をフラグから消去
4.フラグが1つしかないマスは確定
5.縦、横、同じブロックでフラグが1つしかない数字はその箇所を確定
6.3.に戻る
7.埋まらない場合はバックトラックで解く

7.は難しい問題のときに起こりますので、そこも理詰めで解きたい場合は
高度な解法を実装することになります。詳しくは検索してみてください。

現在プログラムをアップできないのですが、必要とあればアップいたしますので、
返信ください。

よっぴー

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

#5

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

たいちうさん、みけCATさん、yokoさん回答ありがとうございます。

自身の解き方を忠実に再現するのも、無限ループが仕様なのもおっしゃるとおりだと思います。

また、具体的なアルゴリズムを教えていただきありがとうございます。
yokoさんの書き方だと2次元配列ではなく3次元配列を使うのでしょうか?
どの程度の難易度の問題を解くことができるのでしょうか?空白の数などで難易度を教えていただきたいです。


もし仮にyokoさんのプログラムと似たプログラムをつくったとして、
皆さんは人間に近いと思いますか?それとも大きく離れていると思いますか?
あくまで率直な意見で構いませんので回答お願いします。

プログラムは自分で考えたい気持ちの方が強いので、
できればある程度プログラムが完成してからアップして欲しいです。

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

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

#6

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

> もし仮にyokoさんのプログラムと似たプログラムをつくったとして、
> 皆さんは人間に近いと思いますか?それとも大きく離れていると思いますか?
> あくまで率直な意見で構いませんので回答お願いします。

バックトラックの部分が人間らしくないと思います。
プログラミングは簡単なのですが。
人間が難問を解くための定石が他にもあるので、
それを実装すると人間らしいのではないでしょうか。
それでも解けない問題があった場合も、とことん深さ優先のバックトラックではなく、
反復深化のような方法を取ると人間らしくなるかも。

# 人間らしく数独を解く、というテーマが、
# 人工知能に近づいているとも思えないのですが、
# そこの辺はどっちでもいいか。

yoko
記事: 24
登録日時: 13年前

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

#7

投稿記事 by yoko » 8年前

>プログラムは自分で考えたい気持ちの方が強いので、
>できればある程度プログラムが完成してからアップして欲しいです。
ご要望あり次第アップいたしますので、その際はご連絡ください。
なお、私のプログラムのアルゴリズムは下記の本を参考にしています。
また、DXライブラリでの作成となります。

鉛筆パズルゲームプログラミング ナンバープレース・お絵かきパズル・ナンバークロスワードのアルゴリズム

たいちろうさんが書かれている通り、バックトラックの部分は人間らしくないのはその通りです。
そのために
>7.は難しい問題のときに起こりますので、そこも理詰めで解きたい場合は
>高度な解法を実装することになります。詳しくは検索してみてください。
と記載しました。

ナンバープレース、数独 解法まとめ
に高度な解法が記載されていましたので、バックトラックの部分をこちらに変更すれば
人間らしい(理詰めで解ける)となりそうです。

よっぴー

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

#8

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

yoko さんが書きました:自分も数独のプログラムは作成したことがありますが、
次のように作りました。

1.問題読み込み
2.取り合えす空白部分にすべての数字のフラグを立てる
3.空白マスを上から順に見ていき、縦、横、同じブロック(3×3)にある数字をフラグから消去
4.フラグが1つしかないマスは確定
5.縦、横、同じブロックでフラグが1つしかない数字はその箇所を確定
6.3.に戻る
7.埋まらない場合はバックトラックで解く
とりあえず、上の1~4までができるプログラムを自分なりに書いてみました。
ですが、実際に実行すると1マスすら埋めることができません。どこが悪いのでしょうか?
突っ込みどころ満載だと思いますがご指摘、ご教授よろしくお願いします。
数独プログラムとしてのご指摘はもちろん、変数名や{}の数などどんなことでもご指摘ください。
具体的な回答を頂けると助かります。

コード:

#include "stdafx.h"
#include "stdio.h"
#include <time.h>

#include <iostream>

using namespace std;

#define Size 9
#define dataSize 82

int ban[Size][Size][Size + 1];//[Line][Column][0]が実際の盤,[1]以降は1で可能性あり。0でなし。


void resetBan(){

	for (int Line = 0; Line < Size; Line++){

		for (int Column = 0; Column < Size; Column++){

			ban[Line][Column][0] = 0;

		}
	}
}

void resetFlag(){
	for (int Line = 0; Line < Size; Line++){

		for (int Column = 0; Column < Size; Column++){

			for (int Number = 1; Number < Size + 1; Number++)
				ban[Line][Column][Number] = 1;//すべての数字の入る可能性をありにする

		}
	}
	
}

void show(){

	int Line, Column;

	printf("\n   1 2 3   4 5 6   7 8 9\n");

	for (Line = 0; Line < Size; Line++){

		printf("%d0", Line + 1);

		for (Column = 0; Column < Size; Column++){

			if (Column == 3 || Column == 6)
				printf(" |");							//マスの区切り表示

			printf("%2d", ban[Line][Column][0]);			//数字の表示

		}

		if (Line == 2 || Line == 5)
			printf("\n   ------+-------+------");		//マスの区切り表示

		printf("\n");

	}

	printf("\n");

}

void ReadData(){

	FILE *fp;
	char c_data[dataSize];
	int Line = 0, Column = 0;

	fp = fopen("data.txt", "r");

	if (fp == NULL)
		printf("FILE OPEN ERROR1\n");

	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][0] = c_data[i] - '0';   //数字を数値に変換

			}
		}

		else
			printf("FILE OPEN ERROR2\n");

		fclose(fp);
	}
}

void checkNumFlag(int Line, int Column){

	int startLine = Line / 3 * 3;

	int startColumn = Column / 3 * 3;

	for (int Number = 1; Number < Size + 1; Number++){

		if (ban[Line][Column][Number] != 0){//チェックする必要がなければチェックしない

			for (int x = 0; x < Size; x++){//横方向のチェック

				if (Number == ban[Line][x][0])
					ban[Line][Column][Number] = 0;//そのマスのNumberの可能性を0にする

			}

			for (int y = 0; y < Size; y++){//縦方向のチェック

				if (Number == ban[y][Column][0])
					ban[Line][Column][Number] = 0;

			}

			for (int i = startLine; i < startLine + 3; i++){//ボックス内のチェック

				for (int j = startColumn; j < startColumn + 3; j++){

					if (Number == ban[i][j][0])
						ban[Line][Column][Number] = 0;
				}
			}

		}
	}

}

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] == 0){//空白である

				checkNumFlag(Line, Column);//入る可能性のある数字を減らす

				for (Num = 1; Num < Size + 1; Num++){

					if (ban[Line][Column][Num] != 0)//入る可能性のある数字を発見
						possibleNumCount++;//カウントする

				}

				//カウントした結果
				if (possibleNumCount == 1){//入る可能性のある数字が一つならば

					for (Num = 1; Num < Size + 1; Num++)
						if (ban[Line][Column][Num] == 1)//唯一可能性のある数字を代入
							ban[Line][Column][Num] = Num;

				}
			}
		}

	}

}

bool IsEnd(){

	for (int Line = 0; Line < Size; Line++){

		for (int Column = 0; Column < Size; Column++){

			if (ban[Line][Column][0] == 0)
				return false;
		}
	}

	return true;

}


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

	int mode = 0, next = 1;

	resetBan();
	resetFlag();

	printf("| ナンプレ・数独解読プログラム |\n");
     
       ReadData();//ファイルから問題読み込み(0を空白とする)

	show();

	solve();

	do{//解く

		if (next != 0)
			solve();//具体的に解く

		show();

		printf("0以外を入力すると次に進む:");//解いている工程をみせるため
		cin >> next;


	} while (!IsEnd());

	printf("| 答え |\n");
	show();

	return 0;

}

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

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

#9

投稿記事 by みけCAT » 8年前

とりあえずコンパイル用stdafx.hです。

コード:

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

int main(void) {
	const char *a;
	return _tmain(0, &a);
}
よっぴー さんが書きました:数独プログラムとしてのご指摘はもちろん、変数名や{}の数などどんなことでもご指摘ください。
具体的な回答を頂けると助かります。
  • 202行目のmodeが使用されていない
  • 217行目、222行目、223行目で、0を入力すると次に進まない仕様にしている意味がよくわからない
  • 174行目ではban[Line][Column][Num]ではなく、ban[Line][Column][0]に代入するべきである
  • 162行目の前でpossibleNumCountを0に初期化していないので、例えば

    コード:

    023456780456789123780123456234567891567891234891234567345678912678912345012345678
    
    という問題が解けない
  • 簡単に入力を変えられるよう、入力ファイル名をコマンドライン引数で指定できるか、ファイルシステム上のファイルではなく標準入力から読み込める方が好きである
  • C++なので、定数は#defineよりconstを使ったほうがよさそう
  • checkNumFlag関数で、各Numberについて縦、横、3x3にあるかのチェックを行うのではなく、
    縦、横、3x3をチェックして、そこに書かれている数字が1以上9以下のとき、それをNumberとしてフラグを折るようにすると、計算量が減ってよさそう
  • C++であり、また標準ライブラリなので、

    コード:

    #include "stdio.h"
    #include <time.h>
    
    ではなく、

    コード:

    #include <cstdio>
    #include <ctime>
    
    と書いたほうがよさそう
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

よっぴー

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

#10

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

たくさんのご指摘ありがとうございます。
ご指摘を受けてどうするか、またご指摘に対する自分の解釈を載せておきました。
引き続き回答お願いします。
  • 202行目のmodeが使用されていない
     →入力の仕方を2種類(ファイル、座標指定入力)に分けていました。ですが、ほぼファイル読み込みしか使用しておらず、202行目を削除を忘れていました。現在は削除しました。
  • 217行目、222行目、223行目で、0を入力すると次に進まない仕様にしている意味がよくわからない
     →数字を埋めているところを定期的に表示したかったからです。ですが、0でなければいけない理由がありませんでした。「何か」入力すると次に進むよう修正したいと思います。
  • 174行目ではban[Line][Column][Num]ではなく、ban[Line][Column][0]に代入するべきである
     →表示が全く変わらなかった原因ですね。修正します。
  • 162行目の前でpossibleNumCountを0に初期化していないので、例えば

    コード:

    023456780456789123780123456234567891567891234891234567345678912678912345012345678
    
    という問題が解けない
     →すみません。自分の読解力ではなぜなのか、また、この問題がどういった問題なのかわかりません。引き続き解説お願いします。
  • 簡単に入力を変えられるよう、入力ファイル名をコマンドライン引数で指定できるか、ファイルシステム上のファイルではなく標準入力から読み込める方が好きである
     →これは、data.txtに限らず、ファイル名を入力するとそのファイルを読み込むように変更せよということでしょうか?
  • C++なので、定数は#defineよりconstを使ったほうがよさそう
     →もともと、C言語で書いておりました。ただ、visualstudioを使うことになり半強制的にC++になったがためにこういったミスが(今後も)あると思います。ご指摘なさった点についてはご指摘通り修正したいと思います。
  • checkNumFlag関数で、各Numberについて縦、横、3x3にあるかのチェックを行うのではなく、
    縦、横、3x3をチェックして、そこに書かれている数字が1以上9以下のとき、それをNumberとしてフラグを折るようにすると、計算量が減ってよさそう
     →なるほど。for文ですべてチェックするのではなく、見つけたものからフラグを折っていくということであっていますか?
  • C++であり、また標準ライブラリなので、

    コード:

    #include "stdio.h"
    #include <time.h>
    
    ではなく、

    コード:

    #include <cstdio>
    #include <ctime>
    
    と書いたほうがよさそう
     →再びC++ならではミスが出てきました。ご指摘通り修正します。
修正次第コードをアップしたいと思います。(早ければ明日)

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

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

#11

投稿記事 by みけCAT » 8年前

よっぴー さんが書きました:162行目の前でpossibleNumCountを0に初期化していないので、例えば

コード:

023456780456789123780123456234567891567891234891234567345678912678912345012345678
という問題が解けない
 →すみません。自分の読解力ではなぜなのか、また、この問題がどういった問題なのかわかりません。引き続き解説お願いします。
見やすい形にすると、

コード:

   1 2 3   4 5 6   7 8 9
10 0 2 3 | 4 5 6 | 7 8 0
20 4 5 6 | 7 8 9 | 1 2 3
30 7 8 0 | 1 2 3 | 4 5 6
   ------+-------+------
40 2 3 4 | 5 6 7 | 8 9 1
50 5 6 7 | 8 9 1 | 2 3 4
60 8 9 1 | 2 3 4 | 5 6 7
   ------+-------+------
70 3 4 5 | 6 7 8 | 9 1 2
80 6 7 8 | 9 1 2 | 3 4 5
90 0 1 2 | 3 4 5 | 6 7 8
となります。
この盤面で、真っ先にチェックされる一番左上のマスに入る可能性のある数字は、1と9の2個あるため、possibleNumCountは2になり、マスを埋めることはできません。
さらに、この時点でpossibleNumCountが2のため、
他のマスもpossibleNumCountが2以上となり(C言語のint型は少なくとも-32767~32767の整数を格納できるので、オーバーフローはしないはず)、
他のマスも埋めることはできません。
よって、全くマスを埋めることができないので、このプログラムでは(正しくフラグではなく盤面にNumを代入したとしても)この問題を解くことはできません。
よっぴー さんが書きました:簡単に入力を変えられるよう、入力ファイル名をコマンドライン引数で指定できるか、ファイルシステム上のファイルではなく標準入力から読み込める方が好きである
 →これは、data.txtに限らず、ファイル名を入力するとそのファイルを読み込むように変更せよということでしょうか?
いいえ、ファイル名を入力するとそのファイルを読み込むように変更するか、ファイルシステム上のファイルではなく標準入力から読み込むように変更せよということです。
よっぴー さんが書きました:checkNumFlag関数で、各Numberについて縦、横、3x3にあるかのチェックを行うのではなく、
縦、横、3x3をチェックして、そこに書かれている数字が1以上9以下のとき、それをNumberとしてフラグを折るようにすると、計算量が減ってよさそう
 →なるほど。for文ですべてチェックするのではなく、見つけたものからフラグを折っていくということであっていますか?
確信は持てませんが、多分あっています。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

よっぴー

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

#12

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

以下のように書き換えたところ数独を解くプログラムとして動くようにはなりました。ありがとうございます。

コード:

#include "stdafx.h"
#include "stdio.h"
#include <time.h>
#include <iostream>
using namespace std;
#define Size 9
#define dataSize 82
int ban[Size][Size][Size + 1];//[Line][Column][0]が実際の盤,[1]以降は1で可能性あり。0でなし。

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

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

void show(){
    int Line, Column;
    printf("\n   1 2 3   4 5 6   7 8 9\n");
    for (Line = 0; Line < Size; Line++){
        printf("%d0", Line + 1);
        for (Column = 0; Column < Size; Column++){
            if (Column == 3 || Column == 6)
                printf(" |");       //マスの区切り表示
            printf("%2d", ban[Line][Column][0]);   //数字の表示
        }
        if (Line == 2 || Line == 5)
            printf("\n   ------+-------+------");  //マスの区切り表示
        printf("\n");
    }
    printf("\n");
}

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

void inputv2(){
    char c_data[10];
    int data[10], ans;
    for (int i = 0; i < Size; i++){
        printf("%d行目のデータを一括で入力してください\n空白は0を入力してください\n", i + 1);
        cin >> c_data;
        
        for (int j = 0; j < Size; j++){
            data[j] = c_data[j] - '0';   //数字を数値に変換
            ban[i][j][0] = data[j];
        }
        show();
        printf("%d行目のデータはこれで合っていますか?\nはい:0を入力, いいえ:0以外を入力\nAns: ", i + 1);
        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("/Users/hibikiyoshida/Desktop/data.txt", "r");
    if (fp == NULL)
        printf("FILE OPEN ERROR1\n");
    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][0] = c_data[i] - '0';   //数字を数値に変換
            }
        }
        else
            printf("FILE OPEN ERROR2\n");
        fclose(fp);
    }
    printf("読み込んだファイルは以下のようになります\n");
    show();
}

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

void solve() {
    int Num,possibleNumCount;
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column][0] == 0){//空白である
                checkNumFlag(Line, Column);//入る可能性のある数字を減らす
                possibleNumCount = 0;//マスごとに初期化
                for (Num = 1; Num < Size + 1; Num++){
                    if (ban[Line][Column][Num] != 0)//入る可能性のある数字を発見
                        possibleNumCount++;//カウントする
                }
                //カウントした結果
                if (possibleNumCount == 1){//入る可能性のある数字が一つならば
                    for (Num = 1; Num < Size + 1; Num++)
                        if (ban[Line][Column][Num] == 1)//唯一可能性のある数字を代入
                            ban[Line][Column][0] = Num;
                }
            }
        }
    }
}

bool IsEnd(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column][0] == 0)
                return false;
        }
    }
    return true;
}

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

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

    resetBan();
    resetFlag();
    setStart();

    do{//解く
        printf("0を入力すると次に進む:");
        cin >> next;
        if (next != '0')
            printf("正しく入力してください\n");
        else{
            solve();//具体的に解く
            show();
        }
    } while (!IsEnd());
    printf("--------答え---------\n");
    show();
    return 0;
}
ですが以前に指摘されたリストに関して一部実装、変更できていませんので、その点については以下のとおりです。
まだまだご指摘ください。
  • 0を入力すると次に進まない仕様にしている意味がよくわからない
     →数字を埋めているところを定期的に(1回のsolveにつき1回)表示したかったからであり、入力されるものや条件はなんでも良いのですが、何かよい方法ありますか?
  • 簡単に入力を変えられるよう、入力ファイル名をコマンドライン引数で指定できるか、ファイルシステム上のファイルではなく標準入力から読み込める方が好きである
     →実装したつもりなのですが、あっていますか??解釈間違ってますか?
  • C++なので、定数は#defineよりconstを使ったほうがよさそう
     →すみません。変更してません。やっぱり変更すべきですか?
  • checkNumFlag関数で、各Numberについて縦、横、3x3にあるかのチェックを行うのではなく、
    縦、横、3x3をチェックして、そこに書かれている数字が1以上9以下のとき、それをNumberとしてフラグを折るようにすると、計算量が減ってよさそう
     →すみません。変更してません。時間ができ次第変更します。
  • C++であり、また標準ライブラリなので、

    コード:

    #include "stdio.h"
    #include <time.h>
    
    ではなく、

    コード:

    #include <cstdio>
    #include <ctime>
    
    と書いたほうがよさそう
     →変更します。
また、難度の高い問題はまだ解けないです。yokoさんの「縦、横、同じブロックでフラグが1つしかない数字はその箇所を確定」は明日には実装しようと思います。

よっぴー

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

#13

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

上のコードにおいて間隔・隙間が少ないのは気しないでください^^;
わざとではなく、今使っているPCとコードを書いているPCが異なり、メールでコードを送ってしまったからです。今後はこのようなことのないようにしたいと思います。見にくくてすみません。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

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

#14

投稿記事 by みけCAT » 8年前

よっぴー さんが書きました:0を入力すると次に進まない仕様にしている意味がよくわからない
 →数字を埋めているところを定期的に(1回のsolveにつき1回)表示したかったからであり、入力されるものや条件はなんでも良いのですが、何かよい方法ありますか?
無駄な条件分岐はせずにstd::getline(std::cin, dummy);とかでしょうか?

コード:

#include <iostream>
#include <string>

int main(void) {
	std::string dummy;
	for(;;) {
		std::cout << "hoge" << std::endl;
		std::getline(std::cin, dummy);
	}
	return 0;
}
よっぴー さんが書きました:簡単に入力を変えられるよう、入力ファイル名をコマンドライン引数で指定できるか、ファイルシステム上のファイルではなく標準入力から読み込める方が好きである
 →実装したつもりなのですが、あっていますか??解釈間違ってますか?
だいたいあっていると思います。
ただし、input関数のエラーチェックが甘く、例えば100と入力すると強制終了しました。
ところで、なぜファイル入力は環境依存なパスを固定値で指定する仕様にしたのでしょうか?
よっぴー さんが書きました:C++なので、定数は#defineよりconstを使ったほうがよさそう
 →すみません。変更してません。やっぱり変更すべきですか?
どっちでもいいと思います。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

よっぴー

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

#15

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

数独プログラムとして難しめの問題も解けるよう、
yoko さんが書きました: 1.問題読み込み
2.取り合えす空白部分にすべての数字のフラグを立てる
3.空白マスを上から順に見ていき、縦、横、同じブロック(3×3)にある数字をフラグから消去
4.フラグが1つしかないマスは確定
5.縦、横、同じブロックでフラグが1つしかない数字はその箇所を確定
6.3.に戻る
上のyokoさんの5番を実装したつもりなのですが、以前よりも解けなくなってしまいました。
具体的にはボックス・列・行に2つ以上同じ数字を入れてしまうなどです。

入力や計算量の削減など多くの問題は存在しますが、数独を解けていませんので、
今は解くことを一番にご指摘いただきたいです。
自分のプログラム(特にsolve2とretLineColumn)が間違っているのは事実です。
具体的な指摘をいただけると幸いです。回答よろしくお願いします。

コード:

// 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][Size + 1];//[Line][Column][0]が実際の盤,[1]以降は1で可能性あり。0でなし。
int checkedTarget = 0;

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

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

void show(){
    int Line, Column;
    printf("\n   1 2 3   4 5 6   7 8 9\n");
    for (Line = 0; Line < Size; Line++){
        printf("%d0", Line + 1);
        for (Column = 0; Column < Size; Column++){
            if (Column == 3 || Column == 6)
                printf(" |");       //マスの区切り表示
            printf("%2d", ban[Line][Column][0]);   //数字の表示
        }
        if (Line == 2 || Line == 5)
            printf("\n   ------+-------+------");  //マスの区切り表示
        printf("\n");
    }
    printf("\n");
}

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

void input2(){
    char c_data[10];
    int data[10], ans;
    for (int i = 0; i < Size; i++){
        printf("%d行目のデータを一括で入力してください\n空白は0を入力してください\n", i + 1);
        cin >> c_data;
        for (int j = 0; j < Size; j++){
            data[j] = c_data[j] - '0';   //数字を数値に変換
            ban[i][j][0] = data[j];
        }
        show();
        printf("%d行目のデータはこれで合っていますか?\nはい:0を入力, いいえ:0以外を入力\nAns: ", i + 1);
        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)
        printf("FILE OPEN ERROR1\n");
    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][0] = c_data[i] - '0';   //数字を数値に変換
            }
        }
        else
            printf("FILE OPEN ERROR2\n");
        fclose(fp);
    }
    printf("読み込んだファイルは以下のようになります\n");
    show();
}

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

int retLineColumn(int Line, int Column, int Num){
    int CountX = 0, CountY = 0, CountBox = 0, possibleLine, possibleColumn;

    for (int x = 0; x < Size; x++){//横方向のチェック
        if (ban[Line][x][Num] == 1){
            possibleColumn = x;//一時的に記憶
            CountX++;
        }
    }
    if (CountX == 1){
        checkedTarget = 1;//横
        return possibleColumn;
    }
    else if (CountX == 0)
        return 99;

    for (int y = 0; y < Size; y++){//縦方向のチェック
        if (ban[y][Column][Num] == 1){
            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 (ban[i][j][Num] == 1){
                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){
    //既に埋められたところはすべての可能性を0にする
    for (int Num = 1; Num < Size + 1; Num++)
        if (ban[Line][Column][0] != 0)
            ban[Line][Column][Num] = 0;
}

void solve() {
    int Num, possibleNumCount;
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column][0] == 0){//空白である
                deleteNumFlag(Line, Column);//入る可能性のある数字を減らす
                possibleNumCount = 0;//マスごとに初期化
                for (Num = 1; Num < Size + 1; Num++){
                    if (ban[Line][Column][Num] == 1)//入る可能性を発見
                        possibleNumCount++;//カウントする
                }
                for (Num = 1; Num < Size + 1; Num++){
                    if (possibleNumCount == 1)//そのマスにおいて入る可能性のある数字が一つならば
                        if (ban[Line][Column][Num] == 1){//その唯一可能性のある数字を
                            ban[Line][Column][0] = Num;//代入
                            filledGrid(Line,Column);
                        }
                }
            }
        }
    }
}

void solve2(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            for (int Num = 1; Num < Size + 1; Num++){
                if (ban[Line][Column][0] == 0){
                    int pos = retLineColumn(Line, Column, Num);
                    if (pos != 99){//99は発見できなかったとき
                        if (checkedTarget == 3){//対象がボックス
                            ban[pos / 10][pos % 10][0] = Num;
                            filledGrid(pos / 10, pos % 10);
                            show();
                            for (int i = 0; i < Size; i++)
                                printf("ban[2][%d][8]:%d\n",i,ban[2][i][8]);
                        }
                        else if (checkedTarget == 2){//縦
                            ban[pos][Column][0] = Num;
                            filledGrid(pos, Column);
                            //show();
                        }
                        else if (checkedTarget == 1){//横
                            ban[Line][pos][0] = Num;
                            filledGrid(Line, pos);
                            //show();
                        }
                    }
                }
            }
        }
    }
}

bool IsEnd(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column][0] == 0)
                return false;
        }
    }
    return true;
}

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

int _tmain(int argc, const char * argv[]) {
    //int main(){//mac用
    char next;
    resetBan();
    resetFlag();
    setStart();
    do{//解く
        cin.sync();//syncとgetで入力待ち
        cin.get();//getが1回だとバグが起こる可能性がある
        cin.get();//ここは今後無くなります(Windowsアプリらしくするため)
        solve();//具体的に解く
        solve2();
        show();
    } while (!IsEnd());
    printf("---------答え----------\n");
    show();
    return 0;
}

よっぴー

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

#16

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

solve()とsolve2()を綺麗に1つにまとめられる気がするのですが、
上手くまとめることができません。どのようにまとめることができますか?
また、まとめるべきでしょうか?

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

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

#17

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

> 上のyokoさんの5番を実装したつもりなのですが、以前よりも解けなくなってしまいました。
> 具体的にはボックス・列・行に2つ以上同じ数字を入れてしまうなどです。

デバッグしましょう。工夫してください。

とりあえず、filledGrid()の実装が間違っています。
ある数字を入れたら、可能性を消すのはそのマスだけではなく、
タテヨコに同じ数字が入る可能性も消さなくてはなりません。

ちなみにfilledGrid()を少し直しても、解けませんでした。
solve()の実装は間違ってないようで、
solve2()で数字が決まるたびにreturnするようにしたら、
wikipediaの問題が解けるようになりました。

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

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

#18

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

> 具体的にはボックス・列・行に2つ以上同じ数字を入れてしまうなどです。

同じ問題に対して同じタイミングで必ず起きる現象なので、デバッグとしては非常に簡単な部類です。
この程度の規模のプログラムにも、必ず必要なスキルですので、上達したいなら必ず身に付けてください。


> ちなみにfilledGrid()を少し直しても、解けませんでした。

↑と書きましたが、タテヨコだけではなく、ブロック内の可能性も消す必要がありました。
それも直したら、完成しました。


solve()とsolve2()の関係については、まだ丁寧に見てません。
色々とちぐはぐな所があるようですので、重要な問題を指摘しにくいです。
続きはまた。

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

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

#19

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

solve()とsolve2()を見てみました。
どちらも無駄は多いですが、致命的な誤りはありません。
慌てて直す必要はないですが、一応伝えると、
206行目と207行目、221行目と222行目は、それぞれ入れ替えた方がいいです。
機械的に入れ替えるのではなく、論理的な意味を考えて入れ替えてください。

ここまでの修正をすると、2つの関数はどちらも、for(Line)、for(Column)、ifで始まります。
ifの内側の前半にsolve()由来のコード、後半にsolve2()由来のコードを書くことで、
まとめることができるでしょう。

まとめるべきか、ということについては、私ならまとめません。
solve()は「4.フラグが1つしかないマスは確定」を実装していて、
solve2()は「5.縦、横、同じブロックでフラグが1つしかない数字はその箇所を確定」を実装しています。
アルゴリズムが別なので、関数も分けた方がよいと思います。
この辺は好みの問題でもあります。


その他、気づいた点。

2. C言語とC++言語が混ざっている。

printfとcinが並んでいたりしています。
どちらの言語を使うか方針を決めて、Cらしく、あるいは、C++らしく書きましょう。
最終的にどちらの言語も使えるようになりたいとしても、
両者を区別することは大事で、それによって言語の特徴をつかみやすくなると思います。
取りあえずは、コンソールの入出力と、ファイルの入出力からでしょうか。

3. 配列banが2つの別のデータを扱っている。

確定した数字と入る可能性のある数字は別のデータです。
前者は2次元配列に、後者は別の3次元配列で管理しましょう。
3次元配列の型はboolが良いでしょう。


書き出したらキリがないので、大きな指摘のみです。
1番目は既に書いたデバッグができないことで、これが最重要課題です。

よっぴー

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

#20

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

返信ありがとうございます。下に変更後のコードを載せておきました。
主に以下の変更をしました。
・cとc++の区別としてprintfを廃止
・banを確定した数字のint banとフラグ用bool flagbanに分ける
・filledGrid()の大幅改善

また、下のように指摘されたところも修正したつもりですが、
これは機械的に入れ替えていることになっているのではないでしょうか?
もし、そうだとしたら論理的に入れ替えるとはどういう意味なのか教えて下さい。
たいちう さんが書きました: 206行目と207行目、221行目と222行目は、それぞれ入れ替えた方がいいです。
機械的に入れ替えるのではなく、論理的な意味を考えて入れ替えてください。
実行結果については、同じ数字を行・列・ボックスに2つ以上入れるようなことはなくなりました。
しかし、多くの空白を残しています。なんとしても解けるようにしたいです。
たくさんのご指摘お待ちしております。

コード:

// 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 checkedTarget = 0;
bool flagban[Size][Size][Size + 1];//[][][0]は使わない

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 + 1; Number++)
                flagban[Line][Column][Number] = true;//すべての数字の入る可能性をありにする
        }
    }
}

void show(){
    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 << " |";//マスの区切り表示
            cout << " " << ban[Line][Column];//数字の表示
        }
        if (Line == 2 || Line == 5){
            cout << endl;
            cout << "   ------+-------+------";//マスの区切り表示
        }
        cout << endl;
    }
    cout << endl;
}

//input関連はいずれGUIを使うようものに変更するつもりです
void input(){
    int add = 0, data = 0;
    cout << "データを以下のように入力してください" << endl << "行:5 列:7 数値:8 => 857" << endl << "1000を入力すると終了" << endl;
    while (add != 1000){
        show();
        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();
        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();
}

void deleteNumFlag(int Line, int Column){
    int startLine = Line / 3 * 3;
    int startColumn = Column / 3 * 3;
    for (int Number = 1; Number < Size + 1; 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, possibleColumn;
    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){//埋めたマスのx,yと埋めた数字を引数とするß
    if (ban[Line][Column] != 0){//改めて空白でないか確認
        
        for(int Number = 1; Number < Size + 1; Number++)//既に埋められたマスのすべての可能性をなくす
            flagban[Line][Column][Number] = false;
        
        for (int x = 0; x < Size; x++){//横方向のチェック
            if (Num == ban[Line][x])
                flagban[Line][Column][Num] = false;//埋めた数字の可能性をなくす
        }
        
        for (int y = 0; y < Size; y++){//縦方向のチェック
            if (Num== ban[y][Column])
                flagban[Line][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++){
                if (Num == ban[i][j])
                    flagban[Line][Column][Num] = false;//埋めた数字の可能性をなくす
            }
        }

    }
}

void solve() {
    int Num, possibleNumCount;
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column] == 0){//空白である
                deleteNumFlag(Line, Column);//入る可能性のある数字を減らす
                possibleNumCount = 0;//マスごとに初期化
                for (Num = 1; Num < Size + 1; Num++){
                    if (flagban[Line][Column][Num])//入る可能性を発見
                        possibleNumCount++;//カウントする
                }
                if (possibleNumCount == 1){//そのマスにおいて入る可能性のある数字が一つならば
                    for (Num = 1; Num < Size + 1; Num++){
                        if (flagban[Line][Column][Num]){//その唯一可能性のある数字を
                            ban[Line][Column] = Num;//代入
                            filledGrid(Line,Column,Num);
                        }
                    }
                }
            }
        }
    }
}

void solve2(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column] == 0){//空白である
                for (int Num = 1; Num < Size + 1; 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);
                            return;
                        }
                        else if (checkedTarget == 2){//縦
                            ban[pos][Column] = Num;
                            filledGrid(pos, Column,Num);
                            return;
                        }
                        else if (checkedTarget == 1){//横
                            ban[Line][pos] = Num;
                            filledGrid(Line, pos,Num);
                            return;
                        }
                    }
                }
            }
        }
    }
}

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);
    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]);
        }
    }
}

int _tmain(int argc, const char * argv[]) {
//int main(){//mac用
    resetBan();
    resetFlag();
    setStart();
    do{//解く
        cin.sync();//syncとgetで入力待ち
        cin.get();//getが1回だとバグが起こる可能性がある
        cin.get();//ここは今後無くなります(Windowsアプリらしくするため)
        solve();//具体的に解く
        solve2();
        show();
    } while (!IsEnd());
    cout << "---------答え----------" << endl;
    show();
    return 0;
}

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

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

#21

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

頑張りましたね。

> また、下のように指摘されたところも修正したつもりですが、
> これは機械的に入れ替えていることになっているのではないでしょうか?
> もし、そうだとしたら論理的に入れ替えるとはどういう意味なのか教えて下さい。

なぜ入れ替えたのか、説明ができるなら結構です。


> 実行結果については、同じ数字を行・列・ボックスに2つ以上入れるようなことはなくなりました。
> しかし、多くの空白を残しています。なんとしても解けるようにしたいです。
> たくさんのご指摘お待ちしております。

この件については、私もyokoさんも既に書いています。
それ以上に何が必要なのですか?指摘の数?

よっぴー

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

#22

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

たいちう さんが書きました:頑張りましたね。
> 実行結果については、同じ数字を行・列・ボックスに2つ以上入れるようなことはなくなりました。
> しかし、多くの空白を残しています。なんとしても解けるようにしたいです。
> たくさんのご指摘お待ちしております。

この件については、私もyokoさんも既に書いています。
それ以上に何が必要なのですか?指摘の数?
→書いていますとのことですが、これは残ってしまった空白はバックトラック法で解くということでしょうか?

また、wikipediaの数独を解かせたところ、
5 3 1 | 6 7 2 | 9 4 8
6 4 4 | 1 9 5 | 3 0 2
1 9 8 | 3 4 2 | 5 6 7
----+-----+----
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
----+-----+----
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 0 5 | 2 8 6 | 1 7 9
といった結果になり、これ以上空白は埋まりませんでした。
みると、左上のボックスに4が二つ入っています。
これをみる限り、コードがまちがっていると思うのですが、間違いはありませんか?
(コードは前回の物と同じです)

p.s yokoさん、コードのアップお願いします。

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

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

#23

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

> →書いていますとのことですが、これは残ってしまった空白はバックトラック法で解くということでしょうか?

単純なバックトラック以外についてだと、No.2、No.3、No.6、No.7に書かれています。
意味が判らないなら、その旨を質問してください。


> みると、左上のボックスに4が二つ入っています。
> これをみる限り、コードがまちがっていると思うのですが、間違いはありませんか?

当然間違っています。判りますよね?
これは、「問題が難しくて解けない」という状態ではなく、
「考え方か実装に間違いがあるから解けない」という状態です。
何度も書いていますが、なぜデバッグしないのですか?

よっぴー

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

#24

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

気になるマスのデバッグ?(フラグを状態を表示)したところ、
filledGrid()がおかしいことがわかり、少しfilledGridを書き換えたところ、無事にwikipediaの問題を解くことができました。ですが、より難しい問題はまだ解けません。極力バックトラック法は使いたくないので、以前に紹介されましたサイトなどで「数独」を勉強してプログラムにかけるよう頑張ります。コードが書け(て問題が起き)次第また来ます。
たくさんの回答ありがとうございました。
p.s 現在のコードは載せるべきですか?

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

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

#25

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

> p.s 現在のコードは載せるべきですか?

掲示板のルールに次のように書かれています。
「また、解決した時は、「解決しました」とだけ言って去らず、ソースコードや解決した方法を明記して下さい。」

まだ完全に解決はしてないと思いますが、キリが良いところで載せてもらいましょうか。
誰かの役に立つかもしれませんし、別の指摘をもらえるかもしれません。


最後に、最初から気になっていたけどスルーしていた点。
細かいことですが、次のように書き換えた方がよいと思います。
「Size + 1」という式に意味はありませんので。

for (int Num = 1; Num < Size + 1; Num++)

for (int Num = 1; Num <= Size; Num++)

よっぴー

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

#26

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

まだ全ての問題を解けるわけでもなく、無駄も多いかと思いますが
ある程度のレベルは解けるようになりましたので、コードを載せておきます。
今後、より高難度の問題をどのようにして解けるようにするか、バックトラックを使うかはグループの人間と相談したいと思います。
たくさんの回答ありがとうございました。

コード:

// 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 checkedTarget = 0;
bool flagban[Size][Size][Size + 1];//0は使わない

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(){
    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 << " |";//マスの区切り表示
            cout << " " << ban[Line][Column];//数字の表示
        }
        if (Line == 2 || Line == 5){
            cout << endl;
            cout << "   ------+-------+------";//マスの区切り表示
        }
        cout << endl;
    }
    cout << endl;
}

//input関連はいずれGUIを使うようものに変更する
void input(){
    int add = 0, data = 0;
    cout << "データを以下のように入力してください" << endl << "行:5 列:7 数値:8 => 857" << endl << "1000を入力すると終了" << endl;
    while (add != 1000){
        show();
        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();
        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();
}

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){//埋めたマスのx,yと埋めた数字を引数とする
    if (ban[Line][Column] != 0){//改めて空白でないか確認
        
        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 solve() {
    int Num, possibleNumCount;
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column] == 0){//空白である
                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]){//その唯一可能性のある数字を
                            ban[Line][Column] = Num;//代入
                            filledGrid(Line,Column,Num);
                        }
                    }
                }
            }
        }
    }
}

void solve2(){
    for (int Line = 0; Line < Size; Line++){
        for (int Column = 0; Column < Size; Column++){
            if (ban[Line][Column] == 0){//空白である
                for (int 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);
                            return;
                        }
                        else if (checkedTarget == 2){//縦
                            ban[pos][Column] = Num;
                            filledGrid(pos, Column,Num);
                            return;
                        }
                        else if (checkedTarget == 1){//横
                            ban[Line][pos] = Num;
                            filledGrid(Line, pos,Num);
                            return;
                        }
                    }
                }
            }
        }
    }
}

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);
    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]);
        }
    }
}

int _tmain(int argc, const char * argv[]) {
    resetBan();
    resetFlag();
    setStart();
    do{//解く
        cin.sync();//syncとgetで入力待ち
        cin.get();//getが1回だとバグが起こる可能性がある
        cin.get();
        
        solve();
        solve2();
        show();
    } while (!IsEnd());
    cout << "---------答え----------" << endl;
    show();
    return 0;
}

閉鎖

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