| Inhalt | Code | Beispiel |
| C++ | Javascript | Kommentare | Zeilennummern | Midnight |
main.cpp
/**
* Author Malte Pagel
* Free to use for any purpose
* Runability or usefulness is NOT guaranteed
*/
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <stdio.h>
#include <time.h>
using namespace std;
#include "KnightPosition.h"
#define ASK_USER 1
#define COL_MIN 5
#define COL_MAX 16
#define DEFAULT_COLS 8
void ask_user(void);
char letters[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P' };
int cols;
int column;
int row;
void ask_user () {
int i;
char c;
cout << endl;
cout << "How many rows resp. columns (" << COL_MIN << " - " << COL_MAX << ")?" << endl;
scanf("%d", &i);
if ( i < COL_MIN || i > COL_MAX ) {
cout << "Invalid value! Taking " << DEFAULT_COLS << endl;
cols = DEFAULT_COLS;
}
else
cols = i;
cout << "Start in which column ('A' to '" << (letters[cols - 1]) << "')?" << endl;
scanf("%s", &c);
i = (int) c - 97;
if ( i >= 0 && i < cols )
column = i;
else {
i = (int) c - 65;
if ( i >= 0 && i < cols )
column = i;
else {
column = rand() % cols;
cout << "Invalid value! Taking " << letters[column] << endl;
}
}
cout << "Start in which row (1 to " << cols << ")?" << endl;
scanf("%d", &i);
if ( i > 0 && i <= cols )
row = i - 1;
else {
row = rand() % cols;
cout << "Invalid value! Taking " << (row + 1) << endl;
}
}
int main (int argc, char** argv) {
KnightPosition * start_position;
KnightPosition *** complete_collection;
int i, j;
time_t t;
time(&t);
srand((unsigned int) t);
if ( ASK_USER )
ask_user();
else {
cols = DEFAULT_COLS;
column = rand() % cols;
row = rand() % cols;
}
/**
* Matrix of pointers needed for a moment
*/
complete_collection = new KnightPosition**[cols];
for ( i = 0; i < cols; i++ )
complete_collection[i] = new KnightPosition*[cols];
for ( i = 0; i < cols; i++ )
for ( j = 0; j < cols; j++ )
complete_collection[i][j] = NULL;
/**
* 'start_position' is - no one would ever guess this - the field where to start,
* temporarily stored at [column][row] in 'complete_collection'
*/
start_position = new KnightPosition(column, row, cols, complete_collection);
/**
* All fields should be initialized; matrix not needed any longer
*/
delete[](complete_collection);
/**
* Setting a knight on 'start_position' and invoking path search
*/
start_position->set_knight_and_start_search(NULL);
/**
* Preparing show,
* cleaning memory
*/
int ** show_collection = new int*[cols];
for ( i = 0; i < cols; i++ ) {
show_collection[i] = new int[cols];
for ( j = 0; j < cols; j++ )
show_collection[i][j] = 0;
}
i = 0;
KnightPosition * position = start_position;
KnightPosition * position_to_delete;
do {
show_collection[cols - position->row - 1][position->column] = ++i;
position_to_delete = position;
if ( position->next_position )
position = position->next_position;
delete(position_to_delete);
}
while ( position->next_position );
delete(position);
show_collection[cols - position->row - 1][position->column] = ++i;
/**
* Dont' blame me for not using 'cout' consequently -
* formatted output is much more readable
*/
cout << endl;
for ( i = 0; i < cols; i++ ) {
printf("%2d", (cols - i));
cout << " |";
for ( j = 0; j < cols; j++ )
printf("%5d", show_collection[i][j]);
cout << endl;
}
cout << " ";
for ( i = 0; i < cols; i++ )
cout << "-----";
cout << endl;
printf("%4s", " ");
for ( i = 0; i < cols; i++ )
printf("%5c", letters[i]);
cout << endl;
/**
* The result should be visible also on windows systems
*/
#ifdef _WIN32
char c = 'n';
while ( c != 'y' ) {
cout << "Quit application [y/n]?" << endl;
scanf("%s", &c);
}
#endif
return 0;
}
KnightPosition.h
// File: KnightPosition.h
/*
* Author: maltepagel
*
* Created November 2013
*/
#ifndef KNIGHTPOSITION_H
#define KNIGHTPOSITION_H
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
/*
IMPORTANT: HIGHER VALUES MIGHT BREAK THE STACK
*/
#define MEMORY_LIMIT 4096
class KnightPosition {
public:
KnightPosition(int, int, int, KnightPosition***);
virtual ~KnightPosition();
static int knight_count;
static int knight_number;
static long memory_count;
int has_knight;
int column, row;
int center_distance;
KnightPosition * next_position;
void set_knight_and_start_search(KnightPosition*);
int get_num_possibilities(void);
void another_try_from_above(void);
private:
static char letters[];
static int cols;
static int reachable_positions_offset_set;
KnightPosition * previous_position;
struct reachable_position_pointer {
KnightPosition * possible_position;
int heuristic;
struct reachable_position_pointer * next;
struct reachable_position_pointer * basic_next;
};
struct reachable_position_pointer * first_collected_position;
struct reachable_position_pointer * last_collected_position;
struct reachable_position_pointer * first_position_to_try;
struct reachable_position_pointer * last_position_to_try;
int lower_or_equal, reachable_positions_offset;
void fill_reachable_positions(KnightPosition***);
void add_to_reachable_positions(KnightPosition*);
void order_reachable_positions(void);
void do_search(void);
void go_back(void);
};
#endif /* KNIGHTPOSITION_H */
KnightPosition.cpp
// File: KnightPosition.cpp
/*
* Author: maltepagel
*
* Created November 2013
*/
#include "KnightPosition.h"
int KnightPosition::knight_count = 0;
int KnightPosition::knight_number = 0;
int KnightPosition::cols = 0;
long KnightPosition::memory_count = 0;
char KnightPosition::letters[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P' };
int KnightPosition::reachable_positions_offset_set = 0;
/**
* Constructor.
* Takes basic values,
* invokes building of other knight positions,
* memorizes reachable knight positions
*
* @param <int> column, row [where are we?]
* @param <int> num_cols [number rows resp. columns of play table]
* @param <KnightPosition***> collection [matrix to temporarily store knight positions]
*/
KnightPosition::KnightPosition(int column, int row, int num_cols, KnightPosition*** collection) {
collection[column][row] = this;
this->column = column;
this->row = row;
if ( !cols )
cols = num_cols;
has_knight = 0;
next_position = NULL;
previous_position = NULL;
first_collected_position = NULL;
last_collected_position = NULL;
/**
* Maybe you have to write 'center_distance = abs((float) ((cols - 1) - (2 * column) - (2 * row)));'
*/
center_distance = 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;
else
reachable_positions_offset = 0;
}
reachable_positions_offset_set = 1;
}
fill_reachable_positions(collection);
knight_count++;
lower_or_equal = ( rand() % (cols * cols + center_distance + 1 - knight_count) == 0 ) ? 1 : 0;
//cout << "KnightPosition number " << knight_count << " constructed at " << letters[column] << (row + 1) << endl;
}
/**
* Clears all allocated memory
*/
KnightPosition::~KnightPosition() {
struct reachable_position_pointer * tmp_position, * next_tmp_position;
if ( !first_collected_position )
return;
tmp_position = first_collected_position->basic_next;
while ( tmp_position ) {
next_tmp_position = first_collected_position->basic_next->basic_next;
first_collected_position->basic_next = next_tmp_position;
delete(tmp_position);
tmp_position = next_tmp_position;
}
delete(first_collected_position->basic_next);
delete(first_collected_position);
first_collected_position = NULL;
//cout << "KnightPosition " << (cols * cols - --knight_count) << " at " << letters[column] << (row + 1) << " destroyed" << endl;
}
/**
* Counts number of possible jumps to free field (i.e. without knight)
*
* @return <int> [number of possible jumps]
*/
int KnightPosition::get_num_possibilities () {
int possibilities = 0;
if ( !first_collected_position )
return 0;
struct reachable_position_pointer * tmp_position = first_collected_position;
while ( tmp_position ) {
if ( !tmp_position->possible_position->has_knight )
possibilities++;
tmp_position = tmp_position->basic_next;
}
return possibilities;
}
/**
* Important heuristic: positions with more possible moves are worse
* Less important heuristic: positions near the center are worse
*/
void KnightPosition::order_reachable_positions () {
int possibilities, success;
struct reachable_position_pointer * tmp_position_to_add;
struct reachable_position_pointer * tmp_tmp_position;
struct reachable_position_pointer * tmp_tmp_tmp_position;
struct reachable_position_pointer * 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->possible_position = tmp_position->possible_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;
}
}
/**
* Jumps to probably best position.
* Clears this position from list.
* Stops if play table is full
*/
void KnightPosition::do_search () {
struct reachable_position_pointer * position_to_try = first_position_to_try;
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) ) {
cout << endl;
cout << "\t**********" << endl;
cout << "\t* SOLVED *" << endl;
cout << "\t**********" << endl;
cout << endl;
return;
}
next_position->set_knight_and_start_search(this);
}
/**
* Last jump was bad - try the next best or, if there is none, go back
*/
void KnightPosition::another_try_from_above () {
next_position->next_position = NULL;
if ( !first_position_to_try ) {
go_back();
return;
}
if ( memory_count > MEMORY_LIMIT || (memory_count && knight_number == 1) ) {
if ( knight_number == 1 )
cout << "Does not seem to be solvable" << endl;
else
cout << "Too much recursion, I'm giving up; knights: " << knight_number << " / " << (cols * cols) << endl;
return;
}
cout << "I am at " << letters[column] << (row + 1) << " at step " << knight_number << " (" << memory_count << " tries)" << endl;
cout << "I came from " << letters[next_position->column] << (next_position->row + 1) << endl;
cout << "I want to try " << letters[first_position_to_try->possible_position->column] << (first_position_to_try->possible_position->row + 1) << endl;
cout << "---" << endl;
do_search();
}
/**
* Delete this position from list of jumps and go back
*/
void KnightPosition::go_back () {
memory_count++;
knight_number--;
has_knight = 0;
previous_position->another_try_from_above();
}
/**
* Remembers previous position,
* estimates quality of possible jumps,
* invokes jumping (if possible)
*
* @param <KnightPosition*> last_position [position where we came from,
* i.e. previous position in list of jumps]
*/
void KnightPosition::set_knight_and_start_search (KnightPosition* last_position) {
knight_number++;
has_knight = 1;
previous_position = last_position;
last_position_to_try = NULL;
first_position_to_try = NULL;
order_reachable_positions();
if ( !first_position_to_try ) {
go_back();
return;
}
do_search();
}
/**
* Creates a data collection for each reachable position
*
* @param <KnightPosition*> position [to add]
*/
void KnightPosition::add_to_reachable_positions (KnightPosition* position) {
struct reachable_position_pointer * position_data = new reachable_position_pointer;
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;
}
}
/**
* Evaluates possible positions for jumping.
* Adds - if not already there - position to 'collection',
* invokes putting it to list of reachable positions
*
* @param <KnightPosition***> collection [matrix to temporarily store knight positions]
*/
void KnightPosition::fill_reachable_positions (KnightPosition*** collection) {
int x_move[] = { 1, 2, 2, 1, -1, -2, -2, -1, 1, 2, 2, 1, -1, -2 };
int y_move[] = { -2, -1, 1, 2, 2, 1, -1, -2, -2, -1, 1, 2, 2, 1 };
int i, x, y;
KnightPosition * tmp_position;
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]);
}
}