Rosetta Code

Knight's tour: Difference between revisions

Page Discussion

Knight's tour (view source)

Revision as of 03:34, 31 May 2011

87 bytes added ,  13 years ago
→‎{{header|C++}}: Improved C++
(→‎{{header|Perl}}: minor cleanup)
(→‎{{header|C++}}: Improved C++)
Line 22:
#include <tuple>
#include <algorithm>
 
using namespace std;
 
template<int N = 8>
structclass Board {
{
public:
array<pair<int, int>, 8> moves;
array<array<int, N>, N> data;
 
Board() {
{
moves[0] = make_pair(2, 1);
moves[1] = make_pair(1, 2);
Line 41 ⟶ 43:
}
 
array<int, 8> sortMoves(const int x, const int y) const {
{
array<tuple<int, int>, 8> counts;
for (int i = 0; i < 8; i++i) {
}{▼
const int dx = get<0>(moves[i]);▼
const int dydx = get<10>(moves[i]);
▲ const int dxdy = get<01>(moves[i]);
 
int c = 0;
for (int j = 0; j < 8; j++j) {
const int x2 = x + dx + get<0>(moves[j]);{
const int y2x2 = yx + dydx + get<10>(moves[j]);
ifint (x2y2 >= 0y &&+ x2dy + get< N && y2 1>= 0 && y2 < N &&(moves[j]);
 
data[y2][x2] == 0)▼
if (x2 < 0 c++;|| x2 >= N || y2 < 0 || y2 >= N)
breakcontinue;▼
▲ if(data[y2][x2] =!= 0)
ok = truecontinue;▼
 
if (u != 0) c++;▼
}
 
Line 61 ⟶ 70:
// Shuffle to randomly break ties
random_shuffle(counts.begin(), counts.end());
 
sort(counts.begin(), counts.end()); // Lexicographic sort▼
// Lexicographic sort
▲ sort(counts.begin(), counts.end()); // Lexicographic sort
 
array<int, 8> out;
for (int i = 0; i < 8; i++i)
out[i] = get<1>(counts[i]);
return out;
}
 
void solve(const string start) {
{
for (int v = 0; v < N; v++)▼
for (int uv = 0; uv < N; u++v)
▲ for for(int vu = 0; vu < N; v++u)
data[v][u] = 0;
 
const int x0 = start[0] - 'a';
const int y0 = N - (start[1] - '0');
data[y0][x0] = 1;
 
Line 82 ⟶ 94:
 
int n = 0;
while (n < N*N-1) {
{
const int x = get<0>(order[n]);▼
const int yx = get<10>(order[n]);
▲ const int xy = get<01>(order[n]);
 
bool ok = false;
for (int i = get<2>(order[n]); i < 8; i++i) {
{
const int dx = moves[get<3>(order[n])[i]].first;▼
const int dydx = moves[get<3>(order[n])[i]].secondfirst;
▲ const int dxdy = moves[get<3>(order[n])[i]].firstsecond;
 
if (x+dx < 0 || x+dx >= N || y+dy < 0 || y+dy >= N)
continue;
if(data[y + dy][x + dx] != 0)
continue;
 
if (data[y + dy][x + dx] == 0) {n;
get<2>(order[n]) = i + 1;
data[y+dy][x+dx] = n ++ 1;
order[n] = make_tuple(x+dx, data[y+dy][, 0, sortMoves(x+dx], = ny+1dy));
order[n]ok = make_tuple(x+dx, y+dy, 0,true;
sortMoves(x+dx, y+dy))break;
▲ ok = true;
▲ break;
▲ }
}
 
if (!ok) { // Failed. Backtrack.
{
data[y][x] = 0;
n--n;
}
}
}
 
template<int N>
friend ostream& operator<<(ostream &out, const Board<N> &b);
};
 
template<int N>
ostream& operator<<(ostream &out, const Board<N> &b) {
{
for (int v = 0; v < N; v++) {
for (int uv = 0; uv < N; u++v) {
{
▲ if (u != 0)
for (int u = 0; u < N; out++u) << ",";
{
if (u != 0) out << ",";
out << setw(3) << b.data[v][u];
}
Line 126 ⟶ 145:
}
 
int main() {
{
Board<5> b1;
b1.solve("c3");
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/183317"