Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Knight tour checking
// t12e15.knightTourCheck.cpp
// juanfc 2021-12-19
//
#include <iostream>
#include <array>
using namespace std;
const int N = 8;
typedef array<array<int,N>,N> TChessboard;
bool checkKnight(TChessboard t, int i=0, int j=0);
int main()
{
TChessboard t = {{
{{ 1, 64, 61, 42, 37, 40, 55, 52}},
{{60, 43, 2, 63, 56, 53, 36, 39}},
{{ 3, 62, 59, 20, 41, 38, 51, 54}},
{{44, 19, 4, 57, 50, 21, 32, 35}},
{{ 5, 58, 45, 18, 31, 34, 49, 22}},
{{14, 17, 6, 25, 46, 11, 30, 33}},
{{ 7, 26, 15, 12, 9, 28, 23, 48}},
{{16, 13, 8, 27, 24, 47, 10, 29}},
}};
cout << "Chess Knight tour ";
if (checkKnight(t)) cout << "CORRECT" << endl;
else cout << "INCORRECT" << endl;
t = (TChessboard) {{
{{ 0, 59, 38, 33, 30, 17, 8, 63}},
{{37, 34, 31, 60, 9, 62, 29, 16}},
{{58, 1, 36, 39, 32, 27, 18, 7}},
{{35, 48, 41, 26, 61, 10, 15, 28}},
{{42, 57, 2, 49, 40, 23, 6, 19}},
{{47, 50, 45, 54, 25, 20, 11, 14}},
{{56, 43, 52, 3, 22, 13, 24, 5}},
{{51, 46, 55, 44, 53, 4, 21, 12}},
}};
cout << "Chess Knight tour ";
if (checkKnight(t)) cout << "CORRECT" << endl;
else cout << "INCORRECT" << endl;
return 0;
}
bool nextIsOk(TChessboard t, int& ii, int& jj);
bool checkKnight(TChessboard t, int i, int j)
{
int cnt = 1;
int cntMax = N*N;
while ( nextIsOk(t, i, j) )
++cnt;
return cnt == cntMax;
}
bool isIn(TChessboard t, int i, int j, int v);
bool nextIsOk(TChessboard t, int& ii, int& jj)
{
int i = ii, j = jj;
int shouldBe = t[i][j] + 1;
if ( isIn(t, i+1, j+2, shouldBe)) { ii = i+1; jj = j+2; }
else if (isIn(t, i-1, j+2, shouldBe)) { ii = i-1; jj = j+2; }
else if (isIn(t, i-2, j+1, shouldBe)) { ii = i-2; jj = j+1; }
else if (isIn(t, i-2, j-1, shouldBe)) { ii = i-2; jj = j-1; }
else if (isIn(t, i-1, j-2, shouldBe)) { ii = i-1; jj = j-2; }
else if (isIn(t, i+1, j-2, shouldBe)) { ii = i+1; jj = j-2; }
else if (isIn(t, i+2, j-1, shouldBe)) { ii = i+2; jj = j-1; }
else if (isIn(t, i+2, j+1, shouldBe)) { ii = i+2; jj = j+1; }
return ii != i;
}
bool isIn(TChessboard t, int i, int j, int v)
{
return i>=0 and i<N and j>=0 and j<N and t[i][j] == v;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment