• ベストアンサー
  • 困ってます

N-Queen 問題

 N-Queen問題を考えています。  なかなかうまくいきません。  どうやったら解けるか、アルゴリズムでも下の私が考えたプログラムでもいいんでアドバイスください。 (4×4の場合) #include<stdio.h> #define BYTESIZE 8 void printbits(unsigned i); struct data { int basho; unsigned l1,l2,tate,x; }; int main(void) { unsigned m,l,hojo=0; int kenchi,i,j,k; struct data a[5]; for(i=0;i<=3;++i) { l=1<<i; hojo|=hojo|l; } a[0].l1=0; a[0].l2=0; a[0].tate=0; for(kenchi=0;kenchi<=3;) { for(i=1;i<=4;) { a[i].x=0; for(j=a[i].x;j<=3 && ((~l)&hojo)==0;++j) { m=1<<j; a[i].l1=((a[i-1].l1)<<1)&hojo; a[i].l2=((a[i-1].l2)>>1)&hojo; a[i].tate=(a[i-1].tate)|m; l=(a[i].l1)|(a[i].l2)|(a[i].tate); a[i].x=j+1; } if((~l)&hojo) { a[i].basho=j; a[i].l1=(a[i].l1)|m; a[i].l2=(a[i].l2)|m; ++i; if(i==5) {for(k=1;k<=4;++k) printf("%d ",a [k].basho);printf("\n");} } if(j==3)--i; if(i==0) kenchi++; } } } void printbits(unsigned intval) { unsigned i; for(i=0;i<BYTESIZE*sizeof(unsigned);++i) printf("%d",(intval<<i&1<<BYTESIZE*sizeof(unsigned)-1)?1:0); putchar('\n'); }  tateで駒があった列、l1で左にずらしたもの、l2で右にずらしたものを表しています(うまく説明出来なくすいません)。 参考URL:http://oshiete1.goo.ne.jp/kotaeru.php3?qid=330589  

共感・応援の気持ちを伝えよう!

  • 回答数1
  • 閲覧数468
  • ありがとう数1

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.1
  • s2t
  • ベストアンサー率79% (47/59)

こんな感じで。 MinGWで確認しました。 #include <stdio.h> #include <stdlib.h> #define N 8 /* 8×8の場合 */ int v[N], x[2*N-1], y[2*N-1], z[N]; void printbits(void) { int i, j; static sol = 0; printf("\nAns. %d\n", ++sol); for(i = 0; i < N; i++) { for(j = 0; j < N; j++) { if(z[i] == j) printf("■"); else printf("□"); } printf("\n"); } } void recursivesums(int i) { int j; for(j = 0; j < N; j++) { if(v[j] && x[i+j] && y[i-j+N-1]) { z[i] = j; if(i < N-1) { v[j] = x[i+j] = y[i-j+N-1] = 0; recursivesums(i+1); v[j] = x[i+j] = y[i-j+N-1] = 1; } else printbits(); } } } int main(int argc, char *argv[]) { memset(v, 1, sizeof(v)); memset(x, 1, sizeof(x)); memset(y, 1, sizeof(y)); recursivesums(0); return 0; }

共感・感謝の気持ちを伝えよう!

質問者からのお礼

ありがとうございます!

