質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C#

C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

Q&A

解決済

1回答

2249閲覧

0か1の値をとる変数を、変数の組み合わせの合計をヒントに求めるというプログラムを書きたいのですが方法が全く分かりません

6HdwN23qILrBn2e

総合スコア6

C#

C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

0グッド

0クリップ

投稿2019/11/11 06:33

編集2019/11/11 06:54

現在、マインスイーパーのソルバーをC#で作っているのですが、どうにもわからない点があるため質問させていただきます。
マインスイーパーのルールをご存じなくてもいいように、一般的な書き方にさせていただきます。
以下のような内容のプログラムを組みたいのですが、どうすればいいのかさっぱりわかりません。大まかでも大変ありがたいので、よろしくご教授願います。

内容としては、
・各変数は0か1の値をとる
・変数の組み合わせによる合計値から、各変数の値(0か1)を求める
・変数が0か1かわからない場合があり、わかった変数にわかった値を代入する
という感じです。

例えば、


{a,b}は1
{b}は1
{b,c,d,e}は3
{d,e,f}は1


というような場合、
〇{a,b}は1、{b}は1より、
a=0,b=1
〇{b,c,d,e}は3、b=1より
{c,d,e}は2
〇{c,d,e}は2、{d,e,f}は1より、{d,e}は1以下だから
c=1
〇{c,d,e}は2、c=1、{d,e,f}は1より、{d,e}は1だから、
f=0
まとめると、a=0、b=1、c=1、f=0、{d,e}は1
となります。

このような計算をプログラムで行いたいのですが、どうすればいいのかさっぱりわかりません。
考え方や方法などを教えていただけると助かります。ソースコードなどはなくても大丈夫です。
マインスイーパーに当てはめると、変数がマスで、0と1の値が地雷がない、あるという意味になります。

自分で調べて分かったことは、制約充足問題というジャンルに当てはまるということなのですが、バックトラックやヒューリスティックのような単語が出てきてよくわからず、マインスイーパーはN-Queens問題や地図彩色問題ほど深い探索が必要になるとは思いませんでしたので、それ以外の方法を考えているのですが、思いつかないためご質問させていただきました。

初めての質問のため至らない点が多々あるかもしれませんので、その点も含めご指摘いただければ幸いです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

m.ts10806

2019/11/11 06:35

言語くらいは絞りましょう。 それに分からないなりに調べたり試したことはあるはずです。 それを書かないと単なる作業依頼ですよ
Zuishin

2019/11/11 06:59

マインスイーパー程度なら総当たりをすればいいんじゃないでしょうか。
6HdwN23qILrBn2e

2019/11/11 08:57

書き込みありがとうございます。 言語をC#のみにさせていただきました。調べたことも追記させていただきました。 総当たりに関して。質問に書いたような手順で地雷のある・なしを調べてから、それで求まらない盤面の場合は、あり得るパターンを探索して求めるという順番になります。 そのため、総当たりの前に上記の手順を踏んだプログラムを書かなければいけません。 学校での学習の事情もあります。 上記のような手順で、地雷のある・なし、0・1を求めるプログラムの方法をご回答いただけると非常に幸いです。
Zuishin

2019/11/11 09:00

各マス目を一つの要素とした二次元配列を作り、一つ一つの要素には候補のリストを入れ、あり得ない候補を削除すれば良いと言って通じるでしょうか?
m.ts10806

2019/11/11 09:11

>学校での学習の事情 「自分でやろうよ」というアドバイスが適当かと思います。 せめて自身が書いてみたプログラムがあり、それについて詰まっていることの質問であればまだ答えようがあるのですが。 ある程度ロジックを考えられているのであればその通り書くだけとも思います。それとも学校ではロジックのみでプログラムを書く授業はないのでしょうか?
6HdwN23qILrBn2e

2019/11/13 04:17

@Zuishin様 ありがとうございます。二次元配列にlistを代入しようとするとどうにも上手くいきません…。例えばcell[3,4](4行5列目のマス)に{a,b,c}みたいな候補を入れることができるんでしょうか? listを扱ったことがなく参考書を見ている状況なのでちゃんと理解できていないのかもしれません…。 @m.ts10806様 ありがとうございます。学校ではプログラムを書く授業はあります。マインスイーパーは私だけ取り組んでいます。エラーなど紆余曲折を経ながらここまで来たのですが、どうにもロジックでつまずいてしまい質問させていただきました…。
guest

回答1

0

ベストアンサー

{a,b}は1
{b}は1
{b,c,d,e}は3
{d,e,f}は1

要は,数値が表示されているマスの分だけ式が立つわけですね.

(問題特有の知識(全ての変数の値は0か1のいずれかである)をどうねじ込めるのかまでは思いつきませんが)
とりえあず連立方程式ですから,(ガウスの消去法とか何でもいいので)連立方程式をどうにかする方法を用いて解けるところまで解いていけばよいのではないでしょうか.
マインスイーパなのであれば,その過程において0であることが確定した要素が得られた時点で,この連立方程式を解き続ける必要はなく,0だとわかったマスを開いて新たなヒントを得れば良いように思います.

判断が付かない場面になったら…可能性のあるパターンの中からどれかを適当に選ぶしかないのかな?

投稿2019/11/11 09:48

fana

総合スコア11632

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

6HdwN23qILrBn2e

2019/11/13 04:04

ご回答誠にありがとうございます。 まだ実現できていないので返信するべきなのかわかりませんが、大いに参考にさせていただき試行錯誤しております。また進めていくうえで不明点がありましたらご連絡させていただくかもしれませんが、そのときはよろしくお願いします。
6HdwN23qILrBn2e

2019/11/22 02:25

こんにちは。 連立方程式を解くという方法が私には難解だったため、四苦八苦しつつ2つの情報で総当たりのようなことをやって何とかできました。2つの情報に含まれるマスの桁数だけ2進数を作り、地雷の数を参考に、その2進数の中で成り立つ2進数だけリストに入れ、各マスにおいてすべて0やすべて1のものが存在する場合、0なら開く、1なら地雷として旗を置くというような処理をしました。 0や1が確定した時点でひとまずループから抜けられるという点でご回答が非常に参考になりました。 力不足で連立方程式はできませんでしたが、励みにもなりました。 ご回答ありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問