[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)

입력자료는 아래와 같은 구조로 되어있음.
- 즉 행의 갯수 -> 첫번째 행의 정보 -> 두번째 행의 정보 ... 열의 갯수 -> ... -> 마지막 열의 정보가 일렬로 나열되어 있음.

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

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()
  
}

[전체]

	pattern_check <- function(number = number, row = row) {

	row <- row

	lcha <- "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"

	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)

	}

	#########################################################################################################################

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

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

	puzzle_info[is.na(puzzle_info)] <- 0

	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)

	}


	checking = F

	im <- -1

	check_col <- col_df
	check_row <- row_df
	check_puzzle <- puzzle
	ci_check <- 0
	cj_check <- 0

	ss <- 0

	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()

	}

view raw nonogram.R hosted with ❤ by GitHub

[결과 이미지]

참고 문헌

[논문]

없음

[보고서]

없음

[URL]

없음

문의사항

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

sangho.lee.1990@gmail.com

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

saimang0804@gmail.com

저작자표시 동일조건

'프로그래밍 언어 > R' 카테고리의 다른 글

[R] 직달 일사계 (CHP1, MS56, DR02, GWNU) 비교 관측 자료를 이용한 감도정수 보정 및 시계열 가시화 (0)	2020.03.01
[R] 하와이 마우나로아 (Manuna Loa)에서 이산화탄소 (CO2) 농도 자료를 이용한 통계 처리 및 시계열 가시화 (0)	2020.03.01
[R] 파일 관련 기본 명령어 (디렉터리/파일 선택, 생성, 삭제, 복사) 소개 (0)	2020.02.13
[R] 데이터 분석에서 자주 사용하는 "tidyverse" 패키지 소개 (0)	2020.02.13
[R] 파일 읽는 GUI를 제공하는 "ezpickr" 패키지 소개 (2)	2020.02.12

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

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

정보

내용

[특징]

[활용 자료]

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

[사용법]

[사용 OS]

[사용 언어]

소스 코드

[명세]

[전체]

[결과 이미지]

참고 문헌

[논문]

[보고서]

[URL]

문의사항

'프로그래밍 언어 > R' 카테고리의 다른 글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역