Welcher Code ist einfacher (zu verstehen) - Motivation Springerproblem

[Werner Salomon]

Ja Wahnsinn, da gibt man den Link auf diesen Thread preis (siehe http://www.c-plusplus.net/forum/326676), und schon stürzen sich die Hyänen auf den hingeworfenen Fleischbrocken.
Soviel Feedback in so kurzer Zeit hätte ich mir im Dezember gewünscht.

camper schrieb:

Keiner der die fehlende Unterscheidung zwischen einer Position und einem Bewegungsvektor bemängelt? :p

Danke Camper, endlich mal eine vernünftige Kritik. Ja - der Gedanke war mir selbst beim Schreiben gekommen - nur..

volkard schrieb:

Habs für Vektorrechnung mit dieser Unterscheidung probiert und es war nur umständlich.

.. mir ging es so wie volkard.
Vielleicht reicht es, Pos einfach einen anderen Namen zu geben (Vector2 ?)

volkard schrieb:

... und Pos kriegt dazu ein Brett gezeigt, um mal schnell Brett-Interna anzuschauen(!!!)), also alles da, wo man es nicht erwartet.

Hm - ok. Irgendwann muss wohl mal entschieden werden, ob ein Springerzug noch auf dem Brett landet. Wen fragt man da?
Das Brett könnte entscheiden, ob die Pos gültig ist, wobei X und Y der Pos zur Verfügung stehen müssten. Zugegeben - ich neige dazu, diese zu 'verstecken'. Aber es spielt natürlich keine Rolle, ob ich die Brettgröße mit X() und Y() abhole oder die Koordinaten der Position.
Also am besten wohl - ab in die Methode Brett::setze mit dieser Abfrage - oder?

macht doch selber mal Vorschläge - oder stehe ich mit meiner Meinung hier tatsächlich gänzlich allein, dass dieses Problem durchaus einen objektorientierten Ansatz verträgt.

Ich lege schon mal was vor - mit Beherzigung Eurer Kritik:

// --   das Spinger Problem (nächster Versuch)
#include <cassert>
#include <complex> // das soll ein Position bzw. ein Zug sein ;-)
#include <iomanip> // setw
#include <iostream>
#include <vector>

namespace knight
{
    const std::complex< int > moves[] = {
        {2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1}
    };
}

// --   syntactic suger (spart aber die class/struct Pos)
template< typename T > T X( const std::complex< T >& c ) { return real( c ); }
template< typename T > T Y( const std::complex< T >& c ) { return imag( c ); }

// --   das (Schach)brett
class Board
{
public:
    typedef std::complex< int > pos_type; // absolute & relative Position auf dem Brett
    friend class Move;
    static int const FREE = -1;

    Board( int rows, int columns )
        : rows_( rows )
        , columns_( columns )
        , occupies_( rows_ * columns_, FREE )
        , occupy_counter_( 0 )
    {}

    bool is_free( const pos_type& next_pos ) const
    {
        return ( ( Y(next_pos) >= 0 ) && ( Y(next_pos) < rows_ ) ) && ( ( X(next_pos) >= 0 ) && ( X(next_pos) < columns_ ) )
            && field(next_pos) == FREE;
    }
    bool full() const
    {
        return occupy_counter_ == occupies_.size();
    }

    friend std::ostream& operator<<( std::ostream& out, const Board& b )
    {
        auto pos = begin(b.occupies_);
        for( int row = 0; row < b.rows_; ++row )
        {
            for( int column = 0; column < b.columns_ ; ++column, ++pos )
                out << std::setw(3) << *pos << " |";
            out << std::endl;
        }
        return out << std::endl;
    }

    // --   diese Klasse modelliert einen konkreten Zug des Springers
    //      auf dem Brett 'b' an die Position 'pos'
    class Move
    {
    public:
        Move( Board& b, const Board::pos_type& pos )
            : board_( b )
            , current_field_( board_.field(pos) )
        {
            assert( board_.is_free( pos ) );
            current_field_ = board_.occupy_counter_++;
        }
        ~Move() // mit Löschen des Zuges wird der Zug zurück genommen
        {
            assert( current_field_ == board_.occupy_counter_-1 );
            --board_.occupy_counter_;
            current_field_ = FREE;
        }
    private:
        Board& board_;
        int& current_field_;
    };

private:
    int field( const pos_type& pos ) const
    {
        return occupies_[ Y(pos) * columns_ + X(pos) ];
    }
    int& field( const pos_type& pos )
    {
        return occupies_[ Y(pos) * columns_ + X(pos) ];
    }

    int rows_, columns_; // Brettgröße
    std::vector< int > occupies_; // die (überstrichenen) Felder 
    std::size_t occupy_counter_; // Anzahl der bereits vom Springer überstrichenen Felder
};

template< typename B >
void solve( B& board, typename B::pos_type const& current_position, std::ostream& out )
{
    if( board.is_free( current_position ) )
    {
        typename B::Move move( board, current_position );
        if( board.full() )
            out << board << std::endl;
        else
            for( auto next_move: knight::moves )
                solve( board, current_position + next_move, out );
    }
}

int main()
{
    using namespace std;
    cout << "Bitte Feldgroesse eingeben: " << endl;
    int zeilen, spalten;
    cin >> zeilen >> spalten;
    Board board( zeilen, spalten );
    solve( board, Board::pos_type(), cout );
    return 0;
}

Gruß
Werner

[volkard]

Sowas kompliziertes schreibe ich normalerweise nicht von oben nach unten, sondern mache es zuerst laufend und bastele dann dran weiter.

Erster Gedanke: Ein vector<int> und eine rekursive solve(int x,int y,int zugNummer,vector<int&> brett,int sizeX,int SizeY)… vor dem Tippen schon verworfen, die lauter Sachen stopfe ich in eine Klasse um Übergaben zu sparen.

Zweite Version: Alles macht eine Klasse Brett.

