/**
 * Author Malte Pagel
 * Free to use for any purpose
 * Runability or usefulness is NOT guaranteed
 */


document.write("<sty" + "le type='text/css'>");
document.write(".table_cell {width: 40px;height: 40px;text-align: center;color: #FF8000;}.table_cell.empty {background-color: #EEEEEE;}.table_cell.full_dark {background-color: #282828;}.table_cell.full_light {background-color: #A5A5A5;}.table_cell.grey, .table_cell.empty.grey {color: gray;font-size: 18px;}");
document.write("</style>");

function personal_debug (message) {
    console.log(message);
    //iD("instruction").innerHTML = message;
}

document.write("<center><span id='instruction'>Klicken Sie auf ein Feld, auf dem der Springer beginnen soll</span><br><br></center>");
                
var upper_array = [ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
                    'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P'];
var table_cols = 8;

document.write("<center><table border='1' rules='none' style='color: #FF8000; font-size: 24px; border: thin ridge #F2F2F2'>");

for ( var table_count = 0; table_count < table_cols; table_count++ ) {
    document.write("<tr>");
    document.write("<td class='table_cell' style='padding-right: 8px; color: silver; background-color: #F6F6F6'>" + (table_cols - table_count) + "</td>");
    for ( var inner_count = 0; inner_count < table_cols; inner_count ++ ) {
        document.write("<td id='cell_" + upper_array[inner_count] + (table_cols - table_count) + "' class='table_cell");
        if ( (table_count + inner_count) % 2 != 0 )
            document.write(" empty");
        document.write("' style='cursor: pointer' onclick='set_start(" + inner_count + ", " + (table_cols - table_count - 1) + ")'>");
        document.write("</td>");
    }
    document.write("</tr>");
}
document.write("<tr><td class='table_cell' style='padding-right: 8px; background-color: #F6F6F6'></td>");
for ( table_count = 0; table_count < table_cols; table_count++ ) {
    document.write("<td class='table_cell' style='padding-top: 8px; color: silver; background-color: #F6F6F6'>");
    document.write(upper_array[table_count]);
    document.write("</td>");
}
document.write("</tr>");
document.write("</table></center>");
 

//
//  KnightPosition: example.js
//
//  Created 2013/11 by Malte Pagel
//  Copyright (c) 2013 Malte Pagel. All rights reserved.
//


