数独の３国同盟のアルゴリズム教えて下さい

Question

はじめまして！
C言語を勉強して３ヶ月になります、現在、勉強のつもりで数独の解法プログラムを作っています

が、解法プログラムを基本から順に実装しようと基本から２国同盟まではわかったのですが３国

同盟以上（まずは自明のNaked Tripleからお願いします<(_ _)>）のアルゴリズムがどうしても

解らずプログラムが書けません。マスの絞り込み方です。例えば横ラインのマスで候補数が２、

３個のマスに絞って・・・次ですが３個のマスには３種類しか入らない。・が解りません！目

で見ればわかりますがそれをプログラムする方法）NAKED（見える）Tripleだけで良いので考え方

を教えて下さい。２日間詰まってます(>< )
どうぞ宜しくお願いします<(_ _)>

（例）
Ｒ３横一行だけを考えたときにR3Ｃ1(６，８）、Ｒ３Ｃ２（１，６）、Ｒ３Ｃ３（2,3,4）、Ｒ３

Ｃ４（1,8）、Ｒ３Ｃ５（1,2,4,5,6）・・・で（）内は候補数です。これはＣ１、Ｃ２、Ｃ４で

（１，６，８）の３国同盟ができています。Ｒ３Ｃ５の（１，６）は削除され候補数（２，４，

５）となる。悩んでいるのはＣ１、Ｃ２、Ｃ４を同盟決定のアルゴリズムです。
「異なる3つのマスを選んだときに、それら3マスに入れられる候補の種類が3種類であること」を

プログラム上でどう表現したら良いかずっと詰まってます(>< )
どう考えたらこの３つのマスを決定（同盟関係）できるのでしょうか？宜しくお願い致します<(_

_)>

hananoppo · Accepted Answer

初めまして。私も数独を解くプログラムをExcelのVBA(BASICの一種)で作っています。
C言語についてはほとんど分からないので、具体的なコードは示せませんが、アルゴリズムについては助言できると思います。

候補数字のデータですが、ビットで処理するのが簡単です。
まず、1マスの候補数字のデータを1つの変数で表します(81マスあるので配列の中の1つですが)。候補数字のデータが仮に4バイトの変数(配列)だとすると、r3c1、r3c2、r3c4の候補数字は次のようにセットします(シフト演算やOR演算が必要になると思います)。
　　r3c1={6,8} → 0000 0000 1010 0000
　　r3c2={1,6} → 0000 0000 0010 0001
　　r3c4={1,8} → 0000 0000 1000 0001
右端の第0ビットから第8ビットが1～9の候補数字を表します。ビットが1なら候補数字であり、0なら候補数字でないことを意味します。このように候補数字をビットで表すと、論理演算で簡単に各マスの候補数字を比較できます。

Naked Tripleの場合、まず候補数が2または3個のマスを3箇所選びます。
※ 候補数は値が1となるビットを数えて求めます(シフト演算やAND演算が必要になると思います)。

Naked Tripleが成立するかどうかを判定するには、まず3マスの候補数字のORを求めます。r3c1、r3c2、r3c4の3マスの場合で候補数字のORを求めると、次のようになります。
　　r3c1 OR r3c2 OR r3c4 → 0000 0000 1010 0001 ‥‥‥(1)
(1)の候補数を求めると3個なので、Naked Tripleが成立します。

Naked Tripleをr3c1、r3c2、r3c4以外のマスに適用する方法ですが、まず(1)のNOTを求めます。
　　NOT (1) → 1111 1111 0101 1110 ‥‥‥(2)
例えば、r3c5の候補数字は次のようにセットされています。
　　r3c5={1,2,4,5,6} → 0000 0000 0011 1011
r3c5にNaked Tripleを適用するには、r3c5の候補数字と(2)のANDを求めます。
　　r3c5 AND (2) → 0000 0000 0001 1010
これを新しいr3c5の候補数字とします。これで{1,6}が除外され、{2,4,5}が候補数字に残ります。

Naked Tripleはこんな感じでよいと思います。

なお、C言語で具体的にどうするのかは全く分からないので、ビット演算(シフト演算や論理演算)についてはご自分でお調べください。

usatan2 · Answer

No2です。
＞先ず、if(A[i]の候補数 <= 3) の行ですがＡ[i]ｉはマスをさすのでしょうか？
A[i] は、質問者さんのR3Ciの括弧の中のつもりです。
つまり、R3Ｃ1(６，８）なら　A[1]={6,8}、Ｒ３Ｃ２（１，６）ならA[2]={1,6}のつもりです。
A[1]とA[2]の候補は {1,6,8} の３つなので n=3 です。

日本語で書いた「A[i]の候補数」や「A[i]とA[j]の候補数」「A[i]+A[j]の候補」は全てこのままではC言語になっていませんので、日本語の意味になるような関数を定義するわけですよ。
この関数の定義にはNo1さんの回答が参考になると思います。
＃正確には添え字は０から８のつもりなので、A[0],A[1]ですけど・・・
プログラミング、がんばってください。

hananoppo · Answer

ANo.1です。少し誤りがあったので訂正します。

× 「候補数字のデータが仮に4バイトの変数(配列)だとすると」
○ 「候補数字のデータが仮に2バイトの変数(配列)だとすると」

usatan2 · Answer

「３個のマスには３種類しか入らない」を
「３個目のマスの候補は、２つ目のマスの候補に含まれる」と読み替えて素直に以下のようにチェックするだけではダメですか？

for(i=0; i<9-3; i++) {
　if(A[i]の候補数 <= 3) {
　　for(j=i+1; j<9-2; j++) {
　　　if(A[j]の候補数　<= 3) {
　　　　n = A[i]とA[j]の候補数
　　　　if(n == ２）２国同盟に決定
　　　　else if(n==3) {
　　　　　A[i]+A[j]の候補をp,q,r とする
　　　　　for(k=j+1; k<9; k++) {
　　　　　　if(A[k]にp,q,r以外の候補がない) ３国同盟に決定
　　　　　}
　　　　}
　　　}
　　}
　}
}

数独の３国同盟のアルゴリズム教えて下さい

初めまして。

No2です。

ANo.1です。

この回答への補足

「３個のマスには３種類しか入らない」を

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング