Hi, guys, my son just finished his elementary shcool life, prepared for his junior middle school. Very hard to compete wiht his mates now in Beijing of China, the junior middle school release some problems for them to solve so as to sort the excellent ones out, here are one sample problem. It took me about two hours to make thourgh this problem with C++. RUNNING TRIPLETS There are nine teams of runners, with three runners in each team. Each team wear uniforms with the same number. They crossed the finish line such that each team's second team member to finish was separated from his teammates by a number of other runners equal to his uniform number, as show below, * * * 2 * * 2 * * 2 * * * * * * * * (Note every asterisk represents a runner, digit 2 represents the number 2 team runner) Team number 2's middle finisher is separated from his teammates by two runners on each side at the finish. （Note that these are not necessaryily the places in which the members of team 2 finished.) The same principle applies to the other numbered teams. Given that a member of team 1 won the race, can you figure out how they all crossed the finish line? Is there at least one solution to this puzzle? (No two or more runners cross the finish line in the same time.) Later I would post my code here.
Okay, here are the snippet code, #define RUNNER_TEAM_SIZE 9 #define RUNNER_TEAM_RUNNER 3 #define RUNNER_SIZE RUNNER_TEAM_SIZE * RUNNER_TEAM_RUNNER int arrPos[RUNNER_SIZE] = { 0 }; //int arrOccupied[RUNNER_SIZE] = { 0 }; int arrMap[RUNNER_TEAM_SIZE+1] = { 0 }; int iCount = 0; bool checkValid(int pos, int iNumber) { bool Ret = false; int next = pos + iNumber + 1; int end = next + iNumber + 1; do { if (arrMap[iNumber] > 0) break; if (pos >= RUNNER_SIZE || next >= RUNNER_SIZE || end >= RUNNER_SIZE) break; if (arrPos[pos] > 0 || arrPos[next] > 0 || arrPos[end] > 0) break; arrPos[pos] = arrPos[next] = arrPos[end] = iNumber; arrMap[iNumber] = true; Ret = true; } while (false); return Ret; } void revert(int pos, int iNumber) { int next = pos + iNumber + 1; int end = next + iNumber + 1; arrPos[pos] = arrPos[next] = arrPos[end] = 0; arrMap[iNumber] = false; } void dfs(int iLevel, int next) { int i = 0; int pos = 0; // if (iLevel == RUNNER_TEAM_SIZE) { // match for (i = 0; i < RUNNER_SIZE; i++) printf("%d ",arrPos); iCount++; printf("\n"); return; } if (iLevel > RUNNER_TEAM_SIZE) return; for (i = next; i < RUNNER_SIZE; i++) { if (arrPos == 0) { pos = i; break; } } if (pos < RUNNER_SIZE) { for (i = 1; i < 10; i++) { if (checkValid(pos, i)) { dfs(iLevel + 1,pos+1); // successfully stuff the arry, need revert revert(pos, i); } } } } int main() { arrMap[1] = true; arrPos[0] = arrPos[2] = arrPos[4] = 1; int iLevel = 0; int iPos = 1; iLevel++; dfs(iLevel, iPos); return 0; } Output: 1 8 1 9 1 5 2 6 7 2 8 5 2 9 6 4 7 5 3 8 4 6 3 9 7 4 3 1 9 1 2 1 8 2 4 6 2 7 9 4 5 8 6 3 4 7 5 3 9 6 8 3 5 7 1 9 1 6 1 8 2 5 7 2 6 9 2 5 8 4 7 6 3 5 4 9 3 8 7 4 3