Na, die hatte oben alle Brett-Funktionen und unten die drei Solver-Funktionen, das ließ sich mal schnell trennen.
Dritter Version:

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

class Board {
	int const sizeX;
	int const sizeY;
	vector<int> fields;
	int moveNo;
public:
	Board(int sizeX,int sizeY):
		sizeX(sizeX),
		sizeY(sizeY),
		fields(sizeX* sizeY,0),
		moveNo(0) {
	}
	int getSizeX() {
		return sizeX;
	}
	int getSizeY() {
		return sizeY;
	}
	int& at(int x,int y) {
		return fields[y*sizeX+x];
	}
	bool isFull() {
		return moveNo==sizeX*sizeY;
	}
	bool isMoveValid(int x,int y) {
		if(not(0<=x and x<sizeX)) return false;
		if(not(0<=y and y<sizeY)) return false;
		if(at(x,y)!=0) return false;
		return true;
	}
	void doMove(int x,int y) {
		++moveNo;
		at(x,y)=moveNo;
	}
	void undoMove(int x,int y) {
		at(x,y)=0;
		--moveNo;
	}
	void print() {
		for(int y=0; y!=sizeY; ++y) {
			cout<<'|';
			for(int x=0; x!=sizeX; ++x)
				cout<<setw(3)<<at(x,y)<<" |";
			cout<<'\n';
		}
		cout<<'\n';
	}
};

class Solver {
	Board board;
public:
	Solver(int sizeX,int sizeY):
		board(sizeX,sizeY) {
	}
	void search(int x,int y) {
		if(board.isFull()) {
			board.print();
			return;
		}
		moveAndSearch(x-1,y-2),moveAndSearch(x+1,y-2);
		moveAndSearch(x-2,y-1),moveAndSearch(x+2,y-1);
		moveAndSearch(x-2,y+1),moveAndSearch(x+2,y+1);
		moveAndSearch(x-1,y+2),moveAndSearch(x+1,y+2);
	}
	void moveAndSearch(int x,int y) {
		if(!board.isMoveValid(x,y))
			return;
		board.doMove(x,y);
		search(x,y);
		board.undoMove(x,y);
	}
	void solve() {
		for(int y=0; y!=board.getSizeY(); ++y)
			for(int x=0; x!=board.getSizeX(); ++x)
				moveAndSearch(x,y);
	}
};

int main() {
	cout<<"Bitte Feldgroesse eingeben:\n";
	int sizeX=8,sizeY=8;
	cin>>sizeX>>sizeY;
	Solver s(sizeX,sizeY);
	s.solve();
}

[volkard]

Eine Klasse Move einzuführen ging dann locker von der Hand. Natürlich nicht einfach so, sondern für die sauschnelle Version ganz unten.

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

class Move {
public:
	int x;
	int y;
};

class Board {
	int const sizeX;
	int const sizeY;
	vector<int> fields;
	int moveNo;
public:
	Board(int sizeX,int sizeY):
		sizeX(sizeX),
		sizeY(sizeY),
		fields(sizeX* sizeY,0),
		moveNo(0) {
	}
	int getSizeX() {
		return sizeX;
	}
	int getSizeY() {
		return sizeY;
	}
	int& at(int x,int y) {
		return fields[y*sizeX+x];
	}
	bool isFull() {
		return moveNo==sizeX*sizeY;
	}
	bool isMoveValid(Move m) {
		if(not(0<=m.x and m.x<sizeX)) return false;
		if(not(0<=m.y and m.y<sizeY)) return false;
		if(at(m.x,m.y)!=0) return false;
		return true;
	}
	void doMove(Move m) {
		++moveNo;
		at(m.x,m.y)=moveNo;
	}
	void undoMove(Move m) {
		at(m.x,m.y)=0;
		--moveNo;
	}
	void print() {
		for(int y=0; y!=sizeY; ++y) {
			cout<<'|';
			for(int x=0; x!=sizeX; ++x)
				cout<<setw(3)<<at(x,y)<<" |";
			cout<<'\n';
		}
		cout<<'\n';
	}
};

class Solver {
	Board board;
public:
	Solver(int sizeX,int sizeY):
		board(sizeX,sizeY) {
	}
	vector<Move> collectValidMoves(Move lastMove) {
		vector<Move> moves;
		std::pair<int,int> offsets[]= {
			{2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1},
		};
		for(auto offset:offsets) {
			Move m {lastMove.x+offset.first,lastMove.y+offset.second};
			if(board.isMoveValid(m))
				moves.push_back(m);
		}
		return moves;
	}
	void search(Move oldMove) {
		if(board.isFull()) {
			board.print();
			return;
		}
		for(auto m:collectValidMoves(oldMove))
			moveAndSearch(m);
	}
	void moveAndSearch(Move m) {
		if(!board.isMoveValid(m))
			return;
		board.doMove(m);
		search(m);
		board.undoMove(m);
	}
	void solve() {
		for(int y=0; y!=board.getSizeY(); ++y)
			for(int x=0; x!=board.getSizeX(); ++x)
				moveAndSearch(Move {x,y});
	}
};

int main() {
	cout<<"Bitte Feldgroesse eingeben:\n";
	int sizeX=8,sizeY=8;
//	cin>>sizeX>>sizeY;
	Solver s(sizeX,sizeY);
	s.solve();
}

Dann kann man auch noch einen Todesrand machen: Oben unten links und rechts zwei Felder mehr, dadurch braucht es beim isMoveValid keine Bereichsgrenzen mehr zu prüfen. Bringt hier nix! Ich habs nur als Tech-Demo gemacht. War bei Schachcomputern üblich.

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

class Move {
public:
	int x;
	int y;
};

class Board {
	int const sizeX;
	int const sizeY;
	vector<int> fields;
	int moveNo;
public:
	Board(int sizeX,int sizeY):
		sizeX(sizeX),
		sizeY(sizeY),
		fields((sizeX+4)* (sizeY+4),-1),
		moveNo(0) {
			for(int y=0; y!=sizeY; ++y)
				for(int x=0; x!=sizeX; ++x)
					at(x,y)=0;
	}
	int getSizeX() {
		return sizeX;
	}
	int getSizeY() {
		return sizeY;
	}
	int& at(int x,int y) {
		return fields[(y+2)*(sizeX+4)+(x+2)];
	}
	bool isFull() {
		return moveNo==sizeX*sizeY;
	}
	bool isMoveValid(Move m) {
//		if(not(0<=m.x and m.x<sizeX)) return false;
//		if(not(0<=m.y and m.y<sizeY)) return false;
		if(at(m.x,m.y)!=0) return false;
		return true;
	}
	void doMove(Move m) {
		++moveNo;
		at(m.x,m.y)=moveNo;
	}
	void undoMove(Move m) {
		at(m.x,m.y)=0;
		--moveNo;
	}
	void print() {
		for(int y=0; y!=sizeY; ++y) {
			cout<<'|';
			for(int x=0; x!=sizeX; ++x)
				cout<<setw(3)<<at(x,y)<<" |";
			cout<<'\n';
		}
		cout<<'\n';
	}
};

class Solver {
	Board board;
public:
	Solver(int sizeX,int sizeY):
		board(sizeX,sizeY) {
	}
	vector<Move> collectValidMoves(Move lastMove) {
		vector<Move> moves;
		std::pair<int,int> offsets[]= {
			{2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1},
		};
		for(auto offset:offsets) {
			Move m {lastMove.x+offset.first,lastMove.y+offset.second};
			if(board.isMoveValid(m))
				moves.push_back(m);
		}
		return moves;
	}
	void search(Move oldMove) {
		if(board.isFull()) {
			board.print();
			return;
		}
		for(auto m:collectValidMoves(oldMove))
			moveAndSearch(m);
	}
	void moveAndSearch(Move m) {
		if(!board.isMoveValid(m))
			return;
		board.doMove(m);
		search(m);
		board.undoMove(m);
	}
	void solve() {
		for(int y=0; y!=board.getSizeY(); ++y)
			for(int x=0; x!=board.getSizeX(); ++x)
				moveAndSearch(Move {x,y});
	}
};

int main() {
	cout<<"Bitte Feldgroesse eingeben:\n";
	int sizeX=8,sizeY=8;
//	cin>>sizeX>>sizeY;
	Solver s(sizeX,sizeY);
	s.solve();
}

Und jetzt geht's dem Move an den Kragen, er wird eindimensional.
(Upps, at() hätte vorher schon einen Move nehmen sollen?) Bringt hier auch nix, auch nur Tech-Demo. Durch Werners rumobjektgeorientiere kann man sowas halt dann noch einbauen, ohne überall im Code rumsuchen zu müssen! Es ist klar, wo man was anpassen muss. Und fast alle Anpassungen verrät einem auch der Compiler durch passende Compilerfehler.
(Zur Not kann man sich die auch erzwingen, wenn man aus at(x,y) das für mich üblichere at(y,x) macht, einfach ein at(y,x,dummy) machen und Compilerfehler reparieren.)

class Move {
	Move(int xy):
		xy(xy){
	}
public:
	int xy;
	Move(int x,int y,int sizeX):
		xy((y+2)*(sizeX+4)+(x+2)){
	}
	friend Move operator+(Move m,int offset){
		return Move(m.xy+offset);
	}
};

class Board {
	int& at(Move m) {
		return fields[m.xy];
	}
//und ein paar Kleinigkeiten.

Das war alles aber nur Vorbereitung, um die Heuristik einzubauen.
Mir ist nämlich aufgedallen, daß ein 8x8-Brett noch einigermaßen flotte Anzeigen kriegt. Bei 10x10 hängt die Sache aber. Da muss was geschehen.

Deswegen die teure collectValidMoves()!
Selbst bei 50x50-Brettern brettern die Lösungen nur so rein, so soll's sein.

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

class Move {
	Move(int xy):
		xy(xy) {
	}
public:
	int xy;
	Move(int x,int y,int sizeX):
		xy((y+2)*(sizeX+4)+(x+2)) {
	}
	friend Move operator+(Move m,int offset) {
		return Move(m.xy+offset);
	}
};

class Board {
	int const sizeX;
	int const sizeY;
	vector<int> fields;
	int moveNo;
public:
	Board(int sizeX,int sizeY):
		sizeX(sizeX),
		sizeY(sizeY),
		fields((sizeX+4)* (sizeY+4),-1),
		moveNo(0) {
		for(int y=0; y!=sizeY; ++y)
			for(int x=0; x!=sizeX; ++x)
				at(Move(x,y,sizeX))=0;
	}
	int getSizeX() {
		return sizeX;
	}
	int getSizeY() {
		return sizeY;
	}
	int& at(Move m) {
		return fields[m.xy];
	}
	bool isFull() {
		return moveNo==sizeX*sizeY;
	}
	bool isMoveValid(Move m) {
//		if(not(0<=m.x and m.x<sizeX)) return false;
//		if(not(0<=m.y and m.y<sizeY)) return false;
		if(at(m)!=0) return false;
		return true;
	}
	void doMove(Move m) {
		++moveNo;
		at(m)=moveNo;
	}
	void undoMove(Move m) {
		at(m)=0;
		--moveNo;
	}
	void print() {
		for(int y=0; y!=sizeY; ++y) {
			cout<<'|';
			for(int x=0; x!=sizeX; ++x)
				cout<<setw(3)<<at(Move(x,y,sizeX))<<" |";
			cout<<'\n';
		}
		cout<<'\n';
	}
};

class Solver {
	Board board;
	struct WeightedMove:public Move {
		int weight;
		WeightedMove(Move m):
			Move(m),
			weight(0) {
		}
		friend bool operator<(WeightedMove a,WeightedMove b) {
			return a.weight<b.weight;
		}
	};
public:
	Solver(int sizeX,int sizeY):
		board(sizeX,sizeY) {
	}
	vector<WeightedMove> collectValidMoves(Move lastMove) {
		vector<WeightedMove> moves;
		int fy=board.getSizeX()+4;
		int offsets[]= {
			2+1*fy, 1+2*fy, -1+2*fy, -2+1*fy,
			-2-1*fy, -1-2*fy, 1-2*fy, 2-1*fy,
		};
		for(auto offset:offsets) {
			WeightedMove m(lastMove+offset);
			if(board.isMoveValid(m)) {
				for(auto offset:offsets) {
					Move m2(m+offset);
					if(board.isMoveValid(m2))
						++m.weight;
				}
				moves.push_back(m);
			}
		}
		sort(moves.begin(),moves.end());
		return moves;
	}
	void search(Move oldMove) {
		if(board.isFull()) {
			board.print();
			return;
		}
		for(auto m:collectValidMoves(oldMove))
			moveAndSearch(m);
	}
	void moveAndSearch(Move m) {
		if(!board.isMoveValid(m))
			return;
		board.doMove(m);
		search(m);
		board.undoMove(m);
	}
	void solve() {
		for(int y=0; y!=board.getSizeY(); ++y)
			for(int x=0; x!=board.getSizeX(); ++x)
				moveAndSearch(Move(x,y,board.getSizeX()));
	}
};

int main() {
	cout<<"Bitte Feldgroesse eingeben:\n";
	int sizeX=8,sizeY=8;
	cin>>sizeX>>sizeY;
	Solver s(sizeX,sizeY);
	s.solve();
}

Und jetzt mache ich mir Gedanken um den Rückbau. Wo bin ich übers Ziel hinausgeschossen? Wo zu verspielt gewesen? Überall eigentlich, nur die Heuristik bringt's. *hihi*
Na, die ist ja schnell in die erste Version dieses Postings gecopypastet.

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

struct Move {
//Fühle mich einfach freier, wenn ich dazu selber eine kleine struct anlege.
	Move(int x,int y):
		x(x),
		y(y) {
	}
	int x;
	int y;
};

class Board {
//Leider kein Array2D zum Inkludieren da.
	int const sizeX;
	int const sizeY;
	vector<int> fields;//Vector ist eigentlich falsch, müßte Array sein, was
	//zwar zur Laufzeit seine Größe kriegt, aber sie dann nicht mehr ändern kann.
	int moveNo;
public:
	Board(int sizeX,int sizeY):
		sizeX(sizeX),
		sizeY(sizeY),
		fields(sizeX* sizeY,0),
		moveNo(0) {
	}
	int getSizeX() {//hat der Solver gebraucht. Klar darf er sich das anschauen.
		return sizeX;
	}
	int getSizeY() {
		return sizeY;
	}
	int& at(Move m) {
		return fields[m.y*sizeX+m.x];
	}
	bool isFull() {
		return moveNo==sizeX*sizeY;
	}
	bool isMoveValid(Move m) {
		if(not(0<=m.x and m.x<sizeX)) return false;
		if(not(0<=m.y and m.y<sizeY)) return false;
		if(at(m)!=0) return false;
		return true;
	}
	void doMove(Move m) {
		++moveNo;
		at(m)=moveNo;
	}
	void undoMove(Move m) {
		at(m)=0;
		--moveNo;
	}
	void print() {
		for(int y=0; y!=sizeY; ++y) {
			cout<<'|';
			for(int x=0; x!=sizeX; ++x)
				cout<<setw(3)<<at(Move(x,y))<<" |";
			cout<<'\n';
		}
		cout<<'\n';
	}
};

class Solver {
	struct WeightedMove:public Move {//Für die Heuristik, gute Züge zuerst testen.
		int weight;
		WeightedMove(int x,int y):
			Move(x,y),
			weight(0) {
		}
		friend bool operator<(WeightedMove a,WeightedMove b) {
			return a.weight<b.weight;
		}
	};
	Board board;
public:
	Solver(int sizeX,int sizeY):
		board(sizeX,sizeY) {
	}
	vector<WeightedMove> collectValidMoves(Move lastMove) {
		vector<WeightedMove> moves;
		std::pair<int,int> offsets[]= {
			{2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1},
		};
		for(auto offset:offsets) {
			WeightedMove m(lastMove.x+offset.first,lastMove.y+offset.second);
			if(board.isMoveValid(m)) {
				for(auto offset:offsets) {
					Move m2(m.x+offset.first,m.y+offset.second);
					if(board.isMoveValid(m2))
						++m.weight;
				}
				moves.push_back(m);
			}
		}
		sort(moves.begin(),moves.end());
		return moves;
	}
	void search(Move oldMove) {
		if(board.isFull()) {
			board.print();
			return;
		}
		for(auto m:collectValidMoves(oldMove))
			moveAndSearch(m);
	}
	void moveAndSearch(Move m) {
		if(!board.isMoveValid(m))
			return;
		board.doMove(m);
		search(m);
		board.undoMove(m);
	}
	void solve() {
		for(int y=0; y!=board.getSizeY(); ++y)
			for(int x=0; x!=board.getSizeX(); ++x)
				moveAndSearch(Move {x,y});
	}
};

int main() {
	cout<<"Bitte Feldgroesse eingeben:\n";
	int sizeX=8,sizeY=8;
	cin>>sizeX>>sizeY;
	Solver s(sizeX,sizeY);
	s.solve();
}

[Columbo]

Cool, die Assertion kannte ich noch gar nicht:

sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.

Ist die bei dir schon mal aufgetaucht?

... und mein Code.

#include <boost/container/static_vector.hpp>

#include <iostream>
#include <iomanip>   // setw
#include <vector>    // vector
#include <utility>   // pair
#include <algorithm> // count_if

struct PositionInfo
{
	int const pos;
	boost::container::static_vector<std::pair<int, unsigned>, 8> moves;

