[C언어] 스레드 갯수 27에서 12개로 줄이기

/**
 * 멀티스레드 스도쿠 솔루션 검증기 by Sarmad Hashmi
 *
 * 이 프로그램은 스도쿠 퍼즐 솔루션을 정의한 후 27개의 스레드를 사용하여 퍼즐 솔루션이 유효한지 여부를 결정한다. 
 * 각 3x3 하위 섹션에 9개, 9개 열에 9개, 9개 행에 9개. 각 스레드는
 * 글로벌 배열의 인덱스를 1로 업데이트하여 담당했던 퍼즐의 해당 영역이 유효함을 표시한다.
 * 그런 다음 프로그램은 모든 스레드가 실행을 완료할 때까지 기다린 후
 * 유효한 배열의 모든 항목이 1로 설정되었는지 확인하십시오.
 * 맞다면, 해결책(풀이)은 유효하다. 그렇지 않으면 해결책(풀이)이 유효하지 않다.
 * 
 */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#define num_threads 27

/* 
	작업자 스레드가 담당했던 스도쿠 퍼즐의 해당 영역이 유효한 경우,
	작업자 스레드를 1로 업데이트할 수 있는 배열을 초기화한다.
*/
int valid[num_threads] = {0};

//스레드에 전달할 데이터를 저장하는 구조체 
typedef struct {
	int row;
	int column;		
} parameters;

// 풀이할 스도쿠 퍼즐
int sudoku[9][9] = {
	{6, 2, 4, 5, 3, 9, 1, 8, 7},
	{5, 1, 9, 7, 2, 8, 6, 3, 4},
	{8, 3, 7, 6, 1, 4, 2, 9, 5},
	{1, 4, 3, 8, 6, 5, 7, 2, 9},
	{9, 5, 8, 2, 4, 7, 3, 6, 1},
	{7, 6, 2, 3, 9, 1, 4, 5, 8},
	{3, 7, 1, 9, 5, 6, 8, 4, 2},
	{4, 9, 6, 1, 8, 2, 5, 7, 3},
	{2, 8, 5, 4, 7, 3, 9, 1, 6}
};

//숫자 1~9가 열에 한 번만 표시되는지 여부를 결정하는 방법
void *isColumnValid(void* param) {
	// 매개변수(파라메터)가 올바른 열(col) 하위섹션(subsection)을 나타내는지 확인
	parameters *params = (parameters*) param;
	int row = params->row;
	int col = params->column;		
	if (row != 0 || col > 8) {
		fprintf(stderr, "Invalid row or column for col subsection! row=%d, col=%d\n", row, col);
		pthread_exit(NULL);
	}

	// 숫자 1-9가 열에 한 번만 표시되는지 확인
	int validityArray[9] = {0};
	int i;	
	for (i = 0; i < 9; i++) {
		int num = sudoku[i][col];
		if (num < 1 || num > 9 || validityArray[num - 1] == 1) {
			pthread_exit(NULL);
		} else {
			validityArray[num - 1] = 1;		
		}
	}
	// 이 지점에 도달한 경우 열 하위 섹션(subsection)이 유효함. 
	valid[18 + col] = 1;
	pthread_exit(NULL);
}

// 숫자 1~9가 연속적으로 한 번만 표시되는지 여부를 결정하는 방법
void *isRowValid(void* param) {
	// 매개 변수가 올바른 "roe(행)" 아래 항목을 나타내는지 확인
	parameters *params = (parameters*) param;
	int row = params->row;
	int col = params->column;		
	if (col != 0 || row > 8) {
		fprintf(stderr, "Invalid row or column for row subsection! row=%d, col=%d\n", row, col);
		pthread_exit(NULL);
	}

	// 숫자 1-9가 roe(행)에 한 번만 표시되는지 확인
	int validityArray[9] = {0};
	int i;
	for (i = 0; i < 9; i++) {
		// 해당 번호의 지수를 1로 설정하고, 번호를 다시 맞추면,
		// 유효한 배열이 업데이트되지 않고 스레드가 종료됨
		int num = sudoku[row][i];
		if (num < 1 || num > 9 || validityArray[num - 1] == 1) {
			pthread_exit(NULL);
		} else {
			validityArray[num - 1] = 1;		
		}
	}
	// 이 지점에 도달하면 "row" 하위 섹션(subsection)이 유효하다.
	valid[9 + row] = 1;
	pthread_exit(NULL);
}

