1

私は8 クイーン パズルの解決策を開発しようとしています。8 x 8 のチェス盤に 8 クイーンを配置して、2 人が互いに攻撃できないようにする必要があります。「#」のボードを印刷することはできますが、最初のスポットにクイーンを配置し、水平、垂直、斜めのすべてのスポットを「x」にする方法がわかりません。

これが私がこれまでに持っているものです：

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define ROW 8
#define COL 8

// Make the chessboard

int main(int argc, char * argv[])
{
    char board[ROW][COL];
    int i, j;

    for(i = 0; i < ROW; i++)
    {
        for(j = 0; j < COL; j++)
        {
            board[i][j] = '#';
            printf(" %c", board[i][j]);
        }
        printf("\n");
    }
    return 0;
}

// Place queen on first '#'

int placeQueen(char board[ROW][COL])
{
    char queenSpace;
    int i, j;

    for(i = 0; i < ROW; i++)
    {
        for(j = 0; j < COL; j++)
        {
            queenSpace = 'Q';
            board[i][j] = queenSpace;
            printf(" %c", board[1][1]);
        }
        printf("\n");
    }
    return 0;
}

現在の出力は左側にあります。右側に示すようにする必要があります。

# # # # # # # #            Q x x x x x x x
# # # # # # # #            x x # # # # # #
# # # # # # # #            x # x # # # # #
# # # # # # # #            x # # x # # # #
# # # # # # # #            x # # # x # # #
# # # # # # # #            x # # # # x # #
# # # # # # # #            x # # # # # x #
# # # # # # # #            x # # # # # # x

これが私のアルゴリズムです：

  1. すべて「#」で 8x8 配列を作成します。
  2. 最初に利用可能な「#」にクイーンを配置します。
  3. 横、縦、斜めのすべての正方形をクイーンの位置から「x」に変更します。
  4. 「#」である最初のスポットに別のクイーンを配置します。
  5. 水平、垂直、および斜めのすべての正方形を新しいクイーンの位置から「x」に変更します。
  6. 使用可能な「#」がなくなるまで、手順 4 ～ 5 を繰り返します。
  7. > 7 クイーンの場合、配列を出力して再度実行します。
  8. クイーンが 7 個以下の場合は、もう一度実行しますが、2 番目のクイーンの位置に「#」を付けて、手順 4 ～ 5 を繰り返します。
  9. > 7 クイーンの場合、配列を出力して再度実行します。
  10. クイーンが 7 個以下の場合は、2 番目のクイーンの行に「#」がなくなるまでステップ 8 を繰り返します。
  11. 2 番目のクイーンの行に「#」がない場合は、その行からメモリを解放します。
  12. 手順 8 を繰り返しますが、3 番目のクイーンの位置を除きます。
  13. 手順 8 ～ 11 を繰り返しますが、4 番目のクイーンの位置を指定します。等。
  14. これ以上解決策がない場合は、手順 2 ～ 13 を繰り返しますが、今回は最初のクイーンがあった場所に「#」をマークします。
  15. 最初の行に「#」がなくなるまで、手順 14 を繰り返します。

私は 2 次元配列を使用した作業やプログラムを行ったことがないので、ヘルプやサンプル コードをいただければ幸いです。

4

1 に答える 1

1

いくつかのヒント。主なデータ型を抽象化します。

#define ROW 8
#define COL 8
typedef char t_board[ROW][COL];
#define ItRows(Var) for (int Var = 0; Var < ROW; Var++)
#define ItCols(Var) for (int Var = 0; Var < COL; Var++)
#define EMPTY  '+'
#define QUEEN  'Q'
#define ATTACK '-'

#define bool int
#define true 1
#define false 0

次に、データ型で実行される操作の宣言を簡素化し、単一のステップのロジックに集中できます。

void init(t_board board) {
   ItRows(r)
       ItCols(c)
           board[r][c] = EMPTY;
}
void show(t_board board) {
   ItRows(r) {
       ItCols(c)
           printf(" %c", board[r][c]);
       printf("\n");
   }
}
void assign(t_board target, const t_board source) {
   ItRows(r)
       ItCols(c)
           target[r][c] = source[r][c];
}
bool reserve(t_board board, int row, int col, char cell) {
    if (board[row][col] == QUEEN)
        return false;
    board[row][col] = cell;
    return true;
}
bool place_queen(t_board board, int row, int col) {
   ItRows(r)
       if (r != row && !reserve(board, r, col, ATTACK))
           return false;
    ItCols(c)
       if (c != col && !reserve(board, row, c, ATTACK))
           return false;

    #define AttackDiag(R, C) \
       for (int r = row + R, c = col + C; r >= 0 && c >= 0 && r < ROW && c < COL; r += R, c += C) \
          if (!reserve(board, r, c, ATTACK)) \
              return false;
    AttackDiag(+1, +1)
    AttackDiag(+1, -1)
    AttackDiag(-1, +1)
    AttackDiag(-1, -1)

    return reserve(board, row, col, QUEEN);
}
int main_queens(int argc, char **argv) {
    t_board b;
    init(b);
    assert(place_queen(b, 3, 2));
    show(b);
    return 0;
}
于 2012-07-26T00:18:36.630 に答える