	explicit PositionInfo( int pos ) : pos(pos) {}
};

class Board
{
	std::size_t mWidth, mHeight;

	int const knight_jumps[8];

	std::size_t full_w() const { return w() + 4; }
	std::size_t full_h() const { return h() + 4; }

	std::vector<int> mArray;
	std::vector<PositionInfo> mTrace;

public:

	explicit Board( std::size_t width, std::size_t height ) :
		mWidth{width}, mHeight{height},
		knight_jumps{ 2*int(full_w())+1, 2*int(full_w())-1, -2*int(full_w())-1, -2*int(full_w())+1,
		                int(full_w())+2,   int(full_w())-2,   -int(full_w())-2,   -int(full_w())+2 }, // hässlich wie sonst was, aber was solln wir machen?
		mArray( full_w()*full_h(), -1 ) {}

	std::size_t w() const { return mWidth; }
	std::size_t h() const { return mHeight; }

	void createMoves( PositionInfo& info ) const
	{
		for (auto i : knight_jumps)
			if (mArray[info.pos + i] == 0)
			{
				unsigned viable = std::count_if( std::begin(knight_jumps), std::end(knight_jumps),
				                                 [=, &info] ( int j ) {  return mArray[info.pos + i + j] == 0 && i != -j;  } );

				info.moves.emplace_back( info.pos + i, viable );

				std::sort( std::begin(info.moves), std::end(info.moves), []( auto& lhs, auto& rhs ){ return lhs.second > rhs.second; } );
			}
	}

	void clear()
	{
		auto i = 2*full_w() + 2;
		while( i != (full_h()-2)*full_w() + 2 )
		{
			std::fill_n( begin(mArray) + i, full_w() - 4, 0 );
			i += full_w();
		}

		mTrace.clear();
	}

	void do_next_move()
	{
		auto const next = last().moves.back();
		last().moves.pop_back();

		mTrace.emplace_back( next.first );
		mArray[next.first] = mTrace.size();
	}

	PositionInfo& last() { return mTrace.back(); }

	bool backtrack()
	{
		while( last().moves.empty() )
		{
			mArray[last().pos] = 0;

			mTrace.pop_back();

			if( mTrace.empty() )
				return false;
		}

		return true;
	}

	bool solve( int start_x, int start_y )
	{
		clear();

		mTrace.reserve( w()*h() );

		// Start-Position
		mTrace.emplace_back( (start_y + 2)*full_w() + 2 + start_x );

		mArray[last().pos] = 1;

		while( mTrace.size() != w()*h() )
		{
			createMoves( last() );

			if( !backtrack() )
				return false;

			do_next_move();
		}

		return true;
	}

