数独かを判断するプログラム

質問

私が作ろうとしているプログラムは数独を解くものではなく、予めテキストファイルに書かれている横9つ縦9つ、計81個の数字の表が、数独として成り立っているかを判断するものです。
数独についてはこちらで
http://ja.wikipedia.org/wiki/数独
or
http://sudoku.ara3.net/rule.htm

配列をa[9][9]と用意し、テキストファイルから数字を左上から順に配列に確保していき、その表が数独かどうか判断する段階で躓いています。3×3のマスの中に1～9までの数字が1個ずつあり、かつそのマスが計9つあれば数独なので、まず最初の3×3のマスの中の数字を1～9まで確認し、それを残り8つのマスにも同様に繰り返すだけで良いと思うのですが、その方法がわからず困っています。どなたかお解かりになる方、よろしくお願いします。
例として、テキストファイルの数字の表は以下の様になっています。

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

ちなみにこの表は数独として成り立っています。

回答No.2

fonera · ベストアンサー

No.1で回答したモノです。

申し訳ありません、ブロック判定がおかしかったです。

for(bx = 0; bx < 9; bx+=3) {
　for(by= 0; by < 9; by+=3) {
　　for(x = 0+bx; x < 3+bx; x++) {
　　　for(y= 0+by; y < 3+by; y++) {
　　　　check[array[x][y]]++;
　　　}
　　}
　/*ここで判定する*/
　}
}
ですな。
# 卓上で考えたのでバグに気がつきませんでした・・・手元ではとりあえずこれで動いてます。

補足

とても理解しやすかったです。おかげさまでプログラムができました！
一つだけ確認したいのですが、ｘ軸ｙ軸のチェックは、それぞれどれか1行だけ選んでチェックすればいいんですよね？数独はすべての行をチェックする必要はありませんよね？

回答No.6

masa6272

すみません。
アイディアが、先走って変なプログラム投稿しちゃいました。
基本的な考え方は、checkの右側から27個のビットを、1～9までの数字が現れたかどうかのチェックに使っています。

for(i = 0; i < 9; i++) {
　check = 0;
　for(j = 0;j < 9;j++) {
　　r = a[i * 9 + j] - 1;
　　c = a[j * 9 + i] - 1;
　　b = a[i / 3 * 27 + i % 3 * 3 + j % 3 + j / 3 * 9] - 1;
　　check != ((1 << (r + 18)) + (1 << (c + 9)) + (1 << b));
　　}
　　if(check != 0x7ffffff) {
　　　return 0;
　　}
　}
}
return 1;

お礼

あぁなるほどビット演算ですか。たしかにこれだとやりやすいかもしれません。
私なんかでは全然アイデアが浮かばず、しかしいくつもアイデアがあり驚きました。いやはや、なんとも未熟です。。
本当にありがとうございました！

回答No.5

masa6272

ループを1つにまとめるアイディアです。
for(i = 0; i < 9; i++) {
　for(j = 0;j < 9;j++) {
　　r = i * 9 + j;
　　c = j * 9 + i;
　　b = i / 3 * 27 + i % 3 * 3 + j % 3 + j / 3 * 9;
　　if((((1 << r) << 18) |= ((1 << c) << 9) |= 1 << b) != 0x7FFFFFF) {
　　　return 0;
　　}
　}
}
return 1;

変数の宣言などは、省いてます。全て整数です。
考え方には、自信がありますが、動かしてないんで、タイプミスがあるかもしれません。

回答No.4

masa6272

ループの回し方と、判定についてのアイディアです。

for(i = 0;i < 3;i++) {
　for(j = 0;j < 3;j++) {
　　check = 0;
　　for(k = 0;k < 9;k++) {
　　　check |= (1 << (a[(k % 3 + i * 3) + (k / 3 + j * 3)] - 1));
　　}
　　if(check != 0x1ff) {
　　　数独ではないときの処理、多分これが関数なら、0 でも返す
　　}
　}
}

aは81個の、1次元配列です。ここに挙げたのは、3×3の部分のチェックです。

後、横は
for(i = 0;i < 9;i++) {
　for(j = 0;j < 9;j++) {
　　a[i * 9 + j]に関する処理
　}
}

縦は
for(i = 0;i < 9;i++) {
　for(j = 0;j < 9;j++) {
　　a[i + j * 9]に関する処理
　}
}

