N-Queens 마무리 날이다.
solves 푸는게 너무 힘들었다..
진짜 알고리즘의 꽃이라고 불릴만했다.ㅠㅠ

N-Queens란?

체스 게임이라고 생각하면 된다.
여기선 룩과 퀸을 움직이는 경우의 수를 구현하라고 했다.
N*N 사이즈의 체스판 위에 N 개의 퀸을 놓았을 때 서로 공격하지 못하게 하는 케이스를 구하는 문제이다.

움직일 수 있는 방향

움직일 수 있는 경우의 수는 행, 열, 슬래시 대각선(/), 역 슬래시 대각선()으로 총 4가지가 있다.
의미는 아래와 같다.

행(row) 행렬의 가로줄
열(column) 행렬의 세로줄
슬래시 대각선(Slash diagonal, '/') 오른쪽 상단에서 왼쪽 하단으로 이어지는 대각선
역 슬래시 대각선(Back Slash diagonal, '\') 왼쪽 상단에서 오른쪽 하단으로 이어지는 대각선. 한마디로 슬래시 대각선의 반대방향이다.

룩과 퀸의 역할

룩: 가로 혹은 세로 방향으로 거리에 상관없이 공격이 가능하다.
퀸: 가로, 세로, 슬래시 대각선, 역 슬래시 대각선 방향으로 거리에 상관없이 공격이 가능하다.

움직일 수 있는 경우의 수

(행)

(열)

(슬래시 대각선)

(역 슬래시 대각선)

Conflict란?

0: [0, 0, 0, 0]
1: [0, 0, 0, 0]
2: [0, 0, 0, 0]
3: [0, 0, 0, 0]

위에 보이는 식의 매트릭스가 4 x 4 형식인데, 이러한 체스판 위에 말이 있는지 없는지의 여부는 N의 길이를 가진 배열을 N 개의 키의 값으로 가지고 있는 객체에서 배열 속 값이 1이면 말이 있는 것이고 0이면 말이 없다는 의미이다.
현재는 체스판이 비었다는 것이고 0을 1로 만들면 체스 말이 생기는 것이다.

각각 함수의 의미

1. hasRowConflictAt(): 주어진 행(rowIndex)에 충돌하는 말이 있는지 확인하는 함수
2. hasAnyRowConflicts(): 체스 판 위에 행 충돌이 하나라도 있는지 확인하는 함수
3. hasColConflictAt(): 주어진 열(colIndex)에 충돌하는 말이 있는지 확인하는 함수
4. hasAnyColConflicts(): 체스 판 위에 열 충돌이 하나라도 있는지 확인하는 함수
5. hasSlashConflictAt(): 주어진 슬래시 대각선(/)에 충돌하는 말이 있는지 확인하는 함수
6. hasAnySlashConflicts(): 체스 판 위에 슬래시 대각선(/)에 충돌이 하나라도 있는지 확인하는 함수
7. hasBackSlashConflictAt(): 주어진 역 슬래시 대각선()에 충돌하는 말이 있는지 확인하는 함수
8. hasAnyBackSlashConflicts(): 체스 판 위에 역 슬래시 대각선() 충돌이 하나라도 있는지 확인하는 함수

=====================================================

9. findNRooksSolution(): n이 주어졌을 때 N-Rooks 문제의 해답 한 개를 반환하며, 반환 값은 체스 판을 나타내는 2차원 배열이다.
10. countNRooksSolutions(): n이 주어졌을 때 N-Rooks 문제의 전체 해답 개수를 반환하며, 반환 값은 정수이다.
11. findNQueensSolution(): n이 주어졌을 때 N-Queens 문제의 해답 한 개를 반환하며, 반환 값은 체스 판을 나타내는 2차원 배열이다.
12. countNQueensSolutions(): n이 주어졌을 때 N-Queens 문제의 전체 해답 개수를 반환하며, 반환 값은 정수이다.

N-Queens 알고리즘 해결방안 수도코드

hasRowConflictAt: function (rowIndex) { 
// 한 줄의 rowIndex 확인함수
// 카운트 지정
// 주어진 행을 가져온다
// 주어진 행을 순환한다.
// 주어진 행의 i번째가 1이면 카운트 1씩 증가
// 카운트가 1보다 크면 충돌한다.
// 충돌하면 true
// 아니면 false

hasColConflictAt: function (colIndex) { 
// 한 줄의 colIndex 확인함수
// 카운트 지정
// 2차원 배열을 가져온다.
// 2차원 배열을 순환한다.
// 2차원 배열의 i번째가 1이면 카운트 1씩 증가
// 카운트가 1보다 크면 충돌한다.
// 충돌하면 true
// 아니면 false

hasAnyColConflicts: function () { 
// n줄의 colIndex 확인함수
// 2차원 배열을 가져온다.
// 2차원 배열만큼 순환한다.
// 주어진 열이 충돌나면 true 리턴
// 아니면 false

hasSlashConflictAt: function (SlashColumnIndexAtFirstRow) { 
// 한 줄의 슬래시 대각선(/) 확인함수 
// 매개변수는 슬래시 대각선(/)시작하는 첫번째열의인덱스
// 카운트 지정
// 전체적인 행을 순환한다.
// row에 i를 할당
// col은 매개변수에서 row를 뺀 것
// row와 col이 체스판에 포함된다고 할 때
// 좌표의 x와 y의 합이 매개변수와 같을때를 1이라고 하는데, 1일때면 카운트 1씩증가
// 카운트가 1을 초과하면 충돌한다
// 충돌하면 true
// 아니면 false

hasAnySlashConflicts: function () { 
// n줄의 슬래시 대각선(/) 확인함수
// i는 0부터 시작, 전체적인 행의 2배에서 2를 뺀만큼 순환한다.
// 주어진 배열이 충돌하면 true리턴 
// 아니면 false

hasBackSlashConflictAt: function (BackSlashColumnIndexAtFirstRow) { 
// 한 줄의 역 슬래시 대각선(\) 확인함수
// 매개변수는 백슬래시 대각선(\)시작하는 첫번째열의인덱스
// 카운트 지정
// 전체적인 행을 순환한다.
// row에 i를 할당
// col은 매개변수에서 row를 더한 것
// row와 col이 체스판에 포함된다고 할 때
// 좌표의 x와 y의 차이가 매개변수와 같을때를 1이라고 하는데, 1일때면 카운트 1씩증가
// 카운트가 1을 초과하면 충돌한다
// 충돌하면 true
// 아니면 false

hasAnyBackSlashConflicts: function () { 
// n줄의 역 슬래시 대각선(\) 확인함수
// i는 전체적인 행을 음수로 지정한 것에서부터 시작, 전체적인 행만큼 순회
// 주어진 배열이 충돌하면 true리턴 
// 아니면 false

window.findNRooksSolution = function (n) {
let solution = undefined; // 결과값을 변수로 우선 선언만한다.(값을 undefined로 할당하는 이유)
// 체스 세팅
// 체스의 열 순행
// 체스에서 해당 열을 가져와 i값을 대각선으로 세팅
// 결과값에 체스의 2차원배열을 할당한다.
return solution; // 결과값 리턴

window.countNRooksSolutions = function (n) {
let solutionCount = 0; // 개수 카운트 설정
// 체스 세팅
// 깊이가 n과 같으면 카운트 1씩 증가시켜서 리턴
// 행 순환하면서 탐색 
// 충돌이 일어나면 좌표에 1씩 추가
// 충돌 일어나지 않으면 재귀
// 재귀로 빠져나올 때 해당 좌표가 두번찍혀서 0이 되니 한번 더 0으로 찍어준다.
  console.log('Number of solutions for ' + n + ' rooks:', solutionCount);
  return solutionCount; // 개수 카운트 리턴
};

window.findNQueensSolution = function (n) {
  let solution = undefined; // 결과값을 변수로 우선 선언만한다.(값을 undefined로 할당하는 이유)
// 체스 세팅
// 테스트케이스를 참고하셈.
// 밑으로 내려가는 인자를 column이라고 한다.
// column이 n과 같으면 체스의 결과를 리턴한다.
// 행 순환하면서 탐색 
// i열을 column행에 1씩 추가한다.
// 충돌이 일어나지 않으면 
// 1씩 증가시켜서 재귀로 내려간다.
// 추가한 값이 범위 안에 있는데 계속 진행해야할 경우 멈춘다.
// 순환시작할때 값을 0으로 만듦
// 재귀로 빠져나올 때 해당 좌표가 두번찍혀서 0이 되니 0열부터 순환을 하기 위해 초기값 0으로 세팅한다.
  console.log(
    'Single solution for ' + n + ' queens:',
    JSON.stringify(solution)
  );
  return solution;
};

window.countNQueensSolutions = function (n) {
  let solutionCount = 0; // 개수 카운팅 설정
// 체스 세팅
// 충돌 일어나면 재귀탈출하여 리턴
// 깊이가 n과 같으면 카운트 1씩 증가시켜서 리턴
// 행 순환하면서 탐색 
// 충돌이 일어나지 않으면 좌표에 1씩 추가
// 재귀로 빠져나올 때 해당 좌표가 두번찍혀서 0이 되니 0행부터 순환을 하기 위해 초기값 0으로 세팅한다.
  console.log('Number of solutions for ' + n + ' queens:', solutionCount);
  return solutionCount; // 개수 카운트 리턴
};