教えて!gooグレードポイントがdポイントに!

目的は解を列挙するプログラムを作ることです

#include <stdio.h>
#include <stdlib.h>
#include "iList.h"
#include "bList.h"

#define NUMBER_OF_BLOCKS 9
#define NUMBER_OF_CHOICES 9
#define NUMBER_OF_DIRECTIONS 4

//赤R,緑G,青B,黄Y, 橙W,白W
char *BlockShape[NUMBER_OF_BLOCKS][NUMBER_OF_DIRECTIONS] = {
{"RBGO", "BGOR", "GORB", "ORBG"},
{"RYGW", "YGWR", "GWRY", "WRYG"},
{"RYOG", "YOGR", "OGRY", "GRYO"},
{"ROYW", "OYWR", "YWRO", "WROY"},
{"RWBG", "WBGR", "BGRW", "GRWB"},
{"RWBO", "WBOR", "BORW", "ORWB"},
{"BYOW", "YOWB", "OWBY", "WBYO"},
{"BGOY", "GOYB", "OYBG", "YBGO"},
{"BGWY", "GWYB", "WYBG", "YBGW"}
};

int Number_of_Solutions;

void printBoard(char board[6][6]) {
for (int i = 0; i < 6; i++) {
if (i%2==0) printf("+--+--+--+\n");
for (int j = 0; j < 6; j++) {
if (j%2==0) printf("|");
printf("%c", board[i][j]);
}
printf("|\n");
}
printf("+--+--+--+\n");
}

void printSolution(bLIST *x) {
char board[6][6];

for (int i = 0; i < B_size(x); i++) {
int row = i/3;
int col = i%3;
bSHAPE p = B_retrieve(x, i);
char block = BlockShape[p.BlockID][p.Direction];
board[2row ][2col ] = block[0];
board[2row ][2col+1] = block[1];
board[2row+1][2col+1] = block[2];
board[2row+1][2*col ] = block[3];
}
printBoard(board);
}

int consistent_H(char *block, char *newblock) {
//newblockを追加する際,その左方にあるblockについて,水平方向に関する制約条件をチェック
//制約条件を満たしていれば1,満たしていなければ0を返す.
}

int consistent_V(char *block, char *newblock) {
//newblockを追加する際,その上方にあるblockについて,垂直方向に関する制約条件をチェック
//制約条件を満たしていれば1,満たしていなければ0を返す.
}

int appendable(bLIST *x, bSHAPE e) {
char *newblock = BlockShape[e.BlockID][e.Direction];
int m = B_size(x);
int row = m/3;
int col = m%3;

for (int i = 3*row; i < m; i++) {// 横方向(同じ行のブロックとの比較)
bSHAPE p = B_retrieve(x, i);
char *block = BlockShape[p.BlockID][p.Direction];
if (consistent_H(block, newblock) == 0) return 0;
}
for (int i = col; i < m; i += 3) {// 縦方向(同じ列のブロックとの比較)
bSHAPE p = B_retrieve(x, i);
char *block = BlockShape[p.BlockID][p.Direction];
if (consistent_V(block, newblock)== 0) return 0;
}
return 1;
}

void perm(bLIST x, iLIST rest, int r) {//restからr個選んでxの末尾に付加
if (r == 0) {
printf("#%d\n", ++Number_of_Solutions);
printSolution(&x);
} else {
for (int i = 0; i < size(&rest); i++) {
swap(&rest, 0, i);
int blockID = popFront(&rest);
for (int d = 0; d < NUMBER_OF_DIRECTIONS; d++) {
bSHAPE e = {blockID, d};
if (appendable(&x, e)) {
B_pushBack(&x, e);
perm(x, rest, r-1); // 再帰呼び出し
B_popBack(&x);
}
}
pushFront(&rest, blockID);
}
}
}

int main(void) {
Number_of_Solutions = 0;
int n = NUMBER_OF_BLOCKS;
int r = NUMBER_OF_CHOICES;
bLIST x;
iLIST rest;
B_makeEmpty(&x);
makeEmpty(&rest);
for (int e = 0; e < n; e++) pushBack(&rest, e);
perm(x, rest, r);
return 0;
}
ここからbList.h

#include <stdio.h>

typedef struct {
int BlockID; // 0, 1, ..., 9
int Direction; // 0, 1
} bSHAPE;

#define MAXLENGTH (100)
typedef struct {
int L;
int R;
bSHAPE elem[MAXLENGTH];//要素を格納する配列
} bLIST;

void B_makeEmpty(bLIST *x); // リストを初期化する
int B_isEmpty(bLIST *x); // リストが空であれば1を,そうでなければ0を返す
int B_size(bLIST *x); // リストの要素数を返す
int B_isFull(bLIST *x); // リストが一杯であれば1を,そうでなければ0を返す
void B_pushFront(bLIST *x, bSHAPE e); // リストの先頭に要素eを追加する
void B_pushBack(bLIST *x, bSHAPE e); // リストの末尾に要素eを追加する
bSHAPE B_popFront(bLIST *x); // リストの先頭から要素を取り出す
bSHAPE B_popBack(bLIST *x); // リストの末尾から要素を取り出す
bSHAPE B_retrieve(bLIST *x, int i); // リストのi番目の要素を返す
void B_swap(bLIST *x, int i, int j);//
void B_printList(bLIST *x);
ここからiLisit.h

#include <stdio.h>

#define MAXLENGTH (100)
typedef struct {
int L;
int R;
int elem[MAXLENGTH];//要素を格納する配列
} iLIST;
void makeEmpty(iLIST *x); // リストを初期化する
int isEmpty(iLIST *x); // リストが空であれば1を,そうでなければ0を返す
int size(iLIST *x); // リストの要素数を返す
int isFull(iLIST *x); // リストが一杯であれば1を,そうでなければ0を返す
void pushFront(iLIST *x, int e); // リストの先頭に要素eを追加する
void pushBack(iLIST *x, int e); // リストの末尾に要素eを追加する
int popFront(iLIST *x); // リストの先頭から要素を取り出す
int popBack(iLIST *x); // リストの末尾から要素を取り出す
int retrieve(iLIST *x, int i); // リストのi番目の要素を返す
void swap(iLIST *x, int i, int j);// リストのi番目とj番目の要素を入れ替える
void printList(iLIST *x);

質問者からの補足コメント

  • 画像のことが目的です。

    「このコードを実行すると無限に結果が出てく」の補足画像1
      補足日時:2021/11/22 02:00
教えて!goo グレード

A 回答 (4件)

いずれにしても, これだけの情報では


こっちの手元で動かしようがない
んだ.

ここに書かれていない何かが悪さをしているという可能性も否定できないし.
    • good
    • 0

> 画像のことが目的です。



あ、そ。
でもエラー原因に関して何も書かれてないからどうも手出し出来ないけどね。

ただ、その問題で言える事は、本質的には

「数独を解くプログラム」

とほぼ同じだ、って事だろうねぇ。
だから制約条件(終了条件だけど)の立て方が多分違ってて、無限ループに陥ってるんじゃないのかしらん。

いずれにせよ、数独を解くプログラムを参考にしてみたら?

【C言語】数独(ナンプレ)をプログラミングで解く【バックトラック法】:
https://daeudaeu.com/c_sudoku/
    • good
    • 0

う〜ん。


コンパイルしてみたんだけど、エラーが多すぎてお話にならんですね。

例えば

board[2row ][2col ] = block[0]; // <- 2rowなんて命名法はCでは許されないし、blockの設計とblock[0]が帳尻が合わん

とかね。

そもそも、

> 目的は解を列挙するプログラムを作ることです

とか貴方は書いてるけど、その「解」が何をもって解とするか、は貴方のアタマの中にしか存在せんのですよ。
他の誰も何を解とすれば正しいのか知らん、っちゅうわけだ。

まぁ、

> 無限に結果が出てくるのです

と言えば無限ループに陥ってるんだろうから、恐らくpermutation(順列)の作り方を間違えてるか、あるいは単に終了条件を間違えてるか、のどっちかでしょう。
多分ね。
    • good
    • 0

「実行する」前に, エラーにならないようにすべきだと思う.



あと, (うるさいだろうけど) 警告をなるべき出すようにした方がいい.
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


このカテゴリの人気Q&Aランキング