私が作ろうとしているプログラムは数独を解くものではなく、予めテキストファイルに書かれている横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ベストアンサー
- 回答日時:
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]]++;
}
}
/*ここで判定する*/
}
}
ですな。
# 卓上で考えたのでバグに気がつきませんでした・・・手元ではとりあえずこれで動いてます。
この回答への補足
とても理解しやすかったです。おかげさまでプログラムができました!
一つだけ確認したいのですが、x軸y軸のチェックは、それぞれどれか1行だけ選んでチェックすればいいんですよね?数独はすべての行をチェックする必要はありませんよね?
No.6
- 回答日時:
すみません。
アイディアが、先走って変なプログラム投稿しちゃいました。
基本的な考え方は、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
- 回答日時:
ループを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
- 回答日時:
ループの回し方と、判定についてのアイディアです。
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
- 回答日時:
同じようなことを考える人はいるものですね^^
私は、数独を解く方のプログラムを組みました^^;
>>まず最初の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]] が1~9全部あるかチェック
}
}
ちなみに横は
for(i=0;i<9;i++){
for(j=0;j<9;j++){
a[i*9+j] が1~9全部あるかチェック
}
}
ついでに縦
for(i=0;i<9;i++){
for(j=0;j<9;j++){
a[i+j*9] が1~9全部あるかチェック
}
}
>縦と横も1~9があることを確認しないと数独として成立しません。
確かにその通りですね・・・失念していました^^
a[81]でも出来るという発想はありませんでした。いやはや、自分の初心ぶりがよく自覚できます(涙
おかげさまでプログラムができました!ありがとうございました!
No.1
- 回答日時:
恐れ入ります。
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]]++;
}
}
}
}
とすればチェックできます。
べた書きは見づらいし、インデントが深くなって混乱しがちです。
一回動くモノが出来たら、関数に出来るところはないか、省略できるところはないか考えるようにしてみて下さい。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 統計学 確率の問題です。 7 2022/05/07 01:08
- PostgreSQL 数値が定期的にあらわれる文字列から、いくつめに出現した数値が指定して切り出したい 1 2023/06/08 13:12
- 数学 数独の解法についてお聞きします 4 2023/05/25 17:15
- 統計学 確率の問題です。お詳しい方よろしくお願いします。 8 2022/12/04 17:01
- その他(ゲーム) 数独の解き方 4 2023/05/17 16:09
- Java Java 南京錠 2 2023/02/04 11:46
- その他(ゲーム) 数独 9マスx9マス 何種類くらいありますか。 1 2022/08/04 12:29
- C言語・C++・C# C言語で 英文字のみからなる文字列、”Radar”、”WasItACatISaw”、”a”、””(空 5 2022/12/20 15:17
- Excel(エクセル) SUMIF関数について 4 2023/06/14 13:13
- その他(ゲーム) 3×3ビンゴについて 1 2022/07/31 14:30
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
スカラーのベクトル微分
-
php で1から100までの素数の表...
-
PHPのmin関数、「1」以上の数値...
-
pythonのnumpyでの繰り返しでの...
-
C言語 最大値と最小値を求めて...
-
STLのvectorで作った配列をメン...
-
CArrayの要素としてCStringArra...
-
Pager::factory()の使い方がわ...
-
C言語で全角文字の扱いについて
-
数独かを判断するプログラム
-
PDOのバインドをforeachでまと...
-
C言語の配列をPush(追加)する...
-
PHPは何故値渡しより参照渡しの...
-
行列
-
System.String.Splitでエラー
-
連想配列から<th>を含むテーブ...
-
np.stack()とnp.array()の違い
-
am()の使い方
-
cakephpでのトランザクション処...
-
verilogで、配列の一部をタスク...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
スカラーのベクトル微分
-
STLのvectorで作った配列をメン...
-
特定の文からメールアドレスの...
-
配列の要素(value)に、変数を...
-
読み(あ行~わ行)ごとに分け...
-
ファイルの書き込みについて教...
-
verilogで、配列の一部をタスク...
-
CArrayの要素としてCStringArra...
-
pythonのnumpyでの繰り返しでの...
-
C言語の配列をPush(追加)する...
-
php キーソート キーが重複した...
-
CArrayのソート
-
【PHP】配列のキー名の修正は可...
-
多次元配列をエンコードする関...
-
PHPは何故値渡しより参照渡しの...
-
cakephpでのトランザクション処...
-
pg_copy_fromの使い方について...
-
array_intersectで空欄を比較し...
-
濁点のソート
-
配列中のあるキー、値を取得し...
おすすめ情報