Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
65 kB
1
Indexable
Never
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_set>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <set>
#include <queue>

using namespace std;

bool linkedEdge[55][55][55][55]={0};
int Map[100][100],n,m,an,am;
vector<string> ans;
pair<int,int> start;
bool CheckLinkedEdge(int x1,int y1,int x2,int y2){
    return linkedEdge[x1][y1][x2][y2] || linkedEdge[x2][y2][x1][y1];
}
void PrintGra();

class puzzle
{
public:
    size_t cols, rows = 0;   // of lattice
    vector<vector<int>> lat; // lattice

    enum edge_state
    {
        BAN = -1,  // banned
        NOT = 0,   // not linked
        LINKED = 1 // linked
    };
    vector<vector<edge_state>> hrz; // horizon link
    vector<vector<edge_state>> vrt; // vertical link

    vector<vector<bool>> banned_point;

    size_t get_conn(const int &p_r, const int &p_c)
    {
        size_t conn = 0;
        if (point_has_edge_up(p_r, p_c))
            conn++;
        if (point_has_edge_down(p_r, p_c))
            conn++;
        if (point_has_edge_left(p_r, p_c))
            conn++;
        if (point_has_edge_right(p_r, p_c))
            conn++;
        return conn;
    }

    size_t lat_edge(const int &lat_r, const int &lat_c)
    {
        return hrz_has_edge(lat_r, lat_c) +
               hrz_has_edge(lat_r + 1, lat_c) +
               vrt_has_edge(lat_r, lat_c) +
               vrt_has_edge(lat_r, lat_c + 1);
    }

    size_t get_lat_banned_edge(const int &lat_r, const int &lat_c)
    {
        return (hrz[lat_r][lat_c] == BAN ? 1 : 0) +
               (hrz[lat_r + 1][lat_c] == BAN ? 1 : 0) +
               (vrt[lat_r][lat_c] == BAN ? 1 : 0) +
               (vrt[lat_r][lat_c + 1] == BAN ? 1 : 0);
    }

    bool hrz_sat(const int &h_r, const int &h_c)
    {
        if (hrz_has_up_lat(h_r, h_c) &&
            lat[h_r - 1][h_c] >= 0 &&
            lat_edge(h_r - 1, h_c) > lat[h_r - 1][h_c])
            return false;
        if (hrz_has_down_lat(h_r, h_c) &&
            lat[h_r][h_c] >= 0 &&
            lat_edge(h_r, h_c) > lat[h_r][h_c])
            return false;
        return true;
    }

    bool vrt_sat(const int &v_r, const int &v_c)
    {
        if (vrt_has_left_lat(v_r, v_c) &&
            lat[v_r][v_c - 1] >= 0 &&
            lat_edge(v_r, v_c - 1) > lat[v_r][v_c - 1])
            return false;
        if (vrt_has_right_lat(v_r, v_c) &&
            lat[v_r][v_c] >= 0 &&
            lat_edge(v_r, v_c) > lat[v_r][v_c])
            return false;
        return true;
    }

    bool point_can_up(const int &p_r, const int &p_c)
    {
        if (p_r <= 0)
            return false;
        if (banned_point[p_r - 1][p_c])
            return false;
        if (vrt[p_r - 1][p_c] == puzzle::BAN)
            return false;
        return true;
    }

    bool point_can_down(const int &p_r, const int &p_c)
    {
        if (p_r >= rows)
            return false;
        if (banned_point[p_r + 1][p_c])
            return false;
        if (vrt[p_r][p_c] == puzzle::BAN)
            return false;
        return true;
    }

    bool point_can_left(const int &p_r, const int &p_c)
    {
        if (p_c <= 0)
            return false;
        if (banned_point[p_r][p_c - 1])
            return false;
        if (hrz[p_r][p_c - 1] == puzzle::BAN)
            return false;
        return true;
    }

    bool point_can_right(const int &p_r, const int &p_c)
    {
        if (p_c >= cols)
            return false;
        if (banned_point[p_r][p_c + 1])
            return false;
        if (hrz[p_r][p_c] == puzzle::BAN)
            return false;
        return true;
    }

    bool point_has_edge_up(const int &p_r, const int &p_c)
    {
        return point_can_up(p_r, p_c) && vrt_has_edge(p_r - 1, p_c);
    }

    bool point_has_edge_down(const int &p_r, const int &p_c)
    {
        return point_can_down(p_r, p_c) && vrt_has_edge(p_r, p_c);
    }

    bool point_has_edge_left(const int &p_r, const int &p_c)
    {
        return point_can_left(p_r, p_c) && hrz_has_edge(p_r, p_c - 1);
    }

    bool point_has_edge_right(const int &p_r, const int &p_c)
    {
        return point_can_right(p_r, p_c) && hrz_has_edge(p_r, p_c);
    }

    int hrz_has_edge(const int &h_r, const int &h_c)
    {
        return hrz[h_r][h_c] == LINKED;
    }

    int vrt_has_edge(const int &v_r, const int &v_c)
    {
        return vrt[v_r][v_c] == LINKED;
    }

    bool hrz_has_up_lat(const int &h_r, const int &h_c)
    {
        return h_r > 0;
    }

    bool hrz_has_down_lat(const int &h_r, const int &h_c)
    {
        return h_r < rows;
    }

    bool vrt_has_left_lat(const int &v_r, const int &v_c)
    {
        return v_c > 0;
    }

    bool vrt_has_right_lat(const int &v_r, const int &v_c)
    {
        return v_c < cols;
    }

    bool complete_lat(const int &lat_r, const int &lat_c)
    {
        if (lat[lat_r][lat_c] >= 0 &&
            lat[lat_r][lat_c] != lat_edge(lat_r, lat_c))
            return false;
        else
            return true;
    }

    bool is_fin()
    {
        for (size_t row = 0; row < rows; row++)
        {
            for (size_t col = 0; col < cols; col++)
            {
                if (!complete_lat(row, col))
                    return false;
            }
        }
        for (size_t row = 0; row <= rows; row++)
        {
            for (size_t col = 0; col <= cols; col++)
            {
                if (get_conn(row, col) == 1 || get_conn(row, col) == 3)
                {
                    return false;
                }
            }
        }
        if (is_multiple_loops())
            return false;
        return true;
    }

    bool is_correct() // During solving
    {
        // check lattice
        for (size_t row = 0; row < rows; row++)
        {
            for (size_t col = 0; col < cols; col++)
            {
                if (lat[row][col] >= 0)
                {
                    if (lat[row][col] < lat_edge(row, col))
                        return false;
                    if (4 - lat[row][col] < get_lat_banned_edge(row, col))
                        return false;
                }
            }
        }
        // check point
        for (size_t row = 0; row <= rows; row++)
        {
            for (size_t col = 0; col <= cols; col++)
            {
                if (get_conn(row, col) == 3)
                {
                    return false;
                }
                // if (get_conn(row, col) == 1)
                // {
                //     size_t ban_edges = (point_can_up(row, col) ? 0 : 1) +
                //                        (point_can_left(row, col) ? 0 : 1) +
                //                        (point_can_down(row, col) ? 0 : 1) +
                //                        (point_can_right(row, col) ? 0 : 1);
                //     if (ban_edges >= 3)
                //         return false;
                // }
            }
        }
        if (is_multiple_loops())
            return false;
        if (!is_even_line_out())
            return false;
        return true;
    }

