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

// 전역 변수 선언
int g_n;  // n x n 격자 크기
int **g_grid;  // n x n 격자
int *g_up, *g_down, *g_left, *g_right;  // 시야값

// 동적 메모리 할당 함수
void memory_util(void)
{
    // 동적 메모리 할당 및 초기화
    g_grid = (int **)malloc(g_n * sizeof(int *));
    int i = 0;
    while (i < g_n)
    {
        g_grid[i] = (int *)malloc(g_n * sizeof(int));
        int j = 0;
        while (j < g_n)
        {
            g_grid[i][j] = 0;
            j++;
        }
        i++;
    }
}

// 동적 메모리 해제 함수
void memory_util_release(void)
{
    int i = 0;
    while (i < g_n)
    {
        free(g_grid[i]);
        i++;
    }
    free(g_grid);
}

// 특정 숫자가 현재 위치에 유효한지 확인하는 함수
int is_valid(int row, int col, int num)
{
    int i = 0;
    while (i < g_n)
    {
        if (g_grid[row][i] == num || g_grid[i][col] == num)
        {
            return 0;  // 동일한 행 또는 열에 같은 숫자가 있으면 유효하지 않음
        }
        i++;
    }
    return 1;
}

// 현재 상태가 시야값을 만족하는지 확인하는 함수
int check_views(void)
{
    int i = 0;
    while (i < g_n)
    {
        // 각 방향별로 보이는 건물 수를 계산하고 시야값과 비교
        int max = 0, count = 0;
        int j = 0;

        // 위에서 아래로
        max = 0;
        count = 0;
        j = 0;
        while (j < g_n)
        {
            if (g_grid[j][i] > max)
            {
                max = g_grid[j][i];
                count++;
            }
            j++;
        }
        if (g_up[i] && count != g_up[i])
            return 0;

        // 아래에서 위로
        max = 0;
        count = 0;
        j = g_n - 1;
        while (j >= 0)
        {
            if (g_grid[j][i] > max)
            {
                max = g_grid[j][i];
                count++;
            }
            j--;
        }
        if (g_down[i] && count != g_down[i])
            return 0;

        // 왼쪽에서 오른쪽으로
        max = 0;
        count = 0;
        j = 0;
        while (j < g_n)
        {
            if (g_grid[i][j] > max)
            {
                max = g_grid[i][j];
                count++;
            }
            j++;
        }
        if (g_left[i] && count != g_left[i])
            return 0;

        // 오른쪽에서 왼쪽으로
        max = 0;
        count = 0;
        j = g_n - 1;
        while (j >= 0)
        {
            if (g_grid[i][j] > max)
            {
                max = g_grid[i][j];
                count++;
            }
            j--;
        }
        if (g_right[i] && count != g_right[i])
            return 0;

        i++;
    }
    return 1;
}

// 백트래킹 함수
int solve_sky_scraper(int row, int col)
{
    if (row == g_n) // 모든 행이 채워졌다면 성공, 격자 밖의 숫자로 검토
    {
        return check_views();
    }

    if (col == g_n) // 현재 행을 다 채웠으면 다음 행으로 이동
    {
        return solve_sky_scraper(row + 1, 0);
    }

    int num = 1;
    while (num <= g_n)
    {
        if (is_valid(row, col, num))
        {
            g_grid[row][col] = num;
            if (solve_sky_scraper(row, col + 1))
            {
                return 1; // 해결책을 찾으면 성공
            }
            g_grid[row][col] = 0; // 백트래킹
        }
        num++;
    }
    return 0; // 실패
}

int main(void)
{
    // 스카이 스크래퍼 격자 수
    g_n = 4; // 4x4

    // 동적 메모리 할당
    memory_util();

    // 격자 밖의 요소들 배치
    // col up, col down, row left, row right
    int up_values[] = {1,2,2,2};
    int down_values[] = {4,1,2,3};
    int left_values[] = {1,2,2,2};
    int right_values[] = {4,1,2,3};

    g_up = up_values;
    g_down = down_values;
    g_left = left_values;
    g_right = right_values;

    // sky scraper > 백트래킹 함수, check view > 격자 밖의 숫자로 검토
    if (solve_sky_scraper(0, 0))
    {
        int i = 0;
        while (i < g_n)
        {
            int j = 0;
            while (j < g_n)
            {
                printf("%d ", g_grid[i][j]);
                j++;
            }
            printf("\n");
            i++;
        }
    }
    else
    {
        printf("No solution found\n");
    }

    // 메모리 해제
    memory_util_release();

    return (0);
}