We describe here an O(N2) algorithm.
First of all, we might as well just focus on whether a single king can capture all of the checkers. So, at a cost of multiplying our runtime by N2, we can consider each of the kings one at a time.
Suppose that the king we chose is at square (si,sj). We consider the following graph:
In this graph, each opposing checker belongs to up to two edges. To capture all of the opponent's pieces, we need to start at (si,sj) and then travel along edges so that we have traveled over exactly one edge that contains each checker. However, we can only ever travel over AT MOST one edge, as the following argument shows:
Define a function f on the squares so that f(i,j) = i+j. Then jumping over a checker changes i and j both by 2, and so changes f(i,j) by 4. But of the 4 squares around a checker, two of them differ by 2 from the other 2:
(i-1,j-1) + - + (i+1,j-1)
- o -
(i+1,j+1) + - + (i+1,j+1)
As you can see, the (i-1,j-1) and (i+1,j+1) squares differ by 2 in their f-values from the (i+1,j-1) and (i+1,j+1) squares. Therefore, no sequence of jumps can take us from one of these sets of squares to the other (as f always changes by a multiple of 4). We can therefore never travel over both edges, as we can't even get to the endpoints of one of the edges. We are therefore looking to travel over each edge EXACTLY once. For those unfamiliar with this situation, such a traversal is called an Eulerian path/circuit, and it can be computed in O(E) time, where E is the number of edges in a graph (here E is potentially O(N2)).
We can therefore run the Eulerian path algorithm from each king, check to see if the algorithm returns a sensible path, and if so print it. Since it takes O(N^2) to process each king, the algorithm is potentially O(N^4). This, however, is too slow.
We can do better by splitting up the possible edges based on whether the king starts at a square with f(i,j) equal to 1 or 3 mod 4 (this assumes that the upper-left squares is '-'). If two kings are adjacent to a checker and have the same parity mod 4, then it is impossible to jump over all of the checkers with either of those kings (as one king would have to end up going through the square of the other king). Therefore, the extra O(N^2) factor we added to our runtime is silly. Instead, we can first check if there is more than one king of a given parity that is adjacent to a checker. If there is, then there aren't any Eulerian paths starting from kings of that parity. Otherwise, we just need to check the single king (out of laziness, my code below checks all kings since all but one attempt will terminate after a single move). This means that we only need to do two Eulerian path searches total, thus reducing the running time to O(N2).
Here is the code:
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define E (-1)
#define U (0)
#define O (1)
#define K (2)
//empty, unoccupied, opponent, king
char c;
int opp=0,vp;
int N;
int arr[205][205];
int vi[70000];
int vj[70000];
bool used[205][205];
int epos[205][205];
int dr[4] = {2,2,-2,-2};
int dc[4] = {2,-2,2,-2};
void rec(int i,int j){
while(epos[i][j]<4){ //while we still have unused edges at this vertex
if(i+dr[epos[i][j]]<0) epos[i][j]++; //if this edge takes us out of
bounds, skip it
else if(i+dr[epos[i][j]]>=N) epos[i][j]++;
else if(j+dc[epos[i][j]]<0) epos[i][j]++;
else if(j+dc[epos[i][j]]>=N) epos[i][j]++;
else if(arr[i+dr[epos[i][j]]/2][j+dc[epos[i][j]]/2]!=O) epos[i][j]++; //if
the square underneath this edge isn't an opposing piece, skip it
else if(arr[i+dr[epos[i][j]]][j+dc[epos[i][j]]]!=U) epos[i][j]++; //if the
square on the other side of this edge is occupied, skip it
else if(epos[i+dr[epos[i][j]]][j+dc[epos[i][j]]]>3-epos[i][j]) epos[i][j]++;
//if we have already traversed this edge in the other direction, skip it
else {
epos[i][j]++; //delete this edge and then recurse on it
rec(i+dr[epos[i][j]-1],j+dc[epos[i][j]-1]);
}
}
vi[vp]=i; vj[vp]=j; vp++; //add this vertex to the path
}
bool sanitize(){
for(int s=0;s<vp-1;s++){
if(abs(vi[s+1]-vi[s])!=2) return 0; //check to see that the two adjacent
vertices in the path are connected by an edge
if(abs(vj[s+1]-vj[s])!=2) return 0;
if(arr[(vi[s+1]+vi[s])/2][(vj[s+1]+vj[s])/2]!=O) return 0; //check to see
that the square underneath the edge has an opposing piece
}
return 1;
}
int euler(int si,int sj){
for(int i=0;i<N;i++){
memset(used[i],0,sizeof(used[i]));
memset(epos[i],0,sizeof(epos[i]));
}
vp = 0;
arr[si][sj]=U; //set the starting square to be unoccupied
rec(si,sj); //run Eulerian path algorithm
arr[si][sj]=K; //put the king back down in the starting square
if(!sanitize()) return -1; //if the path is invalid, return -1
return vp; //otherwise, return the number of edges in the path
}
int main(){
FILE *fin = fopen("winchk.in","r");
FILE *fout = fopen("winchk.out","w");
fscanf(fin,"%d",&N);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++){
do fscanf(fin,"%c",&c); while(c==' '||c=='\n');
if(c=='-') arr[i][j]=E;
if(c=='+') arr[i][j]=U;
if(c=='o') { arr[i][j]=O; opp++; }
if(c=='K') arr[i][j]=K;
}
int cnte = 0, cnto = 0;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<4;k++)
if(arr[i][j]==K&&i+dr[k]/2>=0&&i+dr[k]/2<N&&j+dc[k]/2>=0&&j+dc[k]/2<N&&arr[i+dr[k]/2][j+dc[k]/2]==O){
//check how many kings of each parity touch an edge
if((i+j)%4==1) cnto++;
else cnte++;
break;
}
for(int i=0;i<N;i++)
for(int j=0;j<N;j++){
if(cnto!=1&&(i+j)%4==1) continue; //if more than one king of this
parity touches an edge, we can't find a solution for this parity
if(cnte!=1&&(i+j)%4==3) continue;
if(arr[i][j]==K&&euler(i,j)==opp+1){ //check for a path from each king
for(int k=vp-1;k>=0;k--) //print the path if it exists
fprintf(fout,"%d %d\n",vi[k]+1,vj[k]+1);
fclose(fin); fclose(fout); return 0;
}
}
fprintf(fout,"impossible\n");
fclose(fin); fclose(fout);
return 0;
}