#include <iostream>
#include <vector>
#include <stdexcept>
#include <SDL.h>
#include "SDL2_gfxPrimitives.h"

Uint32 timer(Uint32 ms, void* param) {
    SDL_Event ev;
    ev.type = SDL_USEREVENT;
    SDL_PushEvent(&ev);
    return ms;
}

const int WINDOW_SIZE = 720;

SDL_Event ev;
SDL_Renderer *sdlRenderer;
SDL_TimerID sdlTimer;

class Queen {
    unsigned row;
    unsigned column;
public:
    Queen(unsigned i, unsigned j) : row(i), column(j) {
        /* Empty ctor */
    }
    
    unsigned get_row() const {
        return row;
    }
    
    bool is_on(unsigned i, unsigned j) const {
        return (row == i && column == j);
    }
    
    bool is_in_column(unsigned i) const {
        return column == i;
    }
    
    /* Two queens are equal if they're in the same position */
    bool operator==(Queen const& rhs) const {
        return (row == rhs.row && column == rhs.column);
    }
    
    /* Two queens threaten each other if they're in the
     * same row, in the same column, or they are diagonal
     * to each other */
    bool threatens(Queen const& rhs) const {
        return (row == rhs.row ||
                column == rhs.column ||
                abs(row-rhs.row) == abs(column-rhs.column)
               );
    }
};

template <unsigned N>
class Board {
    std::vector<Queen> queens;
    
    /* These are member variables so that printing and
     * drawing functions can access them too, not just
     * the solving function */
    unsigned current_column;
    unsigned current_row;
    
    /* Check if the current board setup is a solution
     * for the problem */
    bool solved() {
        /* If there aren't enough queens */
        if(queens.size() != N) {
            return false;
        }
        
        /* If there are queens that threaten each other,
         * this isn't supposed to happen while the solving
         * algorithm is running, but it's worth a safety
         * check */
        for(auto& q1 : queens) {
            for(auto& q2 : queens) {
                if(&q1 != &q2 && q1.threatens(q2)) {
                    return false;
                }
            }
        }
        
        /* If none of the above, the board is solved */
        return true;
    }
    
    /* Check if there's a queen on a certain square,
     * used for printing and drawing */
    bool queen_on(unsigned i, unsigned j) {
        for(auto q : queens) {
            if(q.is_on(i,j)) {
                return true;
            }
        }
        return false;
    }
    
    /* Find the row index of the queen in a certain column */
    unsigned find_queen_in_column(unsigned j) {
        for(auto q : queens) {
            if(q.is_in_column(j)) {
                return q.get_row();
            }
        }
        
        throw std::runtime_error("Queen is missing!");
        return 0;
    }
    
public:
    Board() : current_column(0), current_row(0) {
        /* Empty ctor */
    }
    
    /* Function for printing the current board and status
     * into the console */
    void print() {
        for(unsigned i = 0; i < N; i++) {
            for(unsigned j = 0; j < N; j++) {
                if(current_row == i && current_column == j)
                    std::cout << "X";
                else
                    std::cout << (queen_on(i,j) ? 'O' : '.');
            }
            std::cout << std::endl;
        }
        
        if(solved()) {
            std::cout << "Solved" << std::endl;
        }
        else {
            std::cout << "Not solved yet" << std::endl;
        }
    }
    
    /* Function for drawing current board on screen */
    void draw() {
        double square_size = (double)WINDOW_SIZE / N;
        
        for(unsigned i = 0; i < N; i++) {
            for(unsigned j = 0; j < N; j++) {
                /* Light squares */
                if((i+j)%2 == 0) {
                    boxColor(sdlRenderer, j*square_size, i*square_size, (j+1)*square_size, (i+1)*square_size, 0xDDDDDDFF);
                }
                /* Dark squares */
                else {
                    boxColor(sdlRenderer, j*square_size, i*square_size, (j+1)*square_size, (i+1)*square_size, 0x222222FF);
                }
                
                /* Current square */
                if(current_row == i && current_column == j) {
                    /* Filled circle */
                    filledCircleColor(sdlRenderer, j*square_size+square_size/2, i*square_size+square_size/2, square_size/2-10, 0x009933FF);
                    /* Antialiased outline, makes the circles look nicer */
                    aacircleColor(sdlRenderer, j*square_size+square_size/2, i*square_size+square_size/2, square_size/2-10, 0x009933FF);
                }
                /* Square that has a queen */
                else if(queen_on(i,j)) {
                    /* Same as above but different colour */
                    filledCircleColor(sdlRenderer, j*square_size+square_size/2, i*square_size+square_size/2, square_size/2-10, 0x9A1919FF);
                    aacircleColor(sdlRenderer, j*square_size+square_size/2, i*square_size+square_size/2, square_size/2-10, 0x9A1919FF);
                }
            }
            std::cout << std::endl;
        }
        
        /* Show changes on screen */
        SDL_RenderPresent(sdlRenderer);
    }
    