var letters = [ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P' ];
var column = -1;
var row = -1;
var cols = 8;
var start_position = null;

var knight_count = 0;
var knight_number = 0;
var memory_count = 0;
var x_move = [ 1, 2, 2, 1, -1, -2, -2, -1, 1, 2, 2, 1, -1, -2 ];
var y_move = [ -2, -1, 1, 2, 2, 1, -1, -2, -2, -1, 1, 2, 2, 1 ];
var reachable_positions_offset = 0;
var reachable_positions_offset_set = 0;

var MEMORY_LIMIT = 4096;

function show_cell_content (col, row, content) {
    if ( content )
        iD("cell_" + letters[col] + (row + 1)).innerHTML = content;
    else
        iD("cell_" + letters[col] + (row + 1)).innerHTML = "";
}

/**
 * Pseudoclass
 */
function KnightPosition (column, row, num_cols, collection) {
    
    /**
     * Public Variables
     */
    //this.column, this.row, this.has_knight, this.center_distance;
    //this.next_position;
    
    /**
     * Private Variables
     */
    var lower_or_equal;
    var previous_position;
    var first_collected_position, last_collected_position, first_position_to_try, last_position_to_try;
    var myself = this;
    
    
    /**
     * Public Functions
     */
    this.set_knight_and_start_search = function (last_position) {
        knight_number++;
        this.has_knight = 1;
        previous_position = last_position;
        
        show_cell_content(this.column, this.row, knight_number);
        
        last_position_to_try = null;
        first_position_to_try = null;
        
        order_reachable_positions();
        
        if ( !first_position_to_try ) {
            go_back();
            return;
        }
        
        do_search();
    };
    
    this.get_num_possibilities = function () {
        var possibilities = 0;

        if ( !first_collected_position )
            return 0;
        
        tmp_position = first_collected_position;
        while ( tmp_position ) {
            if ( !tmp_position.possible_position.has_knight )
                possibilities++;
            tmp_position = tmp_position.basic_next;
        }

        return possibilities;
    };
    
    this.another_try_from_above = function () {
        myself.next_position.next_position = null;
        
        if ( !first_position_to_try ) {
            show_cell_content(myself.column, myself.row, 0);
            go_back();
            return;
        }
        
        if ( memory_count > MEMORY_LIMIT || (memory_count && knight_number == 1) ) {
            if ( knight_number == 1 )
                personal_debug( "Does not seem to be solvable" );
            else
                personal_debug( "Too much recursion, I'm giving up; knights: " + knight_number + " / " + (cols * cols) );
            return;
        }
        
        personal_debug( "I am at " + letters[myself.column] + (myself.row + 1) + " (try " + memory_count + "); "
            + letters[myself.next_position.column] + (myself.next_position.row + 1) + " was bad; trying "
            + letters[first_position_to_try.possible_position.column]
            + (first_position_to_try.possible_position.row + 1) );
        
        do_search();
    };
    
    
    /**
     * Private Functions
     */
    function do_search () {
        var position_to_try = first_position_to_try;
        
        myself.next_position = position_to_try.possible_position;
        
        first_position_to_try = (first_position_to_try.next) ? first_position_to_try.next : null;
        
        if ( knight_number >= (cols * cols - 1) ) {
            make_grey();
            show_cell_content(myself.next_position.column, myself.next_position.row, (cols * cols));
            if ( memory_count )
                personal_debug( "\t* SOLVED *" );
            show_solution(start_position);
            return;
        }
        
        myself.next_position.set_knight_and_start_search(myself);
    }
    
    function order_reachable_positions () {
        var possibilities, success;
        
        var tmp_position_to_add, tmp_tmp_position, tmp_tmp_tmp_position;
        
        var tmp_position = first_collected_position;
        
        while ( tmp_position != null ) {
            
            possibilities = tmp_position.possible_position.get_num_possibilities();
            
            if ( !tmp_position.possible_position.has_knight ) {

                if ( !possibilities )
                    possibilities = cols * 8;

                tmp_position_to_add = tmp_position;
                tmp_position_to_add.heuristic = (cols * possibilities + tmp_position.possible_position.center_distance);
                tmp_position_to_add.next = null;

                if ( !first_position_to_try ) {
                    first_position_to_try = tmp_position_to_add;
                    last_position_to_try = first_position_to_try;
                }
                else {
                    tmp_tmp_position = first_position_to_try;
                    success = 0;
                    while ( tmp_tmp_position && !success ) {
                        if ( tmp_position_to_add.heuristic < tmp_tmp_position.heuristic || (lower_or_equal && tmp_position_to_add.heuristic == tmp_tmp_position.heuristic) ) {
                            if ( tmp_tmp_position == first_position_to_try ) {
                                tmp_position_to_add.next = tmp_tmp_position;
                                first_position_to_try = tmp_position_to_add;
                                success = 1;
                            }
                            else {
                                tmp_tmp_tmp_position = first_position_to_try;
                                while ( tmp_tmp_tmp_position.next != tmp_tmp_position )
                                    tmp_tmp_tmp_position = tmp_tmp_tmp_position.next;
                                tmp_position_to_add.next = tmp_tmp_tmp_position.next;
                                tmp_tmp_tmp_position.next = tmp_position_to_add;
                                success = 1;
                            }
                        }
                        tmp_tmp_position = tmp_tmp_position.next;
                    }
                    if ( !success ) {
                        last_position_to_try.next = tmp_position_to_add;
                        last_position_to_try = tmp_position_to_add;
                    }
                }
            }
            
            tmp_position = tmp_position.basic_next;
        }
    }
    
    function go_back () {
        memory_count++;
        knight_number--;
        myself.has_knight = 0;
        
        setTimeout(previous_position.another_try_from_above, 21);
    }
    
    function add_to_reachable_positions (position) {
        var position_data = {};
        
        position_data.possible_position = position;
        position_data.heuristic = 0;
        position_data.next = null;
        position_data.basic_next = null;
        
        if ( !first_collected_position ) {
            first_collected_position = position_data;
            last_collected_position = first_collected_position;
        }
        else {
            last_collected_position.basic_next = position_data;
            last_collected_position = position_data;
        }
    }
    
    function fill_reachable_positions () {
        var i, x, y;
        var tmp_position = null;
        
        for ( i = reachable_positions_offset; i < (8 + reachable_positions_offset); i++ ) {
            x = column + x_move[i];
            y = row + y_move[i];
            
            if ( x < 0 || x > (cols - 1) || y < 0 || y > (cols - 1) )
                continue;
            if ( !collection[x][y] ) {
                tmp_position = new KnightPosition(x, y, cols, collection);
                add_to_reachable_positions(tmp_position);
            }
            else
                add_to_reachable_positions(collection[x][y]);
        }
    }
    
    
    /**
     * Constructor
     */
    collection[column][row] = this;
    
    this.column = column;
    this.row = row;
    this.has_knight = 0;
    
    this.next_position = null;
    previous_position = null;
    
    first_collected_position = null;
    last_collected_position = null;
    
    this.center_distance = Math.abs((cols - 1) - (2 * column) - (2 * row));
    
    if ( !reachable_positions_offset_set ) {
        if ( column < 4 ) {
            if ( row < 4 )
                reachable_positions_offset = 4;
            else
                reachable_positions_offset = 6;
        }
        else
            if ( row < 4 )
                reachable_positions_offset = 2;
        reachable_positions_offset_set = 1;
    }
    
    fill_reachable_positions();
    
    knight_count++;
    
    lower_or_equal = ( Math.floor(Math.random() * (cols * cols + this.center_distance + 1 - knight_count)) == 0 ) ? 1 : 0;
    
    //personal_debug( "KnightPosition number " + knight_count + " constructed at " + letters[column] + (row + 1) );
}

/*  */

function make_grey () {
    for ( var i = 0; i < cols; i++ )
        for ( var j = 0; j < cols; j++ ) {
            iD("cell_" + letters[i] + (j + 1)).style.cursor = "help";
            iD("cell_" + letters[i] + (j + 1)).className = ((i + j) % 2 != 0) ? "table_cell grey" : "table_cell empty grey";
        }
}

function show_solution (position) {
    var c = position.column;
    var r = position.row;
    
    iD("cell_" + letters[c] + (r + 1)).className = ((c + r) % 2 != 0) ? "table_cell full_light" : "table_cell full_dark";
    
    if ( position.next_position )
        setTimeout(show_solution, 333, position.next_position);
    else {
        personal_debug( "\t************" );
        personal_debug( "\t* FINISHED *" );
        personal_debug( "\t************" );
        
        for ( var i = 0; i < cols; i++ )
            for ( var j = 0; j < cols; j++ )
                iD("cell_" + letters[i] + (j + 1)).style.cursor = "default";
    }
}

function quasi_main () {
    var i, j;
    
    var complete_collection = [];
    for ( i = 0; i < cols; i++ ) {
        complete_collection[i] = [];
        for ( j = 0; j < cols; j++ )
            complete_collection[i][j] = null;
    }
    
    start_position = new KnightPosition(column, row, cols, complete_collection);
    
    complete_collection = null;
    
    start_position.set_knight_and_start_search(null);
}

function set_start (c, r) {
    if ( column >= 0 )
        return;
    
    column = c;
    row = r;
    
    for ( var i = 0; i < cols; i++ )
        for ( var j = 0; j < cols; j++ )
            iD("cell_" + letters[i] + (j + 1)).style.cursor = "wait";
    
    iD("instruction").innerHTML = "";
    
    quasi_main();
}

//set_start(Math.floor(Math.random() * cols), Math.floor(Math.random() * cols));