    bool is_multiple_loops()
    {
        set<pair<int, int>> done;
        size_t loops = 0;
        size_t lines = 0;
        for (size_t row = 0; row <= rows; row++)
        {
            for (size_t col = 0; col <= cols; col++)
            {
                // New point with 2 conn
                // Maybe in a loop
                if (get_conn(row, col) == 2 && done.find({row, col}) == done.end())
                {
                    // Mark one loop or line (BFS)
                    bool is_line = false;
                    queue<pair<int, int>> todo;
                    todo.push({row, col});
                    do
                    {
                        const auto now = todo.front();
                        todo.pop();
                        if (done.find(now) != done.end())
                        {
                            continue;
                        }
                        done.insert(now);
                        if (get_conn(now.first, now.second) == 1) // is a line
                        {
                            is_line = true;
                        }
                        if (point_has_edge_up(now.first, now.second))
                        {
                            if (done.find({now.first - 1, now.second}) == done.end())
                            {
                                todo.push({now.first - 1, now.second});
                            }
                        }
                        if (point_has_edge_down(now.first, now.second))
                        {
                            if (done.find({now.first + 1, now.second}) == done.end())
                            {
                                todo.push({now.first + 1, now.second});
                            }
                        }
                        if (point_has_edge_left(now.first, now.second))
                        {
                            if (done.find({now.first, now.second - 1}) == done.end())
                            {
                                todo.push({now.first, now.second - 1});
                            }
                        }
                        if (point_has_edge_right(now.first, now.second))
                        {
                            if (done.find({now.first, now.second + 1}) == done.end())
                            {
                                todo.push({now.first, now.second + 1});
                            }
                        }
                    } while (!todo.empty());
                    if (is_line)
                    {
                        lines++;
                    }
                    else
                    {
                        loops++;
                    }
                    if (loops > 1)
                        return true;
                    if (loops == 1 && lines > 0)
                        return true;
                }
            }
        }
        return false;
    }

    bool is_even_line_out()
    {
        set<pair<int, int>> done;
        for (size_t row = 0; row <= rows; row++)
        {
            for (size_t col = 0; col <= cols; col++)
            {
                // New point with 0 or 1 conn in one island
                if (get_conn(row, col) <= 1 && done.find({row, col}) == done.end())
                {
                    // Mark one point in this island (BFS)
                    set<pair<int, int>> island;
                    queue<pair<int, int>> todo;
                    size_t thread_cnt = 0;
                    todo.push({row, col});
                    do
                    {
                        const auto now = todo.front();
                        todo.pop();
                        if (island.find(now) != island.end())
                        {
                            continue;
                        }
                        island.insert(now);
                        if (get_conn(now.first, now.second) == 1) // a "thread"
                        {
                            thread_cnt++;
                        }
                        if (point_can_up(now.first, now.second) &&
                            !point_has_edge_up(now.first, now.second))
                        {
                            if (island.find({now.first - 1, now.second}) == island.end() &&
                                get_conn(now.first - 1, now.second) < 2)
                            {
                                todo.push({now.first - 1, now.second});
                            }
                        }
                        if (point_can_down(now.first, now.second) &&
                            !point_has_edge_down(now.first, now.second))
                        {
                            if (island.find({now.first + 1, now.second}) == island.end() &&
                                get_conn(now.first + 1, now.second) < 2)
                            {
                                todo.push({now.first + 1, now.second});
                            }
                        }
                        if (point_can_left(now.first, now.second) &&
                            !point_has_edge_left(now.first, now.second))
                        {
                            if (island.find({now.first, now.second - 1}) == island.end() &&
                                get_conn(now.first, now.second - 1) < 2)
                            {
                                todo.push({now.first, now.second - 1});
                            }
                        }
                        if (point_can_right(now.first, now.second) &&
                            !point_has_edge_right(now.first, now.second))
                        {
                            if (island.find({now.first, now.second + 1}) == island.end() &&
                                get_conn(now.first, now.second + 1) < 2)
                            {
                                todo.push({now.first, now.second + 1});
                            }
                        }
                    } while (!todo.empty());
                    if (thread_cnt % 2)
                        return false;
                    done.insert(island.begin(), island.end());
                }
            }
        }
        return true;
    }

    string to_string()
    {
        const auto link = "█";
        const auto dot = "▪";
        stringstream ss;
        for (size_t row = 0; row <= rows; row++)
        {
            for (size_t col = 0; col <= cols; col++)
            {
                if (get_conn(row, col) > 0)
                    ss << link;
                // else if (banned_point[row][col])
                //     ss << "x";
                else
                    ss << dot;
                if (col < cols)
                {
                    if (hrz_has_edge(row, col))
                        ss << link;
                    else if (hrz[row][col] == BAN)
                        ss << "x";
                    else
                        ss << " ";
                }
            }
            ss << "\n";
            if (row < rows)
            {
                for (size_t col = 0; col <= cols; col++)
                {
                    if (vrt_has_edge(row, col))
                        ss << link;
                    else if (vrt[row][col] == BAN)
                        ss << "x";
                    else
                        ss << " ";
                    if (col < cols)
                    {
                        if (lat[row][col] >= 0)
                            ss << lat[row][col];
                        else
                            ss << " ";
                    }
                }
            }
            ss << "\n";
        }



        stringstream ssa;
        ans.clear();
        for (size_t row = 0; row <= rows; row++)
        {
            for (size_t col = 0; col <= cols; col++)
            {
                if (get_conn(row, col) > 0)
                    ssa << '_';
                // else if (banned_point[row][col])
                //     ss << "x";
                else
                    ssa << '.';
                if (col < cols)
                {
                    if (hrz_has_edge(row, col))
                        ssa << '_';
                    else if (hrz[row][col] == BAN)
                        ssa << ' ';
                    else
                        ssa << ' ';
                }
            }
            ans.push_back(ssa.str());
            ssa.str("");
            if (row < rows)
            {
                for (size_t col = 0; col <= cols; col++)
                {
                    if (vrt_has_edge(row, col))
                        ssa << '_';
                    else if (vrt[row][col] == BAN)
                        ssa << ' ';
                    else
                        ssa << ' ';
                    if (col < cols)
                    {
                        if (lat[row][col] >= 0)
                            ssa << lat[row][col];
                        else
                            ssa << ' ';
                    }
                }
            }
            ans.push_back(ssa.str());
            ssa.str("");
        }
        n=(ans.size()-1)/2;
        m=ans[0].size()/2;
        an=ans.size(),am=ans[0].size();
        memset(linkedEdge,0,sizeof(linkedEdge));
        for(int i=1;i<an;i+=2){
            for(int j=1;j<am;j+=2){
                if(isdigit(ans[i][j])) Map[i/2][j/2]=ans[i][j]-'0';
                else Map[i/2][j/2]=-1;
            }
        }
        start={-1,-1};
        for(int i=0;i<an;i+=2){
            for(int j=0;j<am;j+=2){
                if(ans[i][j]=='_'){
                    start={i,j};
                }
            }
        }
        
        

        return ss.str();
    }
};



#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <set>
#include <queue>
#include <unordered_set>


class puzzle_solver
{
private:
    /* data */
    puzzle p;
    unordered_set<string> puzzle_results;
    ostream *os;

public:
    void read_puzzle(istream &is);
    void set_output(ostream &os)
    {
        this->os = &os;
    }

    int solve();

private:
    bool heuristic(puzzle &p, bool head = true);

    void ban_edge_around_zero(puzzle &p);
    void prelink_around_threes(puzzle &p);

    void ban_edge_around_one(puzzle &p);
    void ban_edge_around_two(puzzle &p);
    void ban_edge_around_three(puzzle &p);
    void ban_edge_around_point(puzzle &p);
    void ban_point(puzzle &p);

