C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[4]: 数独の問題を自動作成するプログラムについて


(過去ログ 26 を表示中)

[トピック内 7 記事 (1 - 7 表示)]  << 0 >>

■11865 / inTopicNo.1)  数独の問題を自動作成するプログラムについて
  
□投稿者/ うに (1回)-(2007/12/22(Sat) 18:11:24)

分類:[C#] 

はじめて質問させて頂きます。
今数独の問題を自動で作成するプログラムを作っています。
その足がかりとしてまず9*9の二次元配列に
* 空いているマスに1〜9のいずれかの数字を入れる。
* 縦・横の各列及び、太線で囲まれた3×3のブロックに同じ数字が複数入ってはいけない。
のルールを守りながらランダムに数字を入れていくプログラムを作ったのですが
ほとんどの確率で何も表示されません。時間がやたらかかるのかと思って6*6マスにしたら
何回か実行するとたまに表示される程度です。
何処が間違ってるかわからないので何か間違いがありましたらご教示お願いします。

using System;

class sudoku
{
System.Random rnd = new System.Random();
public int Random;
public int i, j;
public int[,] X = new int[9, 9];
public sudoku()
{
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
{
Random = rnd.Next(1, 10);
X[i, j] = Random;
hikaku();
}
}
public void hikaku()
{
ST1:;//最初から
int start1=0,end1=0,start2=0,end2=0,shoki1,shoki2,A,B;
//縦についての設定
if (i == 0 || i == 1 || i == 2)
{ start1 = 0; end1 = i; }
if (i == 3 || i == 4 || i == 5)
{ start1 = 3; end1 = i; }
if (i == 6 || i == 7 || i == 8)
{ start1 = 6; end1 = i; }
//横についての設定
if (j == 0 || j == 1 || j == 2)
{ start2 = 0; end2 = 2; }
if (j == 3 || j == 4 || j == 5)
{ start2 = 3; end2 = 5; }
if (j == 6 || j == 7 || j == 8)
{ start2 = 6; end2 = 8; }
//ボックス内を比較
for (shoki1=start1; shoki1 <= end1; shoki1++)
{
for (shoki2 = start2; shoki2 <= end2; shoki2++)
{
if (i == shoki1 && j == shoki2)
{ goto ST2; }
if (X[i, j] == X[shoki1, shoki2])
{
Random = rnd.Next(1, 10);
X[i, j] = Random;
goto ST1;//値を変えたら最初からやり直す
}
}
}
ST2:;//終わり次第強制終了
//ここから横を比較
for (B = 0; B < j; B++)
{
if (X[i, j] == X[i, B])
{
Random = rnd.Next(1, 10);
X[i, j] = Random;
goto ST1;//値を変えたら最初からやり直す
}
}
//ここから縦を比較
for (A = 0; A < i; A++)
{
if (X[i, j] == X[A, j])
{
Random = rnd.Next(1, 10);
X[i, j] = Random;
goto ST1;//値を変えたら最初からやり直す
}
}
}
public void Write()
{
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
Console.Write("{0} ",X[i, j]);
}
Console.WriteLine();
}
}
static void Main()
{
sudoku A = new sudoku();
A.Write();
}
}
引用返信 編集キー/
■11876 / inTopicNo.2)  Re[1]: 数独の問題を自動作成するプログラムについて
□投稿者/ 774RR (108回)-(2007/12/23(Sun) 07:35:51)
ロジックを追っかける気にならないんだけど、そもそもが数独である以上
Next(1,10) で値を入れるというのは原理的に間違っていると思うが。

Next(1,10) は [1,10) の半開空間の乱数を生成するってことだから
同じ値が何度も出ることがあってしかるべきで、それは数独の仕様に反する
[1..9] の値を生成して、それをかき混ぜる (C++ STL なら random_shuffle) ほうがいい

それでも効率が悪いわけで、もう少し枝刈りを考えないと速度が出ないと思うがな。

引用返信 編集キー/
■11877 / inTopicNo.3)  Re[1]: 数独の問題を自動作成するプログラムについて
□投稿者/ カンタービレ (137回)-(2007/12/23(Sun) 08:00:06)
No11865 (うに さん) に返信
> はじめて質問させて頂きます。
> 今数独の問題を自動で作成するプログラムを作っています。
> その足がかりとしてまず9*9の二次元配列に
> * 空いているマスに1〜9のいずれかの数字を入れる。
> * 縦・横の各列及び、太線で囲まれた3×3のブロックに同じ数字が複数入ってはいけない。
> のルールを守りながらランダムに数字を入れていくプログラムを作ったのですが

ロジックの考え方がそもそもよくないのではないかと思いマス。
goto文もやめてほしいデス。
そして基点(固定)となるものを必ずひとつは作っておくべきデス。
ブロック単位に1つは確定させておきたいデスし。
最初の値をセットして毎回hikaku()してるところも変デス。
forの2重ループの記述も{}が足りないのはなぜとか色々・・・。

Randを使うのは最初の確定すべき項目のみ、
その他は使える数字候補から選択していく、と考えるのが妥当かと思いマス。
まず答えを導けないことにはパズルとして成立しませんから
数独のアルゴリズムをもう一度整理してみることをお勧めしマス。