関連するQ&A

  • もう一度質問します。

     N×N-Queen問題を考えています。  チェスの駒の置き方を考えるもので、ある駒を置いた同じ縦列・横列・斜め列には駒が置けない条件下にある時、N×Nの盤の上にN個の駒を置くパターンは何個あるかというものです。  tree構造とbit操作を用いて考えたいのですがなかなかうまくいきません。  どうやったら解けるか、アルゴリズムでも下の私が考えたプログラムでもいいんでアドバイスください。 (4×4の場合) #include<stdio.h> #define BYTESIZE 8 void printbits(unsigned i); struct data { int basho; unsigned l1,l2,tate,x; }; int main(void) { unsigned m,l,hojo=0; int kenchi,i,j,k; struct data a[5]; for(i=0;i<=3;++i) { l=1<<i; hojo|=hojo|l; } a[0].l1=0; a[0].l2=0; a[0].tate=0; for(kenchi=0;kenchi<=3;) { for(i=1;i<=4;) { a[i].x=0; for(j=a[i].x;j<=3 && ((~l)&hojo)==0;++j) { m=1<<j; a[i].l1=((a[i-1].l1)<<1)&hojo; a[i].l2=((a[i-1].l2)>>1)&hojo; a[i].tate=(a[i-1].tate)|m; l=(a[i].l1)|(a[i].l2)|(a[i].tate); a[i].x=j+1; } if((~l)&hojo) { a[i].basho=j; a[i].l1=(a[i].l1)|m; a[i].l2=(a[i].l2)|m; ++i; if(i==5) {for(k=1;k<=4;++k) printf("%d ",a [k].basho);printf("\n");} } if(j==3)--i; if(i==0) kenchi++; } } } void printbits(unsigned intval) { unsigned i; for(i=0;i<BYTESIZE*sizeof(unsigned);++i) printf("%d",(intval<<i&1<<BYTESIZE*sizeof(unsigned)-1)?1:0); putchar('\n'); }  tateで駒があった列、l1で左にずらしたもの、l2で右にずらしたものを表しています(うまく説明出来なくすいません)。 参考URL:http://oshiete1.goo.ne.jp/kotaeru.php3?qid=329998

  • C言語で、引数が構造体の場合

    生徒の名前、点数、順位を表示するプログラムをつくりたいのですが、(下のような関数を用いることを前提として) void rank1(struct data *x,int n) { int i,j; for(i=0;i<n;i++) x[i].rank=1; for(i=0;i<n;i++) for(j=0;j<n;j++) if(x[i].score<x[j].score) x[i].rank++; } このような場合、関数の引数として、構造体が用いられているわけですよね? 引数が構造体の場合、どのように引数の部分を書けばいいのか分かりません。 私が考えたプログラムは下記の通りです。 もちろんうまくいきませんでした。 たぶん最後のprintfの所のrank1の引数が間違っているだけだと思うんですが、どうでしょうか? include<stdio.h> struct data { char name; int score; int rank; }; void rank1(struct data *x,int n) { int i,j; for(i=0;i<n;i++) x[i].rank=1; for(i=0;i<n;i++) for(j=0;j<n;j++) if(x[i].score<x[j].score) x[i].rank++; } void main(void) { int m; static struct data x[] = {{'A',56,1}, {'B',79,1}, {'C',34,1}, {'D',91,1}, {'E',69,1}}; for(m=0;m<5;m++) printf("%c君 %d点 %d位\n",x[m].name,x[m].score,rank1(x,m)); }

  • 以前勉強していたのですが、教えてください。

    今自分でC言語の勉強をしているのですが、解けないプログラムが本に載っていましたので教えてください。 #include<stdio.h> struct DATE_DATA { int yy, mm, dd; }; void sub1(struct DATE_DATA *data, int i); void sub2(struct DATE_DATA *data, int i); void main(void) { int i; struct DATE_DATA data[5]; for(i = 0; i < 5; i++) { sub1(&data[i], i); } for(i = 0; i < 5; i++) { sub2(&data[i], i); } }                                                     void sub1(struct DATE_DATA *data, int i) /&data[i] ,iの {                        アドレスを受け取る/ printf("%d回目\n", i + 1); printf(" year = "); printf("%d", &data->yy); /構造体ポインタ変数名->メンバ名 printf(" month = ");   なのにdataの前に&が付いている/ printf("%d", &data->mm); printf(" day = "); printf("%d", &data->dd); } void sub2(struct DATE_DATA *data, int i) { printf("%d回目 ", i + 1); printf("%02d/", data->yy); /dataの前には&が付いていない/ printf("%02d/", data->mm); printf("%02d\n", data->dd); } 長くなりまして、すみません。質問がプログラムの中にあることも、すみません。 どうしても分からなくて回答をお願いします。

  • 配列の長さについて

    現在課題で書いているプログラムに以下のような関数があるのですが、 unsigned char key[32]; int w[60]; int data[NB]; int nk; int nr; int data2[32]; int Cipher(int *); int invCipher(int *); void encryptEBC(int *); void decryptEBC(int *); main(){ unsigned char keys[]={0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07, 0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f}; unsigned char iv[]={0xcb,0x70,0x05,0x9e,0x27,0x2f,0x4e,0xd2, 0xd0,0xbe,0x0b,0x06,0xbf,0x16,0xec,0x5a}; unsigned char init2[]={'1','2','3','4','5','6','7','8','9','0','1','2','3','4','5','6','7','8','9','0', '1','2','3','4','5','6','7','8','9','0',0x0a}; //unsigned char init2[]={'h','e','l','l','o'}; int isize = sizeof(init2)/sizeof(init2[0]); int dsize2 = sizeof(data2)/sizeof(data2[0]); printf("%d,%d\n",isize,dsize2); FILE *fp; char *fname = "test.txt"; unsigned char init[16]; int i = 0; int c; fp = fopen( fname, "r" ); if( fp == NULL ){ printf( "%sファイルが開けません\n", fname ); return -1; } while( (c = fgetc( fp )) != EOF ){ init[i] = c; i = i+1; } fclose( fp ); memcpy(key,keys,16); nk = 4; nr = nk + 6; KeyExpansion(key); memcpy(data,init,16); memcpy(data2,init2,isize); printf("%d\n",dsize2); datadump("PLAINTEXT: ",data,16); datadump("KEY: ",key,16); Cipher(data); datadump("Cipher: ",data,16); invCipher(data); datadump("invCipher: ",data,16); printf("\n"); printf("%d\n",dsize2); datadump("PLAINTEXT: ",data2,dsize2); encryptEBC(data2); printf("%d\n",dsize2); datadump("EBCCipher: ",data2,dsize2); decryptEBC(data2); datadump("invCipher: ",data2,dsize2); printf("\n"); return 0; } void encryptEBC(int data[]){ int dsize = sizeof(data)/sizeof(data[0]); int tmp[16]; int i,j,k; printf("%d\n",dsize); KeyExpansion(key); for (i = 0; i < dsize; i += 16) { for (j = 0; j < 16; j++){ tmp[j] = data[i + j]; } Cipher(tmp); for(k=0;k<16;k++){ data[i+k] = tmp[k]; } } } 関数encryptEBC内のdsizeの値がこの場合だとmain内の配列data2の長さ32になってほしいのですが、1になってしまいます。 非常に見ずらいプログラムで申し訳ないのですが、どなたか1になってしまう理由、またどうすれば正しくdata2の長さを求められるか教えていただけないでしょうか?

  • c 言語初心者です。

    c 言語初心者です。 私は下記の構造体配列をつくりました。 しかしバッファオーバーランが起きてエラーが起きてしまいます。 ヒープ領域に問題があるのかもしれませんが、プログラム上どこに原因があるのかが良くわかりません。 どなたかよろしければ教えていただけないでしょうか? #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include<memory.h> struct s { int i; char name[25]; char huri[25]; char num[23]; }; void touroku(struct s *p); void hyouji(struct s *p); int main(void) { struct s data; touroku( &data ); hyouji( &data ); //data.num *= 1; /* dataはポインタではないのでドット演算子 */ hyouji( &data ); return 0; } /* 構造体のメンバを設定する */ void touroku(struct s *p) { int i=0; for(i=1;i<3;i++) { printf( "25文字以内の名前を入力して下さい\n" ); memset(p[i].name, 0, sizeof(p[i].name)); fgets( p[i].name,sizeof(p[i].name) , stdin ); if(strchr(p[i].name,'\n')==NULL)//バッファ処理 { while(getchar() != '\n'); } if(p[i].name[strlen(p[i].name)-1]=='\n')//改行解除 { p[i].name[strlen(p[i].name)-1] = '\0'; } printf("25文字以内のふりがなを入力してください\n"); memset(p[i].huri, 0, sizeof(p[i].huri)); fgets(p[i].huri,sizeof(p[i].huri),stdin); if(strchr(p[i].huri,'\n')==NULL)//バッファ処理 { while(getchar() != '\n'); } if(p[i].huri[strlen(p[i].huri)-1]=='\n')//改行解除 { p[i].huri[strlen(p[i].huri)-1] = '\0'; } printf( "整数を入力して下さい\n" ); memset(p[i].num, 0, sizeof(p[i].num)); fgets(p[i].num,sizeof(p[i].num),stdin ); if(strchr(p[i].num,'\n')==NULL)//バッファ処理 { while(getchar() != '\n'); } if(p[i].num[strlen(p[i].num)-1]=='\n')//改行解除 { p[i].num[strlen(p[i].num)-1] = '\0'; } } } /* 構造体のメンバを出力する */ void hyouji(struct s *p) { int i=0; for(i=1;i<3;i++) printf("%-8s %3s %3s %d\n" ,p[i].name , p[i].huri , p[i].num , i); puts("----------------------------------------------------------------"); return ; }

  • 構造体のメモリの確保のされかた

    2つ質問があります。 1. #include <iostream> using namespace std; union Data { unsigned long val1_val2; struct { unsigned short val1; unsigned short val2; } value; }; int main(void) { Data data; data.val1_val2 = (40 /* val1 */ << (sizeof(data.value.val1) * 8)) + 10 /* val2 */; cout << "val1 = " << data.value.val1 << endl; cout << "val2 = " << data.value.val2 << endl; return 0; } 上記ソースコードを実行すると、「val1 = 10 val2 = 40」という結果がでます。val1は上位2バイトを指しているはずだと考えて書いたのですが、何が間違っているのでしょうか? 構造体は上に書いたメンバーを下位に割り当てていくのでしょうか? 2. 32ビットコンピューターでは構造体のサイズは4の倍数バイトになると聞いたのですが、VC++で struct s1{ char c; }; のサイズをsizeof演算子で見てみると、1バイトで struct s2{ unsigned bit: 1; }; のサイズは4バイトでした。 前者は本当に1バイトで扱われているのでしょうか? 以上2つよろしくお願いします。

  • 構造体のファイル書き込み&読み出しに関して2

    C言語を勉強しているものです。指定した番号に構造体を書き込み、指定した番号をの構造体を出力するプログラムを作成したいのですが、表示結果画像のようになってしまいます。 デバックしても、どこが違うのかがわかりません。説明不足かとは思いますがご教授お願いします。 ↓↓ソースコード↓↓ #include<stdio.h> #include<stdlib.h> struct S_data{ char Name[10+1];/*名前*/ int Sex;/*性別*/ int Height;/*身長*/ float Weight;/*体重*/ }; void FR_data(FILE *Fp,int pos); void FW_data(FILE *Fp,int pos); void OUP_data(struct S_data tag); void INP_data(struct S_data *tag); int RF_data(FILE *Fp,struct S_data *tag,int pos); int WF_data(FILE *Fp,struct S_data *tag,int pos); void main(){ FILE *Fp; int pos=0; int Ret; Fp=fopen("aaa.dat","r+b"); if(Fp==NULL){ Fp=fopen("aaa.dat","w+b"); if(Fp==NULL){ printf("File not open\n"); exit(2); } } while(1){ printf("入力の番号[0:終了]->"); scanf("%d",&pos); if(pos==0) break; FW_data(Fp,pos); } while(1){ printf("出力の番号[0:終了]->"); scanf("%d",&pos); if(pos==0) break; FR_data(Fp,pos); } Ret=fclose(Fp); } void FR_data(FILE *Fp,int pos){ struct S_data Temp; /*出力情報*/ int Ret; /*返却値*/ memset(&Temp,'\0',sizeof(Temp)); Ret=RF_data(Fp,&Temp,pos); /*情報の読み込み*/ if (Ret!=1){ printf("File not read\n"); }else{ OUP_data(Temp); /*情報の表示*/ } } void FW_data(FILE *Fp,int pos){ struct S_data wk; /*入力情報*/ int Ret; /*返却値*/ memset(&wk,'\0',sizeof(wk)); INP_data(&wk); /*情報の入力*/ Ret=WF_data(Fp,&wk,pos); /*情報の書き込み*/ if (Ret!=1){ printf("File not write\n"); } } void OUP_data(struct S_data tag){ printf("Name:%s\n",tag.Name); if (tag.Sex==0){ printf("Sex:M\n"); }else{ printf("Sex:F\n"); } printf("Height:%d\n",tag.Height); printf("Weight:%.2f\n",tag.Weight); } void INP_data(struct S_data *tag){ memset(tag,'\0',sizeof(tag)); printf("Name-->"); scanf("%s",&tag->Name); printf("Sex[0:M1:F]-->"); scanf("%d",&tag->Sex); printf("Height-->"); scanf("%d",&tag->Height); printf("Weight-->"); scanf("%f",&tag->Weight); } int RF_data(FILE *Fp,struct S_data *tag,int pos){ int Ret_I; /*fseek返却値*/ size_t Ret_S; /*fread返却値*/ Ret_I=fseek(Fp,sizeof(tag)*(pos),SEEK_SET); Ret_S=fread(tag,sizeof(tag),1,Fp); return Ret_S; } int WF_data(FILE *Fp,struct S_data *tag,int pos){ int Ret_I; /*fseek返却値*/ size_t Ret_S; /*fwrite返却値*/ Ret_I=fseek(Fp,sizeof(tag)*(pos),SEEK_SET); Ret_S=fwrite(tag,sizeof(tag),1,Fp); return Ret_S; }

  • メモリ動的確保について

    こんにちはです。 メモリの動的確保なのですが、 typedef struct DATA{ char name[256]; char pass[256]; int money; }BANK; void insert(BANK *p,int max); int main(){ int i; size_t st; BANK *person; person = (struct DATA *)malloc(sizeof(struct DATA)); //person = (struct DATA *)malloc(5); if(person == NULL){ printf("確保失敗\n"); exit(-1); } //memset(person,'\0',sizeof(struct DATA)); と、言う風に、記載ソースは途中ですがメモリをとりました。 mallocの後ろの部分ですが、sizeof(struct DATA)と5ではどうちがうのでしょう??2通りともコンパイルエラーはないです。 5は動的に最大5までとるって事はわかるのですが、struct DATAの方はいくつとるのです??いくつもで入力次第です? そして、動的したのにたいしてmemsetしたら実行エラー(コンパイルは通りました)おきました。動的にたいしてmemはダメなのでしょうか? アドバイスいただけたらありがたいです。宜しくお願いいたします。

  • プログラム(C)

    #include <stdio.h> #include <stdlib.h> #define FNAME "smp.bmp" #define WSIZE 256 #define HSIZE 256 #define BSIZE 1024 int main(void) { struct BMPFILEHEADER { ・   ・ }; struct BMPINFOHEADER { ・   ・ }; unsigned char img[HSIZE][WSIZE][3]; unsigned char buf[BSIZE]; struct BMPFILEHEADER lpHead; struct BMPINFOHEADER lpInfo; FILE *fp; int i; int j; int k; fp = fopen(FNAME,"rb"); if (fp==NULL) { printf("ファイルをオープンできません\n"); return 0; } fread(&lpHead.bfType, sizeof(unsigned short),1,fp); fread(&lpHead.bfSize, sizeof(unsigned int),1,fp); fread(&lpHead.bfReserved1, sizeof(unsigned short),1,fp); fread(&lpHead.bfReserved2, sizeof(unsigned short),1,fp); fread(&lpHead.bf0ffBits, sizeof(unsigned int),1,fp); fread(&lpInfo, sizeof(struct BMPINFOHEADER),1,fp); for(i=0;i<HSIZE;i++) { fread(buf,sizeof(unsigned char),WSIZE*3,fp); for(j=0;j<WSIZE;j++) { for(k=0;k<3;k++) { img[HSIZE-1-i][j][k]=buf[j*3+k]; } } } fclose; return 0; } このプログラムはBMP画像を読み込むプログラムなんですが このプログラムに画素値を出力するプログラムにしたいのですがうまくできません。 結果は(真っ白な画像の時)255255255・・・255255と出力したいのです。白黒画像なのでR=G=Bで1画素値は255だけでいいのですが。どうしても255255255や25500などとでてしまいます。 アドバイスお願いします。(800字までなので構造体の宣言は抜いてしましました) 。

  • 構造体の構造体 引数

    構造体の中の構造体の関数の引き渡し方法がわかりません。 下記ソースで試したのですが、うまくいきませんでした。 助言お願いいたします。 //repo.c #include <stdio.h> #include <string.h> #include <stdlib.h> #include <ctype.h> #define NUM 20 #define MAX 15 struct seiseki{ float shu[3]; }; struct seito{ char name[NUM]; int age; struct seiseki kekka; }; void input(struct seito *p); void s_input(struct seiseki *p); void ss_input(struct seiseki *data); int main(){ int i; struct seito data[2]; for(i=0;i<2;i++){ printf("------------------------------\n"); printf("%d人目",i+1); input(&data[i]); } printf("%f\n",data[0].kekka.shu[0]); printf("%f\n",data[0].kekka.shu[1]); printf("%f\n",data[0].kekka.shu[2]); //data[1]に格納できない。 printf("%f\n",data[1].kekka.shu[0]); printf("%f\n",data[1].kekka.shu[1]); printf("%f\n",data[1].kekka.shu[2]); return 0; } void input(struct seito *p){ printf("名前->"); scanf("%s",p->name); printf("年齢->"); scanf("%d",p->age); s_input(&(p->kekka)); } void s_input(struct seiseki *data){ printf("国語->"); ss_input(data); printf("算数->"); ss_input(data); printf("英語->"); ss_input(data); } //下記関数で成績をchar型で受け取り、数値化したい。 void ss_input(struct seiseki *data){ char p[100]; int i=0; static int o=0; scanf("%s",p); while( p[i] != '\0'){ if(isdigit(p[i])==0){ printf("再入力してください"); scanf("%s",p); } i++; } data->shu[o]=atof(p); printf("%f\n",data->shu[o]); o++; }