    void link_around_one(puzzle &p);
    void link_around_two(puzzle &p);
    void link_around_three(puzzle &p);
    void link_around_point(puzzle &p);

    bool try_draw(puzzle &p);

    void DFS(puzzle &p);
    void go_with_line(puzzle &p,
                      const int &start_r, const int &start_c,
                      int src_p_r, int src_p_c,
                      int dst_p_r, int dst_p_c);
    void go_without_line(puzzle &p,
                         const int &start_r, const int &start_c,
                         const int &src_p_r, const int &src_p_c,
                         const int &dst_p_r, const int &dst_p_c);
    void draw_line(puzzle p,
                   const int &start_r, const int &start_c,
                   const int &src_p_r, const int &src_p_c,
                   const int &dst_p_r, const int &dst_p_c);
};

void puzzle_solver::read_puzzle(istream &is)
{
    // read puzzle
    string line;
    while(is >> line){
        p.cols=line.size();
        vector<int> tmp_row;
        for (size_t col = 0; col < p.cols; col++)
        {
            const char c = line[col];
            switch (c)
            {
            case '0':
            case '1':
            case '2':
            case '3':
                tmp_row.push_back(c - '0');
                break;
            default:
                tmp_row.push_back(-1);
                break;
            }
        }
        p.lat.push_back(tmp_row);
        p.rows++;
    }
    // init connect state table
    for (size_t row = 0; row < p.rows + 1; row++)
    {
        vector<puzzle::edge_state> tmp_row;
        for (size_t col = 0; col < p.cols; col++)
        {
            tmp_row.push_back(puzzle::NOT);
        }
        p.hrz.push_back(tmp_row);
    }
    for (size_t row = 0; row < p.rows; row++)
    {
        vector<puzzle::edge_state> tmp_row;
        for (size_t col = 0; col < p.cols + 1; col++)
        {
            tmp_row.push_back(puzzle::NOT);
        }
        p.vrt.push_back(tmp_row);
    }
    // init banned point
    for (size_t row = 0; row <= p.rows; row++)
    {
        vector<bool> tmp_row;
        for (size_t col = 0; col <= p.cols; col++)
        {
            tmp_row.push_back(false);
        }
        p.banned_point.push_back(tmp_row);
    }
}

int puzzle_solver::solve()
{
    ban_edge_around_zero(p);
    prelink_around_threes(p);
    if (heuristic(p) == false)
    {
        return -1;
    }
    // Heuristic done
    if (p.is_fin() && p.is_correct())
    {
        // Print solution
        const auto result = p.to_string();
        if (puzzle_results.find(result) == puzzle_results.end())
        {
            puzzle_results.insert(result);
            // cout << result;
            PrintGra();
        }
    }
    DFS(p);
    return puzzle_results.size();
}

bool puzzle_solver::heuristic(puzzle &p, bool ahead)
{
    string last_step = p.to_string();
    string curr_step;
    while (true)
    {
        ban_edge_around_one(p);
        ban_edge_around_two(p);
        ban_edge_around_three(p);
        ban_edge_around_point(p);
        ban_point(p);
        link_around_point(p);
        link_around_three(p);
        link_around_two(p);
        link_around_one(p);
        if (!p.is_correct())
        {
            return false;
        }
        curr_step = p.to_string();
        // run out of normal methods
        if (last_step.compare(curr_step) == 0)
        {
            break;
        }
        else // normal method make sense
        {
            last_step = curr_step;
        }
    }
    // look ahead
    while (ahead == true)
    {
        if (try_draw(p) == false)
        {
            return false;
        }
        else
        {
            // look ahead make sense
            // try normal methods again
            curr_step = p.to_string();
            if (last_step.compare(curr_step) == 0)
            {
                break;
            } 
            last_step = curr_step;
        }
    }
    // look head not useful
    // return to DFS
    return true;
}

void puzzle_solver::ban_edge_around_zero(puzzle &p)
{
    /**
     * . b .
     * b 0 b
     * . b .
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 0)
            {
                p.hrz[row][col] = puzzle::BAN;
                p.hrz[row + 1][col] = puzzle::BAN;
                p.vrt[row][col] = puzzle::BAN;
                p.vrt[row][col + 1] = puzzle::BAN;
            }
        }
    }
}

void puzzle_solver::prelink_around_threes(puzzle &p)
{
    /**
     *   . l .
     *     3
     * b . l . b
     *     3
     *   . l .
     */                                         
    for (size_t row = 0; row < p.rows - 1; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 3 && p.lat[row + 1][col] == 3)
            {
                p.hrz[row][col] = puzzle::LINKED;
                p.hrz[row + 1][col] = puzzle::LINKED;
                p.hrz[row + 2][col] = puzzle::LINKED;
                if (p.point_can_left(row + 1, col))
                    p.hrz[row + 1][col - 1] = puzzle::BAN;
                if (p.point_can_right(row + 1, col + 1))
                    p.hrz[row + 1][col + 1] = puzzle::BAN;
            }
        }
    }
    /**
     *     b
     * .   .   .
     * l 3 l 3 l
     * .   .   .
     *     b
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols - 1; col++)
        {
            if (p.lat[row][col] == 3 && p.lat[row][col + 1] == 3)
            {
                p.vrt[row][col] = puzzle::LINKED;
                p.vrt[row][col + 1] = puzzle::LINKED;
                p.vrt[row][col + 2] = puzzle::LINKED;
                if (p.point_can_up(row, col + 1))
                    p.vrt[row - 1][col + 1] = puzzle::BAN;
                if (p.point_can_down(row + 1, col + 1))
                    p.vrt[row + 1][col + 1] = puzzle::BAN;
            }
        }
    }
    /**
     *   b
     * b . l .   .
     *   l 3
     *   .   .   .
     *         3 l
     *   .   . l . b
     *           b
     */
    for (size_t row = 0; row < p.rows - 1; row++)
    {
        for (size_t col = 0; col < p.cols - 1; col++)
        {
            if (p.lat[row][col] == 3 && p.lat[row + 1][col + 1] == 3)
            {
                p.hrz[row][col] = puzzle::LINKED;
                p.vrt[row][col] = puzzle::LINKED;
                p.hrz[row + 2][col + 1] = puzzle::LINKED;
                p.vrt[row + 1][col + 2] = puzzle::LINKED;
                if (p.point_can_up(row, col))
                    p.vrt[row - 1][col] = puzzle::BAN;
                if (p.point_can_left(row, col))
                    p.hrz[row][col - 1] = puzzle::BAN;
                if (p.point_can_down(row + 2, col + 2))
                    p.vrt[row + 2][col + 2] = puzzle::BAN;
                if (p.point_can_right(row + 2, col + 2))
                    p.hrz[row + 2][col + 2] = puzzle::BAN;
            }
        }
    }
    /**
     *           b
     *   .   . l . b
     *         3 l
     *   .   .   .
     *   l 3
     * b . l .   .
     *   b
     */
    for (size_t row = 0; row < p.rows - 1; row++)
    {
        for (size_t col = 0; col < p.cols - 1; col++)
        {
            if (p.lat[row][col + 1] == 3 && p.lat[row + 1][col] == 3)
            {
                p.hrz[row][col + 1] = puzzle::LINKED;
                p.vrt[row][col + 2] = puzzle::LINKED;
                p.hrz[row + 2][col] = puzzle::LINKED;
                p.vrt[row + 1][col] = puzzle::LINKED;
                if (p.point_can_up(row, col + 2))
                    p.vrt[row - 1][col + 2] = puzzle::BAN;
                if (p.point_can_right(row, col + 2))
                    p.hrz[row][col + 2] = puzzle::BAN;
                if (p.point_can_down(row + 2, col))
                    p.vrt[row + 2][col] = puzzle::BAN;
                if (p.point_can_left(row + 2, col))
                    p.hrz[row + 2][col - 1] = puzzle::BAN;
            }
        }
    }
}

