[재귀] 회문, 재귀적 나누기, 재귀함수를 이용한 스도쿠 풀이

1.

코드:

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

int isPalindrome(char A[], int n, int i) {
	if (n < 2)
		return 1;
	else if (A[i] != A[n - 1])
		return 0;
	else
		isPalindrome(A, n - 1, ++i);
}

int main() {
	char A[100];
	gets(A);

	printf("%d", isPalindrome(A, strlen(A), 0));
}

 

2.

코드:

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

void divide(int a, int b, int cnt) {
	if (a < b)
		printf("%d %d", cnt, a);
	else {
		cnt++;
		divide(a - b, b, cnt);
	}
}

int main() {
	int a, b;
	scanf("%d %d", &a, &b);

	divide(a, b, 0);
}

 

3.

 

코드:

#include <stdio.h>

void backtracking(int n);
int check(int x, int y); // 빈칸에 들어갈 숫자가 스도쿠 조건에 만족하는지 검사 함수

int sutoku[9][9] = { 0 };
int blank[2][81] = { 0 }; // 빈 칸의 인덱스 저장 (blank[0][n] >>row, blank[1][n] >> column)
int cnt = 0; // 빈칸의 총 갯수 저장
int end = 0; // 스도쿠 완성 >> 재귀함수 탈출시 사용

int main() {
int b = 0;

for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
scanf("%d", &sutoku[i][j]);

if (sutoku[i][j] == 0) {
blank[0][b] = i;
blank[1][b] = j;
b++;
cnt++;
}
}
}

for (int i = 1; i <= 9; i++) {
sutoku[blank[0][0]][blank[1][0]] = i;
backtracking(0);
if (end == 1)
break;
}

for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
printf("%d ", sutoku[i][j]);
if (j / 8 == 1)
printf("\n");
}
}

return 0;
}

void backtracking(int n) {
int x = blank[0][n], y = blank[1][n];

if (check(x, y) == 0)
return;

if (n == cnt - 1) {
end = 1;
return;
}

for (int i = 1; i <= 9; i++) {
sutoku[blank[0][n + 1]][blank[1][n + 1]] = i;
backtracking(n + 1);
if (end == 1)
return;
}
sutoku[blank[0][n + 1]][blank[1][n + 1]] = 0;
}


int check(int x, int y) {
for (int i = 0; i < 9; i++) { // 빈칸이 있는 행 검사
if (sutoku[x][y] == sutoku[x][i]) {
if (y == i) // 현재 빈칸과 같은 곳을 가리킬 때는 return 아님 >> 같은 위치에 존재할 때는 그냥 넘어가기
continue;
return 0;
}
}

for (int i = 0; i < 9; i++) { //빈 간이 속한 열 검사
if (sutoku[x][y] == sutoku[i][y]) {
if (x == i) //위와 같은 의미
continue;
return 0;
}
}

for (int k = x / 3 * 3; k < x / 3 * 3 + 3; k++) {
for (int l = y / 3 * 3; l < y / 3 * 3 + 3; l++) {
if (x == k && y == l)
continue;
if (sutoku[x][y] == sutoku[k][l])
return 0;
}
}
return 1;
}