	void pretty_print( std::ostream& stream )
	{
		auto const width = std::log10(w()*h()) + 1;
		for( auto anchor = 2*full_w() + 2; anchor != (full_h()-2)*full_w() + 2; anchor += full_w() )
		{
			for( auto i = anchor; i != anchor + full_w() - 4; ++i )
				stream << '|' << std::setw(width) << mArray[i];
			stream << "|\n";
		}
	}
};

int main()
{
	size_t w , h;
	if( !(std::cin >> w >> h) )
		return 0;

	Board board(w, h);

	for( size_t x = 0; x != w; ++x )
	for( size_t y = 0; y != h; ++y )
	{
		if( board.solve( x, y ) )
			board.pretty_print( std::cout );
		std::cout << std::string(50, '~') << '\n';
	}
}

Versagt aber leider bei so 16x16. Eine Ahnung woran es liegen könnte?

Eindimensionale Indizierung und static_vector (welchen ich im Übrigen verdammt sexy finde!) sind für die Optimierung, genau wie die Sentinels. Seitlich an Sentinels sparen geht hier leider nicht (weil die Dimensionen kleiner als 8x8 sein können).

Mir fällt gerade auf dass die Eindimensionale Indizierung hier Schwachsinn ist... tja. Hätte ich nicht vom Schachprogrammieren übernehmen dürfen.

Edit: Ist schon krass wieviel lesbarer dein Code ist... wie schaffst du das nur?

[Mechanics]

Arcoth schrieb:

Edit: Ist schon krass wieviel lesbarer dein Code ist... wie schaffst du das nur?

Wahrscheinlich, weil sein Code weniger verspielt ist. Ich weiß auch nicht, volker´s Code kann ich irgendwie direkt lesen und verstehen. Bei dir ist das Problem wahrscheinlich, dass die Syntax viel zu stark von der Struktur ablenkt. Sowas kann ich z.B. praktisch gar nicht lesen:

unsigned viable = std::count_if( std::begin(knight_jumps), std::end(knight_jumps),
                                                 [=, &info] ( int j ) {  return mArray[info.pos + i + j] == 0 && i != -j;  } );

Ich weiß nicht, obs anderen auch so geht. Der Code ist ja nicht schwer, den versteht man an sich problemlos, wenn man sich etwas reindenkt. Aber so beim drüberschauen ist die Informationsdichte erstmal viel zu hoch, man erkennt überhaupt nicht, was passiert und steigt aus.

Finde ich an sich übrigens nicht schlimm, ich schreibe auch öfters ähnlichen Code. Spontante Hypothese wäre, dass man komplexere Algorithmen möglichst einfach ausdrücken sollte, weil man sofort eine Struktur und einen Zusammenhang erkennen will.

[hustbaer]

Arcoth schrieb:

Cool, die Assertion kannte ich noch gar nicht:

sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.

rofl

Verdammter Dreisternprogrammierer.

[Columbo]

unsigned viable = std::count_if( std::begin(knight_jumps), std::end(knight_jumps),
                                 [=, &info] ( int j ) {  return mArray[info.pos + i + j] == 0 && i != -j;  } );

Ja, einer der miesesten Zeilen. Habe mir auch überlegt es zu einer Schleife umzuschreiben, aber dann hatte ich IIRC gleich Vier Zeilen, also wieder zurückgeändert.

So schwer ist es doch nicht, sich da reinzudenken. i und j stellen jeweils einen Sprung dar. i + j Zwei verkettete Sprünge. Vielleicht aber sollte man das wohl nicht in ein Lambda welches als Prädikat für count_if fungiert quetschen.

@hustbaer: Am geilsten finde ich diesen Ausschnitt ((1) - 1) * 2
Das ist entweder ein schlechter Scherz - oder Ergebnis eines Makros.

[Nexus]

Mechanics schrieb:

Spontante Hypothese wäre, dass man komplexere Algorithmen möglichst einfach ausdrücken sollte, weil man sofort eine Struktur und einen Zusammenhang erkennen will.

Code wird auch unnötig komplex, wenn man ständig auf Biegen und Brechen versucht, die Standardbibliothek und fortgeschrittene Sprachmittel zu verwenden. Sowohl STL-Algorithmen als auch Lambda-Ausdrücke sind sehr praktisch, aber manchmal sind Schleifen um einiges einfacher.

Was allerdings auch schon massiv helfen würde, wäre die Aufteilung komplexer Ausdrücke auf mehrere Zeilen. Also den Lambda-Ausdruck separat deklarieren, eventuell in mehreren Zeilen, und an den Algorithmus übergeben. Inline übergeben lohnt sich nur bei sehr kurzen Funktionskörpern. std::begin(c) ist auch nur in der Theorie besser als c.begin() .

[volkard]

Arcoth schrieb:

Cool, die Assertion kannte ich noch gar nicht:

sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.

Ist die bei dir schon mal aufgetaucht?

Nee, die kenne ich nicht.

//Ich kommentiere direkt rein

Arcoth schrieb:

... und mein Code.

#include <boost/container/static_vector.hpp>//gut, den hätte ich gebraucht

#include <iostream>
#include <iomanip>   // setw //ballastkommentare
#include <vector>    // vector
#include <utility>   // pair
#include <algorithm> // count_if

struct PositionInfo
{
	int const pos;
	boost::container::static_vector<std::pair<int, unsigned>, 8> moves;
//ok, die folgenden möglichen bis zu 8 Moves werden hier gespeichert. 
//Wäre nach "PositionInfo" nicht gleich drauf gekommen. Warum nicht 
//einfach "DieFolgendenMoeglichenBisZu8Moves"?
	explicit PositionInfo( int pos ) : pos(pos) {}
};

class Board
{
	std::size_t mWidth, mHeight;
//Uih, Breite, Höhe, Zeilen, Spalten, X, Y, das verwirrt mich immer. 
//Nur bei X/Y bin ich fest. Gerade die Matrizen mit m/n machen mich kaputt. 
//Wenn ich voll unsicher bin, mache ich google an. 
//Bei "geile Zeile" habe ich 89k Treffer, 
//bei "geile Spalte" sind es 402k Treffer. 
//So kann ich immer nachschauen, ob Zeilen oder Spalten senkrecht sind. 
//Aber wehe, Du verwendest nachher x und y, dann wären sizeX und sizeY 
//doch so, daß man gar nicht wissen muss, ob Height nun x oder y ist. 

	int const knight_jumps[8];

	std::size_t full_w() const { return w() + 4; }
	std::size_t full_h() const { return h() + 4; }
//das +4 ist jetzt ein wenig aus der Luft gegriffen. 

	std::vector<int> mArray;
	std::vector<PositionInfo> mTrace;
//oh, "mTrace". Sagt mir jetzt nix. 
public:

	explicit Board( std::size_t width, std::size_t height ) :
		mWidth{width}, mHeight{height},
		knight_jumps{ 2*int(full_w())+1, 2*int(full_w())-1, -2*int(full_w())-1, -2*int(full_w())+1,
		                int(full_w())+2,   int(full_w())-2,   -int(full_w())-2,   -int(full_w())+2 }, // hässlich wie sonst was, aber was solln wir machen?
		mArray( full_w()*full_h(), -1 ) {}
//Hä????
	std::size_t w() const { return mWidth; }
	std::size_t h() const { return mHeight; }
//intern Klartext aber nach außen Abkürzung? 
	void createMoves( PositionInfo& info ) const
	{
		for (auto i : knight_jumps)
			if (mArray[info.pos + i] == 0)
			{
				unsigned viable = std::count_if( std::begin(knight_jumps), std::end(knight_jumps),
				                                 [=, &info] ( int j ) {  return mArray[info.pos + i + j] == 0 && i != -j;  } );

				info.moves.emplace_back( info.pos + i, viable );

				std::sort( std::begin(info.moves), std::end(info.moves), []( auto& lhs, auto& rhs ){ return lhs.second > rhs.second; } );
			}
	}
//Ok, aber warum nicht die leichten Methoden nach vorn? 
	void clear()
	{
		auto i = 2*full_w() + 2;
		while( i != (full_h()-2)*full_w() + 2 )
		{
			std::fill_n( begin(mArray) + i, full_w() - 4, 0 );
			i += full_w();
		}

		mTrace.clear();
	}
//Weiß nicht, hast irgendwie eine innere Schleife gespart. 
	void do_next_move()
	{
		auto const next = last().moves.back();
		last().moves.pop_back();

		mTrace.emplace_back( next.first );
		mArray[next.first] = mTrace.size();
	}
//So fohle ich mich, wenn ich fremden Lisp-Code lese. 
	PositionInfo& last() { return mTrace.back(); }

