ページ 1 ／ 1
数独を解けるか解けないかの判定をするプログラム
Posted: 2009年5月03日(日) 18:26
by R
#include<stdio.h>
#define BUFLEN 80
int map[4][4];
int gyo[4][4];/*gyo[m]=0:i+1行に数字m+1が出現していない*/
int retu[4][4];/*retu[m]=0:i+1行に数字m+1が出現していない*/
int block[4][4];/*block[m]=0:i+1ブロックに数字mが出現していない*/
int count=0;
int numpre(){
int i,j,k,m;
/*配列の初期化*/
for(i=0;i<4;i++)
for(j=0;j<4;j++){
block[j]=0; retu[j]=0; gyo[j]=0;}
for(i=0;i<4;i++)
for(j=0;j<4;j++){
m = map[j];
if(m>0){
gyo[m-1]=1;retu[j][m-1]=1;
k=(i/2)*2+j/2+1;
block[k-1][m-1]=1;
}
}
/*ここから先に可能性をしぼりこむコードをかく*/
}
int main(void){
char buf[BUFLEN];
int i,j;
for(i=0;i<4;i++){
fgets(buf,BUFLEN,stdin);
sscanf(buf,"%d %d %d %d",
&map[0],&map[1],
&map[i][2],&map[i][3]);
}
if(numpre()==1)
printf("解けた");
else
printf("解けない");
}
4×4の数独の問題を入力し、それが解けるか否かを出力するプログラムを作成しています。
http://puzzle.lavot.com/java/numberplace/algorithm.html
こちらのアルゴリズムを参考に、行,列,2×2のブロックに1~4の数字が出現しているときに配列gyo,retu,blockに格納するところまで作ったのですが、URLのステップ1,"ある数字が入る可能性のあるマスが１ヶ所しか残っていない場合"の判定をどうするかで詰まりました。
助言をお願いします。
なお、大学の課題なのでmain関数は改変不可です。
Re:数独を解けるか解けないかの判定をするプログラム
Posted: 2009年5月03日(日) 19:51
by non
課題の意味について質問ですが、
数独が解けるか否かというのはどういう意味なのでしょうか？
つまり、数独なら未記入の枠を与えると思うのですが、その枠はどのように
与えるのでしょうか？
もしくは、適当に１６個入力された数字が、数独としての矛盾がないかチェックすると
いうことなのでしょうか？
入力データ例を示してもらえますか？
また、
int gyo[4][4];/*gyo[m]=0:i+1行に数字m+1が出現していない*/
int retu[4][4];/*retu[m]=0:i+1行に数字m+1が出現していない*/
int block[4][4];/*block[m]=0:i+1ブロックに数字mが出現していない*/
これらの変数は課題で与えられているのでしょうか？
Re:数独を解けるか解けないかの判定をするプログラム
Posted: 2009年5月03日(日) 21:13
by R
>>課題の意味について質問ですが、
数独が解けるか否かというのはどういう意味なのでしょうか？
適当に1～4までの数字で問題を与え
つまり、数独なら未記入の枠を与えると思うのですが、その枠はどのように
与えるのでしょうか？
与えた問題に対して、以下の条件を満たす数字の配置ができるとき解けるといいます。空白は0で与えます。
・同一ブロック内に配置された数字はすべて異なっている
・同一行、同一列に配置された数字はすべて異なっている
・最初に問題として与えた数字を上書きしてはいけない
解けるときに1を、解けないときに0を返す関数を作成するのが課題です
>>入力データ例を示してもらえますか？
1 0 0 2
0 0 0 0
0 0 0 1
3 0 0 1
この場合は解けません。
>>また、
int gyo[4][4];/*gyo[m]=0:i+1行に数字m+1が出現していない*/
int retu[4][4];/*retu[m]=0:i+1行に数字m+1が出現していない*/
int block[4][4];/*block[m]=0:i+1ブロックに数字mが出現していない*/
これらの変数は課題で与えられているのでしょうか？
いいえ、main関数以外は与えられていません。
Re:数独を解けるか解けないかの判定をするプログラム
Posted: 2009年5月03日(日) 21:35
by non
空白は０を入力するのですね。理解しました。
私なら、各マスに対し、９つの数字をチェックするための配列を用意します。
例えば、
struct NUM{
int dif_num; //決定された数字
int chk[10]; // 入れる可能性のある数字 0は未使用
}num[4][4];
つまり、あるマスに格納できる数字が１か３なら、
chk[1]とchk[3]を１にします。他は０（booleanの型にしてもいいのですが）
あのアルゴリズムの第１ステップと第２ステップだと第２の方が簡単なので
先に解きたいのでけどね。あの方がいいのでしょうか。
どっちが、先でもいいのかもね。
Re:数独を解けるか解けないかの判定をするプログラム
Posted: 2009年5月06日(水) 04:04
by R
nonさんに教えていただいた方法でリンク先ステップ２を実行することができました。
あとはこれを無限ループに組み込んだときの終了条件を考えればなんとかなりそうです。
Re:数独を解けるか解けないかの判定をするプログラム
Posted: 2009年5月14日(木) 09:06
by R
無事終わりました。nonさんありがとうございました。