// 숫자 1~9가 3x3 하위 섹션(subsection)에 한 번만 표시되는지 여부를 결정하는 방법
void *is3x3Valid(void* param) {
	// 매개변수(파라메터)가 유효한 3x3 하위섹션(subsection)을 나타내는지 확인
	parameters *params = (parameters*) param;
	int row = params->row;
	int col = params->column;		
	if (row > 6 || row % 3 != 0 || col > 6 || col % 3 != 0) {
		fprintf(stderr, "하위 섹션(subsection)의 행 또는 열이 잘못되었습니다 ! row=%d, col=%d\n", row, col);
		pthread_exit(NULL);
	}
	int validityArray[9] = {0};
	int i, j;
	for (i = row; i < row + 3; i++) {
		for (j = col; j < col + 3; j++) {
			int num = sudoku[i][j];
			if (num < 1 || num > 9 || validityArray[num - 1] == 1) {
				pthread_exit(NULL);
			} else {
				validityArray[num - 1] = 1;		
			}
		}
	}
	// 이 지점에 도달하면 3x3 하위 섹션(subsection)이 유효하다.
	valid[row + col/3] = 1; // 하위섹션(subsection)을 유효한 배열의 처음 8개 인덱스에 있는 인덱스에 매핑
	pthread_exit(NULL);
}

int main() {	
	pthread_t threads[num_threads];
	
	int threadIndex = 0;	
	int i,j;
	// 9개의 3x3 하위 섹션(subsection)에 9개의 스레드, 9개의 열에 9개의 스레드, 9개의 행에 9개의 스레드 만들기.
	// 이로써 총 27개의 스레드가 나오게 됨.
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {						
			if (i%3 == 0 && j%3 == 0) {
				parameters *data = (parameters *) malloc(sizeof(parameters));	
				data->row = i;		
				data->column = j;
				pthread_create(&threads[threadIndex++], NULL, is3x3Valid, data); // 3x3 하위 섹션(subsection) 스레드
			}
			if (i == 0) {
				parameters *columnData = (parameters *) malloc(sizeof(parameters));	
				columnData->row = i;		
				columnData->column = j;
				pthread_create(&threads[threadIndex++], NULL, isColumnValid, columnData);	// 열 스레드 
			}
			if (j == 0) {
				parameters *rowData = (parameters *) malloc(sizeof(parameters));	
				rowData->row = i;		
				rowData->column = j;
				pthread_create(&threads[threadIndex++], NULL, isRowValid, rowData); // 행 스레 드  
			}
		}
	}

	for (i = 0; i < num_threads; i++) {
		pthread_join(threads[i], NULL);			// 모든 스레드가 완료될 때까지 대기
	}

	// 유효한 배열의 항목 중 하나가 0이면 스도쿠 솔루션이 잘못됨
	for (i = 0; i < num_threads; i++) {
		if (valid[i] == 0) {
			printf("스도쿠 해결책 무효!\n");
			return EXIT_SUCCESS;
		}
	}
	printf("스도쿠 해결책 유효\n");
	return EXIT_SUCCESS;
}

안녕하세요. 가입한지 얼마안됐는데 질문드려서 죄송합니다.

우선 위 프로그램은 27개의 스레드를 사용하여 해당 스도쿠 퍼즐이 올바른 퍼즐인지 아닌지를 검증하는 프로그램입니다.

현재 보시면 아시겠지만 이 프로그램의 스레드 갯수가
총 27개 (소형격자 3x3스레드 9개 x 열 스레드 9개 x 행 스레드 9개)입니다.

대략 스도쿠 프로그램의 규칙은 이렇습니다.

9x9 격자판을 사용하고, 3x3 소형 격자판이 9개 존재합니다.

소형 격자판에는 1~9까지 숫자가 하나씩 들어갑니다.

9x9 격자판의 가로와 세로에는 1~9까지 숫자가 하나씩 들어갑니다.

여기서 아래 조건에 맞게 바꾸고 싶은데

스레드 수 12개:

  • 각 소형 격자판을 검증하는 스레드 9개,

  • 가로를 검사하는 스레드 1개,

  • 세로를 검사하는 스레드 1개,

  • 마지막으로 이러한 결과를 종합하는 메인 스레드 1개

으로 바꾸고 싶습니다.

