Cwords는 크로스워드(낱말퍼즐)를 자동으로 생성해 내는 프로그램입니다. 이 프로그램은 다음과 같은 부문(component)을 가집니다.

1. 그리드 생성기
2. 낱말 사전
3. 낱말 삽입기
4. 사용자 인터페이스

프로그램의 작동과정은 다음과 같습니다.
1. 그리드 생성기를 사용하여 크로스워드의 바탕이 될 그리드를 생성한다.
2. 낱말 삽입기를 사용하여 낱말 사전으로부터 가져온 낱말을 과정 1에서 생성된 그리드의 블록 안에 삽입한다.
3. 사용자 인터페이스를 이용하여 과정 2에서 생성된 크로스워드를 낱말이 숨겨진 채 전시하고, 사용자로부터 낱말을 입력받아 숨겨진 낱말과 일치할시, O를 내놓고 그렇지 않을시, X를 내놓는다.


1. 그리드 생성기

그리드 생성기는 1보다 큰 홀수(3, 5, 7, ...)를 입력받아 입력받은 홀수를 길이로 가지는 정사각형의 그리드와, 그리드 안에 들어있는 블록에 대한 정보를 내놓습니다.

(1) 용어(term)

그리드(grid): 크로스워드의 바탕을 이루는 칸(square)의 집합. 
// 제약조건: 1. 그리드의 길이는 가로와 세로가 같아야 한다. 2. 그리드의 길이는 홀수여야한다. 3. 그리드를 180도 회전하였을 때, 회전하기 전과 회전한 후의 모양이 같아야 한다.

블록(block): 낱말이 들어갈 칸의 연결체. 
// 제약조건: 1. 블록의 길이는 그리드의 길이를 넘어선 안된다. 2. 블록의 길이가 가로 세로 모두 1이어선 안된다(홀로 고립되어 있는 칸이 존재하는 경우).

칸(square): 고유한 좌표를 갖는 크로스워드의 최소단위.
닫힌 칸(closed square): 연결되어 블록을 이룰 수 없는 칸, 코드 상에 "X"로 표시됨.
열린 칸(opened square): 연결되어 블록을 이룰 수 있는 칸. 코드 상에 "O"로 표시됨.

교차점(intersection): 수직방향의 블록과 수평방향의 블록이 겹치는 칸. 


(2) 블록의 표시(representation of a block)

하나의 블록은 다음과 같이 특별한 의미가 부여된 정수의 리스트로 표시될 수 있습니다.

교차점의 개수, 길이, x축 좌표, y축 좌표, 방향(수평 또는 수직)

예시) 
3, 7, 1, 0, 100  // 좌표 (1,0)에서부터 수평방향으로 길이 7만큼 뻗어나가며 교차점을 3개 가지는 블록
0, 0, 6, 0, 1, -100  // 좌표 (0,1)에서부터 수직방향으로 길이 6만큼 뻗어나가며 교차점을 0개 가지는 블록


(3) 그리드 크기별로 열어야 할 칸의 적정한 개수 (지극히 주관적인)
11x11: recursiveRowCloser 함수를 이용하여 (0,0)에서 부터 닫을 때, 만약 randomlyAndSymmetricallyClose 함수를 7번 호출한다면, 121칸 중 75칸 열림  / (1,0)에서부터 닫을 때, if n == 8, then 75/121 
13x13: (0,0)에서 부터 닫을 때, if n == 13, then 93/169  / (1,0)에서부터 닫을 때, if n == 17, then 93/169
15x15: (0,0)에서 부터 닫을 때, if n == 20, then 121/225  / (1,0)에서부터 닫을 때, if n == 24, then 121/225
17x17: (0,0)에서 부터 닫을 때, if n == 28, then 151/289 / (1,0)에서부터 닫을 때, if n == 33, then 151/289
19x19: (0,0)에서 부터 닫을 때, if n == 33, then 196/361  / (1,0)에서부터 닫을 때, if n == 38, then 196/361


(4) 하위부문(sub-components)
1) 그리드 생성부 - 그리드를 생성하는 하위부문
2) 블록 추출부 - 그리드 생성부에서 생성된 그리드가 가지고 있는 블록에 대한 정보를 리스트의 리스트의 형태로 추출하는 하위부문
3) 그리드 검사부 - 그리드 생성부에서 생성된 그리드가 제약조건을 만족하는 정형(well-formed)의 그리드인지, 또는 '쓸만한' 그리드인지 검사하는 하위부문



2. 낱말 사전
낱말 사전은 구성하기 나름이며, 영어 낱말 사전, 한국어 낱말 사전, 꽃 이름 사전, 지명 사전, 동음이의어 사전 등 다양한 사전을 구성할 수 있습니다. (코드 상에 구현한 사전은 영어의 기본 어휘에 추가로, 웹과 본인의 머리에서 마구잡이로 수집한 영어 어휘 사전입니다)


3. 낱말 삽입기

낱말 삽입기는 그리드의 길이와 블록에 대한 정보를 입력받아 낱말이 삽입된 그리드를 내놓습니다.


예시)

그리드의 길이 11과 다음과 같은,

0, 0, 0, 0, 0
1, 2, 3, 2, 100
1, 2, 7, 7, 100
1, 3, 0, 1, -100
1, 3, 8, 9, -100
1, 5, 0, 9, -100
1, 5, 6, 1, -100
3, 6, 1, 0, 100
3, 6, 3, 5, 100
3, 6, 7, 0, 100
3, 6, 9, 5, 100
3, 7, 5, 2, 100
4, 11, 0, 3, -100
4, 11, 0, 7, -100
5, 11, 0, 5, -100


정수 리스트의 리스트로 이루어진 블록에 대한 정보를 입력값으로 받아, 다음과 같은 크로스워드를 출력합니다.

* w * t * h * f * m * 
c h e e s e * o * a * 
* o * m * a * r * n * 
* * u p * d a m a g e 
* * * e * q * u * o * 
* * t r o u b l e * * 
* l * a * a * a * * * 
w i n t e r * t o * * 
* m * u * t * i * e * 
* i * r * e n o u g h 
* t * e * r * n * g * 



낱말 삽입기의 하위부문(sub-components)
1) 그리드 전사부 - 그리드의 각 블록에 대한 정보를 담고 있는 리스트의 리스트를 입력 받아, 그리드를 그리는 부문
2) 낱말 삽입부 - 그리드 그리기부에 의해서 그려진 그리드에 대해서 낱말 사전으로부터 단어를 가져와 삽입하는 부문.
3) 크로스워드 검사부 - 낱말 삽입부에 의해서 생성된 크로스워드가 정형의 크로스워드인지, 즉 낱말이 제대로 삽입되었는지 확인하는 부문.


4. 사용자 인터페이스
개발 예정


5. Agenda
현재는 모든 블록에 한꺼번에 낱말을 삽입하기 때문에 정형의 크로스워드 생성에 성공할 확률이 매우 낮은데, 블록들을 그래프의 집합으로 간주하여 모든 연결 성분(connected component)을 구한 뒤, 각각의 연결 성분에 대하여 서로 다른 낱말 사전으로부터 낱말을 가져와 삽입하면, 생성 성공률이 훨씬 더 높아질 거라고 예상됨, 따라서 연결 성분을 구할 수 있는 자료구조 도입 및 코드 작성을 목표.