void puzzle_solver::ban_edge_around_one(puzzle &p)
{
    /**
     *   x
     * x . b .
     *   b 1
     *   .   .
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 1 && p.get_lat_banned_edge(row, col) < 2)
            {
                if (!p.point_can_up(row, col) &&
                    !p.point_can_left(row, col))
                {
                    p.hrz[row][col] = puzzle::BAN;
                    p.vrt[row][col] = puzzle::BAN;
                }
                if (!p.point_can_up(row, col + 1) &&
                    !p.point_can_right(row, col + 1))
                {
                    p.hrz[row][col] = puzzle::BAN;
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
                if (!p.point_can_down(row + 1, col) &&
                    !p.point_can_left(row + 1, col))
                {
                    p.hrz[row + 1][col] = puzzle::BAN;
                    p.vrt[row][col] = puzzle::BAN;
                }
                if (!p.point_can_down(row + 1, col + 1) &&
                    !p.point_can_right(row + 1, col + 1))
                {
                    p.hrz[row + 1][col] = puzzle::BAN;
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
            }
        }
    }
    /**
     * . b .
     * b 1 |
     * . b .
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 1 && p.get_lat_banned_edge(row, col) != 3)
            {
                if (p.hrz_has_edge(row, col))
                {
                    p.hrz[row + 1][col] = puzzle::BAN;
                    p.vrt[row][col] = puzzle::BAN;
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
                else if (p.hrz_has_edge(row + 1, col))
                {
                    p.hrz[row][col] = puzzle::BAN;
                    p.vrt[row][col] = puzzle::BAN;
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
                else if (p.vrt_has_edge(row, col))
                {
                    p.hrz[row][col] = puzzle::BAN;
                    p.hrz[row + 1][col] = puzzle::BAN;
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
                else if (p.vrt_has_edge(row, col + 1))
                {
                    p.hrz[row][col] = puzzle::BAN;
                    p.hrz[row + 1][col] = puzzle::BAN;
                    p.vrt[row][col] = puzzle::BAN;
                }
            }
        }
    }
    /**
     *   x
     * - .   .
     *     1 b
     *   . b .
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 1 && p.get_lat_banned_edge(row, col) < 2)
            {
                if ((p.point_has_edge_up(row, col) || p.point_has_edge_left(row, col)) &&
                    (!p.point_can_up(row, col) || !p.point_can_left(row, col)))
                {
                    p.hrz[row + 1][col] = puzzle::BAN;
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
                if ((p.point_has_edge_up(row, col + 1) || p.point_has_edge_right(row, col + 1)) &&
                    (!p.point_can_up(row, col + 1) || !p.point_can_right(row, col + 1)))
                {
                    p.hrz[row + 1][col] = puzzle::BAN;
                    p.vrt[row][col] = puzzle::BAN;
                }
                if ((p.point_has_edge_down(row + 1, col) || p.point_has_edge_left(row + 1, col)) &&
                    (!p.point_can_down(row + 1, col) || !p.point_can_left(row + 1, col)))
                {
                    p.hrz[row][col] = puzzle::BAN;
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
                if ((p.point_has_edge_down(row + 1, col + 1) || p.point_has_edge_right(row + 1, col + 1)) &&
                    (!p.point_can_down(row + 1, col + 1) || !p.point_can_right(row + 1, col + 1)))
                {
                    p.hrz[row][col] = puzzle::BAN;
                    p.vrt[row][col] = puzzle::BAN;
                }
            }
        }
    }
}
 
void puzzle_solver::ban_edge_around_two(puzzle &p)
{
    /**
     * . - .
     * b 2 |
     * . b .
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 2 && p.get_lat_banned_edge(row, col) != 2)
            {
                if (p.hrz_has_edge(row, col) &&
                    p.vrt_has_edge(row, col))
                {
                    p.hrz[row + 1][col] = puzzle::BAN;
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
                else if (p.hrz_has_edge(row, col) &&
                         p.hrz_has_edge(row + 1, col))
                {
                    p.vrt[row][col] = puzzle::BAN;
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
                else if (p.hrz_has_edge(row, col) &&
                         p.vrt_has_edge(row, col + 1))
                {
                    p.hrz[row + 1][col] = puzzle::BAN;
                    p.vrt[row][col] = puzzle::BAN;
                }
                else if (p.hrz_has_edge(row + 1, col) &&
                         p.vrt_has_edge(row, col))
                {
                    p.hrz[row][col] = puzzle::BAN;
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
                else if (p.hrz_has_edge(row + 1, col) &&
                         p.vrt_has_edge(row, col + 1))
                {
                    p.hrz[row][col] = puzzle::BAN;
                    p.vrt[row][col] = puzzle::BAN;
                }
                else if (p.vrt_has_edge(row, col) &&
                         p.vrt_has_edge(row, col + 1))
                {
                    p.hrz[row][col] = puzzle::BAN;
                    p.hrz[row + 1][col] = puzzle::BAN;
                }
            }
        }
    }
}

void puzzle_solver::ban_edge_around_three(puzzle &p)
{
    /**
     * . - .
     * | 3 |
     * . b .
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 3 && p.get_lat_banned_edge(row, col) != 1)
            {
                if (p.hrz_has_edge(row, col) &&
                    p.hrz_has_edge(row + 1, col) &&
                    p.vrt_has_edge(row, col))
                {
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
                else if (p.hrz_has_edge(row, col) &&
                         p.hrz_has_edge(row + 1, col) &&
                         p.vrt_has_edge(row, col + 1))
                {
                    p.vrt[row][col] = puzzle::BAN;
                }
                else if (p.vrt_has_edge(row, col) &&
                         p.vrt_has_edge(row, col + 1) &&
                         p.hrz_has_edge(row, col))
                {
                    p.hrz[row + 1][col] = puzzle::BAN;
                }
                else if (p.vrt_has_edge(row, col) &&
                         p.vrt_has_edge(row, col + 1) &&
                         p.hrz_has_edge(row + 1, col))
                {
                    p.hrz[row][col] = puzzle::BAN;
                }
            }
        }
    }
}

void puzzle_solver::ban_edge_around_point(puzzle &p)
{
    /**
     *   x
     * x . x
     *   b
     */
    for (size_t row = 0; row <= p.rows; row++)
    {
        for (size_t col = 0; col <= p.cols; col++)
        {
            if (!p.point_can_up(row, col) &&
                !p.point_can_down(row, col) &&
                !p.point_can_left(row, col) &&
                p.point_can_right(row, col))
            {
                p.hrz[row][col] = puzzle::BAN;
            }
            else if (!p.point_can_up(row, col) &&
                     !p.point_can_down(row, col) &&
                     p.point_can_left(row, col) &&
                     !p.point_can_right(row, col))
            {
                p.hrz[row][col - 1] = puzzle::BAN;
            }
            else if (!p.point_can_up(row, col) &&
                     p.point_can_down(row, col) &&
                     !p.point_can_left(row, col) &&
                     !p.point_can_right(row, col))
            {
                p.vrt[row][col] = puzzle::BAN;
            }
            else if (p.point_can_up(row, col) &&
                     !p.point_can_down(row, col) &&
                     !p.point_can_left(row, col) &&
                     !p.point_can_right(row, col))
            {
                p.vrt[row - 1][col] = puzzle::BAN;
            }
        }
    }
    /**
     *   b
     * - . b
     *   |
     */
    for (size_t row = 0; row <= p.rows; row++)
    {
        for (size_t col = 0; col <= p.cols; col++)
        {
            if (p.point_has_edge_up(row, col) &&
                p.point_has_edge_down(row, col))
            {
                if (p.point_can_left(row, col))
                    p.hrz[row][col - 1] = puzzle::BAN;
                if (p.point_can_right(row, col))
                    p.hrz[row][col] = puzzle::BAN;
            }
            else if (p.point_has_edge_left(row, col) &&
                     p.point_has_edge_right(row, col))
            {
                if (p.point_can_up(row, col))
                    p.vrt[row - 1][col] = puzzle::BAN;
                if (p.point_can_down(row, col))
                    p.vrt[row][col] = puzzle::BAN;
            }
            else if (p.point_has_edge_up(row, col) &&
                     p.point_has_edge_left(row, col))
            {
                if (p.point_can_right(row, col))
                    p.hrz[row][col] = puzzle::BAN;
                if (p.point_can_down(row, col))
                    p.vrt[row][col] = puzzle::BAN;
            }
            else if (p.point_has_edge_up(row, col) &&
                     p.point_has_edge_right(row, col))
            {
                if (p.point_can_left(row, col))
                    p.hrz[row][col - 1] = puzzle::BAN;
                if (p.point_can_down(row, col))
                    p.vrt[row][col] = puzzle::BAN;
            }
            else if (p.point_has_edge_down(row, col) &&
                     p.point_has_edge_left(row, col))
            {
                if (p.point_can_up(row, col))
                    p.vrt[row - 1][col] = puzzle::BAN;
                if (p.point_can_right(row, col))
                    p.hrz[row][col] = puzzle::BAN;
            }
            else if (p.point_has_edge_down(row, col) &&
                     p.point_has_edge_right(row, col))
            {
                if (p.point_can_up(row, col))
                    p.vrt[row - 1][col] = puzzle::BAN;
                if (p.point_can_left(row, col))
                    p.hrz[row][col - 1] = puzzle::BAN;
            }
        }
    }
}

