분류 전체보기 (165)
과학 꼼지락 (35)
수학 꼼지락 (41)
 시 꼼지락 (21)
언어 꼼지락 (6)
잡다 꼼지락 (61)
비밀 꼼지락 (0)
BLOG main image





수학 꼼지락
2007. 11. 18. 14:57

모든 네모네모로직(Nonogram)문제의 해는 언제나 단 한 개만 존재하는 것일까?
궁금해 죽겠는데,,, 누구 아시는 분 있나요?

중학교3학년 때, 담임선생님께서 주셨던 퍼즐중에 답이 두 개 있었던 것으로 기억하는데 제대로 된 기억인지 확신이 가지 않는다. 어디 증명이 있나 찾아보고 있는데, 찾기 힘들다... NP문제로 치환할 수 있으니까, 분명히 증명 가능할 것도 같은데..

다만 찾은 것이 있다면, 위키페디아영문판에서 본 내용이다. "모든 nonogram을 풀 수 있는 알고리즘은 아직 없다. 사람이 짱이다" 뭐 이정도?;;

'수학 꼼지락' 카테고리의 다른 글

차량 내비게이션  (10) 2007.12.07
네모네모로직(Nonogram)  (5) 2007.11.18
적분에 대한 새로운 시각  (11) 2007.10.14
무한등비급수  (2) 2007.10.13
snowall | 2007.11.18 16:05 신고 | 절대주소 | 수정/삭제 | 댓글
스도쿠는 답이 두개인 이상인 부분과 한개인 부분의 임계점이 있는 것 같아요. 뭐, 어차피 스도쿠 문제의 갯수는 한정되어 있으니 구별하려고 마음만 먹으면 구별할 수 있겠죠 -_-;
꼼지락 | 2007.11.19 13:17 신고 | 절대주소 | 수정/삭제
한정되 있는 그 갯수가 엄청나게 많을 것이라는 게 구별에 어려움을 주겠죠^^:;
꼼지락 | 2007.11.19 13:38 신고 | 절대주소 | 수정/삭제
아, 그리고 스도쿠와 노노그램은 다른 퍼즐을 가르키는 말 인것 같아요;;;
snowall | 2007.11.19 16:08 신고 | 절대주소 | 수정/삭제 | 댓글
네, 전혀 다른 게임이죠 -_-;
그냥 물어본거예요...;;;;;
꼼지락 | 2008.09.13 19:18 신고 | 절대주소 | 수정/삭제 | 댓글
http://ggomjirak.tistory.com/223
에 답을 달았습니다.
이름   
비밀번호 
홈페이지 
비밀글