그래서 바꿔볼려고 하는데 3x3은 이미 9개를 사용하여 그대로 두면되지만

  1. for문안에 있는 열 스레드 함수(columnData)와 행 스레드 부분(columnData)을 각각 9개가 아닌 1개로 바꿀려면
    열과 행의 스레드 if (i == 0)를 for문에 따로 빼서 쓰면 될까요?
    ex)
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {						
			if (i%3 == 0 && j%3 == 0) {
				parameters *data = (parameters *) malloc(sizeof(parameters));	
				data->row = i;		
				data->column = j;
				pthread_create(&threads[threadIndex++], NULL, is3x3Valid, data); // 3x3 하위 섹션(subsection) 스레드
			}
		}
	}
	for (i = 0; i < 1; i++) {
		for (j = 0; j < 1; j++) {
			if (i == 0) {
				parameters *columnData = (parameters *) malloc(sizeof(parameters));	
				columnData->row = i;		
				columnData->column = j;
				pthread_create(&threads[threadIndex++], NULL, isColumnValid, columnData);	// 열 스레드 
			}
			if (j == 0) {
				parameters *rowData = (parameters *) malloc(sizeof(parameters));	
				rowData->row = i;		
				rowData->column = j;
				pthread_create(&threads[threadIndex++], NULL, isRowValid, rowData); // 행 스레 드  
			}
		}
	}
  1. 우선 열과 행 스레드를 각각 1개로 만들면 총11개(9+1+1)로 1개남는데 이러한 결과를 종합하는 메인 스레드는 어떻게 만드나요? 혹시 data X columnData X rowData 의 함수 하나 만들면 되나요?

질문은 대략 여기까지입니다.

그렇게 해서 다 되면 맨위에 #define num_threads 27를 12로 바꿔서 정상적으로 솔루션이 유효하는게 목적입니다.

스도쿠프로그램이랑 스레드를 사용해서 검증하는게 인터넷에 많이 알려져 있다보니 왠만하면 안물어보고 최대한 혼자서 해볼려고 하지만
몇주 동안 여기 저기 옮기고 for문안에 있는걸 뺴보기도 하고 했지만 이 프로그램이 검증만하지 스레드 숫자를 확인하는 방법이 없다보니 따로만들까하다가 시간부족해서 포기하고
코딩 초보라 코딩에 입문한지 얼마 안된상태에서 프로젝트 제출 기간이 얼마 남지 않다보니 결국 질문을 올리게 되었습니다.

또한 원본이 github에 올려진 영문이다 보니 번역이 많이 어색합니다. 이점 양해바랍니다.

이 프로그램은 by Sarmad Hashmi 가 만들었습니다.

소스코드 공개에 감사드립니다.

안녕하세요.

3x3은 그냥 두면된다고 하셨고
가로 세로 쭉 체크하는 함수를 for문 이용해서 만드셔서 그 함수를 스레드로 실행해서 결과를 반환하게 하면 될거 같네요.

1 Like

우선 답변을 달아주셔서 진심으로 감사드립니다.

답변해 주신대로라면

가로 세로 쭉 체크하는 함수void isColumnValid(void param)와 void isRowValid(void param)를
for을 이용하고

스레드는 제 질문 본문에 올라온 ex)처럼 별도로 for (i = 0; i < 1; i++) { for (j = 0; j < 1; j++) { } }
꺼내서 각각 1로 만들면 되나요?

그리고 “함수를 스레드로 실행해서 결과를 반환” => 결과를 종합하는 메인 스레드 1개 인가요?

제 질문의 의도가 부실한것같아 죄송합니다. 같은 질문 내용이지만 좀 더 직설적으로 설명하자면

  1. 가로(행) 스레드 9개와 세로(열) 스레드 9개를 각각 1개씩 바꾸기

  2. 결과(3x3, 행, 열)를 종합하는 메인스레드 1개를 어떻게 만드는지

코딩 초보라 모르는게 많습니다. 이 점 정말 죄송합니다.

그러니까 이제… 좀 더 설명을 드리자면

main: // 메인함수 시작.

sudoku = input_sudoku() // 스도쿠 입력

res_row = new Thread(check_row, sudoku) // row를 check 하는 함수를 새 스레드로 호출
res_col = new Thread(check_col, sudoku) // col을 check 하는 함수를 새 스레드로 호출
res_cell[3][3]

for i is 0 to 2
for j is 0 to 2
    res_cell[i][j] = new Thread(check_cell, i*3, j*3)

if (res_row && res_col && res_cell)
    print("sudoku is correct!")

대강 메인함수는 이렇게 될거 같고…

check_row(sudoku_board): // row check함수.

for i is 0 to 8
    if (sudoku_board.row(i) is not 0-9) 
        return false
return true

이건 check_col도 비슷하게 하면 되겠죠?

1 Like

답변 정말 감사드립니다.
이제 갈피를 잡는것같습니다.
올려주신 코드를 참고하여 만들어보겠습니다. 다시한번 감사인사드립니다.

하시다가 어려우시면, 먼저 스레드 사용하지 않고 구현해보세요~ ㅎㅎㅎ
그 다음에 스레드로 변경해도 괜찮으니까용