インターネットで検索すると数独のアルゴリズムも結構出てくると思いマスよ。
引用返信 編集キー/
■11880 / inTopicNo.4)  Re[2]: 数独の問題を自動作成するプログラムについて
□投稿者/ うに (3回)-(2007/12/23(Sun) 10:46:55)
No11876 (774RR さん) に返信
> ロジックを追っかける気にならないんだけど、そもそもが数独である以上
> Next(1,10) で値を入れるというのは原理的に間違っていると思うが。
>
> Next(1,10) は [1,10) の半開空間の乱数を生成するってことだから
> 同じ値が何度も出ることがあってしかるべきで、それは数独の仕様に反する
> [1..9] の値を生成して、それをかき混ぜる (C++ STL なら random_shuffle) ほうがいい
>
> それでも効率が悪いわけで、もう少し枝刈りを考えないと速度が出ないと思うがな。

返信有難う御座います。Next(1,10)で値を入れた後hikaku()で値を修正するようにしてあるので
同じ値が出ても修正するように作っています。
効率云々は所詮大学の自由制作に過ぎないので二の次で考えてます。

No11877 (カンタービレ さん) に返信

返信有難う御座います。

> ロジックの考え方がそもそもよくないのではないかと思いマス。

まだC#を学び始めたばかりですので自分なりに出来る範囲で考えてみたのですがまずかったでしょうか?

> goto文もやめてほしいデス。

hikaku()で値を入れなおした際入れた値が他の場所で被っていることも考慮して初めからやり直す為に
gotoを使ったのですが問題があるのでしょうか?

> そして基点(固定)となるものを必ずひとつは作っておくべきデス。
> ブロック単位に1つは確定させておきたいデスし。

hikaku()でどこの値とも被ってなければその数字は確定されるように作っているはずです。

> 最初の値をセットして毎回hikaku()してるところも変デス。

値を入れたときにその値が何処かと被ってないかを調べて被ってるなら値を入れなおす為にhikaku()を使っています。

> forの2重ループの記述も{}が足りないのはなぜとか色々・・・。

確かに最初の方のforの2重ループに{}が足りませんでしたね。でも付けた所で進展はありませんでした。

> Randを使うのは最初の確定すべき項目のみ、
> その他は使える数字候補から選択していく、と考えるのが妥当かと思いマス。
> まず答えを導けないことにはパズルとして成立しませんから
> 数独のアルゴリズムをもう一度整理してみることをお勧めしマス。
>
> インターネットで検索すると数独のアルゴリズムも結構出てくると思いマスよ。

やはりこのままでは無理があるのでしょうか・・・?



こちらでも色々試行錯誤した結果途中までは値が出来ていることがわかりました。
値は終わる場所がバラバラですがその途中まで出た値については最初に書いたルールを守っています。
色々考えて見たのですが途中までしかいかない原因がわかりません。
何かあればまたご教示お願いします。
引用返信 編集キー/
■11881 / inTopicNo.5)  Re[2]: 数独の問題を自動作成するプログラムについて
□投稿者/ 774RR (109回)-(2007/12/23(Sun) 11:35:10)
だからかぶってたら入れ替えるというロジック自体がまずいわけで
最初からかぶらない値を入れるようにしようよ。

効率なんかドーデもいいではなくて、効率を考えないで作ると有限時間に答えが出ないよ

この手のパズルはいかにうまく枝刈りするか次第なので
テキトーにプログラム組んでもすぐ行き詰るのがオチ(今行き詰ってるんだろ?)

引用返信 編集キー/
■11888 / inTopicNo.6)  Re[3]: 数独の問題を自動作成するプログラムについて
□投稿者/ Jitta on the way (69回)-(2007/12/23(Sun) 16:51:07)
No11881 (774RR さん) に返信
> だからかぶってたら入れ替えるというロジック自体がまずいわけで
> 最初からかぶらない値を入れるようにしようよ。
>
> 効率なんかドーデもいいではなくて、効率を考えないで作ると有限時間に答えが出ないよ
>
> この手のパズルはいかにうまく枝刈りするか次第なので
> テキトーにプログラム組んでもすぐ行き詰るのがオチ(今行き詰ってるんだろ?)
>

賛成

ランダムな場所にランダムな数字を入れて、ダブっていたら入れ替える

だと、効率が悪いです
いつ問題ができるかわからないものを、待ち続けていられますか?

とりあえず 3×3 なら、電話番号順に0〜9の配列と考え、ランダムな位置に1〜9の数字を順にいれていってもいいはずじゃないでしょうか

それよりも、1〜9までならんでいる配列から適当に2つ取り出し、入れ替えます。これを何回か繰り返し、場所の配列にいれていけば、絶対にダブらないし、必ず一定の時間で完了します


このように、刈り込みを行います。
引用返信 編集キー/
■11901 / inTopicNo.7)  Re[4]: 数独の問題を自動作成するプログラムについて
□投稿者/ うに (4回)-(2007/12/24(Mon) 14:18:03)
No11888 (Jitta on the way さん) に返信
No11881 (774RR さん) に返信

そうですね。
途中まで値が出ているし止まる場所もバラバラなので
すこしいじればこのままいけるのではと思っていたのですがいくら考えても進展しないし
このままでは埒があかないので一旦初めから考え直して見ることにします。

どうもお手数かけました。
解決済み
引用返信 編集キー/


トピック内ページ移動 / << 0 >>

このトピックに書きこむ

過去ログには書き込み不可

管理者用

- Child Tree -