노노그램 - 위키백과, 우리 모두의 백과사전 노노그램 위키백과, 우리 모두의 백과사전. ( 네모로직에서 넘어옴 ) 둘러보기로 가기 검색하러 가기 노노그램 예시 노노그램 ( 영어 : Nonogram, 일본어 : [UNK] [UNK] [UNK] 오에가키로짓쿠 [ * ] ) 은 일본의 퍼즐 게임이다. [ 1 ] 각각 적혀있는 숫자를 보면서 숨겨져 있는 숫자를 예상하여 지워나가면서 그림을 그리는 게임이다. NP - 완전 문제이다. 한국에서는 네모네모로직이라고 불린다. 목차 1 기본적인 규칙 1. 1 숫자가 하나인 경우 1. 2 숫자가 여러개인 경우 1. 2. 1'빈칸'에 대해서 1. 2. 2 순서에 대해서 2 풀 때의 정석 2. 1 첫 번째 단계 2. 1. 1 0과 최고값을 먼저 2. 1. 2 더해서 최고값이 되는 것을 풀기 2. 1. 3 좌우에 채울 때에 생기는 공통된 검은 칸을 처리 2. 2 두 번째 단계 2. 2. 1 모든 검은 칸, 모든 빈칸이 확정된 예시의 처리 2. 2. 2 검은 칸의 이웃 칸 처리 2. 2. 3 가장자리의 처리 2. 2. 4 협소한 칸의 처리 2. 2. 5 확실히 검은 칸이 닿는 칸, 닿지 않는
번째 단계 [ 편집 ] 첫 번째 단계에서는 풀기 시작하는 단계로 아무 단서가 없는 상태이기에 단서가 없이도 풀 수 있는 곳부터 풀어간다. 여기서의 작업을 빼먹으면 도중에 막히기에 확실하게 해야한다. 0과 최고값을 먼저 [ 편집 ] 먼저 처음에 할 것은 0과 최고값 ( 여기서는 10 ) 부터 처리하는 것이다. 생각할 필요가 없는 0은 모두 빈칸이며 최고값인 경우에는 모두 검은 칸인 것이 확실하기 때문이다. 10 빈칸인 것이 확정된 칸에는 x 같은 것으로 빈칸이라는 것을 구분시켜둔다. 다만, 너무 크게 표기하면 완성됐을 때의 그림이 보기에 흉해지기에 주의가 필요하다. 0 x x x x x x x x x x 더해서 최고값이 되는 것을 풀기 [ 편집 ] 둘 이상의 숫자가 있는 예시에서 숫자와 숫자 사이에 빈칸이 하나라고 가정하고 계산하면 조금 최고값과 같은 수가 되는 예시는 하나의 가능성 밖에 없기에 숫자와 숫자 사이에 한 칸만 빈칸을 넣고 나머지는 검은 칸으로 칠한다. ( 예시 ) 7 2 는 7과 2 사이에는 빈칸이 한 칸밖에 없다고 가정하면 712 = 10 ( 1은 빈칸 분량, 아래와
g는 위치부터 생각해서 명확히'3'에서 나온 검은 칸이다. 따라서, 이 열의 맨위 Ag는 빈칸인 것이 확정된다. c열'2, 1, 2'에 대해서 Bc, Dc의 검은 칸은 위치부터 생각해서 각각'2 ','1'에서 나온 것을 알 수 있다. 따라서, Dc의 위아래의 이웃칸은 빈칸인게 결정된다 ( # 검은 칸의 이웃 칸 처리를 참조 ). 또, 그에 따라서 맨위의 Ac가 검은 칸인 것도 확정된다 ( # 가장자리나 최고값의 갱신에 대한 처리를 참조 ). f열도 c열과 마친가지로 처리할 수 있다. A열'4'에 있는 두 개의 검은 칸 Ac, Af는 당연히 같은'4'에서 나온 것이다. 따라서, 그 사이의 두 칸은 검은 칸으로 결정되며 # 모든 검은 칸, 모든 빈칸이 확정된 예시의 처리를 할 수 있다. B열'2, 2'은 어느쪽도 확실히 검은 칸이 닿는 칸, 닿지 않는 칸을 처리의 정석으로 양쪽 가장자리의 칸 Ba, Bh을 검은 칸으로 확정한다. G열도 마찬가지이다. C열'2, 2'는 Cc가 빈칸이라고 확정되어 있기 때문에 # 가장자리나 최고
는 아래의 내용에 주의할 필요가 있다. 숫자와 숫자 사이에 들어가지 않은 경우가 있기 때문에 확정된 칸이 적어진다. 각 색이 어떤 열에서 사용되고 있는지를 확인한다. 이것에 의해서 그 색으로 칠할 수 없는 범위가 나뉘며 그곳에서부터 [UNK] 경우가 있다. 문제 만들기 [ 편집 ] 아직 도트 그림을 그려도 반드시 문제로 성립한다고는 할 수 없다. 답이 하나로 좁히지 않는 경우가 있기 때문이다. 컴퓨터 상에서 문제를 만들 수 있는 소프트웨어 등에서는 문제로 성립하는지 아닌지를 자동적으로 판정해주는 기능이 달려있는 것도 있다. 삼각형 칸 [ 편집 ] 칠하는 칸을 정사각형을 비스듬히 자른 삼각형으로 한 규칙도 있다. 이러한 것을 다이아몬드 로직 또는 다이아 로직 등으로 불린다 [ 2 ]. 비고 [ 편집 ] 100x100 칸 등 방대한 칸 수가 되어 오면 칠할 수 있는 칸을 찾는 것이 상당히 힘들어진다. 여기서 첫 번째 단계에서 칠할 수 있는 칸을 계산에 따라서 구할 수 있는 방법이 있다. 먼저, 구하고 싶은 행A의 힌트로 나와있는 수를 모두 합한다 ( 이것은 검은 칸의 계산 ). 다음으로 해A의 힌트 개수에 1을 뺀 값을 위에서 계산된 숫자와 합한다
( 예시2 ) 5 이 경우, 우측 끝부터 검은 칸을 했다해도 반드시 오른쪽부터 다섯 번째 칸에 검은 칸이 닿아버린다. 또, 확정되어 있는 칸부터 좌측으로 다섯 칸을 해도 왼쪽부터 세 번째 칸까지 검은 칸은 닿지 않는 것이 명확해진다. 따라서, 5 x x x 로 확정한다. ( 예시3 ) 3 4 이 경우, 우측의 검은 칸부터 좌측에 최대한 네 칸 분량을 늘려줘도 두 개의 검은 칸은 이어지지 않는다. 또, 그 사이에는 규칙에 따라서 최저 하나의 빈칸이 필요하기에 왼쪽부터 네 번째 칸은 4의 칸으로는 채울 수 없다. 그렇게 되면 4의 좌측이 오른쪽으로 벗어나기 때문에 ( 왼쪽부터 다섯 번째 칸 ), 그 곳부터 오른쪽으로 센 네 번째 칸을 검은 칸으로 확정한다. 3 4 가장자리나 최고값의 갱신에 대한 처리 [ 편집 ] 바깥 측의 빈칸을 연속해서 확정하면 그 분량만 가장자리가 안 쪽으로 밀리는 것으로 가정할 수 있으며 그에 따라서 그 예시의 최고값이 그것만 적어진다고 가정할 수 있다. 거기서 갱신된 가장자리나 최고값을 사용해서 검은 칸과 빈칸을 확정한다. ( 예시1 ) 5 이것은, 첫 번째 단계에서는 확정할 수 없었다. 하지만
예시1 ) 1 2 1 이 경우, 이미 칠해진 검은 칸은'2'에서 와서 연속하고 있는 것은 확실하다. 숫자와 숫자 사이에는 반드시 하나 이상의 빈칸이 있기에, 1 2 1 x x 로 빈칸을 확정한다. ( 예시2 ) 1 2 1 ( 예시1 ) 의 경우와 비슷하지만 이번에는 이미 확정지은 칸은'1'에서 온 것인지'2'에서 온 것인지, 이 시점에서는 밝혀지지 않기에 새롭게 확정지을 수 있는 칸은 없다. 가장자리의 처리 [ 편집 ] 가장 바깥 측이 확정되면 바깥 측의 숫자가 나나태는 검은 칸은 확정이다. ( 예시1 ) 3 2 처럼 가장 왼쪽이 확정짓고 있을 경우에는 자동적으로'3'이 나타내고 있는 것은 3 2 x 로 확정된다. 앞의 항에서 말한'검은 칸의 이웃칸을 처리'에 따라서 왼쪽부터 네 번째에 x를 붙이는 것도 잊지 않았으면 한다. ( 예시2 ) 3 2 f로, 가장 오른쪽이 확정되었을 경우에는 자동적으로'2'가 나타나고 있는 것은, 3 2 x 로 확정한다. 오른쪽에서 세 번째 x는'검은 칸의 이웃칸을 처리'에 따른 것이다. 협소한 칸의 처리 [ 편집 ] 연속되어서
는 확정된 빈칸의 좌우 어느 한방향으로 모든 검은 칸이 들어가는 것은 있을 수 없기에 좌우 각각 하나씩 들어가게 되며, 3 3 x 로 확정할 수 있다. 세 번째 단계 [ 편집 ] 문제 중에는 위의 기술을 구사해도 풀 수 없는 경우도 있다. 소거법 [ 편집 ] 위의 방법만으로 막힌 경우. 주의의 장소를 임시로 모두 칠하는 장소로 가정한다. 게다가 그것을 단서로 문제를 풀어간 경우에 후에 모순점이 생겨버린다면 그곳은 실은 칠해서는 안되는 장소였다는 것을 알게된다. 또한, 모순범이 발생하기까지의 전개가 긴 만큼, 예측하기도 힘들어지며 고전을 강요당할 수 있다. 그러므로, 이 방법은 기술 중에도 고도의 훈련이 요구된다. 게임 " 피크로스 ", " 피크로스 NP " 에서는'[UNK]'[UNK] " NP " 에서는'[UNK]'),'x ','[UNK]'가 있지만,'[UNK] [UNK] [UNK] [UNK]'( " NP " 에서는'[UNK] [UNK] [UNK] [UNK]'[UNK] 마크라는 조작성은 마리오의 슈퍼 피크로스 내에 등장했다. 풀이의 흐름 [ 편집 ] 왼쪽의 8x8 칸의 문제를 예로 퍼즐의 전체 흐름을 나타낸다. 편의상 가로열을 대문자 A ~ H, 세로 열을 소문자 a ~
처리 2. 2. 3 가장자리의 처리 2. 2. 4 협소한 칸의 처리 2. 2. 5 확실히 검은 칸이 닿는 칸, 닿지 않는 칸을 처리 2. 2. 6 가장자리나 최고값의 갱신에 대한 처리 2. 2. 7 나눠진 칸의 처리 2. 3 세 번째 단계 2. 3. 1 소거법 3 풀이의 흐름 4 다색화 5 문제 만들기 6 삼각형 칸 7 비고 8 예시 9 각주 기본적인 규칙 [ 편집 ] 숫자가 하나인 경우 [ 편집 ] 1개의 숫자는 연속해서 검게 칠하는 칸 ( 이하'검은 칸') 의 수를 나타내고 있다. 단, 위치까지 나타내고 있는 것은 아니다. ( 예시 3 에 대해서는 다음의 3개의 가능성을 생각할 수 있다. 3 3 3 숫자가 여러개인 경우 [ 편집 ]'빈칸'에 대해서 [ 편집 ] 숫자가 둘 이상인 경우에 각각이 검은 칸의 수를 나타내며 사이에는 반드시 검게 칠하지 않은 칸 ( 이하'빈칸') ( 이하'빈칸') 이 최소 하나가 들어간다. 단, 하얀 칸의 위치와, 검은 칸 사이에 얼마나 들어갈 지는 나타내고 있지 않다. ( 예시1 ) 1 1 에 대해서는 여섯 가지의 방법을 생각할 수 있다. 1 1 1 1 1 1
칸이 확정된 예시의 처리 [ 편집 ] 숫자의 합계와 이미 확정지은 검은 칸의 수가 일치할 경우에 아직 확정 못 지은 칸을 모두 빈칸으로 확정시킨다. 아직 확정 못 지은 칸과 검은 칸으로 확정지은 칸의 합계가 숫자의 합계에 일치한 경우에는 아직 확정 못 지은 칸은 검은 칸으로 확정시킨다. ( 예시1 ) 1 이 경우, 숫자'1'에 대해서 이미 하나의 검은 칸이 확정되어 있기에 이 이외의 검은 칸은 없다. 따라서, 1 x x x x x x x x x 로 빈칸이 확정된다. ( 예시2 ) 1 1 1 1 x x x x x x 이 경우, 이 예시에는 합계 4칸의 검은 칸이 있는 것이기 때문에 아직 확정 못 지은 칸이 검은 칸이 아니면 검은 칸의 수가 부족해진다. 따라서, 1 1 1 1 x x x x x x 로 검은 칸이 된다. 검은 칸의 이웃 칸 처리 [ 편집 ] 숫자와 숫자 사이에는 빈칸이 한 칸 이상이 들어가기에 검은 칸이 연속인 것을 알 수 있으면 그 이웃 칸은 빈칸으로 황정한다. ( 예시1 ) 1 2 1 이 경우, 이미 칠해진 검은 칸은'2'에서 와서 연속하고 있는 것은 확실하다. 숫자와 숫자 사이에는
확정한다. 오른쪽에서 세 번째 x는'검은 칸의 이웃칸을 처리'에 따른 것이다. 협소한 칸의 처리 [ 편집 ] 연속되어서 나타나는 숫자보다 협소한 칸의 경우에는 그 부분은 빈칸이라고 확정한다. ( 예시1 ) 3 x 는, 우측부터 검은 칸을 취하면 두 칸만 나타나기에 우측 끝에는 검은 칸은 넣지 않는다. 따라서 3 x x x 확정한다. ( 예시2 ) 3 x x 는, x와 x의 사이에는 두 칸만 나타날 수 있기에 거기에는 검은칸은 넣지 않는다. 따라서 3 x x x x 로 확정한다. 확실히 검은 칸이 닿는 칸, 닿지 않는 칸을 처리 [ 편집 ] 이미 검은 칸의 확정되어 있으며 숫자와 비교해서 닿지 않는 칸이 있는 경우에는 그 곳은 빈칸으로 확정한다. 또, 몇몇 가장자리에 붙여도 검은 칸이 초과하는 부분에 대해서는 검은 칸으로 확정한다. ( 예시1 ) 2 이 경우에 가능성은 아래 두 가지밖에 없다. 2 2 따라서, 다음처럼 확정한다. 2 x x x x x x x ( 예시2 ) 5 이 경우, 우측 끝부터 검은 칸을 했다해도 반드시 오른쪽부터 다섯 번째 칸에 검은 칸이 닿아버린다. 또
노노그램(영어: Nonogram, 일본어: お絵かきロジック 오에가키로짓쿠[*])은 일본의 퍼즐 게임이다. 각각 적혀있는 숫자를 보면서 숨겨져 있는 숫자를 예상하여 지워나가면서 그림을 그리는 게임이다. NP-완전 문제이다. 한국에서는 네모네모로직이라고 불린다.