void puzzle_solver::ban_point(puzzle &p)
{
    /**
     *   x
     * x b x
     *   x
     */
    for (size_t row = 0; row <= p.rows; row++)
    {
        for (size_t col = 0; col <= p.cols; col++)
        {
            if (!p.point_can_up(row, col) &&
                !p.point_can_down(row, col) &&
                !p.point_can_left(row, col) &&
                !p.point_can_right(row, col))
            {
                p.banned_point[row][col] = true;
            }
        }
    }
}

void puzzle_solver::link_around_one(puzzle &p)
{
    /**
     * . x .
     * x 1 x
     * . l .
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 1 &&
                !p.complete_lat(row, col) &&
                p.get_lat_banned_edge(row, col) == 3)
            {
                if (p.hrz[row][col] != puzzle::BAN)
                {
                    p.hrz[row][col] = puzzle::LINKED;
                }
                else if (p.hrz[row + 1][col] != puzzle::BAN)
                {
                    p.hrz[row + 1][col] = puzzle::LINKED;
                }
                else if (p.vrt[row][col] != puzzle::BAN)
                {
                    p.vrt[row][col] = puzzle::LINKED;
                }
                else if (p.vrt[row][col + 1] != puzzle::BAN)
                {
                    p.vrt[row][col + 1] = puzzle::LINKED;
                }
            }
        }
    }
}

void puzzle_solver::link_around_two(puzzle &p)
{
    /**
     * . l .
     * x 2 x
     * . l .
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 2 &&
                !p.complete_lat(row, col) &&
                p.get_lat_banned_edge(row, col) == 2)
            {
                if (p.hrz[row][col] == puzzle::BAN &&
                    p.hrz[row + 1][col] == puzzle::BAN)
                {
                    p.vrt[row][col] = puzzle::LINKED;
                    p.vrt[row][col + 1] = puzzle::LINKED;
                }
                else if (p.vrt[row][col] == puzzle::BAN &&
                         p.vrt[row][col + 1] == puzzle::BAN)
                {
                    p.hrz[row][col] = puzzle::LINKED;
                    p.hrz[row + 1][col] = puzzle::LINKED;
                }
                else if (p.hrz[row][col] == puzzle::BAN &&
                         p.vrt[row][col] == puzzle::BAN)
                {
                    p.hrz[row + 1][col] = puzzle::LINKED;
                    p.vrt[row][col + 1] = puzzle::LINKED;
                }
                else if (p.hrz[row][col] == puzzle::BAN &&
                         p.vrt[row][col + 1] == puzzle::BAN)
                {
                    p.hrz[row + 1][col] = puzzle::LINKED;
                    p.vrt[row][col] = puzzle::LINKED;
                }
                else if (p.hrz[row + 1][col] == puzzle::BAN &&
                         p.vrt[row][col] == puzzle::BAN)
                {
                    p.hrz[row][col] = puzzle::LINKED;
                    p.vrt[row][col + 1] = puzzle::LINKED;
                }
                else if (p.hrz[row + 1][col] == puzzle::BAN &&
                         p.vrt[row][col + 1] == puzzle::BAN)
                {
                    p.hrz[row][col] = puzzle::LINKED;
                    p.vrt[row][col] = puzzle::LINKED;
                }
            }
        }
    }
    /**
     *       ?
     *   .   . ?
     *     2  
     * ? .   . x
     *   ?   x
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 2 &&
                !p.complete_lat(row, col))
            {
                if (!p.point_can_up(row, col) && !p.point_can_left(row, col))
                {
                    if (!p.point_can_left(row + 1, col) && p.point_can_down(row + 1, col))
                        p.vrt[row + 1][col] = puzzle::LINKED;
                    if (p.point_can_left(row + 1, col) && !p.point_can_down(row + 1, col))
                        p.hrz[row + 1][col - 1] = puzzle::LINKED;
                    if (!p.point_can_right(row, col + 1) && p.point_can_up(row, col + 1))
                        p.vrt[row - 1][col + 1] = puzzle::LINKED;
                    if (p.point_can_right(row, col + 1) && !p.point_can_up(row, col + 1))
                        p.hrz[row][col + 1] = puzzle::LINKED;
                }
                if (!p.point_can_up(row, col + 1) && !p.point_can_right(row, col + 1))
                {
                    if (!p.point_can_left(row, col) && p.point_can_up(row, col))
                        p.vrt[row - 1][col] = puzzle::LINKED;
                    if (p.point_can_left(row, col) && !p.point_can_up(row, col))
                        p.hrz[row][col - 1] = puzzle::LINKED;
                    if (!p.point_can_right(row + 1, col + 1) && p.point_can_down(row + 1, col + 1))
                        p.vrt[row + 1][col + 1] = puzzle::LINKED;
                    if (p.point_can_right(row + 1, col + 1) && !p.point_can_down(row + 1, col + 1))
                        p.hrz[row + 1][col + 1] = puzzle::LINKED;
                }
                if (!p.point_can_down(row + 1, col + 1) && !p.point_can_right(row + 1, col + 1))
                {
                    if (!p.point_can_right(row, col + 1) && p.point_can_up(row, col + 1))
                        p.vrt[row - 1][col + 1] = puzzle::LINKED;
                    if (p.point_can_right(row, col + 1) && !p.point_can_up(row, col + 1))
                        p.hrz[row][col + 1] = puzzle::LINKED;
                    if (!p.point_can_left(row + 1, col) && p.point_can_down(row + 1, col))
                        p.vrt[row + 1][col] = puzzle::LINKED;
                    if (p.point_can_left(row + 1, col) && !p.point_can_down(row + 1, col))
                        p.hrz[row + 1][col - 1] = puzzle::LINKED;
                }
                if (!p.point_can_down(row + 1, col) && !p.point_can_left(row + 1, col))
                {
                    if (!p.point_can_left(row, col) && p.point_can_up(row, col))
                        p.vrt[row - 1][col] = puzzle::LINKED;
                    if (p.point_can_left(row, col) && !p.point_can_up(row, col))
                        p.hrz[row][col - 1] = puzzle::LINKED;
                    if (!p.point_can_right(row + 1, col + 1) && p.point_can_down(row + 1, col + 1))
                        p.vrt[row + 1][col + 1] = puzzle::LINKED;
                    if (p.point_can_right(row + 1, col + 1) && !p.point_can_down(row + 1, col + 1))
                        p.hrz[row + 1][col + 1] = puzzle::LINKED;
                }
            }
        }
    }
}

void puzzle_solver::link_around_three(puzzle &p)
{
    /**
     * . l .
     * x 3 l
     * . l .
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 3 &&
                !p.complete_lat(row, col) &&
                p.get_lat_banned_edge(row, col) == 1)
            {
                if (p.hrz[row][col] == puzzle::BAN)
                {
                    p.hrz[row + 1][col] = puzzle::LINKED;
                    p.vrt[row][col] = puzzle::LINKED;
                    p.vrt[row][col + 1] = puzzle::LINKED;
                }
                else if (p.hrz[row + 1][col] == puzzle::BAN)
                {
                    p.hrz[row][col] = puzzle::LINKED;
                    p.vrt[row][col] = puzzle::LINKED;
                    p.vrt[row][col + 1] = puzzle::LINKED;
                }
                else if (p.vrt[row][col] == puzzle::BAN)
                {
                    p.hrz[row][col] = puzzle::LINKED;
                    p.hrz[row + 1][col] = puzzle::LINKED;
                    p.vrt[row][col + 1] = puzzle::LINKED;
                }
                else if (p.vrt[row][col + 1] == puzzle::BAN)
                {
                    p.hrz[row][col] = puzzle::LINKED;
                    p.hrz[row + 1][col] = puzzle::LINKED;
                    p.vrt[row][col] = puzzle::LINKED;
                }
            }
        }
    }
    /**
     *   x
     * x . l .
     *   l 3
     *   .   .
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 3 && !p.complete_lat(row, col))
            {
                if (!p.point_can_up(row, col) &&
                    !p.point_can_left(row, col))
                {
                    p.hrz[row][col] = puzzle::LINKED;
                    p.vrt[row][col] = puzzle::LINKED;
                }
                if (!p.point_can_up(row, col + 1) &&
                    !p.point_can_right(row, col + 1))
                {
                    p.hrz[row][col] = puzzle::LINKED;
                    p.vrt[row][col + 1] = puzzle::LINKED;
                }
                if (!p.point_can_down(row + 1, col) &&
                    !p.point_can_left(row + 1, col))
                {
                    p.hrz[row + 1][col] = puzzle::LINKED;
                    p.vrt[row][col] = puzzle::LINKED;
                }
                if (!p.point_can_down(row + 1, col + 1) &&
                    !p.point_can_right(row + 1, col + 1))
                {
                    p.hrz[row + 1][col] = puzzle::LINKED;
                    p.vrt[row][col + 1] = puzzle::LINKED;
                }
            }
        }
    }
    /**
     * - .   .
     *     3 l
     *   . l .
     */
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 0; col < p.cols; col++)
        {
            if (p.lat[row][col] == 3 && !p.complete_lat(row, col))
            {
                if (p.point_has_edge_up(row, col) ||
                    p.point_has_edge_left(row, col))
                {
                    if (p.hrz[row + 1][col] == puzzle::NOT &&
                        p.vrt[row][col + 1] == puzzle::NOT)
                    {
                        p.hrz[row + 1][col] = puzzle::LINKED;
                        p.vrt[row][col + 1] = puzzle::LINKED;
                    }
                }
                if (p.point_has_edge_up(row, col + 1) ||
                    p.point_has_edge_right(row, col + 1))
                {
                    if (p.hrz[row + 1][col] == puzzle::NOT &&
                        p.vrt[row][col] == puzzle::NOT)
                    {
                        p.hrz[row + 1][col] = puzzle::LINKED;
                        p.vrt[row][col] = puzzle::LINKED;
                    }
                }
                if (p.point_has_edge_down(row + 1, col) ||
                    p.point_has_edge_left(row + 1, col))
                {
                    if (p.hrz[row][col] == puzzle::NOT &&
                        p.vrt[row][col + 1] == puzzle::NOT)
                    {
                        p.hrz[row][col] = puzzle::LINKED;
                        p.vrt[row][col + 1] = puzzle::LINKED;
                    }
                }
                if (p.point_has_edge_down(row + 1, col + 1) ||
                    p.point_has_edge_right(row + 1, col + 1))
                {
                    if (p.hrz[row][col] == puzzle::NOT &&
                        p.vrt[row][col] == puzzle::NOT)
                    {
                        p.hrz[row][col] = puzzle::LINKED;
                        p.vrt[row][col] = puzzle::LINKED;
                    }
                }
            }
        }
    }
}

