[R] nonogram (네모네모로직) 해결 알고리즘 및 가시화

 정보

• 업무명     : nonogram (네모네모로직) 해결 알고리즘 및 가시화

• 작성자     : 박진만

• 작성일     : 2020-02-23

• 설   명      :

• 수정이력 :

 

 내용

[특징]

• R 프로그램을 이용하여 nonogram 을 해결하고 이를 표출하는 알고리즘

 

[활용 자료]

• 위키백과 nonogram 예시 입력자료

 

[자료 처리 방안 및 활용 분석 기법]

• 반드시 칠해지는 행  / 반드시 칠해지지 않는 행 / 아직 알 수 없는 행의 구분

• 1차적으로 가능한 모든 경우를 구한 후 상기 조건에 맞지 않는 경우를 제거하는 소거법을 이용하여 해결

 

[사용법]

• 입력 자료를 동일 디렉터리 위치

• 소스 코드를 실행 

• 결과를 확인

 

[사용 OS]

• Windows10

 

[사용 언어]

• R v3.6.2

• R Studio v1.2.5033

 

 소스 코드

[명세]

• 라이브러리 로드

library(gtools)
library(partitions)
library(stringr)
library(dplyr)
library(tidyr)
library(data.table)

 

• 입력자료 (퍼즐 정보 읽기)

puzzle_info <- read.csv("./puzzle.csv",header = F)

 

• 입력자료는 아래와 같은 구조로 되어있음.

  • 즉 행의 갯수 -> 첫번째 행의 정보 -> 두번째 행의 정보 ... 열의 갯수 -> ...  -> 마지막 열의 정보가 일렬로 나열되어 있음.

20				
3				
5				
3	1			
2	1			
3	3	4		
2	2	7		
6	1	1		
4	2	2		
1	1			
3	1			
6				
2	7			
6	3	1		
1	2	2	1	1
4	1	1	3	
4	2	2		
3	3	1		
3	3			
3				
2	1			
20				
2				
1	2			
2	3			
2	3			
3	1	1		
2	1	1		
1	1	1	2	2
1	1	3	1	3
2	6	4		
3	3	9	1	
5	3	2		
3	1	2	2	
2	1	7		
3	3	2		
2	4			
2	1	2		
2	2	1		
2	2			
1				
1				

 

• 퍼즐 정보를 기반으로 한 비어있는 매트릭스 생성

row_info <- puzzle_info[1,1]
col_info <- puzzle_info[1+row_info+1,1]

row_number <- c()

# 0 = unknown / -1 = not fill / 1 = fill
puzzle <- matrix(nrow = row_info, ncol = col_info,0)

 

• 매트릭스 출력 예시

 

• 최초 숫자정보를 바탕으로 가능한 패턴 계산 (행, 열 모두)

row_df <- data.frame()

for (i in 1:row_info) {
  
  row_number <- as.numeric(puzzle_info[1+i,])
  row_number <- row_number[row_number != 0]
  
  row_df_part <- pattern_check(row = col_info,number = row_number)
  row_df_part[["row_num"]] <- i
  
  row_df <- rbind(row_df,row_df_part)
  
}

col_df <- data.frame()
for (i in 1:col_info) {
  
  col_number <- as.numeric(puzzle_info[i+row_info+2,])
  col_number <- col_number[col_number != 0]
  col_df_part <- pattern_check(row = row_info,number = col_number)
  col_df_part[["col_num"]] <- i
  
  col_df <- rbind(col_df,col_df_part)
  
}

 

• 아래의 출력 예시에 보이는 것 처럼 1과 0의 조합을 이용하여 각 행별로 가능한 가짓수 및 조합을 계산하였음

 

• 상기 pattern_check 함수는 사용자 정의 함수로서 패턴을 찾아내 데이터 형태로 만드는 작업을 하고 있음.

• 해당 함수의 코드는 아래와 같음