ここで、縦と横は同じ形のループですので、1つにまとめることもできます。
ここまでが、回し方のアイディア。

判定ですが、ダブってないかをチェックするのに、ビット演算を使っています。これで、1～9までが、ダブりなく存在するか、簡単にチェックできるはずです(動かしてないんで・・)

回答No.3

yuu_yuu

同じようなことを考える人はいるものですね＾＾
私は、数独を解く方のプログラムを組みました＾＾；

＞＞まず最初の3×3のマスの中の数字を1～9まで確認し、
＞＞それを残り8つのマスにも同様に繰り返すだけで良いと思うのですが
これは、違います。縦と横も1～9があることを確認しないと数独として成立しません。

回答ですが。。。
頭の良い人なら、計算で求める事が出来るのかもしれませんが、私は頭が悪いので
ベタに書きました＾＾；
（私はa[9][9]の配列は使わず、a[81]の配列を使用。）

int SANxSAN[9][9];
//左上の3×3
SANxSAN[0][0] = 0;
SANxSAN[0][1] = 1;
SANxSAN[0][2] = 2;
SANxSAN[0][3] = 9;
SANxSAN[0][4] = 10;
SANxSAN[0][5] = 11;
SANxSAN[0][6] = 18;
SANxSAN[0][7] = 19;
SANxSAN[0][8] = 20;
//中上の3×3
SANxSAN[1][0] = 3;
SANxSAN[1][1] = 4;
SANxSAN[1][2] = 5;
SANxSAN[1][3] = 12;
SANxSAN[1][4] = 13;
SANxSAN[1][5] = 14;
SANxSAN[1][6] = 21;
SANxSAN[1][7] = 22;
SANxSAN[1][8] = 23;
　　以下全部ベタに書く・・・

で、チェックするところでは
for(i=0;i<9;i++){
　　for(j=0;j<9;j++){
　　　　a[SANxSAN[i][j]] が１～９全部あるかチェック
　　}
}

ちなみに横は
for(i=0;i<9;i++){
　　for(j=0;j<9;j++){
　　　　a[i*9+j] が１～９全部あるかチェック
　　}
}

ついでに縦
for(i=0;i<9;i++){
　　for(j=0;j<9;j++){
　　　　a[i+j*9] が１～９全部あるかチェック
　　}
}

お礼

>縦と横も1～9があることを確認しないと数独として成立しません。
確かにその通りですね・・・失念していました＾＾
a[81]でも出来るという発想はありませんでした。いやはや、自分の初心ぶりがよく自覚できます（涙
おかげさまでプログラムができました！ありがとうございました！

回答No.1

fonera

恐れ入ります。
array[9][9]の配列でチェックする方法で回答します。
（判定の方法は他にいくつかあると思いますが、理解しやすいベタな書き方で回答します）

・まず、X軸のチェックをします。
例えばcheck[9]の配列を全て0で初期化しておき、
check[array[x][y]]++
などで、2以上もしくは0の配列が一つでもあれば数独ではないですよね。
for(x = 0; x < 9; x++) {
　check[array[x][0]]++;
}
であれば、一番上の列のX軸のチェックが出来ます。

・次に、Y軸のチェックをします。
X軸と同様に行います。

・3x3マスのチェックを行います。
X軸と同様ですが、
array[x][y]で、xだけ・yだけ変えつつループさせるわけにはいかないので工夫が必要です

こういうときは、まず手でべた書きして、その後省略できないか考えた方が楽です。
array[0][0], array[0][1], array[0][2]
array[1][0], arrya[1][1], array[1][2]
array[2][0], arrya[2][1], array[2][2]

こうやって書けば、何となく判りますか？
先ほどまでと同様に、
for(x = 0; x < 3; x++) {
　for(y= 0; y < 3; y++) {
　　check[array[x][y]]++;
　}
}
とすればチェックできますね？あとは、これを9ブロック分やりたいので・・・

for(bx = 0; bx < 3; bx++) {
　for(by= 0; by < 3; by++) {
　　for(x = 0+bx; x < 3+bx; x++) {
　　　for(y= 0+by; y < 3+by; y++) {
　　　　check[array[x][y]]++;
　　　}
　　}
　}
}
とすればチェックできます。

べた書きは見づらいし、インデントが深くなって混乱しがちです。
一回動くモノが出来たら、関数に出来るところはないか、省略できるところはないか考えるようにしてみて下さい。