void puzzle_solver::link_around_point(puzzle &p)
{
    /**
     *   x
     * l . x
     *   |
     */
    for (size_t row = 0; row <= p.rows; row++)
    {
        for (size_t col = 0; col <= p.cols; col++)
        {
            if (p.get_conn(row, col) == 1)
            {
                if (p.point_can_up(row, col) &&
                    p.point_can_down(row, col) &&
                    !p.point_can_left(row, col) &&
                    !p.point_can_right(row, col))
                {
                    p.vrt[row - 1][col] = puzzle::LINKED;
                    p.vrt[row][col] = puzzle::LINKED;
                }
                else if (p.point_can_up(row, col) &&
                         !p.point_can_down(row, col) &&
                         p.point_can_left(row, col) &&
                         !p.point_can_right(row, col))
                {
                    p.vrt[row - 1][col] = puzzle::LINKED;
                    p.hrz[row][col - 1] = puzzle::LINKED;
                }
                else if (p.point_can_up(row, col) &&
                         !p.point_can_down(row, col) &&
                         !p.point_can_left(row, col) &&
                         p.point_can_right(row, col))
                {
                    p.vrt[row - 1][col] = puzzle::LINKED;
                    p.hrz[row][col] = puzzle::LINKED;
                }
                else if (!p.point_can_up(row, col) &&
                         p.point_can_down(row, col) &&
                         p.point_can_left(row, col) &&
                         !p.point_can_right(row, col))
                {
                    p.vrt[row][col] = puzzle::LINKED;
                    p.hrz[row][col - 1] = puzzle::LINKED;
                }
                else if (!p.point_can_up(row, col) &&
                         p.point_can_down(row, col) &&
                         !p.point_can_left(row, col) &&
                         p.point_can_right(row, col))
                {
                    p.vrt[row][col] = puzzle::LINKED;
                    p.hrz[row][col] = puzzle::LINKED;
                }
                else if (!p.point_can_up(row, col) &&
                         !p.point_can_down(row, col) &&
                         p.point_can_left(row, col) &&
                         p.point_can_right(row, col))
                {
                    p.hrz[row][col - 1] = puzzle::LINKED;
                    p.hrz[row][col] = puzzle::LINKED;
                }
            }
        }
    }
}