pattern_check <- function(number = number, row = row) {
  
  row <- row
  
  number <- number
  
  fill_num <- c()
  cc <- 0
  
  for (i in number) {
    
    cc <- cc + 1
    fill_num[cc] <- ""
    
    for (j in 1:i) {
      
      fill_num[cc] <- paste0(fill_num[cc],"1")
      
      if(j == i) {
        fill_num[cc] <- paste0(fill_num[cc],"0")
      }
      
    }
    
    
  }
  
  fill_num[cc] <- str_replace(fill_num[cc], pattern="0", replacement="")
  
  row_df <- as.data.frame(t(fill_num),stringsAsFactors = F)
  
  
  n <- sum(nchar(fill_num))
  target_0 <- row - n
  bang_count <- length(fill_num) + 1
  
  combin <- compositions(target_0,bang_count)
  combin <- as.matrix(t(combin))
  combin <- data.frame(combin)
  
  
  ## set col names ##
  for (i in seq(1,length(fill_num)+1,1)) {
    
    colnames(combin)[i] <- paste0("B",i)
    combin[[paste0("B",i)]] <- str_sub(lcha,1,combin[[paste0("B",i)]])
    
    #MAKE NA
    combin[[paste0("B",i)]] <- ifelse(combin[[paste0("B",i)]] == "",NA,combin[[paste0("B",i)]])
    
    if(i <=  length(fill_num)) {
      colnames(row_df)[i] <- paste0("R",i)
    }
    
  }
  ## set col names ##
  
  
  for (i in seq(1,length(fill_num)+1,1)) {
    
    if(i == 1){
      df <- cbind(combin[paste0("B",i)],row_df[paste0("R",i)])
      next
    }
    
    if(i <= length(fill_num)) {
      df <- cbind(df,combin[paste0("B",i)],row_df[paste0("R",i)])
    } else {
      df <- cbind(df,combin[paste0("B",i)])
    }
    
  }
  
  
  for (i in seq(1,length(number)+1,1)) {
    df[[paste0("B",i)]] <- as.character(df[[paste0("B",i)]])
  }
  
  
  df_L1 <- df %>%
    tidyr::unite("result", na.rm = T, sep="")
  
  
  df_L2 <- as.data.frame(str_split(df_L1$result,pattern = "",simplify = TRUE),stringsAsFactors = F)
  
  
  if(number[1] == 0) {
    df_L2 <- as.data.frame(matrix(nrow = 1, ncol = row, 0))
  }
  

  return(df_L2)
  
}

combin_check <- function(df = df, row = row) {
  
  
  row_percent <- c()
  
  for (i in 1:row) {
    
    calc <- sum(as.integer(df[[paste0("V",i)]]))/dim(df)[1]
    
    row_percent <- append(row_percent,calc)
    
  }
  
  return(row_percent)
  
}

 

• 소거법을 이용한 가짓수 제거 및 최종 출력 결과 도출

  • 이후 부터는 퍼즐을 채우면서 가능한 가짓수를 줄여나가면서 최종적으로 결과를 도출하는 부분임

  • 각 행과 열의 패턴 체크 -> 가짓수 제거 -> 그림 표출 의 반복 작업임.

  • 더이상 채울 칸이 없는 경우 프로그램이 종료됨

  • 패턴 체크를 통해 더이상 칸이 지워지지 않는 경우 임의의 칸에 색칠 후 모순이 발생할 때 까지 퍼즐을 채워나가는 알고리즘 수행

