8クイーン問題に挑戦
8クイーン問題をC言語で書いてみました！
元々はNクイーンの予定だったため、無駄なコードが多いのですが、Nクイーンはなかなかうまくいかず、結局複雑な8クイーンが完成しました（笑）
⇒8クイーンって？という方はこちらから（Wikipedia）
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 |
#include <stdio.h> #include <stdlib.h> #include <time.h> void QueenPut(int); void resetBoard(int length,int board[length][length]); void printBoard(int length,int board[length][length]); int main(int argc,char *argv[]) { //時間計測用変数 clock_t start,end; start = clock(); //char型からint型に変更 int length = atol(argv[1]); //関数実行 QueenPut(length); //終了時間表示 end = clock(); printf("実行時間：%.3fsec\n",(double)(end-start)/CLOCKS_PER_SEC); } void QueenPut(int length){ //盤面配列 int board[length][length]; //乱数格納変数 int numLeft = 0; //試行回数 int testCount=1; //盤面初期化 resetBoard(length,board); //乱数初期化 srand((unsigned int)time(NULL)); //盤面番号配列 int numTable[length+1]; //乱数格納変数 int randNum; //試行ループ for(int cnt1=0;cnt1<length;cnt1++){ //盤面番号配列 for(int cnt2=1;cnt2<length+1;cnt2++) numTable[cnt2]=cnt2; //行内配置ループ for(int cnt2=0;;cnt2++){ //乱数による配置 if(length-cnt2==0){ randNum = 1; }else{ randNum = rand()%(length-cnt2)+1; } numLeft = numTable[randNum] - 1; //盤面番号配列変更 for(int cnt3=randNum;cnt3<length-cnt2;cnt3++){ numTable[cnt3]=numTable[cnt3 + 1]; } if(board[cnt1][numLeft]==0){ //クイーン配置 board[cnt1][numLeft]=2; //クイーン移動箇所マーク 縦/横 for(int cnt3=0;cnt3<length;cnt3++){ if(board[cnt1][cnt3]==0) board[cnt1][cnt3]=1; if(board[cnt3][numLeft]==0) board[cnt3][numLeft]=1; } //クイーン移動箇所マーク 斜め int point1 = 0; int point2 = 0; if(cnt1>numLeft) { point1 = cnt1 - numLeft; for (int cnt3 = 0; cnt3 < length; cnt3++) { if (board[point1][point2] == 0) board[point1][point2] = 1; point1++; point2++; } }else{ point2 = numLeft - cnt1; for (int cnt3 = 0; cnt3 < length; cnt3++) { if (board[point1][point2] == 0) board[point1][point2] = 1; point1++; point2++; } } //クイーン移動箇所マーク 斜め逆 if(cnt1 > length - numLeft) { point1 = cnt1 + numLeft - length; point2 = length; for (int cnt3 = 0; cnt3 < length; cnt3++) { if (board[point1][point2] == 0) board[point1][point2] = 1; point1++; point2--; } }else{ point1 = 0; point2 = cnt1 + numLeft; for (int cnt3 = 0; cnt3 < length; cnt3++) { if (board[point1][point2] == 0) board[point1][point2] = 1; point1++; point2--; } } //次の行へ break; }else if(cnt2 > length){ //盤面初期化 resetBoard(length,board); //試行回数カウント testCount++; //ループ初期化 cnt1=-1; //やり直し break; } } } //盤面表示 printBoard(length,board); //試行回数表示 printf("試行回数：%d\n",testCount); } //盤面初期化 void resetBoard(int length,int board[length][length]){ for(int cnt1=0;cnt1<length;cnt1++){ for(int cnt2=0;cnt2<length;cnt2++){ board[cnt1][cnt2]=0; } } return; } //盤面表示 void printBoard(int length,int board[length][length]){ int queenFlg=0; for(int cnt1=0;cnt1<length;cnt1++){ queenFlg=0; for(int cnt2=0;cnt2<length;cnt2++){ if(board[cnt1][cnt2]==2){ printf("|＊"); queenFlg++; }else if(board[cnt1][cnt2]==1){ printf("| "); }else if(board[cnt1][cnt2]==0){ printf("|ER"); } } printf("|\n"); } return; } |
基本的にコメントアウトされているため、分かり易くはなっていると思います。
アルゴリズムとしては、
- 1行ずつ駒をランダムに配置
- 配置した場所に駒のフラグ（2）、駒の移動可能位置に移動フラグ（1）を配置
- もし駒が置けない場所（駒がある、もしくは他の駒が移動可能）なら位置を変更
- コマを置けない行があった場合、1行目からやり直し
という感じです。
因みに実行結果は、
- 試行回数は観測したのは1回～1500回
- 平均実行時間は約0.006秒
といった感じです。
また時間があればNクイーンにも挑戦してみたいと思います。
今回のブログ曲
今回投稿中に聴いていた曲はこちら！
アニメも見ましたが、個人的にはEDがドストライク過ぎて、最近頻繁に聴いています…