bool puzzle_solver::try_draw(puzzle &p)
{
    // horizontal
    for (size_t row = 0; row <= p.rows; row++)
    {
        for (size_t col = 1; col < p.cols; col++)
        {
            if (p.hrz[row][col] == puzzle::NOT)
            {
                puzzle np = p;
                bool no_link = false;
                bool no_ban = false;
                np.hrz[row][col] = puzzle::BAN;
                if (heuristic(np, false) == false)
                {
                    no_ban = true;
                }
                np = p;
                np.hrz[row][col] = puzzle::LINKED;
                if (heuristic(np, false) == false)
                {
                    no_link = true;
                }
                if (no_link && no_ban)
                {
                    return false;
                }
                else if (no_link)
                {
                    p.hrz[row][col] = puzzle::BAN;
                    heuristic(p, false);
                }
                else if (no_ban)
                {
                    p.hrz[row][col] = puzzle::LINKED;
                    heuristic(p, false);
                }
            }
        }
    }
    // vertical
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 1; col <= p.cols; col++)
        {
            if (p.vrt[row][col] == puzzle::NOT)
            {
                puzzle np = p;
                bool no_link = false;
                bool no_ban = false;
                np.vrt[row][col] = puzzle::BAN;
                if (heuristic(np, false) == false)
                {
                    no_ban = true;
                }
                np = p;
                np.vrt[row][col] = puzzle::LINKED;
                if (heuristic(np, false) == false)
                {
                    no_link = true;
                }
                if (no_link && no_ban)
                {
                    return false;
                }
                else if (no_link)
                {
                    p.vrt[row][col] = puzzle::BAN;
                    heuristic(p, false);
                }
                else if (no_ban)
                {
                    p.vrt[row][col] = puzzle::LINKED;
                    heuristic(p, false);
                }
            }
        }
    }
    // around two
    for (size_t row = 0; row < p.rows; row++)
    {
        for (size_t col = 1; col < p.cols; col++)
        {
            if (p.lat[row][col] == 2 &&
                p.lat_edge(row, col) == 0 &&
                p.get_lat_banned_edge(row, col) == 0)
            {
                puzzle np = p;
                int not_allow[6][4] = {0};
                np.hrz[row][col] = puzzle::LINKED;
                np.vrt[row][col] = puzzle::LINKED;
                if (heuristic(np, false) == false)
                {
                    not_allow[0][0] = -1;
                    not_allow[0][1] = -1;
                    not_allow[0][2] = 1;
                    not_allow[0][3] = 1;
                }
                np = p;
                np.hrz[row][col] = puzzle::LINKED;
                np.vrt[row][col + 1] = puzzle::LINKED;
                if (heuristic(np, false) == false)
                {
                    not_allow[1][0] = 1;
                    not_allow[1][1] = -1;
                    not_allow[1][2] = -1;
                    not_allow[1][3] = 1;
                }
                np = p;
                np.hrz[row + 1][col] = puzzle::LINKED;
                np.vrt[row][col + 1] = puzzle::LINKED;
                if (heuristic(np, false) == false)
                {
                    not_allow[2][0] = 1;
                    not_allow[2][1] = 1;
                    not_allow[2][2] = -1;
                    not_allow[2][3] = -1;
                }
                np = p;
                np.hrz[row + 1][col] = puzzle::LINKED;
                np.vrt[row][col] = puzzle::LINKED;
                if (heuristic(np, false) == false)
                {
                    not_allow[3][0] = -1;
                    not_allow[3][1] = 1;
                    not_allow[3][2] = 1;
                    not_allow[3][3] = -1;
                }
                np = p;
                np.hrz[row][col] = puzzle::LINKED;
                np.hrz[row + 1][col] = puzzle::LINKED;
                if (heuristic(np, false) == false)
                {
                    not_allow[4][0] = 1;
                    not_allow[4][1] = -1;
                    not_allow[4][2] = 1;
                    not_allow[4][3] = -1;
                }
                np = p;
                np.vrt[row][col] = puzzle::LINKED;
                np.vrt[row][col + 1] = puzzle::LINKED;
                if (heuristic(np, false) == false)
                {
                    not_allow[5][0] = -1;
                    not_allow[5][1] = 1;
                    not_allow[5][2] = -1;
                    not_allow[5][3] = 1;
                }
                int no_cnt[4] = {0};
                int link_cnt[4] = {0};
                for (size_t i = 0; i < 6; i++)
                {
                    for (size_t j = 0; j < 4; j++)
                    {
                        no_cnt[j] += (not_allow[i][j] == -1 ? 1 : 0);
                        link_cnt[j] += (not_allow[i][j] == 1 ? 1 : 0);
                    }
                }
                if (no_cnt[0] == 3)
                {
                    p.vrt[row][col] = puzzle::BAN;
                }
                if (no_cnt[1] == 3)
                {
                    p.hrz[row][col] = puzzle::BAN;
                }
                if (no_cnt[2] == 3)
                {
                    p.vrt[row][col + 1] = puzzle::BAN;
                }
                if (no_cnt[3] == 3)
                {
                    p.hrz[row + 1][col] = puzzle::BAN;
                }
                if (link_cnt[0] == 3)
                {
                    p.vrt[row][col] = puzzle::LINKED;
                }
                if (link_cnt[1] == 3)
                {
                    p.hrz[row][col] = puzzle::LINKED;
                }
                if (link_cnt[2] == 3)
                {
                    p.vrt[row][col + 1] = puzzle::LINKED;
                }
                if (link_cnt[3] == 3)
                {
                    p.hrz[row + 1][col] = puzzle::LINKED;
                }
                heuristic(p, false);
            }
        }
    }
    return true;
}

void puzzle_solver::DFS(puzzle &p)
{
    // Start with one line
    for (size_t row = 0; row <= p.rows; row++)
    {
        for (size_t col = 1; col <= p.cols; col++)
        {
            if (!p.banned_point[row][col] && p.get_conn(row, col) == 1)
            {
                go_without_line(p, row, col, row, col, row, col);
                return;
            }
        }
    }
    // No line on this map
    // For every points find all solutions
    for (size_t row = 0; row <= p.rows; row++)
    {
        // Optimized
        for (size_t col = 1; col <= p.cols; col += 2)
        {
            go_without_line(p, row, col, row, col, row, col);
            // set point banned
            p.banned_point[row][col - 1] = true;
            p.banned_point[row][col] = true;
            if (col + 1 == p.cols)
                p.banned_point[row][col + 1] = true;
        }
    }
}


