-1

したがって、このアルゴリズムを作成する必要があり (このバージョンは、ナイトが開始したのと同じ場所で終了する必要はありません)、機能するようになりましたが、遅すぎます。サイズ= 8の開始位置x = 0およびy = 0で動作しますが、xとyをたとえば2と4に操作しようとすると、数分後に終了しません。誰でも助けることができますか？

#include <stdio.h>
#define size 8
int ruch_x[]={ -1,  1, -2,  2, -2,  2, -1,  1}; //arrays of possible knight moves, for example 2nd move is [1,2]//
int ruch_y[]={  2,  2,  1,  1, -1, -1, -2, -2};

int done(int szach[][size])
{
   for(int i=0;i<size;i++)
   {
      for(int j=0;j<size;j++)
      {
         if(szach[i][j]==0)
            return 0;
      }
   }
   return 1;
}
//licz - variable for counting knights moves//
void konik(int szach[][size], int x, int y, int licz)
{
    szach[x][y]=licz;
    if(licz<size*size){
        for(int i=0;i<=7;i++){ //loop that checks every possible knight move//
            if(szach[x+ruch_x[i]][y+ruch_y[i]]==0&&x+ruch_x[i]>=0&&x+ruch_x[i]<size&&y+ruch_y[i]>=0&&y+ruch_y[i]<size)
// checking if candidat was already visited and if it's not outside of the board//
            {
                konik(szach, x+ruch_x[i], y+ruch_y[i], licz+1);}}}

    if(done(szach)==1) return; //checking if whole board is filled with numbers, if yes then skip zeroing current move//
    szach[x][y]=0;
}

int main()
{
    int i, j, x,y;
    printf("set x\n");
    scanf("%d", &x);
    printf("set y\n");
    scanf("%d", &y);

    int szach[size][size];
    for(i=0;i<size;i++) {  //zeroing array//
            for(j=0;j<size; j++) {
                    szach[i][j]=0; }}
    konik(szach, x, y, 1);

    for(int i=0;i<size;i++) {
            for(int j=0;j<size; j++) {
                    printf("%d\t",szach[j][i]); }
            printf("\n\n");}
    printf("\n");
    return 0;
}
4

3 に答える 3

0

ileの提案は良いようです。グラフ内の次数(位置からの可能な移動数) が最も低い候補 ( 4 つのコーナーの中で最も近い方向に向かうことで概算) を最初に考慮するように 1 つだけ実装した場合、開始位置xの解を見つけるための実行時間は=2とy=4は 10 時間半から 1 分 15 秒に短縮されました。プログラムの変更は次のとおりです。

// arrays of possible knight moves, for example 2nd move is [1,2]
// rearranged so that adjacent moves differ by 45 angular degrees
int ruch_x[]={  2,  1, -1, -2, -2, -1,  1,  2};
int ruch_y[]={  1,  2,  2,  1, -1, -2, -2, -1};


#include <stdlib.h>

//licz - variable for counting knights moves//
void konik(int szach[][size], int x, int y, int licz)
{
    szach[x][y]=licz;
    if (licz<size*size)
    {   static char firstmove[2][2][2] = { 1, 0, 6, 7, 2, 3, 5, 4 };
        int m = firstmove[x<size/2][y<size/2][abs(size-1-x*2)<abs(size-1-y*2)];
        for (int s=0; s<=7; s++) //loop that checks every possible knight move//
        {   static int ply[8] = { 0, -1, 1, -2, 2, -3, 3, -4 };
            int i = m+ply[s];   // firstmove towards corner, then back and forth
            if (i < 0) i += 8;
            else
            if (i > 7) i -= 8;
            // checking if candidate ...
            if (x+ruch_x[i]>=0&&x+ruch_x[i]<size    // not outside of the board
             && y+ruch_y[i]>=0&&y+ruch_y[i]<size
             && szach[x+ruch_x[i]][y+ruch_y[i]]==0  // not already visited
               )
                konik(szach, x+ruch_x[i], y+ruch_y[i], licz+1);
        }
    }

    if (done(szach)==1) return; //checking if whole board is filled with numbers
                                //if yes then skip zeroing current move//
    szach[x][y]=0;
}

ちなみに、元のプログラムの動作は厳密には定義されていませんでした。これは、 がボード配列の外側にないことをszach[x+ruch_x[i]][y+ruch_y[i]]確認する前に確認されたためです。x+ruch_x[i]y+ruch_y[i]

于 2016-09-16T14:15:56.240 に答える