ナンバーリンクゲーム？
番号リンクは、グリッド内の番号を接続するためのパスを見つけることを含む一種のロジックパズルです。
ナンバーリンクパズルの簡単な例ナンバーリンクパズルの解決策
ルール −プレーヤーは、グリッド上のすべての一致する番号を単一の連続した線（またはパス）とペアにする必要があります。線は互いに分岐したり交差したりすることはできず、数字は各線の終わりにある必要があります（つまり、中央ではありません）。一部のNumberlink設計者はこれを規定していませんが、問題は独自の解決策があり、グリッド内のすべてのセルが塗りつぶされている場合にのみ適切に設計されていると見なされます。
ゲーム −n×n個の正方形の配列を考えます。いくつかの正方形は空で、いくつかは中実で、いくつかの非中実の正方形は整数1、2、3、…でマークされています。各整数はボード上で正確に2つの異なる正方形を占めます。プレーヤーのタスクは、水平方向と垂直方向の動きだけを使用して、ボード上の各整数の2つのオカレンスを単純なパスで接続することです。 2つの異なるパスが互いに交差することはできません。パスに塗りつぶされた正方形を含めることはできません（塗りつぶされた正方形をパスに表示することは禁止されています）。最後に、すべての非塗りつぶしの正方形はパスで埋める必要があります。
アルゴリズム −与えられたボードサイズn×nで有効なランダムパズルを準備するために、最初にボード上にランダムで単純な相互に交差しないパスを生成します。生成されたすべてのパスの外側にいくつかの孤立した正方形が残っている場合は、これらの孤立した正方形を塗りつぶし（禁止）としてマークします。次に、パスの端点と塗りつぶされた正方形のリストをパズルとして提供します。
したがって、最初にソリューションを生成し、次にソリューションからパズルを解きます。パスと塗りつぶされた正方形は、n×nボードを分割します。 union-findデータ構造を使用して、このパーティションを生成します。データ構造は、ボード上のn^2個の正方形のセットのサブセットを処理します。
説明
-
ボード上で正方形（i、j）と（k、l）をランダムに配置し、次のようにします。（a）（i、j）と（k、l）が互いに隣接し、（b）どちらも（i、j）また、（k、l）は、これまでに生成されたパスに属しません。ボード全体にそのような正方形のペアが見つからない場合は、FAILURE / *を返します。ここで、（i、j）と（k、l）は、構築される新しいパスの最初の2つの正方形です。 *
-
（i、j）と（k、l）を含む2つのunion-findツリーの結合を作成します。
-
現在のパスを拡張できる限り繰り返します。名前を（i、j）=（k、l）に変更します。 （a）（k、l）がこれまでに生成されたパス（現在のパスを含む）に属していないように、（i、j）のランダムな隣接正方形（k、l）を見つけます（b）唯一の隣接（k 、l）部分的に構築された現在のパスは（i、j）です。
-
そのようなネイバー（k、l）が見つからない場合、パスをそれ以上拡張できないため、ループを解除します
-
それ以外の場合は、（i、j）と（k、l）が属する2つの和集合ツリーを和集合にします。
-
新しいパスの最初と最後にある2つの正方形のエンドポイントフラグを設定します。
-
成功を返す
入力
| || || || || || || 4 | | || || || || || 3 || | | || || 2 || 2 || || || 3 | | || || || || X || || 1 | | || || 6 || || || 7 || 7 | | 5 || 4 || || X || || X || 1 | | || 5 || || 6 || || || |
出力
上記の表の解決策
| 4 || 4 || 4 || 4 || 4 || 4 || 4 | | 4 || 1 || 1 || 1 || 1 || 3 || 3 | | 4 || 1 || 2 || 2 || 1 || 1 || 3 | | 4 || 1 || 1 || 1 || X || 1 || 1 | | 4 || 4 || 6 || 1 || 1 || 7 || 7 | | 5 || 4 || 6 || X || 1 || X || 1 | | 5 || 5 || 6 || 6 || 1 || 1 || 1 |
例
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct _node {
struct _node *parent;
int rank;
int path_number;
int endpoint;
};
typedef struct _node node;
/* Name: initboard()
Input: 2D-array of pointers, size of array row/column
Output: --void--
Description: Takes a table of pointers and initializes it. */
void initboard(node ***arr, int n) {
int i, j;
for (i=0;i<n;i++){
for (j=0;j<n;j++){
node *np;
np = (node *)malloc(sizeof(node));
np->rank = 0;
np->parent = NULL;
np->path_number = 0;
np->endpoint = 0;
arr[i][j] = np;
}
}
}
/*
Input:a node Output:the set pointer of the set the node belongs to
node *findset(node *n) {
if (n->parent != NULL)
n = n->parent;
return n;
}
void setunion(node *x, node *y) {
x = findset(x);
y = findset(y);
if (x->rank > y->rank)
y->parent = x;
else {
x->parent = y;
if(x->rank == y->rank)
y->rank++;
}
}
int neighbour(int n, node ***arr) {
int i1, i2, j1, j2, ct = 0, flag = 0, a, b,k2;
int k = rand()%(n*n);
while (ct < (n*n)) {
k %= (n*n);
i1 = k/n;
j1 = k%n;
if (arr[i1][j1]->path_number==0) {
int kk = rand()%4;
int cc = 0;
switch (kk) {
case 0: i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 1: i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 2: i2= i1+1;
j2= j1-0;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 3: i2= i1-0;
j2= j1+1;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 4: if(cc==4)
break;
i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 5: if(cc==4)
break;
i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 6: if(cc==4)
break;
i2= i1+1;
j2= j1-0;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 7: if(cc==4)
break;
i2= i1-0;
j2= j1+1;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
}
}
if(flag==1)
break;
ct++;
k++;
}
if(ct<n*n) {
k2= (i2*n)+j2;
return k*(n*n)+k2;
} else {
return -1;
}
}
int checkneigh(int k1, int k2, int n, node ***arr) {
int i= k2/n;
int j= k2%n;
int ii= k1/n;
int jj= k1%n;
int ct=0;
if(i>0 && findset(arr[i-1][j])==findset(arr[ii][jj]))
ct++;
if(i<n-1 && findset(arr[i+1][j])==findset(arr[ii][jj]))
ct++;
if(j>0 && findset(arr[i][j-1])==findset(arr[ii][jj]))
ct++;
if(j<n-1 && findset(arr[i][j+1])==findset(arr[ii][jj]))
ct++;
if(ct>1)
return 0;
else
return 1;
}
int valid_next(int k, int n, node ***arr) {
int i1, i2, j1, j2, a, b, kk, stat,ct=0;
int flag=0;
i1= k/n;
j1= k%n;
kk= rand()%4;
switch(kk) {
case 0: i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 1: i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 2: i2= i1+1;
j2= j1-0;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 3: i2= i1-0;
j2= j1+1;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 4: if(ct==4)
break;
i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 5: if(ct==4)
break;
i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 6: if(ct==4)
break;
i2= i1+1;
j2= j1-0;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 7: if(ct==4)
break;
i2= i1-0;
j2= j1+1;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
}
//printf("flag- %d\n",flag);
if(flag==0)
return -1;
if(flag) {
//printf("value sent- %d\n", i2*n + j2);
return (i2*n)+j2;
}
}
int addpath(node ***arr, int n, int ptno) {
int a,b,k1,k2;
int i1,j1,i2,j2;
k2= neighbour( n, arr);
if(k2==-1) //no valid pair found to start with
return 0;
k1= k2/(n*n);
k2= k2%(n*n);
//printf("%d %d\n",k1,k2);
i1= k1/n;
j1= k1%n;
i2= k2/n;
j2= k2%n;
arr[i1][j1]->endpoint= 1;
arr[i2][j2]->path_number= ptno;
arr[i1][j1]->path_number= ptno;
node *n1, *n2;
n1= arr[i1][j1];
n2= arr[i2][j2];
n1= findset(n1);
n2= findset(n2);
setunion(n1, n2);
while(1) {
i1= i2;
j1= j2;
k1= (i1*n)+j1;
k2= valid_next(k1,n,arr);
if(k2==-1) {
arr[i1][j1]->endpoint= 1;
break;
}
i2=k2/n;
j2=k2%n;
arr[i2][j2]->path_number= ptno;
node *n1, *n2;
n1= arr[i1][j1];
n2= arr[i2][j2];
n1= findset(n1);
n2= findset(n2);
setunion(n1,n2);
}
return 1;
}
void printtable(node ***arr, int n) {
int i,j;
printf("Table to be solved:\n");
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
if(arr[i][j]->endpoint ==1){
if(arr[i][j]->path_number/10==0)
printf("| %d |",arr[i][j]->path_number);
else
printf("| %d|",arr[i][j]->path_number);
} else if(arr[i][j]->path_number==0)
printf("| X |");
else
printf("| |");
}
printf("\n");
}
printf("\n\nThe solution to the above table:\n");
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
if(arr[i][j]->path_number != 0){
if(arr[i][j]->path_number/10==0)
printf("| %d |",arr[i][j]->path_number);
else
printf("| %d|",arr[i][j]->path_number);
} else
printf("| X |");
}
printf("\n");
}
}
int main(void) {
srand((unsigned int) time (NULL));
int i, j;
int ct = 1;
int n = 7;
node*** pointers= (node ***)malloc(n*sizeof(node **));
for (i=0; i<n; i++)
pointers[i] = (node **)malloc(n*sizeof(node *));
initboard(pointers, n);
while(1) {
i = addpath(pointers, n, ct);
if (i==0) {
break;
} else {
ct++;
}
}
printtable(pointers,n);
return 0;
} -
C＃のセマフォ
セマフォクラスを使用すると、クリティカルセクションにアクセスできるスレッドの数に制限を設定できます。このクラスは、リソースのプールへのアクセスを制御するために使用されます。 System.Threading.Semaphoreは、Semaphoreの実装に必要なすべてのメソッドとプロパティを備えているため、Semaphoreの名前空間です。 C＃でセマフォを使用するには、セマフォオブジェクトのインスタンスをインスタンス化する必要があります。少なくとも2つの引数があります- 参照 − MSDN Sr.No。 コンストラクターと説明 1 セマフォ（Int32、Int32
-
Pythonで数を減らすゲームの勝者を見つけるためのプログラム
AmalとBimalがゲームをしていると仮定します。彼らは数nを持ち、それが2の累乗であるかどうかをチェックします。もしそうなら、彼らはそれを2で割ります。そうでなければ、彼らはそれを次に小さい数で減らします。これも2の累乗です。数を1に減らした人は誰でもゲームに勝ちます。アマルは常にゲームを開始し、勝者の名前を見つける必要があります。 したがって、入力がn =19の場合、19は2の累乗ではないため、出力はAmalになります。したがって、Amalはそれを16に減らし、Bimalは2で除算して8になり、次にAmalは2で除算して次のようになります。 4、次にBimalが2になり、最後にAmal