void puzzle_solver::go_with_line(puzzle &p,
                                 const int &start_r, const int &start_c,
                                 int src_p_r, int src_p_c,
                                 int dst_p_r, int dst_p_c)
{
    while (p.get_conn(dst_p_r, dst_p_c) == 2) // with line
    {
        // If solved
        if (dst_p_r == start_r && dst_p_c == start_c)
        {
            // Do final check
            if (p.is_fin() && p.is_correct())
            {
                // Print solution
                const auto result = p.to_string();
                if (puzzle_results.find(result) == puzzle_results.end())
                {
                    puzzle_results.insert(result);
                    // cout << result;
                    PrintGra();
                }
            }
            return;
        }
        // one step
        if (p.point_can_up(dst_p_r, dst_p_c) &&
            p.vrt_has_edge(dst_p_r - 1, dst_p_c) &&
            dst_p_r - 1 != src_p_r)
        {
            src_p_r = dst_p_r;
            src_p_c = dst_p_c;
            --dst_p_r;
        }
        else if (p.point_can_down(dst_p_r, dst_p_c) &&
                 p.vrt_has_edge(dst_p_r, dst_p_c) &&
                 dst_p_r + 1 != src_p_r)
        {
            src_p_r = dst_p_r;
            src_p_c = dst_p_c;
            ++dst_p_r;
        }
        else if (p.point_can_left(dst_p_r, dst_p_c) &&
                 p.hrz_has_edge(dst_p_r, dst_p_c - 1) &&
                 dst_p_c - 1 != src_p_c)
        {
            src_p_r = dst_p_r;
            src_p_c = dst_p_c;
            --dst_p_c;
        }
        else if (p.point_can_right(dst_p_r, dst_p_c) &&
                 p.hrz_has_edge(dst_p_r, dst_p_c) &&
                 dst_p_c + 1 != src_p_c)
        {
            src_p_r = dst_p_r;
            src_p_c = dst_p_c;
            ++dst_p_c;
        }
    }
    // without line
    go_without_line(p,
                    start_r, start_c,
                    src_p_r, src_p_c,
                    dst_p_r, dst_p_c);
}

void puzzle_solver::go_without_line(puzzle &p,
                                    const int &start_r, const int &start_c,
                                    const int &src_p_r, const int &src_p_c,
                                    const int &dst_p_r, const int &dst_p_c)
{
    if (p.point_can_up(dst_p_r, dst_p_c) &&
        p.vrt[dst_p_r - 1][dst_p_c] == puzzle::NOT) // try draw up
    {
        draw_line(p,
                  start_r, start_c,
                  dst_p_r, dst_p_c,
                  dst_p_r - 1, dst_p_c);
    }
    if (p.point_can_down(dst_p_r, dst_p_c) &&
        p.vrt[dst_p_r][dst_p_c] == puzzle::NOT) // try draw down
    {
        draw_line(p,
                  start_r, start_c,
                  dst_p_r, dst_p_c,
                  dst_p_r + 1, dst_p_c);
    }
    if (p.point_can_left(dst_p_r, dst_p_c) &&
        p.hrz[dst_p_r][dst_p_c - 1] == puzzle::NOT) // try draw left
    {
        draw_line(p,
                  start_r, start_c,
                  dst_p_r, dst_p_c,
                  dst_p_r, dst_p_c - 1);
    }
    if (p.point_can_right(dst_p_r, dst_p_c) &&
        p.hrz[dst_p_r][dst_p_c] == puzzle::NOT) // try draw right
    {
        draw_line(p,
                  start_r, start_c,
                  dst_p_r, dst_p_c,
                  dst_p_r, dst_p_c + 1);
    }
}

void puzzle_solver::draw_line(puzzle p,
                              const int &start_r, const int &start_c,
                              const int &src_p_r, const int &src_p_c,
                              const int &dst_p_r, const int &dst_p_c)
{
    if (src_p_r == dst_p_r) // previous go horizontally
    {
        int h_r, h_c;
        if (src_p_c > dst_p_c) // previous go left
        {
            h_r = dst_p_r;
            h_c = dst_p_c;
        }
        else // previous go right
        {
            h_r = src_p_r;
            h_c = src_p_c;
        }
        // Draw line
        p.hrz[h_r][h_c] = puzzle::LINKED;
        // Check lattice
        if (!p.hrz_sat(h_r, h_c))
            return;
    }
    else // previous go vertically
    {
        int v_r, v_c;
        if (src_p_r > dst_p_r) // previous go up
        {
            v_r = dst_p_r;
            v_c = dst_p_c;
        }
        else // previous go down
        {
            v_r = src_p_r;
            v_c = src_p_c;
        }
        // Draw line
        p.vrt[v_r][v_c] = puzzle::LINKED;
        // Check lattice
        if (!p.vrt_sat(v_r, v_c))
            return;
    }
    // Check connectivity
    if (p.get_conn(dst_p_r, dst_p_c) > 2 || p.get_conn(dst_p_r, dst_p_c) == 0)
        return;
    // Do heuristic
    if (heuristic(p) == false)
        return;
    // If solved
    if (dst_p_r == start_r && dst_p_c == start_c)
    {
        // Do final check
        if (p.is_fin() && p.is_correct())
        {
            // Print solution
            const auto result = p.to_string();
            if (puzzle_results.find(result) == puzzle_results.end())
            {
                puzzle_results.insert(result);
                // cout << result;
                PrintGra();
            }
        }
        return;
    }
    // Go next point
    if (p.get_conn(dst_p_r, dst_p_c) == 2)
    {
        go_with_line(p, start_r, start_c, src_p_r, src_p_c, dst_p_r, dst_p_c);
    }
    else // 1
    {
        go_without_line(p, start_r, start_c, src_p_r, src_p_c, dst_p_r, dst_p_c);
    }
}

void PrintGra(){
    int x=start.first,y=start.second;
    pair<int,int> pre={x,y};
    int cnt=0;
    do{
        if(x+1<an && ans[x+1][y]=='_' && make_pair(x+2,y)!=pre){
            linkedEdge[x/2][y/2][x/2+1][y/2]=true;
            linkedEdge[x/2+1][y/2][x/2][y/2]=true;
            pre={x,y};
            x+=2;
        }else if(x-1>=0 && ans[x-1][y]=='_' && make_pair(x-2,y)!=pre){
            linkedEdge[x/2][y/2][x/2-1][y/2]=true;
            linkedEdge[x/2-1][y/2][x/2][y/2]=true;
            pre={x,y};
            x-=2;
        }else if(y+1<am && ans[x][y+1]=='_' && make_pair(x,y+2)!=pre){
            linkedEdge[x/2][y/2][x/2][y/2+1]=true;
            linkedEdge[x/2][y/2+1][x/2][y/2]=true;
            pre={x,y};
            y+=2;
        }else if(y-1>=0 && ans[x][y-1]=='_' && make_pair(x,y-2)!=pre){
            linkedEdge[x/2][y/2][x/2][y/2-1]=true;
            linkedEdge[x/2][y/2-1][x/2][y/2]=true;
            pre={x,y};
            y-=2;
        }
    }while(make_pair(x,y)!=start);
    
    for(int i=0;i<m;i++){
        cout << "." << (CheckLinkedEdge(0,i,0,i+1)?"___":"   ");
    }
    cout << ".\n";
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout << (CheckLinkedEdge(i,j,i+1,j)?'|':' ') << ' ' << (Map[i][j]!=-1?char(Map[i][j]+'0'):' ') << ' ';
        }
        cout << (CheckLinkedEdge(i,m,i+1,m)?'|':' ') << '\n';

        for(int j=0;j<m;j++){
            cout << (CheckLinkedEdge(i,j,i+1,j)?'!':'.') << (CheckLinkedEdge(i+1,j,i+1,j+1)?"___":"   ");
        }

        cout << (CheckLinkedEdge(i+1,m,i,m)?'!':'.') << '\n';
    }
}

int main(int argc, char **argv)
{
    ifstream puzzle_file(argv[1]);

    puzzle_solver ps;
    ps.read_puzzle(puzzle_file);
    ps.solve();
    return 0;
}