-2

私は自分でCコースを持っています。コードを実行しても何も起こらず (何も出力されず)、問題がわかりません。そして、チェック機能が不器用であることがわかりました。どうすれば改善でき、スリムでシンプルになりますか? これが私のコードです。

#include <stdio.h>

#define ON     1
#define OFF    0
#define SIZE   8

void initial(int (*table)[SIZE]);
void setqueen(int (*table)[SIZE], const int row);
int check(const int (*table)[SIZE], const int row, const int col);
void prtable(const int (*table)[SIZE]);

int main(void)
{
        int table[SIZE][SIZE];
        int row = 0;

        initial(table);

        setqueen(table, row);

        return 0;
}

void initial(int (*table)[SIZE])
{
        int row, col;

        for (row = 0; row < SIZE; row++)
                for (col = 0; col < SIZE; col++)
                        table[row][col] = OFF;
}
/*
place a queen(set value = 1) in the first column of the first row and
check there is no conflict. if there is a conflict, count and move to
next column. if there is conflict in every column(count = 8), return.
if there is no conflict, call it recursively. when it place all queens,
print the table.
*/
void setqueen(int (*table)[SIZE], const int row)
{
        int c = 0;
        int count = 0;

        for ( ; c < SIZE; c++) {
                table[row][c] = ON;
                if (check(table, row, c) == ON) {
                        table[row][c] = OFF;
                        count++;
                        continue;
                }
                if (count == SIZE)
                        return;
                if (row != SIZE - 1)
                        setqueen(table, row + 1);
                else
                        prtable(table);
        }
}

void prtable(const int (*table)[SIZE])
{
        int row, col;

        for (row = 0; row < SIZE; row++) {
                for (col = 0; col < SIZE; col++)
                        printf("%2d", table[row][col]);
                putchar('\n');
        }
        putchar('\n');
}

int check(const int (*table)[SIZE], const int row, const int col)
{
        int r = 0;
        int c = 0;

        for (r = 0; r < SIZE; r++)
                if (r != row && table[r][col] == ON)
                        return ON;
        for (c = 0; c < SIZE; c++)
                if (c != col && table[row][c] == ON)
                        return ON;
        for (r = row + 1, c = col + 1;
             (r >= 0 && r < SIZE) || (c >= 0 && c < SIZE);
             r++, c++)
                if (table[r][c] == ON)
                        return ON;
        for (r = row + 1, c = col - 1;
             (r >= 0 && r < SIZE) || (c >= 0 && c < SIZE);
             r++, c--)
                if (table[r][c] == ON)
                        return ON;
        for (r = row - 1, c = col + 1;
             (r >= 0 && r < SIZE) || (c >= 0 && c < SIZE);
             r--, c++)
                if (table[r][c] == ON)
                        return ON;
        for (r = row - 1, c = col - 1;
             (r >= 0 && r < SIZE) || (c >= 0 && c < SIZE);
             r--, c--)
                if (table[r][c] == ON)
                        return ON;

        return OFF;
}
4

2 に答える 2

1

期待どおりに再帰しません。
setqueenすべての可能性を試す呼び出しですが、それが失敗した場合は、ループsetqueen内の同じ行にクイーンを配置しようとしますが、これは失敗します。の冒頭で 呼び出して、アルゴリズムが何をしているかを確認すると、次のように表示されます。for(c)
prtablesetqueen

 1 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0
 0 0 0 0 1 0 0 0
 0 1 0 0 0 0 0 0
 0 0 0 1 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0

次に、アルゴリズムは列 5 にクイーンを配置しようとしますが、失敗しますが、以前に配置されたクイーンを移動しようとしません。また、再帰呼び出しが失敗した場合は
setqueen、クイーンを削除して次へ移動する必要があります (したがって、値を返す必要があります)。 それとは別に、それは同じことだと私には見えます.cを前ではなくforループで初期化し（より読みやすく）、各forループチェックのチェックにコメントを追加できます（列、行、... )、およびチェックの戻り値に ON と OFF を使用しないようにします (それが何を意味するかは明確ではありません)。table[row][c] = OFF;setqueen

countc

于 2014-06-30T08:57:42.793 に答える
-1

ボード上にクイーンが配置されていても、関数が再帰的に呼び出されるたびにカウントが0に設定されるため、関数内で行うvoid setqueen(int (*table)[SIZE], const int row)必要があります。static int count=0

サポートについては、以下のコードを参照してください

#include<stdio.h>
#include<stdlib.h>
#define N 8
#define true 1
#define false 0
void printsol(int sol[][N])
{
int i,j;
for(i=0;i<N;i++)
{
    for(j=0;j<N;j++)
    {
        printf("%d ",sol[i][j]);
    }
    printf("\n");
}
}
int issafe(int sol[][N],int x,int y)
{
int i,j;

//Check Row
for(i=x,j=y-1;j>=0;j--)
{
    if(sol[i][j]==1)
        return false;
}

//Check Upper left diagonal
for(i=x-1,j=y-1;i>=0 && j>=0;i--,j--)
{
    if(sol[i][j]==1)
        return false;
}

//Check Lower Left Diagonal
for(i=x+1,j=y-1;i<N && j>=0;i++,j--)
{
    if(sol[i][j]==1)
        return false;
}

return true;
}
int solve(int sol[][N],int x,int y)
{
int i,j=y;
if(y==N)
{
    printsol(sol);
    return 1;
}
for(i=0;i<N;i++)
{
    //printf("LOL");
    if(issafe(sol,i,y)==true)
    {

        sol[i][y]=1;
        if(solve(sol,0,y+1)==true)
        {
            return true;
        }
        else
            sol[i][y]=0;
    }
}
return false;
}
int main()
{
int sol[N][N];
int i,j;
for(i=0;i<N;i++)
    for(j=0;j<N;j++)
        sol[i][j]=0;

solve(sol,0,0);
}
于 2014-06-30T08:48:22.613 に答える