予想のつかない突然のプログラムの終了

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
snr
記事: 4
登録日時: 2ヶ月前

予想のつかない突然のプログラムの終了

#1

投稿記事 by snr » 2ヶ月前

現在、バックトラック法による数独の解を計算するプログラムを作成しています。

backtrackという関数を用いて、行っているのですが
この関数がうまく動作しないためその原因を探るために、printfでいろんな記号を表示したところ自分の予想もしない部分で終了しています。

どうか解析よろしくお願いいたします。
ボードが表示される際に、
<>+
までしか表示されないというのが不思議です。
VisualStudioCodeでコマンドラインでコンパイル実行しています

コード:

void backtrack(int board[SIZE][SIZE] , int *board_is , int n){
	if( (*board_is) == 0){
		printf("no Solve\n");
		return ;
	}
	int row , col;
	int p;

	if(n == SIZE*SIZE){
		//solve Found
		printf("solved\n");
		printBoard(board , board_is);
		return ;
	}else{
		printf("*********   n = %2d\t*********\n" , n);
		printBoard(board , board_is);
		printf("<");
	}
printf(">");
	row = p / SIZE;
	col = p % SIZE;
printf("+");
printf("board[%d][%d] = %d\n" , row , col , board[row][col]);
	if(board[row][col] != 0){
		printf("&");
		backtrack(board , board_is , n+1);
	}else{
		//zen tan saku
printf("@");
		for(p = 0; p < SIZE; p++){
printf("#");
			if(	check_row(board,row,(p+1))==1 && 
				check_col(board,col,(p+1))==1 && 
				check_3x3(board,row,col,(p+1))==1){
printf("_");
				board[row][col] = (p+1);
				backtrack(board , board_is , n+1);
				board[row][col] = 0;
			}
		}

	}
}

void solve(int board[SIZE][SIZE] , int *board_is){
	backtrack(board , board_is , 0);
}

int main(){
	int board[SIZE][SIZE];
	int board_is = 1;
	//board_is	0:no solve
	//			1:

	initBoardZero(board);
	initInputBoard(board , &board_is);
	printBoard(board , &board_is);
	solve( board , &board_is );

	return 0;
}

フィーロ
記事: 2
登録日時: 8ヶ月前

Re: 予想のつかない突然のプログラムの終了

#2

投稿記事 by フィーロ » 2ヶ月前

こんにちは

記載されているコードをコンパイルしたところ、コンパイルが通りませんでした。(当然ですが)
問題無ければ全文記載した方が回答が付くと思います。

また、この辺りがわかりにくい(orわからない)ので、記載した方が良いと思います。
[1] 質問文
 [1.1] 自分が今行いたい事は何か
 [1.2] どのように取り組んだか(プログラムコードがある場合記載)
 [1.3] どのようなエラーやトラブルで困っているか(エラーメッセージが解る場合は記載)
 [1.4] 今何がわからないのか、知りたいのか

[2] 環境  
 [2.1] OS : Windows, Linux等々
 [2.2] コンパイラ名 : VC++ 2008EE, Borand C++, gcc等々

[3] その他
 ・どの程度C言語を理解しているか
 ・ライブラリを使っている場合は何を使っているか
ちなみに、このpには何が入っているんですか?

コード:

	row = p / SIZE;
	col = p % SIZE;

かずま

Re: 予想のつかない突然のプログラムの終了

#3

投稿記事 by かずま » 2ヶ月前

snr さんが書きました:
2ヶ月前

コード:

	row = p / SIZE;
	col = p % SIZE;
n が p になっています。

コード:

	row = n / SIZE;
	col = n % SIZE;
未定義関数を適当に定義してみました。

コード:

#include <stdio.h>   // scanf, printf, putchar
#include <stdlib.h>  // exit
#include <string.h>  // memset

#define SIZE 9

void printBoard(int board[SIZE][SIZE], int *board_is) {
	for (int i = 0; i < SIZE; i++, putchar('\n'))
		for (int j = 0; j < SIZE; j++)
			printf(" %d", board[i][j]);
}

int check_row(int board[SIZE][SIZE], int row, int n) {
	for (int i = 0; i < SIZE; i++)
		if (board[row][i] == n) return 0;
	return 1;
}

int check_col(int board[SIZE][SIZE], int col, int n) {
	for (int i = 0; i < SIZE; i++)
		if (board[i][col] == n) return 0;
	return 1;
}

int check_3x3(int board[SIZE][SIZE], int row, int col, int n) {
	int r = row - row % 3;
	int c = col - col % 3;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			if (board[r+i][c+j] == n) return 0;
	return 1;
}

void initBoardZero(int board[SIZE][SIZE])
{
	memset(board, 0, sizeof(int) * SIZE * SIZE);
}

void initInputBoard(int board[SIZE][SIZE], int *board_is)
{
	char c;
	for (int i = 0; i < SIZE; i++)
		for (int j = 0; j < SIZE; j++) {
			if (scanf(" %c", &c) != 1) exit(1);
			if (c >= '0' && c <= '9') board[i][j] = c - '0';
			else board[i][j] = 0;
		}
}

void backtrack(int board[SIZE][SIZE] , int *board_is , int n){
	if( (*board_is) == 0){
		printf("no Solve\n");
		return ;
	}
	int row , col;
	int p;

	if(n == SIZE*SIZE){
		//solve Found
		printf("solved\n");
		printBoard(board , board_is);
		return ;
	}else{
/*
		printf("*********   n = %2d\t*********\n" , n);
		printBoard(board , board_is);
		printf("<");
*/
	}
//printf(">");
	row = n / SIZE;
	col = n % SIZE;
//printf("+");
//printf("board[%d][%d] = %d\n" , row , col , board[row][col]);
	if(board[row][col] != 0){
//		printf("&");
		backtrack(board , board_is , n+1);
	}else{
		//zen tan saku
//printf("@");
		for(p = 0; p < SIZE; p++){
//printf("#");
			if(	check_row(board,row,(p+1))==1 && 
				check_col(board,col,(p+1))==1 && 
				check_3x3(board,row,col,(p+1))==1){
//printf("_");
				board[row][col] = (p+1);
				backtrack(board , board_is , n+1);
				board[row][col] = 0;
			}
		}

	}
}

void solve(int board[SIZE][SIZE] , int *board_is){
	backtrack(board , board_is , 0);
}

int main(){
	int board[SIZE][SIZE];
	int board_is = 1;
	//board_is	0:no solve
	//			1:

	initBoardZero(board);
	initInputBoard(board , &board_is);
	printBoard(board , &board_is);
	solve( board , &board_is );

	return 0;
}
入力

コード:

..36....7
.7..4..2.
.8....9..
..6..9...
89..1..63
...2..8..
..9....5.
.2..9..4.
7....56..
実行結果

コード:

 0 0 3 6 0 0 0 0 7
 0 7 0 0 4 0 0 2 0
 0 8 0 0 0 0 9 0 0
 0 0 6 0 0 9 0 0 0
 8 9 0 0 1 0 0 6 3
 0 0 0 2 0 0 8 0 0
 0 0 9 0 0 0 0 5 0
 0 2 0 0 9 0 0 4 0
 7 0 0 0 0 5 6 0 0
solved
 9 5 3 6 8 2 4 1 7
 6 7 1 9 4 3 5 2 8
 4 8 2 7 5 1 9 3 6
 2 4 6 8 3 9 1 7 5
 8 9 7 5 1 4 2 6 3
 3 1 5 2 6 7 8 9 4
 1 6 9 4 7 8 3 5 2
 5 2 8 3 9 6 7 4 1
 7 3 4 1 2 5 6 8 9
もっと簡潔にすると

コード:

#include <stdio.h>   // scanf, printf, putchar
#include <stdlib.h>  // exit

#define N 2   // 解の最大表示個数

int b[9][9], k;

int ok(int r, int c, int n)
{
	for (int i = 0; i < 9; i++)
		if (b[r][i] == n || b[i][c] == n) return 0;
	r -= r % 3, c -= c % 3;
	for (int p = r + 3; r < p; r++)
		if (b[r][c] == n || b[r][c+1] == n || b[r][c+2] == n) return 0;
	return 1;
}

void step(int r, int c)
{
	if (c == 9) {
		c = 0;
		if (++r == 9) {
			for (r = 0; r < 9; r++, putchar('\n'))
				for (c = 0; c < 9; c++) printf(" %d", b[r][c]);
			putchar('\n');
			if (++k < N) return;
			exit(0);
		}
	}
	if (b[r][c]) step(r, c+1);
	else
		for (int n = 1; n <= 9; n++)
			if (ok(r, c, n)) b[r][c] = n, step(r, c+1), b[r][c] = 0;
}

int main(void)
{
	for (int r = 0; r < 9; r++)
		for (int c = 0; c < 9; c++) {
			char n;
			if (scanf(" %c", &n) != 1) return 1;
			b[r][c] = (n>='0' && n<='9') ? n - '0' : 0;
		}
	step(0, 0);
}

かずま

Re: 予想のつかない突然のプログラムの終了

#4

投稿記事 by かずま » 2ヶ月前

かずま さんが書きました:
2ヶ月前

コード:

			if (c >= '0' && c <= '9') board[i][j] = c - '0';

コード:

			b[r][c] = (n>='0' && n<='9') ? n - '0' : 0;
結果は同じですが、訂正します。

コード:

			if (c >= '1' && c <= '9') board[i][j] = c - '0';

コード:

			b[r][c] = (n>='1' && n<='9') ? n - '0' : 0;

返信

“C言語何でも質問掲示板” へ戻る