통합검색
· 마을서비스란?  · 포럼마을  · 일반마을  · 테마마을  · 마을랭킹  · 활동왕
· 덱스퍼트란?  · TECBOX   · PRSBOX   · 이용안내  
· DEXT제품군  · 솔루션베이  · S/W & ESD 컴포넌트
· 프로그램베이
· LiveSeminar  · LiveConference
Visual C++ 포럼마을 입니다.
  마을등급 Visual C++   이 마을은 포럼마을 입니다이 마을은 자유가입제 마을 입니다 마을소개 페이지로 이동 전입신청
마을촌장촌장 나성훈 주민 34000 since 2006-12-29
우리마을 공지사항
질문&답변
강좌&팁
자유게시판
자료실
앨범
개인게시판
마을 게시판
등록된 마을 게시판이
없습니다.
랑데브 게시판
칼럼 게시판
개발자 고충상담
Dev Talk
자유토론방
벼룩시장
재나미 우스개
구인/프로젝트 정보
사람인 채용 게시판
  고객지원 게시판
마이 데브피아
 나의 e-Money 내역
 활동왕 My Page
 스크랩한 게시글보기
 쪽지관리
 주소록관리

 질문&답변
 풀리지 않는 8퍼즐의 이상현상(?)  | VC++ 일반 2006-11-01 오전 2:05:20
 ilovestarc  ilovestarc님께 메시지 보내기ilovestarc님을 내 주소록에 추가합니다.ilovestarc님의 개인게시판 가기 번호: 614868  / 읽음:1,990

 8퍼즐 아시죠?? 9개의 3*3 블록의 섞여있는 블록을 맞추는 퍼즐이요.

 

8퍼즐을 작게나마 만들기는 무사히 마쳤는데...

 

퍼즐이 풀리지 않는 경우도 있을까요??

 

직접 몇번 풀려고 시도 했었는데.. 풀리지 않는 경우가 있더라고요..

 

마지막 3번째줄 7,8이 바뀐 상태로 마무리가 되는데 이것좀 풀어주실분 계신가요..

 

아니면 어떤 상황에서 퍼즐이 풀리지 않는지 알고 계신분 있나요??

 

 

 

네이버, 구글, 데브 다 검색해도 8퍼즐의 알고리즘은 찾기 힘들더라고요.

 

풀리지 않는 경우에 대한 알고리즘이 있나 싶어서요..

이 글에 답변 등록하기
 [답변]....... 2006-11-01 오전 4:31:46
 wkqlgmltk  wkqlgmltk님께 메시지 보내기wkqlgmltk님을 내 주소록에 추가합니다.wkqlgmltk님의 개인게시판 가기 번호: 614873  

 퍼즐을 처음 섞을때 무조건 랜덤하게 섞으면 안됩니다.

그렇게 섞으면 아무리 풀어도 풀리지 않는 경우가 있습니다.

완성된 형태의 모양에서 빈칸으로 움직여 가면서 정해진 횟수만큼

이동하면서 섞어야 합니다. 그래야 최소한 섞은 순서의 역순이

되는 한가지 이상의 푸는 경우가 존재할 수 있습니다.

 

이 글에 답변 등록하기
         [답변]그렇군요.. 감사합니다. 2006-11-01 오전 5:36:21
 ilovestarc  ilovestarc님께 메시지 보내기ilovestarc님을 내 주소록에 추가합니다.ilovestarc님의 개인게시판 가기 번호: 614874  

 그걸 미처 생각지 못하고 있었네요.

 

섞이는 이동방향으로만 역순으로 다시 풀수 있다는 사실을 까마득히 잊어 먹고 있었네요 ^^

 

섞을수 있는 방향이 무조건 랜덤순이 아니라 섞일수 있는 한도내에서 랜덤해야 한다는거네요 ^^

 

정말 정말 감사합니다.

이 글에 답변 등록하기
         [답변]case 4: 인경우... 2007-04-29 오전 9:42:31
 serahero  serahero님께 메시지 보내기serahero님을 내 주소록에 추가합니다.serahero님의 개인게시판 가기 번호: 655119  

3 2

1

 

은 풀수 없다고 사료됩니다.-_-

 

2 3

1

이면 모를까...

 

많은 도움 감사합니다.

이 글에 답변 등록하기
 [답변]................... 2006-11-01 오전 9:48:55
 sjtkfkd77  sjtkfkd77님께 메시지 보내기sjtkfkd77님을 내 주소록에 추가합니다.sjtkfkd77님의 개인게시판 가기 번호: 614883  

 :)

 

퍼즐의 초기 상태를 보고

 

풀 수 있는 건지 아닌지 알 수 있습니다.

 

간단하게 2 * 2 블럭을 생각하면

 

 1 2

 3 X

 

위 처럼 순서를 매김니다.(1차원 배열로 생각하면 됩니다)

 

그리고 순서대로 그 위치의 값이 이전 값보다 작아지는를 판별합니다.

 

모든 순서에 대해 작아지는 경우가 홀수 인지 짝수인지 알 수 있는데

 

홀수가 된다면 이 퍼즐은 풀 수가 없습니다.

 

예를 들어 보면, 퍼즐 초기 상태가 아래와 같습니다.

 

case 1)         case 2)         case 3)         case 4)       

 1 2               1 3               2 1                 3 2             

 3                 2                  3                    1               

 

각각의 case마다 풀 수 있는지 알아 보면,

 

case 1은 1 2 3 순서이므로 작아지는 경우가 없습니다(즉, 0이므로 짝수) 그러므로 풀 수 있음.

 

case 2는 1 3 2 순서이기 때문에 3 -> 2로 갈때 작아집니다. 작아지는 경우가 1로 홀수, 그래서 풀 수 없음.

 

case 3은 2 1 3 , 이것도 2 -> 1 로 작아지는 경우가 1로 홀수. 풀 수 없음

 

case 4는 3 2 1, 이것은 3 -> 2 , 2 -> 1로 작아지는 경우가 2이므로 짝수. 그래서 이 경우는 풀 수 있음.

 

..................

 

퍼즐 크기가 커져도 위와 같이하면 다 알 수 있습니다.

 

판별 알고리즘이 간단하기 때문에 프로그래밍도 간단합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이 글에 답변 등록하기
목록 보기   지금 보고 계시는 글을 회원님의 my Mblog >> 스크랩에 넣어두고 다음에 바로 보실 수 있습니다.  
회사소개  |   개인정보취급방침  |  제휴문의  |   광고문의  |   E-Mail 무단수집거부  |   고객지원  |   이용안내  |   세금계산서
사업자등록번호 안내: 220-81-90008 / 통신판매업신고번호 제 2017-서울구로-0055호 / 대표: 홍영준, 서민호
08390, 서울시 구로구 디지털로32길 30, 1211호 / TEL. 02_6719_6200 / FAX. 02-6499-1910
Copyright ⓒ (주) 데브피아. All rights reserved.