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

質問

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

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

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

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

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

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

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

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

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

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

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

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

_)>

回答No.1

hananoppo · ベストアンサー

初めまして。私も数独を解くプログラムを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言語で具体的にどうするのかは全く分からないので、ビット演算(シフト演算や論理演算)についてはご自分でお調べください。

お礼

はじめまして！hananoppo さん回答ありがとうございます<(_ _)>
わかりやすい回答ありがとうございます！
今ひとつ理解できないでいますので宜しくお願いします<(_ _)>
３マスの確定の処理が理解わかりません・・・
r3c1、r3c2、r3c4のマスに決定する時の処理ですが左の３つのマスの間にあったＲ３Ｃ３（2,3,4）（r1,r2,（r3),r4,…）マスがとばされた処理です。
総当りで横ラインにあたっているのでしょうか？それともビット演算で上手く排除できるのでしょうか？順に3国が決定される処理がわからないので、すみません、宜しくお願いします<(_ _)>
　後の同盟が確定してからの処理はよく理解できました。確定３マスをビット反転し、残りのマスと論理積（ＡＮＤ）で残ったのが４国Hiddenが発見できるかもしれませんね（最初にマスが７個確定していない場合）
※すみません、No.３の回答の方にも同様な事を書いてます。（利用方法が理解できてなかったので）

回答No.4

usatan2

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]ですけど・・・
プログラミング、がんばってください。

お礼

usatan2 さんの２回目のヒントで一気に道が開けました(^人^)感謝♪　３重ループとビット演算を使ってn国同盟プログラムを組むことができました。まだまだ解らない所ばかりのC言語ですがナンバープレース解法プログラムを通じて勉強しようと思ってます！この解法だけでは解けない難問もあると思いますがそれそのときに新しい解法を実装しようと思ってます。丸３日かかって心が折れそうになりました(>< )o本当に大変有難うございました。<(_ _)>

回答No.3

hananoppo

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

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

お礼

usatan2 さん、色々解りやすく教えて頂き有難うございました<(_ _)>
hananoppoさん、
usatan2 さんの
ヒントを基に３重ループとビット演算を使ってn国同盟プログラムを組むことができました。おか

げで今まで雑誌などで解けなかった問題も解いて進んでくれるようになりました。まだまだこの

解法だけでは解けない難問もあるのでこれからも頑張ります！大変有難うございました。<(_ _)>

全ての回答者の方の回答が、素晴らしかったので、私にはとても優劣が付けられません。
大変申し訳ありませんが、一番最初に回答をいただいた方をベストアンサーにする事にします。

補足

はじめまして！hananoppo さん回答ありがとうございます<(_ _)>
わかりやすい回答ありがとうございます！
今ひとつ理解できないでいますので宜しくお願いします<(_ _)>
３マスの確定の処理が理解わかりません・・・
r3c1、r3c2、r3c4のマスに決定する時の処理ですが左の３つのマスの間にあったＲ３Ｃ３（2,3,4）（r1,r2,（r3),r4,…）マスがとばされた処理です。
総当りで横ラインにあたっているのでしょうか？それともビット演算で上手く排除できるのでしょうか？順に3国が決定される処理がわからないので、すみません、宜しくお願いします<(_ _)>
　後の同盟が確定してからの処理はよく理解できました。確定３マスをビット反転し、残りのマスと論理積（ＡＮＤ）で残ったのが４国Hiddenが発見できるかもしれませんね（最初にマスが７個確定していない場合）

回答No.2

usatan2

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

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以外の候補がない) ３国同盟に決定
　　　　　}
　　　　}
　　　}
　　}
　}
}

お礼

返答遅くなってすみません<(_ _)>
回答ありがとうございます！
ソースまで載せて頂き有難うございます。
勉強不足の為にソースの意味が解らない所がありますので教えて頂きたいのですが、
先ず、if(A[i]の候補数 <= 3) の行ですがＡ[i]ｉはマスをさすのでしょうか？a[j]他のマスを指すという事でしょうか？
n = A[i]とA[j]の候補数の所の行はa[i],a[j]マスの中の候補数という意味でしょうか？
そうするとR3Ｃ1(６，８）、Ｒ３Ｃ２（１，６）、のような場合は候補を２つ持つ、Ｎ＝＝２は２国同盟とはならないと思うのですが…僕の考え違いでしょうね？候補の種類という意味でしょうか？
もう少し教えて頂ければと思います<(_ _)>