while(T) {
  
  im <- im + 1
  b_row <- dim(row_df)[1]
  b_col <- dim(col_df)[1]
  
  
  ################## elimination  ##################
  for (i in 1:row_info) {
    for (j in 1:col_info) {
      
      
      if(puzzle[i,j] == 1) {
        
        ### row ###
        row_df_part <- row_df %>%
          dplyr::filter(row_num == i)
        
        row_df <- row_df %>%
          dplyr::filter(row_num != i)
        
        row_df_part <- row_df_part[row_df_part[[paste0("V",j)]] == "1",]
        
        row_df <- rbind(row_df,row_df_part)
        ### row ###
        
        ### col ###
        col_df_part <- col_df %>%
          dplyr::filter(col_num == j)
        
        col_df <- col_df %>%
          dplyr::filter(col_num != j)
        
        col_df_part <- col_df_part[col_df_part[[paste0("V",i)]] == "1",]
        
        col_df <- rbind(col_df,col_df_part)
        ### col ###
        
        
      } else if (puzzle[i,j] == -1) {
        
        ### row ###
        row_df_part <- row_df %>%
          dplyr::filter(row_num == i)
        
        row_df <- row_df %>%
          dplyr::filter(row_num != i)
        
        row_df_part <- row_df_part[row_df_part[[paste0("V",j)]] == "0",]
        
        row_df <- rbind(row_df,row_df_part)
        ### row ###
        
        ### col ###
        col_df_part <- col_df %>%
          dplyr::filter(col_num == j)
        
        col_df <- col_df %>%
          dplyr::filter(col_num != j)
        
        col_df_part <- col_df_part[col_df_part[[paste0("V",i)]] == "0",]
        
        col_df <- rbind(col_df,col_df_part)
        ### col ###
        
      }
      
    }
  }
  ################## elimination  ##################
  
  a_row <- dim(row_df)[1]
  a_col <- dim(col_df)[1]
  
  ###################### row ###########################
  for (i in 1:row_info) {
    
    false_flag <- F
    
    row_df_part <- row_df %>%
      dplyr::filter(row_num == i)
    
    
    ## 모순 체크 ##
    if(dim(row_df_part)[1] == 0) {
      false_flag <- T
      break
    }
    ## 모순 체크 ##
    
    percent <- combin_check(df = row_df_part,row = col_info)
    #print(percent)
    
    for (j in 1:length(percent)) {
      
      if(percent[j] == 1){
        puzzle[i,j] <- 1
        
        #row_df_part <- row_df_part[row_df_part[[paste0("V",j)]] == "1",]
        
      } else if (percent[j] == 0) {
        puzzle[i,j] <- -1
        #print(puzzle[i,j])
        
      } else {
        puzzle[i,j] <- 0
        
      }
      
      
    }
    
    
  }
  ###################### row ###########################
  
  
  ###################### col ###########################
  for (i in 1:col_info) {
    
    false_flag <- F
    
    col_df_part <- col_df %>%
      dplyr::filter(col_num == i)
    
    ## 모순 체크 ##
    if(dim(col_df_part)[1] == 0) {
      false_flag <- T
      break
    }
    ## 모순 체크 ##
    
    percent <- combin_check(df = col_df_part,row = row_info)
    #print(percent)
    for (j in 1:length(percent)) {
      
      if(percent[j] == 1){
        
        puzzle[j,i] <- 1
        
      } else if (percent[j] == 0) {
        
        puzzle[j,i] <- -1
        
      } else {
        
        if(puzzle[j,i] == -1 | puzzle[j,i] == 1) {
          puzzle[j,i] <- puzzle[j,i]
        } else {
          puzzle[j,i] <- 0
        }
        
      }
      
    }
    
    #print(percent)
    #print(max(percent))
  }

  
  row_dis <- b_row - a_row
  col_dis <- b_col - a_col
  
  if(a_row == row_info & a_col == col_info) {
    break
  } else if (row_dis == 0 & col_dis == 0 & checking == F & im != 0) {
    
    check_col <- col_df
    check_row <- row_df
    check_puzzle <- puzzle
    
    count <- 0 
    checking <- T
    for (ci in 1:row_info) {
      for (cj in 1:col_info) {
        
        
        if(check_puzzle[ci,cj] == 0 & count == 0) {
          
          print(paste0("fix",ci," ",cj))
          count <- count + 1
          puzzle[ci,cj] = 1
          ci_check <- ci
          cj_check <- cj
        }
        
      }
    }
    

  } else if (row_dis == 0 & col_dis == 0 ) {
    
    
    puzzle1 <- as.numeric(puzzle)
    puzzle1 <- puzzle1[puzzle1 == 0]
    len <- length(puzzle1)
    
    if(len >= col_info) {
    
    col_df <- check_col
    row_df <- check_row
    puzzle <- check_puzzle
    puzzle[ci_check,cj_check] <- -1
    checking <- F
    
      next 
    
    } else {
      break
    }
    
 
    
  }
  
  
  if (false_flag == T) {
    
    col_df <- check_col
    row_df <- check_row
    puzzle <- check_puzzle
    puzzle[ci_check,cj_check] <- -1
    checking <- F
  }
  ################## elimination 2 ##################
  
  ss <- ss + 1
  jpeg(paste0('result_',ss,'.jpg'),width = 800,height = 800)
  plot(puzzle,col=c('gray', 'white','black'), key=NULL, axis.col=NULL, axis.row=NULL, xlab='', ylab='')
  dev.off()
  
}

 

[전체]

 

 

[결과 이미지]

참고 문헌

[논문]

• 없음

[보고서]

• 없음

[URL]

• 없음

 

 문의사항

[기상학/프로그래밍 언어]

• sangho.lee.1990@gmail.com

[해양학/천문학/빅데이터]

• saimang0804@gmail.com