	bool backtrack()
	{
		while( last().moves.empty() )
		{
			mArray[last().pos] = 0;

			mTrace.pop_back();

			if( mTrace.empty() )
				return false;
		}

		return true;
	}
//Das ist das Problem! Du redest hier nicht von Brettern, Stellungen, 
//Zügen, Springen und so, und daß sie Züge machen oder zurücknehmen, 
//sondern von empty, last, pop_back, und std::gehansele
	bool solve( int start_x, int start_y )
	{
		clear();

		mTrace.reserve( w()*h() );
//Habs wieder vergessen, was w und h waren. w war die anzahl der Spalten? 

		// Start-Position
		mTrace.emplace_back( (start_y + 2)*full_w() + 2 + start_x );

		mArray[last().pos] = 1;

		while( mTrace.size() != w()*h() )
		{
			createMoves( last() );

			if( !backtrack() )
				return false;

			do_next_move();
		}

		return true;
	}

	void pretty_print( std::ostream& stream )
	{
		auto const width = std::log10(w()*h()) + 1;
		for( auto anchor = 2*full_w() + 2; anchor != (full_h()-2)*full_w() + 2; anchor += full_w() )
		{
			for( auto i = anchor; i != anchor + full_w() - 4; ++i )
				stream << '|' << std::setw(width) << mArray[i];
			stream << "|\n";
		}
	}
};

int main()
{
	size_t w , h;
	if( !(std::cin >> w >> h) )
		return 0;

	Board board(w, h);

	for( size_t x = 0; x != w; ++x )
	for( size_t y = 0; y != h; ++y )
	{
		if( board.solve( x, y ) )
			board.pretty_print( std::cout );
		std::cout << std::string(50, '~') << '\n';
	}
}

Versagt aber leider bei so 16x16. Eine Ahnung woran es liegen könnte?

Hab keine Lust, Fehler zu suchen. Ich bau lieber Code ohne Fehler.

Arcoth schrieb:

Eindimensionale Indizierung und static_vector (welchen ich im Übrigen verdammt sexy finde!) sind für die Optimierung, genau wie die Sentinels. Seitlich an Sentinels sparen geht hier leider nicht (weil die Dimensionen kleiner als 8x8 sein können).

Geht.

Arcoth schrieb:

Mir fällt gerade auf dass die Eindimensionale Indizierung hier Schwachsinn ist... tja. Hätte ich nicht vom Schachprogrammieren übernehmen dürfen.

Ist hier nur O(1)-Schwachsinn, weil das Schachprogramm viel mehr Feldgrenzenüberprüfungen machen muss. Hab's ja auch gemacht (und dann rückgebaut).

Arcoth schrieb:

Edit: Ist schon krass wieviel lesbarer dein Code ist... wie schaffst du das nur?

Ich bin einfach viel zu faul, um Fehler zu suchen. Also gewöhne ich mir einen Stil an, den sogar ein Schimpanse lesen kann. Denn ICH muss nachher die Fehler wegmachen. Schmuddelcode nach einem halben Jahr?

Gleichzeitig bin ich total performancefixiert und haue keine Zeile raus, die lahmer wäre als mit C. Das geht mit C++. Ich kenne keine andere Sprache, wo ich so gut meine beiden Hobbies unter einen Hut bringen könnte.

Mein Schlüsselerlebnis war, als ich zu Studienbeginn (schon 5 Jahre Basic-Erfahtung) einen Kompimierer (in C) schrieb, wegen Zeitbelastung ihn ein halbes Jahr liegen lassen musste, und bei Wiederaufnahme von ca 300 Zeilen Code genau außer der "void main()" (ja, damals war void üblich) und geschweiften Klammern genau keine Zeile Code entschlüsseln konnte, obwohl mir mein geplantes Verfahren noch 100%-ig klar war. Einige Wochen habe ich damit verbracht, mir den alten Code anzuschauen, in der Hoffnung, das Rätsel zu knacken. Nöö, es ist nicht gelungen. Ok, damals war ich jung und doof. Jetzt bin ich nicht mehr jung.

Dann so rumgelesen und rumgelernt…
Irgendwann kam der C++-Hype. Mein erstes C++-Buch war ein Wurstbrot-Buch. Danach war ich so klug als wie zuvor oder dümmer.

Das zweite war der Meyers, GRANATE! Habs ca 30-mal gelesen. Anfangs nix verstanden und mit jedem Lesen ein wenig mehr. 9 Monate nix außer Meyers und nicht vermeidbaren Körperfunktionen.

Gegenfrage: Warum willst Du (in Vertretung der PlayStation-Generation) immer den Code noch komplizierter machen als das Problem ist?

[volkard]

Arcoth schrieb:

unsigned viable = std::count_if( std::begin(knight_jumps), std::end(knight_jumps),
                                 [=, &info] ( int j ) {  return mArray[info.pos + i + j] == 0 && i != -j;  } );

Ja, einer der miesesten Zeilen. Habe mir auch überlegt es zu einer Schleife umzuschreiben, aber dann hatte ich IIRC gleich Vier Zeilen, also wieder zurückgeändert.

Hätte ein Schimpanse die 4 Zeilen auf Anhieb verstanden?

Ich hätte die innere Schleife von

if(board.isMoveValid(m)) {
                for(auto offset:offsets) {
                    Move m2(m+offset);
                    if(board.isMoveValid(m2))
                        ++m.weight;
                }
                moves.push_back(m);
            }

behandeln müssen.

Wegalgorithmieren? Nee, ist selten gut. Also im Prinzip

if(board.isMoveValid(m)) {
                moves.push_back(m,r=for(auto offset:offsets) {
                    Move m2(m+offset);
                    if(board.isMoveValid(m2))
                        ++r;
                });
            }

und die ähnlichen Schreibweisen verbessern das Problem nicht wirklich.

Lamdas sind in manchen Fällen unendlich geil, aber fast nie.
(wie auch Referenzen)

[hustbaer]

Arcoth schrieb:

@hustbaer: Am geilsten finde ich diesen Ausschnitt ((1) - 1) * 2
Das ist entweder ein schlechter Scherz - oder Ergebnis eines Makros.

Jaaaaa, Makro, das wird der Grund sein.
Trotzdem... bäh!

EDIT: Wobei, ... eigentlich sollte der Parameter von assert() ohne Makro-Expansion angezeigt werden. Ist natürlich nicht standardisiert, aber ich sag' mal es wäre verdammt schlau.

[volkard]

hustbaer schrieb:

EDIT: Wobei, ... eigentlich sollte der Parameter von assert() ohne Makro-Expansion angezeigt werden. Ist natürlich nicht standardisiert, aber ich sag' mal es wäre verdammt schlau.

Hab's noch nie anders erlebt. Türlich liefert assert den Quelltext.
Vielleicht ist diese assert-Bedingung vorher von einem Make-Tool erzeugt worden.

[Columbo]

Warum willst Du immer den Code noch komplizierter machen als das Problem ist?

Ich möchte den Code so knapp wie möglich halten, und ihn außerdem nie wieder anschauen müssen oder auch wollen (bei dem Code ist letzteres ja auch selbstverständlich). Das wars. Kacke Einstellung, brauchst nichts zu sagen. Kommt von selber schon bald weg - schreibe gerade eine Schachengine, die will ich definitiv lesbar halten, da eigne ich mirs an.

//Uih, Breite, Höhe, Zeilen, Spalten, X, Y, das verwirrt mich immer.

Was ist direkter als width , welches für Breite steht? WidthOfDaBoard ?

Hätte ein Schimpanse die 4 Zeilen auf Anhieb verstanden?

Ein Schimpanse hätte die 4 Zeilen wie eine Banane aufgegessen. Im Nachhinein habe ich wenig Ahnung mehr, warum ich nicht die Schleife gewählt habe...

unsigned viable = 0;
for( auto j : knight_jumps )
    if( mArray[info.pos + i + j] == 0 && i != -j )
        ++viable;

Lamdas sind in manchen Fällen unendlich geil, aber fast nie.

Hihi, deine Sprüchlein werden nur besser und besser. Bist du eine Frucht, die noch reift?

Ist natürlich nicht standardisiert, aber ich sag' mal es wäre verdammt schlau.

Da stimm' ich dir mal zu. Und nein. Der Standard legt nicht klar fest was hier passiert. C11 sagt "including the text of the argument", was aber soviel wie Stringize heißen wird.

Jetzt gibt es aber ein Problem: Forwardest du den Parameter an ein anderes Makro tritt folgendes in Kraft:

A parameter in the replacement list, unless preceded by a # or ## preprocessing token or followed by a ## preprocessing token (see below), is replaced by the corresponding argument after all macros contained therein have been expanded. Before being substituted, each argument’s preprocessing tokens are completely macro replaced as if they formed the rest of the preprocessing file; no other preprocessing tokens are available.

Das heißt, falls assert so definiert ist

#define assert(...) ((void)__call_my_func(#__VA_ARGS__))

Dann werden tatsächlich die Makros im Text beibehalten. Anders ist es hier

#define assert(...) ((void)__call_my_func(__STRING(__VA_ARGS__)))

Hier wird __VA_ARGS__ noch gescannt bevor es durchgereicht wird. Und das macht den Unterschied aus. Jetzt schaun wir mal in die Definition von cassert:

# define assert(expr)							\
  ((expr)								\
   ? __ASSERT_VOID_CAST (0)						\
   : __assert_fail (__STRING(expr), __FILE__, __LINE__, __ASSERT_FUNCTION))

Und in Zeile 89 von cdefs.h :

#define __STRING(x)	#x

Reicht schon. Makros werden aufgelöst. Menno. Und ich kann den Fehler leider auch nicht reproduzieren.

Türlich liefert assert den Quelltext.

Ja, genau... und die Makros darin sind aufgelöst. Also war es ein Makro, höchstwahrscheinlich kein Make-Tool, so einfach ist das.

Ich hatte Dir angeboten, hatte darum gebettelt, daß wir KarateKid oder 256KammernDerShaoLin oder so zusammen spielen. Du erinnerst Dich.

Ich habe angenommen, Sensei! Ich darf dich daran erinnern dass du 'keine Zeit für mich hattest', privater Schnickschnack und dergleichen.

[volkard]

Arcoth schrieb:

volkard schrieb:

Ich hatte Dir angeboten, hatte darum gebettelt, daß wir KarateKid oder 256KammernDerShaoLin oder so zusammen spielen. Du erinnerst Dich.

Ich habe angenommen, Sensei! Ich darf dich daran erinnern dass du 'keine Zeit für mich hattest'.

Jup, nachdem Du abgelehnt hattest, meine Hausprobleme zu erledigen. Meinen Zauberwürfelzugfolgenfinder, …, waren noch einige. Holla(!), an denen arbeitest Du ja selber jetzt gerade.

Da hätte ich soo viel angemeckert und gelehrt. Mit Selbstaufgabe.

Wischi wischi Auto putzi… Wie im Film.

[Columbo]

Jup, nachdem Du abgelehnt hattest, meine Hausprobleme zu erledigen

Hab' und hätte ich nie getan. Ich kann mich im Übrigen überhaupt nicht daran erinnern deine Hausproblemchen vorgeschlagen bekommen zu haben.

Zauberwürfelzugfolgenfinder

Ist das ein Hausproblemchen? Verdammt, das trifft genau ins Schwarze - man muss alles definieren, sowas wie Cube , Position und so, alles schön aufteilen in kleine Funktionen. Soll ich mich dran machen?

[volkard]

Arcoth schrieb:

Zauberwürfelzugfolgenfinder

Ist das ein Hausproblemchen? Verdammt, das trifft genau ins Schwarze - man muss alles definieren, sowas wie Cube , Position und so, alles schön aufteilen in kleine Funktionen. Soll ich mich dran machen?

Falls Du so einen mal anfängst, dann schau dir zuerst an, wie es Cube Explorer http://kociemba.org/cube.htm macht und mach es anders. Keine Klasse für Cubies. Die schränkt den Fragesteller zu stark ein.