    /* Waits until the next timer event */
    bool delay() {
        while(SDL_WaitEvent(&ev)) {
            if(ev.type == SDL_QUIT) {
                return true;
            }
            else if(ev.type == SDL_USEREVENT) {
                return false;
            }
        }
        
        /* Dismiss warning */
        return false;
    }
    
    /* Main algorithm */
    /* Returns true if it was cancelled by user */
    /* Returns false if it finished running */
    bool solve() {
        /* Draw and delay*/
        draw();
        
        if(delay()) {
            return true;
        }
        
        /* This case doesn't make sense */
        if(N == 0) {
            std::cout << "Huh?" << std::endl;
            return false;
        }
        
        while(!solved()) {
            /* Draw and delay*/
            draw();
            
            if(delay()) {
                return true;
            }
            
            /* Assume that our current position is clear */
            bool position_clear = true;
            
            /* Create a candidate in the current position to
             * check existing queens against */
            Queen candidate(current_row, current_column);
            
            /* Check if our current position is suitable for
             * placing the next queen here */
            for(auto q : queens) {
                if(q.threatens(candidate)) {
                    position_clear = false;
                    break;
                }
            }
            
            /* If current position determined by current_row and
             * current_column is clear to place a queen in */
            if(position_clear) {
                /* Put candidate on the board */
                queens.push_back(candidate);
                /* Proceed to next column */
                current_column++;
                /* Reset row position */
                current_row = 0;
            }
            /* Current position is blocked, but there are squares
             * left in the current column */
            else if(current_row < N-1) {
                /* Move position to next row */
                current_row++;
            }
            /* There aren't any squares left in this column and
             * we didn't find a suitable one */
            else {
                /* Step back a column */
                current_column--;
                /* Current position updated to just below the queen
                 * that's in this previous (now current) column */
                while((current_row = find_queen_in_column(current_column) + 1) >= N) {
                    /* If this new position is out of bounds, attempt
                     * to move back another column */
                    if(current_column != 0) {
                        current_column--;
                    }
                    /* If we're in the first column, there's nowhere
                     * left to step back - end search here */
                    else {
                        std::cout << "No solution found" << std::endl;
                        return false;
                    }
                    /* Remove queen that we stepped in the position below */
                    queens.pop_back();
                }
                /* Remove queen that we stepped in the position below */
                queens.pop_back();
            }
        }
        
        draw();
        return false;
    }
};

int main(int argc, char *argv[]) {
    SDL_Window *sdlWindow;
    try {
        sdlWindow = SDL_CreateWindow("Queens",
                                     SDL_WINDOWPOS_UNDEFINED,
                                     SDL_WINDOWPOS_UNDEFINED,
                                     WINDOW_SIZE, WINDOW_SIZE,
                                     0);
        if(sdlWindow == NULL) throw 1;
        
        sdlRenderer = SDL_CreateRenderer(sdlWindow, -1, 0);
        if(sdlRenderer == NULL) throw 1;
    }
    catch(int error) {
        SDL_Quit();
        return error;
    }
    
    /* Setting a very small (<10) value here crashes the program
     * after a while, especially when large (10+) boards,
     * but recommended min value is still around 20 */
    sdlTimer = SDL_AddTimer(50, timer, nullptr);
    
    /* Change board size here */
    Board<8> b;
    bool result;
    
    try {
        result = b.solve();
    }
    catch(std::exception& x) {
        std::cerr << x.what() << std::endl;
    }
    
    SDL_RemoveTimer(sdlTimer);
    
    /* If the program wasn't force quitted by user */
    if(!result) {
        /* Wait until a key is pressed or windows is closed */
        while(SDL_WaitEvent(&ev) && ev.type != SDL_QUIT && ev.type != SDL_KEYDOWN);
    }
    
    SDL_Quit();
    
    return 0;
}