퀸 퍼즐-01

체스에서 퀸 두는 문제 푸려고 하다가

퀸이 움직일 수 있는 위치 구하는 코드가 너무 더럽고 마음에 안들어서 책에 나온 방식을 적용해보려고 했다.

 

근데 c++로 옮기기가 참 어려웠다.

 

결국 고민한 끝에 책을 완전히 배끼지는 못했고, 내가 할 수 있는 최선으로 했다.

 

물론 문제는 다 못풀었다. 최선으로 하고 있는 과정 중인 것이다.

 

아래 코드 쓴다고 자그마치 3시간을 투자했다.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <windows.h>
 
void movecursor(int x, int y)
{
    COORD pos = { x, y };
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
}
int ab(int i)
{
    return i > 0 ? i : -1 * i;
}
bool is_okay(std::pair<int, int>&& test_loc, std::pair<int, int>& cur_loc)
{
    if (test_loc.first == cur_loc.first)
    {
        return true;
    }
    else if (test_loc.second == cur_loc.second)
    {
        return true;
    }
    else if (ab(test_loc.first - cur_loc.first) == ab(test_loc.second - cur_loc.second))
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
void get_movable_locs(std::vector<std::pair<int,int>>& ref, std::pair<int, int>& cur_loc)
{
    std::vector<std::pair<int, int>> v;
    for (int i = 0; i < 64; i++)
    {
        for (int j = 0; j < 64; j++)
        {
            if (is_okay({ i, j }, cur_loc)) { ref.push_back({ i, j }); }
        }
    }
}
 
void get_answer(std::pair<int, int>&& cur_loc)
{
    
    std::vector < std::pair<int, int> > movable_locs;
    movable_locs.reserve(4000);
 
    //움직일 수 있는 퀸의 위치들 
    get_movable_locs(movable_locs, cur_loc);
 
    //출력
    for (int i = 0; i < movable_locs.size(); i++)
    {
        movecursor(movable_locs[i].first, movable_locs[i].second);
        puts("*");
    }
    for (int i = 0; i < 100; i++)
    {
        puts("\n");
    }
}
 
int main()
{
    get_answer({ 3,4 });
}

 

그리고 책에서 읽은 유용한 팁이 있어 블로그에 남긴다.

 

순열 {1, 2, 3}이 있다고 할 때 이를 S라고 하고 S의 원소를 x라고 하면

이를 모두 섞는 알고리즘은 다음과 같다.

 

1. S - x를 생성한다.
2. 각 순차열의 앞에 x를 삽입한다.
3. 이러면 x로 시작하는 S의 순차열들이 모두 만들어진다.
4. 이를 합치면 S의 모든 순열이 나온다.

이를 재귀적으로 반복하면 된다고 한다.

분할정복과 비슷해보인다.