Section 1: Print 92 Eight-Queens
Section 2: Walk-through a Maze
Section 3: Simulate Tortoise and Hare Race
Section 4: Simulate TicTac games
Section 5: Play Hanoi Towers game
Section 6: Print commercial styled calendar (1776-2775)
Section 7: Breaking Enigma Message
Section 8: Computer-assisted Poker Playing
Section 9: Print 1441 solutions for a difficult sudoku puzzle
Section 10: Print 6 million Knight's Tours
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <fstream>
#include <sstream>
#include <cstdio>
#include <conio.h>
using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::ifstream;
using std::ofstream;
using std::ostringstream;
using std::ios;
using std::strtok;
Section 1: A Simple Solution to Eight-Queens Puzzle (by dynamic permutation)
string mNum[64], mQueen[92];
string mIndex1[64], mIndex2[64], mIndex3[64];// Explanation in Setup1()
void Show4() // Convert one-dimensional to two-dimensional representation of a 8-queen
{
int k1, k2, n1, n2;
string x1, x2, aShow[64], aNum[] = {"0 ","1 ","2 ","3 ","4 ","5 ","6 ","7 ","8 ","9 "};
char c1[8];
ifstream InFile("91Queen.txt", ios::in);
n1 = 91; // n1 can be 0 - 91.
for (k1 = 0; k1 <= n1; k1++)
InFile >> x1;
InFile.close();
x1.copy(c1,8); // Convert string to char
for (k1 = 0; k1 <= 63; k1++) // Make a mold of a chessboard
aShow[k1] = "- ";
for (k1 = 0; k1 <= 7; k1++)
{
n1 = int(c1[k1]) - 48; // Convert char to integer
aShow[n1] = aNum[k1+ 1]; // Pour data into the mold
}
n1 = -1;
for (k2 = 1; k2 <= 8; k2++)
{
for (k1 = 1; k1 <= 8; k1++)
{
n1 = n1 + 1;
cout << aShow[n1];
}
cout << endl;
}
}
void Check3() // Check for any errors
{
int k1, k2, k3, n1;
string x1, x2,x3,aMove[92];
bool aFilter[64];
char c1[8];
ifstream InFile("91Queen.txt", ios::in);
for (k1 = 0; k1 <= 91; k1++)
InFile >> aMove[k1];
InFile.close();
for (k3 = 0; k3<= 91; k3++) // Does any queen attaches any of the other 7 queens?
{
aMove[k3].copy(c1,8); // First convert 8 queens (8 characters) into char then int
for (k2 = 0; k2 <= 63; k2++)
aFiler[k2] = false; // aFilter[n] is defaulted to be false
for (k2 = 0; k2 <= 7; k2++)
{
n1 = int(c1[k2]) - 48; // When there is a queen on a particular square
aFilter[n1] = true; // make the aFilter[n) true
}
for (k2 = 0; k2 <= 63; k2++)
{
if (aFilter[k2] == true) // Use 8 queens' square numbers to retrieve their value.
{
x1 = mIndex1[k2]; x2 = mIndex2[k2]; x3 = mIndex3[k2];
for (k1 = k2 + 1; k1 <= 63; k1++) // Any queen who shares a value with
{ // any other queen means she attacks her.
if (aFilter[k1] == true)
{
if (x1 == mIndex1[k1] || x2 == mIndex2[k1] || x3 == mIndex3[k1])
cout << "Mutual attack: in " << k2 << " " << k1 << endl;
}
}
}
}
}
aMove[91] = aMove[0]; // Set up an error test. Does this loops picks up a duplicit 8 queens
for (k2 = 0; k2 <= 90; k2++)
{
x1 = aMove[k2];
for (k1 = k2 + 1; k1 <= 91; k1++)
{
if (x1 == aMove[k1]) cout << "Dup in " << k2 << " and " << k1 << endl;
}
}
}
void Move2() // Permutate all possible 8-queen with a filtering. Row by row.
{
int k1, k2, k3, k4, n1, n2, aCount = -1, aLen = 7, aStart = 0,aEnd;
string x1, x2, x3, q1, q2,aMove[568], bMove[568], aShow[64];
bool aFilter[64];
char c1[8];
for (k1 = 0; k1 <= 7; k1++) // Load the first 8 queens on Row 0
aMove[k1] = mNum[k1];
for (k4 = 0; k4 <= 6; k4++) // permutate 7 rows (0 - 6)
{
aStart = aStart + 8; aEnd = aStart + 7; // Start with Row 2 (Square 8 to 17)
for (k3 = 0; k3 <= aLen; k3++)
{
q1 = aMove[k3]; q1.copy(c1,k4+1); //Convert string to char and then integer
for (k2 = aStart; k2 <= aEnd; k2++)
aFilter[k2] = true;
for (k2 = 0; k2 <= k4; k2++)
{
n1 = int(c1[k2]) - 48; // Use the integers to retrieve their value
x1 = mIndex1[n1]; x2 = mIndex2[n1]; x3 = mIndex3[n1];
for (k1 = aStart; k1 <= aEnd; k1++)
if (x1 == mIndex1[k1] || x2 == mIndex2[k1] || x3 == mIndex3[k1])
aFilter[k1] = false;
}
for (k2 = aStart; k2 <= aEnd; k2++)
{
if (aFilter[k2] == true)
{
aCount = aCount + 1; // If a queen does not share any
bMove[aCount] = q1 + mNum[k2]; // value with the next queen, strings
} // her up
}
}
aLen = aCount; aCount = -1;
for (k3 = 0; k3 <= aLen; k3++)
aMove[k3] = bMove[k3]; // Copy bMove to aMove and string up more queens.
}
ofstream OutFile("91Queen.txt", ios::out); // Save the 92 8-queens into a textfile.
for (k1 = 0; k1 <= 91; k1++)
OutFile << aMove[k1] << endl;
OutFile.close();
}
void SetUp1()
{
int k1, k2;
string x1, x2, x3;
for (k1 = 0; k1 <= 63; k1++)
mNum[k1] = char(k1+48);
// The chessboard has 64 squares. Each square is assigned 3 values.
// Column, forward diagonal and backward diagonal. Diagonal values are as below
// abcdefgh abcdefgh
// bcdefghi iabcdefg
// cdefghij jiabcdef
// defghijk kjiabcde
// efghijkl lkjiabcd
// fghijklm mlkjiabc
// ghijklmn nmlkjiab
// hijklmno onmlkjia
x1 = "abcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmno"; // Column value
x2 = "abcdefghiabcdefgjiabcdefkjiabcdelkjiabcdmlkjiabcnmlkjiabonmlkjia"; // forward diagonal
x3 = "abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh"; // backward diagonal
for (k1 = 0; k1<= 63; k1++)
{
mIndex1[k1] = x1.substr(k1,1);
mIndex2[k1] = x2.substr(k1,1);
mIndex3[k1] = x3.substr(k1,1);
}
}
void aMain()
{
int k1,k2,n1,n2;
string x1,x2;
SetUp1();
Move2();
Check3();
Show4();
}
int main(int argc, char** argv)
{
int k1,k2,n1,n2;
string x1,x2;
aMain();
exit(0);
system("PAUSE");
return 0;
}
Section 2: Walking through a maze
# # # # # # # # # # # #
# . . . # . . . . . . #
. . # . # . # # # # . #
# # # . # . . . . # . #
# . . . . # # # . # . .
# # # # . # . # . # . #
# . . # . # . # . # . #
# # . # . # . # . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #
Overview
The maze is represented by a string array of 143 positions (one dimentional)
The walls are reprensented by hashes and the path's position, the dots.
The value are set as follows:
The wall: 9; the path: 0 and the exit position: -1.
A position's value increased by 1 when it is stepped on.
There are four walking directions. 1 represents forward: -1, backward,
-12, left and 12, right."Place your hand on the wall and begin walking
forward" means the program sets direction priorities as step(0) = 1,
step(1) = 12, step(2) = -12, step(3) = -1. A person starts on left side
of the maze means his start values 24. The 24 + step(n) yields 4 positions:
25(value: 0),12(value: 9), 36(value: 9) and 23(value: 9). The program,
through a loop of 0 - 3, picks the position with the smalles value, 25.
Now his start value is 25. The program ends when he steps on the exit
ofstream OutFile("MazeTra.txt", ios::out);
int mRate[144] = {0};
string mMaze[144]; // hashes mean wall and dots means path. s means start and e means end.
void Move2a() // The walking through step by step is printed in a text file with the
// the folder named Mazetra.txt
{
int k1,k2;
string x1;
for (k2 = 0; k2 <= 132; k2+= 12)
{
x1 = "";
for (k1 = k2; k1 <= k2 + 11; k1++)
x1 = x1 + mMaze[k1] + " ";
OutFile <<" " << x1 << endl; // Print a snapshots of the maze board
}
OutFile << "" << endl;
}
void Move3() // Walking through a no exit maze
{
int k1, k2,n1, n2,aStart = 24, bStart = 24,cStart, aMin;
int Start1[] = {0,24,59},aStep[] = {1,12,-12,-1};
string x1;
mMaze[aStart] = "s"; mMaze[59] = "#";
mRate[aStart] = 0; mRate[59] = 9;
do
{
aMin = 9; // Find out the position with the smallest value
for (k1 = 0; k1 <= 3; k1++)
{
n1 = aStart + aStep[k1];
n2 = mRate[n1];
if (aMin > n2)
{
aMin = n2; bStart = n1;
}
}
aStart = bStart; mRate[aStart] = mRate[aStart] + 1;
if (mRate[aStart] == 1)
x1 = "x";
else if (mRate[aStart] == 2)
x1 = "y";
else
x1 = "z";
mMaze[aStart] = x1;
Move2a();
} while (aStart != 24);
}
void Move2(int pStart) // User input: 1 means starts on left side and 2, right side.
{
int k1, k2,n1, n2,aStart, aEnd,bStart, aMin, Start1[] = {0,24,59},aStep[] = {1,12,-12,-1};
string x1;
aStart = Start1[pStart]; aEnd = 83 - aStart; // If start = 24 then end = 83 - 24
mMaze[aStart] = "s"; mMaze[aEnd] = "e"; // If start = 59 then end = 83 - 59
mRate[aStart] = 1; mRate[aEnd] = -1;
while (aStart != aEnd)
{
aMin = 9;
for (k1 = 0; k1 <= 3; k1++)
{
n1 = aStart + aStep[k1];
n2 = mRate[n1];
if (aMin > n2)
{
aMin = n2; bStart = n1;
}
}
aStart = bStart; mRate[aStart] = mRate[aStart] + 1;
if (mRate[aStart] == 1)
x1 = "x";
else if (mRate[aStart] == 2)
x1 = "y";
else
x1 = "z";
mMaze[aStart] = x1;
if (aStart != aEnd) break;
Move2a();
}
}
void SetUp1()
{
int k1;
string x1,x2;
x1 = "#############...#......#..#.#.####.####.#....#.##....###.#..####.#.#.#.##..#.#.#.#.###.#.#.#.#.##........#.#######.###.##......#...#############";
for (k1 = 0; k1 <= 143; k1++)
{
x2 = x1.substr(k1,1);
mMaze[k1] = x2;
if (x2 == "#") mRate[k1] = 9;
}
}
void aMain()
{
int k1,n1;
string x1,x2;
string Direc[] = {"","Starting on left", "Starting on right","A maze without an exit"};
SetUp1();
OutFile << "Walking through the maze" << endl;
Move2a();
cout << "Start from left TYPE 1. From right, type 2, a maze without an exit,3: ";
cin >> n1;
OutFile << Direc[n1] << endl;
if (n1 == 2)
OutFile << "(x means the path was stepped on once while y means twice" << endl;
if (n1 == 3)
{
OutFile << "(x: the path stepped on once, y: twice, and z: three times." << endl;
Move3();
}
else
Move2(n1);
OutFile.close();
}
int main(int argc, char** argv)
{
aMain();
exit(0);
system("PAUSE");
return 0;
}
Section 3
Simulate the Race of Tortoise and Hare
1. Permutate 1 million races
2. Evaluate the fairness of the moves of the tortoise and the hare (each animal wins half races.)
3. Play back easily any race (win, lose and tie)
4. The program makes it easily to do statistical analysis for the 1 million race.
(e.g. the shortest race and the longest one and the average race length, so on
Tortoise 50% 3 squares forward
20% 6 squares backward
30% 1 square forward
Hare 20% 0 square forward
20% 9 squares forward
10% 12 squares backward
30% 1 square forward
10% 2 squares backward
10% 4 squares backward
Race course: 70 squares
// Length of race: 10 - 378;
int tIndex[] = {3,3,3,3,3,-6,-6,1,1,1},hIndex[] = {0,0,9,9,-12,1,1,1,-2,-4},mFlip[101];
//int tIndex[] = {3,3,3,3,3,-6,-6,1,1,1},hIndex[] = {0,0,9,9,-12,1,1,1,-2,-2};
string mNum[70];
void PlayBack4() // This is stand-alone function depending on a textfile "Racekk2.txt"
{
int k1,n1,aLen;
string x1, x2,aWin[] = {"H","T","I"}, bWin;
char c1[1500];
cout << "Hare racing tortoise. Who wins? type 0 for hare, 1 for tortoise, 2 for a tie: ";
cin >> n1;
bWin = aWin[n1];
ifstream InFile("Racekk2.txt", ios::in);
for (k1 = 0; k1 <= 999999; k1++)
{
getline(InFile,x1);
aLen = x1.length() - 71;
x2 = x1.substr(aLen,1);
if (x2 == bWin) break;
}
aLen = x1.length() / 71; // Race is 70 squares + 1 (finished line)
n1 = -71;
for (k1 = 1; k1 <= aLen ; k1++)
{
n1 = n1 + 71;
cout << x1.substr(n1,71) << endl;
}
}
void Race3()
{
int k1,k2, n1,n2, n3,r1, r2,aLen;
string x1,aRace, bRace,cRace,aMess[3];;
char c1[999];
aRace = " |";
aMess[0] = "Tortoise wins! ";
aMess[1] = "Hare wins! ";
aMess[2] = "It's a tie. ";
ifstream InFile("Racekk1.txt", ios::in); // Change positions into race course snapshots.
ofstream OutFile("Racekk2.txt", ios::out);
for (k2 = 0; k2 <= 999999; k2++)
{
InFile >> x1; // A move has 2 ASCII numbers:
aLen = x1.length(); // the first is Tortoise' position and the second is Hare's
x1.copy(c1,aLen); cRace = ""; // e.g. 25: T is in position 2 and H is in 5
for (k1 = 0; k1 < aLen; k1+= 2)
{
bRace = aRace;
n1 = int(c1[k1]) - 48; n2 = int(c1[k1+1]) - 48;
if (n1 != n2)
{
bRace.replace(n1,1,"T"); bRace.replace(n2,1,"H");
}
else
{
if (n1 < 63)
n3 = n1; // Race must stay within 70-course
else
n3 = 63;
bRace.replace(n3,7,"OUCH!!!");
}
cRace = cRace + bRace;
}
if (n1 > n2)
n3 = 0; // Tortoise wins
else if (n1 < n2)
n3 = 1; // Hare wins
else
n3 = 2; // It's a tie
cRace = cRace + aMess[n3];
OutFile << cRace << endl;
}
OutFile.close();
InFile.close();
}
void Race2()
{
int k1,k2,n1 = 0,n2 = 0,n3 = 0,t1, t2,h1, h2; // t1,t2: tortoise; h1,h2: hare
string aRace;
ofstream OutFile("Racekk1.txt", ios::out);
for (k2 = 0; k2 <= 999999; k2++) // Pile up position changes
{
t1 = 20; h1 = 20; aRace = ""; // To avoid arrays with minus' index
while (t1 != 89 && h1 != 89) // use 20 to represent 1 and 89, square 70
{
t2 = rand() % 10; h2 = rand() % 10;
t1 = tIndex[t2] + t1; t1 = mFlip[t1]; // When position drops below 1
h1 = hIndex[h2] + h1; h1 = mFlip[h1]; // position = 1
t2 = t1 - 20; h2 = h1 - 20;
aRace = aRace + mNum[t2] + mNum[h2];
}
OutFile << aRace << endl;
if (t2 > h2)
n1 = n1 + 1;
else if (t2 < h2)
n2 = n2 + 1;
else
n3 = n3 + 1; //Count the wins and tie
}
OutFile.close();
ofstream aOutFile("RaceSum.txt", ios::out);
aOutFile << "Simulating a million races of tortoise vs hare."<< endl;
aOutFile << "Tortoise's Win " << " Hare's Win " << "Tie" << endl;
aOutFile << n1 << " " << n2 << " " << n3 << endl;
aOutFile.close();
}
void SetUp1()
{
int k1,n1;
n1 = 47; //Use ASCCI to represent the positions (1 - 70)
for (k1 = 0; k1 <= 69; k1++)
{
n1 = n1 + 1; mNum[k1] = char(n1);
}
for (k1 = 0; k1 <= 20; k1++) // If position drops to below 1 then position = 1
mFlip[k1] = 20;
for (k1 = 21; k1 <= 89; k1++)
mFlip[k1] = k1;
for (k1 = 90; k1 <= 99; k1++) // If position rises to above 70 then position = 70
mFlip[k1] = 89;
}
void aMain()
{
int k1,k2,n1, n2;
string x1,x2;
srand(time(0));
SetUp1();
// Race2(); // Race2,3 compile a race list
// Race3(); // They need to run only once.
PlayBack4(); // Playback4 runs many times.It does not need to run race2,3.
}
int main(int argc, char** argv)
{
aMain();
exit(0);
system("PAUSE");
return 0;
}
Section 4: Simulate TicTac games
Using dynamic permutation to solve problems
This program accomplishes 3 tasks
1. Compile a complete list of all possible single moves in the form of text file
using snapshots of the game board to represent moves. e.g. "000010000" means
player 1 putting a soldier in Square 4 while player 2 answers with a move in
Square 0: "200010000"
2. Compile a complete list of all games in the forms of snapshots. The shortes game is:
"000010000 200010000 200011000 200211000 210211000 2100211200 w". w means it is a win.
3. Compile a complete list of all games formatted and in 2-D form. The format is:
"012 - - - - - - 345 - - - 678 - - - ". The print0ut:
012 - - - - - -
345 - - - - - -
678 - - - - - -
The first 2 moves of ""000010000 200010000" is displayed:
012 - - - 2 - -
345 - 1 - - 1 -
678 - - - - - -
4. A human player vs the program live.
The program uses human's moves to retrieve the program's answering moves in the form of
snapshot from the snapshot list (a text file) and displays the moves.
Data representation
1. Game board: a string array[9]
2. 1 means Player 1 and 2 means Player 2
3. Use an integer mCheck[23] to reorder the 9 squares by row, column and diagonally.
So we can find out quickly and easily a checkmate situation and checkmate.
Permutation
Human moves first:
1. A game starts with "000000000"
2. Permutate to "100000000 010000000 ... 000000001
3. The program answers these moves with "100020000 010020000 ... 000020001"
4. When the game moves to round 3, filter out the winning games.
5. From now on alternate between filtering out and permutation until the game is over.
Program moves first
1. A game starts with "000020000"( the dead center of the board)
The TicTac program is divided in 5 mini-sub-programs
1. Compilation of all moves' snapshot (human as first mover)
2. Compilation of all moves' snapshot (human as second mover)
3. Compilation of all possible games (human as first mover)
4. Compilation of all possible games (hman as second mover)
5. Live game playing (human starts by choosing as either first mover or the second)
The program displays a promt: "Play Tic-tac-toe as first mover type 1 else type 2:"
The program then print the game board as follows:
012 - - - - - -
345 - - - - - -
678 - - - - - -
The program prints: "To play a game, type a number now:" 4
It then displays a human's move and the program's return move (square 0)
012 - - - 2 - -
345 - 1 - - 1 -
678 - - - - - -
At the end the program diplays: Game's over. You lost (or Game's over. You tied.)
Some return moves are individually decided by the programmer for efficiency purpose.
By design, the program never loses and all games are made to as short as possible.
When the program is the first mover. Its first move is the dead center: square 4.
//Part 1: Player 1: human vs Player 2: computer.
//compiles a list of every move in the form of snapshot (of the game board).
//Processing from bottom up.
int mStart, mEnd, mCheck[] = {0,1,2,3,4,5,6,7,8,0,3,6,1,4,7,2,5,8,0,4,8,2,4,6};
string mMove[319], nMove[319]; // Total sets of moves.
void Move4() // 206 - 318
{
int k1,k2, k3,n1,aCount = -1,bCount, aLen, aKey, bKey;
int aHole[] = {3,1,2,1,6,6,2,3}; // Programmer decided individual moves
string x1,x2, x3, aWin,aMove[43], bMove[129],aPosit[9];
for (k1 = mStart; k1 <= mEnd; k1++)
{
x1 = nMove[k1];
if (x1.substr(9,1) == "c") // if the snapshot's status is "c" then continues
{
aCount = aCount + 1;
aMove[aCount] = x1.substr(0,9);
}
}
aLen = aCount; aCount = -1; mStart = mEnd + 1;
for (k2 = 0;k2 <= aLen; k2++)
{
x1 = aMove[k2];
for (k1 = 0; k1 <= 8; k1++)
{
x2 = x1;
if (x2.substr(k1,1) == "0")
{
x2.replace(k1,1,"1"); // Permutate player 1's all moves
aCount = aCount + 1;
bMove[aCount] = x2;
}
}
}
aLen = aCount; aCount = mEnd;
for (k2 = 0; k2 <= aLen; k2++) // Filter out the duplicates
{
x1 = bMove[k2];
for (k1 = k2 +1; k1 <= aLen; k1++)
if (x1 == bMove[k1]) goto aSkip;
aCount = aCount + 1;
mMove[aCount] = x1;
aSkip: k1 = 0;
}
mStart = mEnd + 1; mEnd = aCount;
for (k3 = mStart; k3 <= mEnd; k3++)
{
x1 = mMove[k3]; bKey = 9; aWin = "c";
for (k2 = 0; k2 <= 8; k2++)
{
x2 = x1.substr(k2,1);
if (x2 == "0") x2 = "";
aPosit[k2] = x2;
}
for (k2 = 0; k2 <= 21; k2+= 3)
{
x1 = "";
for (k1 = k2; k1 <= k2+ 2; k1++)
{
n1 = mCheck[k1];
x1 = x1 + aPosit[n1];
if (aPosit[n1] == "") aKey = n1;
}
if (x1 == "22")
{
aWin = "w";
aPosit[aKey] = "2"; goto bSkip; // a 222 lineup ends the game
}
if (x1 == "11") bKey = aKey; // Block human's checkmate's attemp
}
if (bKey != 9) // There's a checmate situation.
{
aPosit[bKey] = "2"; goto bSkip;
}
for (k2 = 0; k2 <= 8; k2++)
{
if (aPosit[k2] == "")
{
aPosit[k2] = "2"; break; // No checkmate. It's a draw.
}
}
bSkip: k1 = 0;
x1 = "";
for (k2 = 0; k2 <= 8; k2++)
{
x2 = aPosit[k2];
if (x2 == "") x2 = "0";
x1 = x1 + x2;
}
nMove[k3] = x1 + aWin;
}
ofstream OutFile("Tic318.txt", ios::out); // The total unique move sets(2 moves): 318
for (k1 = 0; k1 <= mEnd; k1++)
{
x2 = nMove[k1];
if (k1 < 44) x2 = x2 + "c"; // There is no winning games before snapshot 44.
x1 = mMove[k1] + " " + x2;
OutFile << x1 << endl; // Save all games (move by move) in text file.
}
OutFile.close(); // The file makes it possible to evaluate the programmer's gamesmanship.
}
void Move3() // 44 - 205
{
int k1,k2, k3,n1,aCount = -1, bCount, aLen,aKey, bKey;
int aHole[] = {3,1,2,1,6,6,2,3};
string x1,x2, x3, aWin,aMove[175], aPosit[9];
for (k3 = mStart;k3 <= mEnd; k3++) // This for-loop permutate the 44 moves
{
x1 = nMove[k3].substr(0,9);
for (k2 = 0; k2 <= 8; k2++)
{
x2 = x1;
if (x2.substr(k2,1) == "0")
{
x2.replace(k2,1,"1");
aCount = aCount + 1;
aMove[aCount] = x2;
aSkip: k1 = 0;
}
}
}
aLen = aCount; aCount = mEnd; mStart = mEnd + 1;
for (k2 = 0; k2 <= aLen; k2++) // This loop filters out the duplicates
{
x1 = aMove[k2];
for (k1 = k2 + 1; k1<= aLen; k1++)
if (x1 == aMove[k1]) goto aBottom;
aCount = aCount + 1;
mMove[aCount] = x1;
aBottom: k1 = 0;
}
mEnd = aCount; aCount = -1;
for (k3 = mStart; k3 <= mEnd; k3++)
{
x1 = mMove[k3]; bKey = 9; aWin = "c";
// An unfinished game is defaults to "c" meaning continuing
for (k2 = 0; k2 <= 8; k2++)
{
x2 = x1.substr(k2,1);
if (x2 == "0") x2 = "";
aPosit[k2] = x2;
}
for (k2 = 0; k2 <= 21; k2+= 3)
{
x1 = "";
for (k1 = k2; k1 <= k2+ 2; k1++)
{
n1 = mCheck[k1];
x1 = x1 + aPosit[n1];
if (aPosit[n1] == "") aKey = n1;
}
if (x1 == "22")
// If there is "22" line-up, move to that unit remaining square
{
aPosit[aKey] = "2"; aWin = "w"; // Finish the game with a win.
goto bSkip;
}
if (x1 == "11") bKey = aKey;
}
if (bKey != 9)
{
aPosit[bKey] = "2"; goto bSkip;
//If there is a checkmate situation, block it.
}
aCount = aCount + 1;
n1 = aHole[aCount]; aPosit[n1] = "2";
bSkip: k1 = 0;
x1 = "";
for (k2 = 0; k2 <= 8; k2++)
{
x2 = aPosit[k2];
if (x2 == "") x2 = "0";
x1 = x1 + x2;
}
nMove[k3] = x1 + aWin;
}
}
void Move2() // 9 - 43
{
int k1,k2, k3,n1,aCount = -1, bCount = 8, aKey;
int aHole[] = {7,5,1,2,0,5,3,3,7,1,3,1,0,1,2,1,2};
string x1,x2, x3,aMove[35], aPosit[9];
for (k3 = 0;k3 <= 8; k3++) // Permutate 8 moves to 43 moves for player 1.
{
x1 = nMove[k3];
for (k2 = 0; k2 <= 8; k2++)
{
x2 = x1;
if (x2.substr(k2,1) == "0") // "0" means unoccupied squares
{
x3 = x2.replace(k2,1,"1");
for (k1 = 0; k1 <= aCount; k1++)
{
if (x3 == aMove[k1]) goto aSkip; //Filter out any duplicates
}
aCount = aCount + 1; bCount = bCount + 1;
mMove[bCount] = x3; aMove[aCount] = x3;
aSkip: k1 = 0;
}
}
}
mStart = k3; mEnd = bCount; aCount = -1;
for (k3 = mStart; k3 <= mEnd; k3++)
{
x1 = mMove[k3];
for (k2 = 0; k2 <= 8; k2++)
{
x2 = x1.substr(k2,1);
if (x2 == "0") x2 = "";
aPosit[k2] = x2;
}
for (k2 = 0; k2 <= 21; k2+= 3)
// Reorder the 9-square game board into 24-square board
// (row, column and diagonal). 3 squares a unit and 8 units in total.
{
x1 = "";
for (k1 = k2; k1 <= k2+ 2; k1++)
{
n1 = mCheck[k1];
x1 = x1 + aPosit[n1];
if (aPosit[n1] == "") aKey = n1;
}
if (x1 == "11") // A unit value "11" means there is a checkmate situation.
{
aPosit[aKey] = "2"; // Player 2 moves to that square to stop a checkmate
goto bSkip;
}
}
aCount = aCount + 1;
bCount = aHole[aCount]; aPosit[bCount] = "2";
// If there is no checkmate situation, programmer what square to go
bSkip: k1 = 0;
x1 = "";
for (k2 = 0; k2 <= 8; k2++)
{
x2 = aPosit[k2];
if (x2 == "") x2 = "0";
x1 = x1 + x2; // Making up the move - snapshot
}
nMove[k3] = x1;
}
}
void Move1() // 0 - 8 Start the first set of moves by player 1 and the returned moves by player 2
{
int k1, n1;
string x1,x2;
x1 = "100000000010000000001000000000100000000010000000001000000000100000000010000000001";
x2 = "100020000010020000001020000000120000200010000000021000000020100000020010000020001";
// x1: all possible 9 moves Player 1 can make. And store the moves into mMove[n]
// x2: the 9 moves Player 2 answers and stores the moves into nMove[n]
n1 = -9;
for (k1 = 0; k1 <= 8; k1++)
{
n1 = n1 + 9;
mMove[k1] = x1.substr(n1,9);
nMove[k1] = x2.substr(n1,9);
}
}
void aMain()
{
int k1,n1;
string x1;
Move1();
Move2();
Move3();
Move4();
}
int main(int argc, char** argv)
{
aMain();
exit(0);
system("PAUSE");
return 0;
}
//Part 2: Player 1 Computer vs Player 2 Human. Computer's first move is square 4 (the center)
// This program translates snapshot representation of games to 2-D and formatted
// representation and save the games into a text file(human as player 2 vs computer
// as player 1). So anyone can play back all the games easily.
int mIndex[9],nIndex[9], mCheck[] = {0,1,2,3,4,5,6,7,8,0,3,6,1,4,7,2,5,8,0,4,8,2,4,6};
string mMove[319],nMove[319], mGame[457];
// Display a move for testing purpose
void Show3b(string pGame)
{
int k1,n1, aLen;
string x1;
aLen = pGame.length() / 21; // Each set of moves is in length of 21 characters
n1 = -21;
for (k1 = 1; k1 <= aLen; k1++)
{
n1 = n1 + 21;
x1 = pGame.substr(n1,21);
cout << x1 << endl;
if (k1 % 3 == 0) cout << endl;
}
}
// From snapshots to 2-D and move by move game representation
string AllGames3a(string pMove,string qMove)
{
int k1,k2,n1;
string x1,x2;
string aMold = "0 1 2 _ _ _ _ _ _ 3 4 5 _ _ _ _ _ _ 6 7 8 _ _ _ _ _ _ ";
for (k1 = 0; k1 <= 8; k1++)
{
x1 = pMove.substr(k1,1);
if (x1 != "0")
{
n1 = mIndex[k1];
aMold.replace(n1,1,x1);
}
}
for (k1 = 0; k1 <= 8; k1++)
{
x1 = qMove.substr(k1,1);
if (x1 != "0")
{
n1 = nIndex[k1];
aMold.replace(n1,1,x1);
}
}
return aMold;
}
void AllGames3()
{
int k1,k2,n1,aLen;
string x1,x2, x3, aMove, bMove,aGame,aWin;
ofstream OutFile("GameA456bx.txt", ios::out);
for (k2 = 0; k2 <= 456; k2++)
{
aMove = mGame[k2]; aWin = "Game's over You tied.";
if (aMove.find("w",0) != -1) aWin = "Game's over. You lost";
aLen = aMove.length() / 20;
n1 = -20; aGame = "";
for (k1 = 1; k1 <= aLen; k1++ )
{
n1 = n1 + 20;
bMove = aMove.substr(n1,20);
x1 = bMove.substr(0,9); x2 = bMove.substr(10,9);
x3 = AllGames3a(x1,x2);
aGame = aGame + x3;
}
aGame = aGame + aWin;
OutFile << aGame << endl;
}
OutFile.close();
}
string MoveA2a(string pMove)
{
int k1;
string x1;
for (k1 = 0; k1 <= 318; k1++)
if (pMove == mMove[k1]) break;
x1 = nMove[k1];
return x1;
}
void MoveA2()
{
int k1,k2,k3,n1,aCount = -1, bCount = -1,aLen = 8;
string x1,x2, x3,aMove, bMove, aPosit[9];
string aGame[457], bGame[457], wGame[457];
//The first set of moves:
x1 = "100000000 010000000 001000000 000100000 000010000 000001000 000000100 000000010 000000001 ";
x2 = "100020000 010020000 001020000 000120000 200010000 000021000 000020100 000020010 000020001 ";
n1 = -10;
for (k1 = 0; k1 <= 8; k1++)
{
n1 = n1 + 10; aGame[k1] = x1.substr(n1,10) + x2.substr(n1,10);
}
for (k3 = 10; k3 <= 30; k3+= 20)
{
for (k2 = 0; k2 <= aLen; k2++)
{
aMove = aGame[k2];
bMove = aMove.substr(k3,10);
for (k1 = 0; k1 <= 8; k1++)
{
x1 = bMove.substr(k1,1);
if (x1 == "0")
{
x2 = bMove;
x2.replace(k1,1,"1");
x3 = MoveA2a(x2);
aCount = aCount + 1;
bGame[aCount] = aMove + x2 + x3;
}
}
}
aLen = aCount; aCount = -1;
for (k2 = 0; k2 <= aLen; k2++) aGame[k2] = bGame[k2];
}
bCount = -1;
for (k3 = 0; k3 <= aLen; k3++)
{
aMove = aGame[k3]; bMove = aMove.substr(50,9);
for (k2 = 0; k2 <= 8; k2++)
aPosit[k2] = bMove.substr(k2,1);
for (k2 = 0; k2 <= 21; k2+= 3)
{
x1 = "";
for (k1 = k2; k1 <= k2 + 2; k1++)
{
n1 = mCheck[k1];
x1 = x1 + aPosit[n1];
}
if (x1 == "222")
{
bCount = bCount + 1;
wGame[bCount] = aMove;
goto aBottom;
}
}
aCount = aCount + 1;
bGame[aCount] = aMove;
aBottom: k1 = 0;
}
aLen = aCount; aCount = -1;
for (k2 = 0; k2 <= aLen; k2++)
{
aMove = bGame[k2]; bMove = aMove.substr(50,10);
for (k1 = 0; k1 <= 8; k1++)
{
x1 = bMove.substr(k1,1);
if (x1 == "0")
{
x2 = bMove;
x2.replace(k1,1,"1");
x3 = MoveA2a(x2);
aCount = aCount + 1;
aGame[aCount] = aMove + x2 + x3;
}
}
}
aLen = aCount; aCount = -1;
for (k3 = 0; k3 <= aLen; k3++)
{
aMove = aGame[k3]; bMove = aMove.substr(70,9);
for (k2 = 0; k2 <= 8; k2++)
aPosit[k2] = bMove.substr(k2,1);
for (k2 = 0; k2 <= 21; k2+= 3)
{
x1 = "";
for (k1 = k2; k1 <= k2 + 2; k1++)
{
n1 = mCheck[k1];
x1 = x1 + aPosit[n1];
}
if (x1 == "222")
{
bCount = bCount + 1; // Computer wins.
wGame[bCount] = aMove;
goto bBottom;
}
}
aCount = aCount + 1;
bGame[aCount] = aMove;
bBottom: k1 = 0;
}
for (k1 = 0; k1 <= bCount; k1++)
wGame[k1] = wGame[k1] + "w";
aLen = aCount;
for (k1 = 0; k1 <= aCount; k1++)
{
bCount = bCount + 1; wGame[bCount] = aGame[k1] + "t"; // t means a tie.
}
ofstream OutFile("GameB139x.txt", ios::out);
for (k1 = 0; k1 <= bCount; k1++)
OutFile << wGame[k1] << endl;
OutFile.close();
}
void SetUp1()
{
int k1, n1;
string x1;
ifstream InFile("TicA318.txt", ios::in);
for (k1 = 0; k1 <= 318; k1++)
{
getline(InFile, x1);
mMove[k1] = x1.substr(0,10); nMove[k1] = x1.substr(10,9) + " ";
}
InFile.close();
// Use this index to transform snapshots to graphical -like display
string p1[] = {"A","B","C","D","E","F","G","H","I","a","b","c","d","e","f","g","h","i"};
x1 = "0 1 2 A B C a b c 3 4 5 D E F d e f 6 7 8 G H I g h i ";
for (k1 = 0; k1 <= 8; k1++)
{
n1 = k1 + 9;
mIndex[k1] = x1.find(p1[k1],k1);
nIndex[k1] = x1.find(p1[n1],k1);
}
ifstream aInFile("GameA456aX.txt", ios::in);
for (k1 = 0; k1 <= 456; k1++)
getline(aInFile,mGame[k1]); //Load up all 456 games for play-back
aInFile.close();
}
void aMain()
{
int k1,n1;
string x1;
SetUp1();
AllGames3();
}
int main(int argc, char** argv)
{
aMain();
exit(0);
system("PAUSE");
return 0;
}
Part 3
// This program translates snapshot representation of games to 2-D and formatted
// representation and save the games into a text file(human as player 1 vs computer
// as player 2). So anyone can play back all the games easily.
int mIndex[9],nIndex[9], mCheck[] = {0,1,2,3,4,5,6,7,8,0,3,6,1,4,7,2,5,8,0,4,8,2,4,6};
string mMove[319],nMove[319], mGame[457];
// Display a move for testing purpose
void Show3b(string pGame)
{
int k1,n1, aLen;
string x1;
aLen = pGame.length() / 21;
n1 = -21;
for (k1 = 1; k1 <= aLen; k1++)
{
n1 = n1 + 21;
x1 = pGame.substr(n1,21);
cout << x1 << endl;
if (k1 % 3 == 0) cout << endl;
}
}
// From snapshots to 2-D and move by move game representation
string AllGames3a(string pMove,string qMove)
{
int k1,k2,n1;
string x1,x2;
string aMold = "0 1 2 _ _ _ _ _ _ 3 4 5 _ _ _ _ _ _ 6 7 8 _ _ _ _ _ _ ";
for (k1 = 0; k1 <= 8; k1++)
{
x1 = pMove.substr(k1,1);
if (x1 != "0")
{
n1 = mIndex[k1];
aMold.replace(n1,1,x1);
}
}
for (k1 = 0; k1 <= 8; k1++)
{
x1 = qMove.substr(k1,1);
if (x1 != "0")
{
n1 = nIndex[k1];
aMold.replace(n1,1,x1);
}
}
return aMold;
}
void AllGames3()
{
int k1,k2,n1,aLen;
string x1,x2, x3, aMove, bMove,aGame,aWin;
ofstream OutFile("GameA456bx.txt", ios::out);
for (k2 = 0; k2 <= 456; k2++)
{
aMove = mGame[k2]; aWin = "Game's over You tied.";
if (aMove.find("w",0) != -1) aWin = "Game's over. You lost";
aLen = aMove.length() / 20;
n1 = -20; aGame = "";
for (k1 = 1; k1 <= aLen; k1++ )
{
n1 = n1 + 20;
bMove = aMove.substr(n1,20);
x1 = bMove.substr(0,9); x2 = bMove.substr(10,9);
x3 = AllGames3a(x1,x2);
aGame = aGame + x3;
}
aGame = aGame + aWin;
OutFile << aGame << endl;
}
OutFile.close();
}
string MoveA2a(string pMove)
{
int k1;
string x1;
for (k1 = 0; k1 <= 318; k1++)
if (pMove == mMove[k1]) break;
x1 = nMove[k1];
return x1;
}
void MoveA2()
{
int k1,k2,k3,n1,aCount = -1, bCount = -1,aLen = 8;
string x1,x2, x3,aMove, bMove, aPosit[9];
string aGame[457], bGame[457], wGame[457];
x1 = "100000000 010000000 001000000 000100000 000010000 000001000 000000100 000000010 000000001 ";
x2 = "100020000 010020000 001020000 000120000 200010000 000021000 000020100 000020010 000020001 ";
n1 = -10;
for (k1 = 0; k1 <= 8; k1++)
{
n1 = n1 + 10; aGame[k1] = x1.substr(n1,10) + x2.substr(n1,10);
}
for (k3 = 10; k3 <= 30; k3+= 20)
{
for (k2 = 0; k2 <= aLen; k2++)
{
aMove = aGame[k2];
bMove = aMove.substr(k3,10);
for (k1 = 0; k1 <= 8; k1++)
{
x1 = bMove.substr(k1,1);
if (x1 == "0")
{
x2 = bMove;
x2.replace(k1,1,"1");
x3 = MoveA2a(x2);
aCount = aCount + 1;
mbGame[aCount] = aMove + x2 + x3;
}
}
}
aLen = aCount; aCount = -1;
for (k2 = 0; k2 <= aLen; k2++) aGame[k2] = bGame[k2];
} //314
bCount = -1;
for (k3 = 0; k3 <= aLen; k3++)
{
aMove = aGame[k3]; bMove = aMove.substr(50,9);
for (k2 = 0; k2 <= 8; k2++)
aPosit[k2] = bMove.substr(k2,1);
for (k2 = 0; k2 <= 21; k2+= 3)
{
x1 = "";
for (k1 = k2; k1 <= k2 + 2; k1++)
{
n1 = mCheck[k1];
x1 = x1 + aPosit[n1];
}
if (x1 == "222")
{
bCount = bCount + 1; // 243
wGame[bCount] = aMove;
goto aBottom;
}
}
aCount = aCount + 1;
bGame[aCount] = aMove;
aBottom: k1 = 0;
}
aLen = aCount; aCount = -1;
for (k2 = 0; k2 <= aLen; k2++)
{
aMove = bGame[k2]; bMove = aMove.substr(50,10);
for (k1 = 0; k1 <= 8; k1++)
{
x1 = bMove.substr(k1,1);
if (x1 == "0")
{
x2 = bMove;
x2.replace(k1,1,"1");
x3 = MoveA2a(x2);
aCount = aCount + 1;
aGame[aCount] = aMove + x2 + x3;
}
}
}
aLen = aCount; aCount = -1;
for (k3 = 0; k3 <= aLen; k3++)
{
aMove = aGame[k3]; bMove = aMove.substr(70,9);
for (k2 = 0; k2 <= 8; k2++)
aPosit[k2] = bMove.substr(k2,1);
for (k2 = 0; k2 <= 21; k2+= 3)
{
x1 = "";
for (k1 = k2; k1 <= k2 + 2; k1++)
{
n1 = mCheck[k1];
x1 = x1 + aPosit[n1];
}
if (x1 == "222")
{
bCount = bCount + 1;
wGame[bCount] = aMove;
goto bBottom;
}
}
aCount = aCount + 1;
bGame[aCount] = aMove;
bBottom: k1 = 0;
}
for (k1 = 0; k1 <= bCount; k1++)
wGame[k1] = wGame[k1] + "w";
aLen = aCount;
for (k1 = 0; k1 <= aCount; k1++)
{
bCount = bCount + 1; wGame[bCount] = aGame[k1] + "t";
}
ofstream OutFile("GameB139x.txt", ios::out);
for (k1 = 0; k1 <= bCount; k1++)
OutFile << wGame[k1] << endl;
OutFile.close();
}
void SetUp1()
{
int k1, n1;
string x1;
ifstream InFile("TicA318.txt", ios::in);
for (k1 = 0; k1 <= 318; k1++)
{
getline(InFile, x1);
mMove[k1] = x1.substr(0,10); nMove[k1] = x1.substr(10,9) + " ";
}
InFile.close();
string p1[] = {"A","B","C","D","E","F","G","H","I","a","b","c","d","e","f","g","h","i"};
x1 = "0 1 2 A B C a b c 3 4 5 D E F d e f 6 7 8 G H I g h i ";
for (k1 = 0; k1 <= 8; k1++)
{
n1 = k1 + 9;
mIndex[k1] = x1.find(p1[k1],k1);
nIndex[k1] = x1.find(p1[n1],k1);
}
ifstream aInFile("GameA456aX.txt", ios::in);
for (k1 = 0; k1 <= 456; k1++)
getline(aInFile,mGame[k1]);
aInFile.close();
}
void aMain()
{
int k1,n1;
string x1;
SetUp1();
AllGames3();
}
int main(int argc, char** argv)
{
aMain();
exit(0);
system("PAUSE");
return 0;
}
Part 4
int mCheck[] = {0,1,2,3,4,5,6,7,8,0,3,6,1,4,7,2,5,8,0,4,8,2,4,6};
string mMove[153],nMove[153];
string MoveA2a(string pMove)
{
int k1;
string x1;
for (k1 = 0; k1 <= 152; k1++)
if (pMove == mMove[k1]) break;
x1 = nMove[k1];
return x1;
}
void MoveA2()
{
int k1,k2,k3,n1,aCount = -1, bCount = -1,aLen = 7;
string x1,x2, x3,aMove, bMove, aPosit[9];
string aGame[140], bGame[140], wGame[140];
for (k1 = 0; k1 <= 7; k1++)
aGame[k1] = mMove[k1] + nMove[k1];
for (k2 = 0; k2 <= aLen; k2++)
{
aMove = aGame[k2]; bMove = aMove.substr(10,10);
for (k1 = 0; k1 <= 8; k1++)
{
x1 = bMove.substr(k1,1);
if (x1 == "0")
{
x2 = bMove;
x2.replace(k1,1,"2");
x3 = MoveA2a(x2);
aCount = aCount + 1;
bGame[aCount] = aMove + x2 + x3;
}
}
}
aLen = aCount; aCount = -1; bCount = -1;
for (k3 = 0; k3 <= aLen; k3++)
{
aMove = bGame[k3]; bMove = aMove.substr(30,9);
for (k2 = 0; k2 <= 8; k2++)
aPosit[k2] = bMove.substr(k2,1);
for (k2 = 0; k2 <= 21; k2+= 3)
{
x1 = "";
for (k1 = k2; k1 <= k2 + 2; k1++)
{
n1 = mCheck[k1];
x1 = x1 + aPosit[n1];
}
if (x1 == "111")
{
bCount = bCount + 1; //19
wGame[bCount] = aMove;
goto aBottom;
}
}
aCount = aCount + 1;
aGame[aCount] = aMove;
aBottom: k1 = 0;
}
aLen = aCount; aCount = -1;
for (k2 = 0; k2 <= aLen; k2++)
{
aMove = aGame[k2]; bMove = aMove.substr(30,10);
for (k1 = 0; k1 <= 8; k1++)
{
x1 = bMove.substr(k1,1);
if (x1 == "0")
{
x2 = bMove;
x2.replace(k1,1,"2");
x3 = MoveA2a(x2);
aCount = aCount + 1;
bGame[aCount] = aMove + x2 + x3;
}
}
}
aLen = aCount; aCount = -1;
for (k3 = 0; k3 <= aLen; k3++)
{
aMove = bGame[k3]; bMove = aMove.substr(50,9);
for (k2 = 0; k2 <= 8; k2++)
aPosit[k2] = bMove.substr(k2,1);
for (k2 = 0; k2 <= 21; k2+= 3)
{
x1 = "";
for (k1 = k2; k1 <= k2 + 2; k1++)
{
n1 = mCheck[k1];
x1 = x1 + aPosit[n1];
}
if (x1 == "111")
{
bCount = bCount + 1; // 123
wGame[bCount] = aMove;
goto bBottom;
}
}
aCount = aCount + 1;
aGame[aCount] = aMove;
bBottom: k1 = 0;
}
aLen = aCount; aCount = -1;
for (k2 = 0; k2 <= aLen; k2++)
{
aMove = aGame[k2]; bMove = aMove.substr(50,10);
for (k1 = 0; k1 <= 8; k1++)
{
x1 = bMove.substr(k1,1);
if (x1 == "0")
{
x2 = bMove;
x2.replace(k1,1,"2");
x3 = MoveA2a(x2);
aCount = aCount + 1;
bGame[aCount] = aMove + x2 + x3;
}
}
}
aLen = aCount; aCount = -1;
for (k3 = 0; k3 <= aLen; k3++)
{
aMove = bGame[k3]; bMove = aMove.substr(70,9);
for (k2 = 0; k2 <= 8; k2++)
aPosit[k2] = bMove.substr(k2,1);
for (k2 = 0; k2 <= 21; k2+= 3)
{
x1 = "";
for (k1 = k2; k1 <= k2 + 2; k1++)
{
n1 = mCheck[k1];
x1 = x1 + aPosit[n1];
}
if (x1 == "111")
{
bCount = bCount + 1; //131
wGame[bCount] = aMove;
goto cBottom;
}
}
aCount = aCount + 1;
aGame[aCount] = aMove;
cBottom: k1 = 0;
}
aLen = bCount;
for (k1 = 0; k1 <= aLen; k1++)
wGame[k1] = wGame[k1] + "w";
aLen = aCount;
for (k1 = 0; k1 <= aLen; k1++)
{
bCount = bCount + 1; wGame[bCount] = aGame[k1] + "t";
}
ofstream OutFile("GameB139x.txt", ios::out);
for (k1 = 0; k1 <= bCount; k1++)
OutFile << wGame[k1] << endl;
OutFile.close();
}
void SetUp1()
{
int k1,k2;
string x1,x2;
ifstream InFile("TicB152.txt", ios::in);
for (k1 = 0; k1 <= 152; k1++)
{
getline(InFile, x1);
mMove[k1] = x1.substr(0,10); nMove[k1] = x1.substr(10,9) + " ";
}
InFile.close();
}
void aMain()
{
int k1,n1;
string x1;
SetUp1();
MoveA2();
}
int main(int argc, char** argv)
{
aMain();
exit(0);
system("PAUSE");
return 0;
}
Part 5
//Tic game: human vs computer. Computer does not lose (win or tie)
//Playing game is actually a search and find operation based on
// 2 text files formed database.
int mIndex[9],nIndex[9], mPlayer;
string mMove[319],nMove[319];
void Play3b(string pMove, string qMove)
{
int k1,n1;
string x1;
string aMold = "0 1 2 _ _ _ _ _ _ 3 4 5 _ _ _ _ _ _ 6 7 8 _ _ _ _ _ _ ";
// This k1 loop transforms a snapshot, e.g. "200010000" and "200010001" into
// "0 1 2 2 _ _ _ _ _ 3 4 5 _ 1 _ _ _ _ 6 7 8 _ _ _ _ _ 1 ";
// then separate into:
// 012 2 _ _ 2 _ _
// 345 _ 1 _ _ 1 _
// 678 _ _ _ _ _ 1 each line is 21 characters in length: 1 means player 1 and so is 2.
for (k1 = 0; k1 <= 8; k1++)
{
x1 = pMove.substr(k1,1);
if (x1 != "0")
{
n1 = mIndex[k1];
aMold.replace(n1,1,x1);
}
}
for (k1 = 0; k1 <= 8; k1++)
{
x1 = qMove.substr(k1,1);
if (x1 != "0")
{
n1 = nIndex[k1];
aMold.replace(n1,1,x1);
}
}
n1 = -21;
for (k1 = 0; k1 <= 42; k1+= 21)
cout << aMold.substr(k1,21) << endl;
cout << endl;
}
string Play3a(string pMove)
{
int k1;
string x1;
for (k1 = 0; k1 <= 152; k1++)
if (pMove == mMove[k1]) break;
// Using human's move as the key to retrieve the computer's answering move
return nMove[k1];
}
void Play3()
{
int k1,n1,Move1[] = {0,2};
string x1, bMove,aWin;
string aMove = "000010000"; // When the computer is player 1, its first move is square 4
Play3b("000010000","000000000");
for (k1 = 0; k1 <= 3; k1++)
{
cout << "Make a move now: ";
cin >> n1;
aMove.replace(n1,1,"2");
x1 = Play3a(aMove);
bMove = x1.substr(0,9); aWin = x1.substr(9,1);
Play3b(aMove,bMove);
if (aWin == "w") break;
aMove = bMove;
}
if (aWin == "w")
cout << "Game's over. You lost";
else
cout << "Game's over. You tied";
}
void Play2b(string pMove, string qMove)
{
int k1,n1;
string x1;
string aMold = "0 1 2 _ _ _ _ _ _ 3 4 5 _ _ _ _ _ _ 6 7 8 _ _ _ _ _ _ ";
for (k1 = 0; k1 <= 8; k1++)
{
x1 = pMove.substr(k1,1);
if (x1 != "0")
{
n1 = mIndex[k1];
aMold.replace(n1,1,x1);
}
}
for (k1 = 0; k1 <= 8; k1++)
{
x1 = qMove.substr(k1,1);
if (x1 != "0")
{
n1 = nIndex[k1];
aMold.replace(n1,1,x1);
}
}
n1 = -21;
for (k1 = 0; k1 <= 42; k1+= 21)
cout << aMold.substr(k1,21) << endl;
cout << endl;
}
string Play2a(string pMove)
{
int k1;
string x1;
for (k1 = 0; k1 <= 318; k1++)
if (pMove == mMove[k1]) break;
return nMove[k1];
}
void Play2()
{
int k1,n1;
string x1, bMove,aWin;
string aMove = "000000000";
Play2b("000000000","000000000");
for (k1 = 0; k1 <= 3; k1++)
{
cout << "Make a move now: ";
cin >> n1;
aMove.replace(n1,1,"1");
x1 = Play2a(aMove);
bMove = x1.substr(0,9); aWin = x1.substr(9,1);
Play2b(aMove,bMove);
if (aWin == "w") break; // Game's over
aMove = bMove;
}
if (aWin == "w")
cout << "Game's over. You lost";
else
cout << "Game's over. You tied";
}
void SetUp1()
{
int k1,n1;
string x1;
// To transform a snapshot into a string that can be displayed almost like graphical
// we set up 2 sets of indexes (one for player 1 and another for player 2.
// The Upcased letters are for player 1 and the lowcase ones are for player 2.
// This is the mold "0 1 2 _ _ _ _ _ _ 3 4 5 _ _ _ _ _ _ 6 7 8 _ _ _ _ _ _ ";
// e.g. snapshots "000010000" and "200010000": we use locate the position of
// "1" in square 4 and them using mIndex[n] to get its proper place and replace the underline
// into "1" For the second snapshot: we use nIndex[n1] to locate the place to replace with
// "2" and "1"
string p1[] = {"A","B","C","D","E","F","G","H","I","a","b","c","d","e","f","g","h","i"};
x1 = "0 1 2 A B C a b c 3 4 5 D E F d e f 6 7 8 G H I g h i ";
for (k1 = 0; k1 <= 8; k1++)
{
n1 = k1 + 9;
mIndex[k1] = x1.find(p1[k1],k1);
nIndex[k1] = x1.find(p1[n1],k1);
}
if (mPlayer == 1) // Human wants to be the first mover
{
ifstream InFile("TicA318.txt", ios::in);
for (k1 = 0; k1 <= 318; k1++)
{
getline(InFile,x1);
mMove[k1] = x1.substr(0,9);
nMove[k1] = x1.substr(10,10);
}
InFile.close();
}
else
{
ifstream InFile("TicB152.txt", ios::in); // To be the second mover
for (k1 = 0; k1 <= 152; k1++)
{
getline(InFile,x1);
mMove[k1] = x1.substr(0,9);
nMove[k1] = x1.substr(10,10);
}
InFile.close();
}
}
void aMain()
{
cout << "Play games now. First Player type 1. Second Player type 2: ";
cin >> mPlayer;
SetUp1();
if (mPlayer == 1)
Play2();
else
Play3();
}
int main(int argc, char** argv)
{
aMain();
exit(0);
system("PAUSE");
return 0;
}
Section 5
Hanoi Towers (1 to 9 disks only)
Overview:
In the Hanoi Towers game, we move disks within 3 stacks. There are only 3 possible
move types: 12,13,23 (12 means: a disk from Stack 1 to Stack 2, so on). We represent
1 with A, 2, B and 3 C. If the disk number, n, is 9, the required move count is:
pow(2,n) - 1 = 511. If n = 3 then pow(2,n) - 1 = 7. The 511 moves are the repetition
of ABC (ABCABCABC....). All odd numbers smaller than 9 are the substring of 511.
If the disk number, n, is 8 (an even number, the required move count is:
pow(2,n) - 1 = 255. The 255 moves are the repetition of BAC(13,12,23) All even numbers
smaller than 8 are the substring of the 255.
Occasionally, we move a disk from A to B. And we see we can not do that
because the A's disk is bigger then the B's. In this case, we reverse the move.
We go B to A, instead of A to B.
We represent 9 disks with the values of 1 - 9 (from smallest to the biggest).
We represent 3 stacks with a single integer array with the length of 27.
We display disk moves as follows (3 disks):
S array: Initial values After loading
0 3 6 0 0 0 1 0 0
1 4 7 0 0 0 2 0 0
2 5 8 0 0 0 3 0 0
----- ----- -----
Move Sequence
M1: 12 M2: 13 M3: 23
0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 1
3 1 0 3 1 2 3 0 2
----- ----- -----
M4: 12 M5:13(31) M6: 23(32) M7: 12 Task completed.
0 0 0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 2 0 0 2 0
0 3 2 1 3 2 1 3 0 0 3 0
----- ----- ----- -----
Array S(0-2) = 000; S(3-5) = 123; S(6-8) = 000;
Warning: some of the ideas from above are orignally
from How to Program C++ by Deitel & Deitel T.R.Nieto.
Here is the whole pragram
int mStep[1022], mMove[1022],mStack[27];
string mNum[33];
ofstream OutFile("HanoiGame.txt", ios::out);
void Show4(int pDisk)
{
int k1,k2, n1,n2;
for (k2 = 0; k2 < pDisk; k2++)
{
n1 = k2;
for (k1 = 1; k1 <= 3; k1++)
{
n2 = mStack[n1];
if (n2 == 10) n2 = 0;
cout << n2 << " ";
OutFile << n2 << " ";
n1 = n1 + pDisk;
}
cout << endl;
OutFile << endl;
}
cout << endl;OutFile << endl; // You can see the game more clearly in HanoiGame.txt"
}
// Translate the 12, 13 ... into value change in Stack Array
// and export the repeated shows to the function above
void Play3()
{
int k1,k2, n1,n2,aDisk,bDisk,aEnd,aStep,bStep,aPick,bPick,aSwap[24];
string x1,x2, aMove;
cout << "To play Hanoi Towers, enter disk number (2 to 9): ";
cin >> aDisk;
bDisk = aDisk -1; aEnd = pow(2,aDisk) - 2;
for (k1 = 0; k1 <= 26; k1++) mStack[k1] = 10; // Initiate value 10 to the array (empty array
for (k1 = 0; k1 < aDisk; k1++) mStack[k1] = k1 + 1;
cout << "Play Hanoi Towers: Disk Number: " << aDisk << endl;
OutFile << "Play Hanoi Towers: Disk Number: " << aDisk << endl;
cout << "------" << endl;
OutFile << "------" << endl;
Show4(aDisk); // Display Hanoi Towers before moving disks
bStep = ((aDisk + 1) % 2) * 511; // Odd numbered Disks: 0 to 510 moves
// Even numbered Disks: 510 to 1021
for (k2 = 0; k2 <= aEnd; k2++)
{
aStep = mMove[k2 + bStep];
n1 = (aStep / 10 - 1) * aDisk;
n2 = (aStep % 10 - 1) * aDisk; // Separate 12 to Stack 1 and Stack 2 etc.
aPick = n1 + bDisk; bPick = n2 + bDisk;
for (k1 = n1; k1 <= n1 + bDisk; k1++)
if (mStack[k1] != 10) break;
aPick = k1; // Pick up a disk to move
for (k1 = n2 + bDisk; k1 >= n2; k1--)
if (mStack[k1] == 10) break;
bPick = k1; // Pick up a location
mStack[bPick] = mStack[aPick]; mStack[aPick] = 10;
// Drop a value (a disk) to the location. Reset the location to 10 (empty)
Show4(aDisk);
}
OutFile.close();
cout << "Go to 'HanoiGame.txt' for more detailed display." << endl;
}
void Move2()
{
int k1,k2, k3,n1,n2,aCount = -1,aStep,aPick,bPick,aSwap[24],aStack[27];
aSwap[12] = 21; aSwap[13] = 31; aSwap[23] = 32; // When can not move 1 to 2 then reverse
// This loop reverses the moves which can not be done.
// Can not move a bigger disk to on top of smaller one
for (k3 = 0; k3 <= 511; k3+= 511) // Make a move list
{
for (k2 = 0; k2 <= 8; k2++) aStack[k2] = k2 + 1;
for (k2 = 9; k2 <= 26; k2++) aStack[k2] = 10;
for (k2 = k3; k2 <= k3 + 510; k2++)
{
aStep = mStep[k2];
n1 = (aStep / 10 - 1) * 9;
n2 = (aStep % 10 - 1) * 9;
aPick = n1 + 8; bPick = n2 + 8;
for (k1 = n1; k1 <= n1 + 8; k1++)
{
if (aStack[k1] != 10) // Value 10 means empty location in stack
{
aPick = k1; break;
}
}
for (k1 = n2; k1 <= n2 + 8; k1++)
{
if (aStack[k1] != 10)
{
bPick = k1; break;
}
}
if (aStack[aPick] < aStack[bPick])
{
if (aStack[bPick] != 10) bPick = bPick -1;
}
else
{
n1 = aPick; aPick = bPick; bPick = n1 -1;
aStep = aSwap[aStep];
}
aStack[bPick] = aStack[aPick]; aStack[aPick] = 10;
aCount = aCount + 1;
mMove[aCount] = aStep;
}
}
}
void SetUp1()
{
int k1,k2, n1;
string x1,x2,aStep = "<=G=
Section 6
Example of String Formatting (Print a 4 months in a row commercial styled calendar
Part 1: Print one thousand years' calendar (1776 to 2775)
Within the 1000 years, there are only 14 unique years (2 groups of 7: 365 days + 366 days
those years starting on sun, mon .... sat total 7.)
int pMonth[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
string mNum[32],nNum[40], mMonth, mYear[14];
void GetYear3()// Make 1000 years' calendar and name it "1776-2775b.txt"
{
int k1,k2, k3,k4,n1,n2;
string x1,x2, x3,aMonth[13],aWeek,aYear[2776], bYear, cYear[18], aTitle[2776], aLine;
char c1[18];
aMonth[0] = " JANUARY FEBRURARY MARCH APRIL ";
aMonth[6] = " MAY JUNE JULY AUGUST ";
aMonth[12] = " SEPTEMBER OCTOBER NOVEMBER DECEMBER ";
aWeek = "Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa ";
for (k1 = 1; k1 <= 96; k1++) aLine = aLine + " ";
x2 = aLine.substr(0,37) + "Calendar Year of ";
for (k1 = 1776; k1 <= 2775; k1++)
{
ostringstream convert;
convert << k1; x1 = convert.str();
aTitle[k1] = x2 + x1 + aLine.substr(0,38); // Title Year
}
ifstream InFile("1776-2775a1.txt", ios::in);
for (k1 = 1776; k1 <= 2775; k1++) //Load up 1000 unformetted years
InFile >> aYear[k1];
InFile.close();
ofstream OutFile("1776-2775b.txt", ios::out);
for (k4 = 1776; k4 <= 2775; k4++)
{
bYear = aYear[k4];
n2 = -1;
for (k3 = 0; k3 <= 336; k3+= 168) // A calendar is laid out in 3 parts and 4 columns
{
x1 = bYear.substr(k3,168);
for (k2 = 0; k2 <= 35; k2+= 7)
{
n1 = k2; x2 = "";
for (k1 = 1; k1 <= 4; k1++)
{
x2 = x2 + x1.substr(n1,7) + "0"; // "0" separates a month from another
n1 = n1 + 42; // A month is 42 characters and six rows
}
n2 = n2 + 1; // Row adding up
cYear[n2] = x2;
}
}
for (k3 = 0; k3 <= 17; k3++) // Starting formatting work.
{
x1 = cYear[k3];
x1.copy(c1,32); x2 = "";
for (k2 = 0; k2 <= 31; k2++)
{
n1 = int(c1[k2]) - 48;
x2 = x2 + nNum[n1] + " ";
}
cYear[k3] = x2;
}
bYear = aTitle[k4] + aLine;
for (k3 = 0; k3 <= 12; k3+= 6)// String up everything into one single variable
{
bYear = bYear + aMonth[k3] + aWeek; //Add year, month and week titles
for (k2 = k3; k2 <= k3 + 5; k2++)
bYear = bYear + cYear[k2];
}
OutFile << bYear << endl; // Save 1000 years' calendar into "1776-2775b.txt"
}
/*
ifstream aInFile("1776-2775b.txt", ios::in); //This is how to print out calendars.
for (k1 = 1776; k1 <= 2775; k1++)
{
getline(aInFile,x2); if (k1 == 2024) break;
}
aInFile.close();
ofstream aOutFile("Calen.txt", ios::out);
n1 = 0;
for (k1 = 0; k1 <= 25; k1++)
{
x1 = x2.substr(n1,96);
n1 = n1 + 96;
aOutFile << x1 << endl;
}
aOutFile.close(); */
}
void kYear2() // Make unformatted years
{
int k1,k2, k3,n1,n2, d1,aYear[2776], bYear[2776];
string x1,x2;
for (k1 = 1775; k1 <= 2775; k1++)
aYear[k1] = 1;
for (k1 = 1776; k1 <= 2775; k1+= 4)
{
n1 = 2;
if ((k1 % 100 == 0) && (k1 % 400 != 0))
n1 = 1;
aYear[k1] = n1;
}
d1 = 1;
for (k1 = 2023; k1 >= 1775; k1--)
d1 = (d1 - aYear[k1] + 7) % 7;
for (k1 = 1776; k1 <= 2775; k1++)
{
d1 = (d1 + aYear[k1 - 1]) % 7;
bYear[k1] = (aYear[k1] - 1) * 7 + d1;
}
ofstream OutFile("1776-2775a1.txt", ios::out);
for (k1 = 1776; k1 <= 2775; k1++)
{
n1 = bYear[k1]; // n1's ranges between 0 to 13. 0 to 6 are common years. 7 - 13: the Lead
OutFile << mYear[n1] << endl;
}
OutFile.close();
}
void SetUp1()
{
int k1,k2, k3,n1,n2, aCount = -1;
string x1,x2, aMonth[13], bMonth[13], cMonth,aZero = "00000000000000000000";
mNum[0] = " ";
for (k1 = 1; k1 <= 31; k1++)
{
x1 = char(k1+48); mNum[k1] = x1;
mMonth = mMonth + x1;
}
for (k2 = 0; k2 <= 3; k2++) // Make 32 formatted numbers
{
x1 = mNum[k2];
for (k1 = 0; k1 <= 9; k1++)
{
x2 = mNum[k1];
if (k1 == 0) x2 = "0";
aCount = aCount + 1;
nNum[aCount] = x1 + x2;
if (aCount == 31) break;
}
}
nNum[0] = " ";
for (k1 = 1; k1 <= 12; k1++)
{
n1 = pMonth[k1];
aMonth[k1] = mMonth.substr(0,n1);
}
n2 = -1;
for (k3 = 1; k3 <= 2; k3++) // Get 14 year's types
{
for (k2 = 0; k2 <= 6; k2++)
{
n1 = k2; x2 = "";
for (k1 = 1; k1 <= 12; k1++)
{
n1 = (n1 + pMonth[k1-1]) % 7;
x1 = aZero.substr(0,n1) + aMonth[k1] + aZero; //Pad months into 42 in length
x2 = x2 + x1.substr(0,42);
}
n2 = n2 + 1;
mYear[n2] = x2;
}
pMonth[2] = 29; aMonth[2] = aMonth[2] + "M"; // Process lead years.
}
}
Part 2: Make Holiday List
string mNum[32],nNum[32];
void MoldUp4() // First I make a mold of holidays
{
int k1, k2, n1, n2, bMark[13];
string x1, aDay, bDay,aFill[13];
string aMark[] =
{"A00","A05","A06","A10","A12","A01","A02","A03","A04","A07","A08","A09","A11"};
x1 = "New Year: A00 Jan 1.King: Mon Jan A01Presiden: Mon Feb A02";
x1 = x1 + "Dayligh1: Sun Mar A03Memorial: Mon May A04Junteen: A05 Jun 19.";
x1 = x1 + "Independ: A06 Jul 4.Labor: Mon Sep A07Columbus: Mon Oct A08";
x1 = x1 + "Dayligh2: Sun Nov A09Veterans: A10 Nov 11.Thanksgi: Thu Nov A11";
x1 = x1 + "Christma: A12 Dec 25. ";
for (k1 = 0; k1 <= 12; k1++)
bMark[k1] = x1.find(aMark[k1],0);
ifstream InFile("2022-2775a.txt", ios::in); // Month order: sun week, month week
ofstream OutFile("2022-2775h.txt", ios::out);
for (k2 = 2022; k2 <= 2775; k2++)
{
getline(InFile,bDay);
aDay = x1;
n1 = -3;
for (k1 = 0; k1 <= 12; k1++)
{
n1 = n1 + 3;
aFill[k1] = bDay.substr(n1,3);
}
for (k1 = 0; k1 <= 12; k1++)
{
n1 = bMark[k1];
aDay.replace(n1,3, aFill[k1]);
}
OutFile<< aDay << endl;
}
OutFile.close();
InFile.close();
n1 = -21;
for (k1 = 1; k1 <= 13; k1++)
{
n1 = n1 + 21;
cout << aDay.substr(n1,21) << endl;
}
}
void Holiday3() // Holiday pileup from 2022 to 2775
{
int k1, k2, k3, k4,n1, n2, n3, n4; // "01" means month 1 and day 1: New Year's Day
string x1, x2, x3, Year1[2776],Year2[504],Year3[2776], aDay[] = {"01","5C","64",":;",";I"};
// "012" means month 1, week 2 (monday) and order 3: Martin Day
string bDay[] = {"012","112","201","414","810","911",":00",":43"};
string cDay,dDay[2276], aWeek[] = {"Sun","Mon","Tue","Wed","Thu","Fri","Sat"};
char c1[3];
ifstream aInFile("1776-2775a1.txt", ios::in);
for (k1 = 1776; k1 <= 2775; k1++)
aInFile >> Year1[k1];
aInFile.close();
ifstream bInFile("1776-2775a2.txt", ios::in);
for (k1 = 1776; k1 <= 2775; k1++)
bInFile >> Year2[k1];
bInFile.close();
ofstream OutFile("2022-2775a.txt", ios::out); // Make unformatted holiday list (2022-2775)
for (k2 = 2022; k2 <= 2775; k2++)
{
x1 = Year1[k2]; cDay = "";
for (k1 = 0; k1 <= 4; k1++)
{
x2 = aDay[k1];
x3 = x2.substr(0,1);
x3.copy(c1,1); n1 = int(c1[0]) - 48;
x3 = x2.substr(1,1);
n2 = n1 * 42;
n1 = x1.find(x3, n2) % 7;
cDay = cDay + aWeek[n1];
}
x1 = Year2[k2];
for (k1 = 0; k1 <= 7; k1++)
{
x2 = bDay[k1]; x2.copy(c1,3);
n1 = int(c1[0]) - 48; // ASCII number of Character "0" is 48 and "1" is 49
n2 = int(c1[1]) - 48;
n3 = int(c1[2]) - 48;
n4 = n1 * 42 + n2 * 6 + n3;
x2 = x1.substr(n4,1);
if (x2 == "0") x2 = x1.substr(n4 -1,1);
x2.copy(c1,1);
n1 = int(c1[0]) - 48;
cDay = cDay + nNum[n1];
}
OutFile << cDay << endl;
}
// 2022 holiday list: SatSunMonFriSun17 21 13 30 5 10 6 24
// New Year: Sat; Junteen: Sun; Independence: Mon; Veterans: Fri; Christmas: Sun
// Martin Jan 17; Presidents Feb 21; ... Thanksgiving: Nov 24
}
void LineUp2()
{
int k1, k2, k3,k4,n1, n2;
string x1, x2, Year1[2776], Year2[504], Year3[2776];
ifstream InFile("1776-2775a1.txt", ios::in);
for (k1 = 1776; k1 <= 2775; k1++)
InFile >> Year1[k1];
InFile.close();
// Change conventioned order of month into week by week month order.
// Order of months now is: sun,mon,..sat
ofstream OutFile("1776-2775a2.txt", ios::out);
for (k4 = 1776; k4<= 2775; k4++)
{
x1 = Year1[k4];
for (k3 = 0; k3<= 503; k3++)
Year2[k3] = x1.substr(k3,1);
n1 = -42; x1 = "";
for (k3 = 1; k3<= 12; k3++)
{
n1 = n1 + 42;
for (k2 = n1; k2<= n1 + 6; k2++)
{
n2 = k2;
for (k1 = n2; k1<= n2 + 35; k1+= 7)
{
x2 = Year2[k1];
if (k1 == n2 && x2 == "0") x2 = "";
x1 = x1 + x2;
}
if (x1.length() % 6 != 0) x1 = x1 + "0";
}
}
OutFile << x1 << endl;
}
OutFile.close();
}
void SetUp1()
{
int k1,k2,n1;
string x1,x2;
for (k1 = 0; k1 <= 31; k1++)
mNum[k1] = char(k1+48);
n1 = -1;
for (k2 = 0; k2 <= 3; k2++)
{
x1 = mNum[k2];
if (k2 == 0) x1 = " ";
for (k1 = 0; k1 <= 9; k1++)
{
n1 = n1 + 1;
nNum[n1] = x1 + mNum[k1] + " ";
if (n1 == 31) k1 = 10;
}
}
}
void aMain()
{
int k1,k2,n1,n2;
string x1,x2;
SetUp1();
LineUp2();
Holiday3();
MoldUp4();
}
Part 3: Print 2 months' calendar //For vacation planning
(If starting date < 16: previous month + the date's month, else the date's
// month + next month
string mNum[32],nNum[32],mYear[2776],nYear[2776],mDay[2776];
void P2Months()
{
int k1,k2,n1, n2, aCount = -1, aYear, Year1, Year2,aMonth,Month1,Month2,aDay;
string x1,x2, d1;
string m1[] = {"Jan","Feb","Mar","Apr","May","Jun","July","Aug","Sep","Oct","Nov","Dec"};
string w1 = "Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa ";
char c1[96];
cout << "To print 2-month side-by-side calendar,enter a date mm/dd/yyyy: ";
cin >> x1;
x2 = x1.substr(6,4); aYear = atoi(x2.c_str());
x2 = x1.substr(0,2); aMonth = atoi(x2.c_str()) -1;
x2 = x1.substr(3,2); aDay = atoi(x2.c_str());
Year1 = aYear; Year2 = aYear;
if (aMonth == 0 && aDay < 16)
Year1 = aYear - 1;
else if (aMonth == 11 && aDay > 15)
Year2 = aYear + 1;
Month1 = aMonth; Month2 = aMonth;
if (aDay < 16)
Month1 = (aMonth + 11) % 12;
else if (aDay > 15)
Month2 = (aMonth + 1) % 12;
ostringstream cvt1; cvt1 << Year1; x1 = cvt1.str();
ostringstream cvt2; cvt2 << Year2; x2 = cvt2.str();
d1 = " " + m1[Month1] + " " + x1;
d1 = d1 + " " + m1[Month2] + " " + x2;
x1 = nYear[Year1]; x2 = nYear[Year2];
n1 = Month1 * 42; x1 = x1.substr(n1,42);
n1 = Month2 * 42; x2 = x2.substr(n1,42);
x1 = x1 + x2; x2 = "";
n1 = 0; n2 = 42;
for (k1 = 1; k1 <= 6; k1++)
{
x2 = x2 + x1.substr(n1,7) + "0" + x1.substr(n2,7) + "0";
n1 = n1 + 7; n2 = n2 + 7;
}
cout << d1 << endl;
cout << w1 << endl;
x2.copy(c1,96); n1 = -1;
for (k2 = 0; k2 <= 80; k2+= 16)
{ x1 = "";
for (k1 = k2; k1 <= k2 + 15; k1++)
{
n1 = n1 + 1;
n2 = int(c1[n1]) - 48;
x1 = x1 + nNum[n2] + " ";
} cout << x1 << endl;
}
}
void PrintCalen()
{
int k1,n1, n2;
string x1,x2, aYear, bYear, aDay;
cout << "Enter the number for the year to print a calendar: ";
cin >> aYear;
n1 = atoi(aYear.c_str());
bYear = mYear[n1];
x1 = aYear + "Cal.txt";
ofstream aOutFile(x1.c_str(), ios::out);
n2 = -96;
for (k1 = 0; k1 <= 25; k1++)
{
n2 = n2 + 96;
aOutFile << bYear.substr(n2,96) << endl;
}
aOutFile.close() ;
cout << "Print a holiday list (2022 to 2775)? Type 1 for yes and -1 for no ";
cin >> n2;
if (n2 == 1)
{
aDay = mDay[n1];
x1 = aYear + " Holidays.txt";
ofstream bOutFile(x1.c_str(), ios::out);
bOutFile << " Holidays of " + aYear << endl;
n2 = -21;
for (k1 = 0; k1 <= 12; k1++)
{
n2 = n2 + 21;
bOutFile << aDay.substr(n2,21) << endl;
}
bOutFile.close();
}
}
void SetUp1()
{
int k1,k2, n1,n2,aCount = -1;
string x1,x2;
for (k1 = 0; k1 <= 31; k1++)
mNum[k1] = char(k1+48);
for (k2 = 0; k2 <= 3; k2++)
{
x1 = mNum[k2];
if (k2 == 0) x1 = " ";
for (k1 = 0; k1 <= 9; k1++)
{
x2 = mNum[k1];
if (k1 == 0) x2 = "0";
aCount = aCount + 1;
nNum[aCount] = x1 + x2;
if (aCount == 31) break;
}
}
nNum[0] = " ";
ifstream aInFile("1776-2775b.txt", ios::in);
for (k1 = 1776; k1 <= 2775;k1++)
getline(aInFile,mYear[k1]);
aInFile.close();
ifstream bInFile("1776-2775a1.txt", ios::in);
for (k1 = 1776; k1 <= 2775;k1++)
bInFile >> nYear[k1];
bInFile.close();
ifstream cInFile("2022-2775h.txt", ios::in);
for (k1 = 2022; k1 <= 2775;k1++)
getline(cInFile,mDay[k1]);
cInFile.close();
}
Section 7
Simulateing Enigma in encoding, and decoding functions, and breaking Enigma code
string mNum[95]; //Use all non-functioning Windows supported keys to do the job.
string mName = "Text1.txt"; // I use the full text of Declaration of Independence.
string mKey = "Allons! Enfants de la Patrie"; //Use this sentence to encode and decode text.
//int mLen = 23, nLen = 24, nKey[26]; // The length of the key
void Break4() // Use the frequency count to retrieve the key
{
int k1, k2, k3, n1, n2, aCount,aLen, aText[50000], bText[50000], aFilter[96] = {0},aKey;
string x1, x2, aError = "~`*{[}]/";
char c1[50000];
for (k1 = 0; k1 <= 94; k1++) // Make 95 string equivalence of the Arabic
mNum[k1] = char(k1+32);
ifstream InFile("TextB.txt", ios::in); // TextB.txt is the encoded text of the Declaration
getline(InFile,x1);
InFile.close();
aLen = x1.length() - 1; // The character count
x1.copy(c1,aLen + 1); //Copy the text into an array of char
for (k1 = 0; k1 <= aLen;k1++)
aText[k1] = int(c1[k1]) - 32; //Change the char into Arabic
for (k3 = 15; k3<= 25; k3++) // Predict the length of the key
{
aCount = 0;
for (k2 = 0; k2<= aLen; k2++)
bText[k2] = aText[k2]; // Make a copy of the encoded text, and then trial and error
for (k2 = 0; k2<= k3 - 1; k2++)
{
for (k1 = k2; k1<= aLen; k1+= k3) // Flip rows into columns
{
n1 = bText[k1];
aFilter[n1] = aFilter[n1] + 1; // Frequency count
}
n1 = 0;
for (k1 = 0; k1<= 94; k1++)
{
if (n1 < aFilter[k1])
{
n1 = aFilter[k1]; aKey = k1;
} // Assume the highest count is the key
aFilter[k1] = 0;
}
for (k1 = k2; k1<= aLen; k1+= k3)
{
n1 = bText[k1];
bText[k1] = (n1 - aKey + 95) % 95; // Decode column by column
if (k2 == 0)
{
n1 = bText[k1];
n2 = aError.find(mNum[n1], 0); // Count the error characters
if (n2 != -1)
{
aCount = aCount + 1;
if (aCount == 4) goto aSkip; //If count is 4, abort
}
}
}
}
aSkip: k1 = 0;
if (aCount < 4) break; // If count < 4, success and exit
}
x2 = "";
for (k1 = 0; k1<= aLen; k1++)
{
n1 = bText[k1];
x2 = x2 + mNum[n1]; // String the array into one single variable
}
ofstream OutFile("TextD.txt", ios::out); //TextD.txt is the decoded text.
OutFile << x2 << endl;
OutFile.close();
}
void Decode3()
{
int k1, k2, n1, n2, aLen, aText[50000];
string x1, x2, bText[50000];
char c1[50000];
ifstream InFile("TextB.txt", ios::in); // TextB.txt is the encoded text
getline(InFile,x1);
InFile.close();
aLen = x1.length() - 1;
x1.copy(c1,aLen + 1);
for (k1 = 0; k1 <= aLen;k1++)
aText[k1] = int(c1[k1]) - 32;
for (k2 = 0; k2<= mLen; k2++)
{
n1 = nKey[k2];
for (k1 = k2; k1<= aLen; k1+= nLen)
{
n2 = (aText[k1] - n1 + 95) % 95; //Deduct the key Arabic
bText[k1] = mNum[n2];
}
}
x2 = "";
for (k1 = 0; k1<= aLen; k1++)
x2 = x2 + bText[k1];
ofstream OutFile("TextC.txt", ios::out); //TextC.txt is the decoded text matching TextA.txt
OutFile << x2 << endl;
OutFile.close();
}
void Code2()
{
int k1, k2, n1, n2, aLen, aText[50000];
string x1, x2, bText[50000];
char c1[50000];
ifstream InFile("TextA.txt", ios::in); // TextA.txt is the plain text
getline(InFile,x1);
InFile.close();
aLen = x1.length() -1;
x1.copy(c1,aLen + 1);
for (k1 = 0; k1<= aLen; k1++)
aText[k1] = int(c1[k1]) - 32; //Change string into Arabic
for (k2 = 0; k2<= mLen; k2++)
{
n1 = nKey[k2];
for (k1 = k2; k1<= aLen; k1+= nLen)
{
n2 = (aText[k1] + n1) % 95; // Add the key to the Arabic
bText[k1] = mNum[n2]; // Change the Arabic to chacters.
}
}
x2 = "";
for (k1 = 0; k1<= aLen; k1++)
x2 = x2 + bText[k1];
ofstream OutFile("TextB.txt", ios::out); //TextB.txt is the coded text.
OutFile << x2 << endl;
OutFile.close();
}
void Load1()
{
int k1, n1, n2,aLen;
string x1, x2, aText, bText;
char c1[26];
for (k1 = 0; k1 <= 94; k1++)
mNum[k1] = char(k1+32);
mKey.copy(c1,nLen);
for (k1 = 0; k1 <= mLen; k1++)
{
nKey[k1] = int(c1[k1]) - 31; //Change key into Arabic
}
ifstream InFile(mName.c_str(), ios::in);
do
{
getline(InFile,x1); // Change the multi-lines text into a single variable
aText = aText + x1;
} while (!InFile.eof());
InFile.close();
aLen = aText.length() - 1;
for (k1 = 0; k1 <= aLen; k1++)
{
x1 = aText.substr(k1,1);
if (x1 == " " && x2 == " ") goto aSkip;
if (x1 >= " " && x1 <= "~") // Filter out any character that is not in the keyboard.
{
bText = bText + x1;
}
aSkip: n1 = 0;
x2 = x1;
}
ofstream OutFile("TextA.txt", ios::out); // TextA.txt is the plain text.
OutFile << bText << endl;
OutFile.close();
}
void aMain()
{
int k1,k2,n1,n2;
string x1,x2;
Load1();
Code2();
Decode3();
Break4();
}
int main(int argc, char** argv)
{
int k1,k2,n1,n2;
string x1,x2;
aMain();
exit(0);
system("PAUSE");
return 0;
}
Section 8: Computer-assisted Poker Playing
C++ program, solving the problem of poker game playing
This program focuses on "recognizing, organizing and creating numerical patterns".
(The problem is listed in a C++ textbook)
Overview
The program is consisted of 3 parts.
Part 1
Build a database in the form of textfile structured for fast and convenient data
retrieval (Inputing a hand and output a string used as the value of the hand.)
Part 2
Simulate a million games (A game means a dealer vs 4 players and resulted in 4 bets)
The program sums bets' win or loss on two different game playing. Game Type A: An all
by-chance. Game Type B. The dealer is allowed for 3-card replacement, but the players
are not. The program decides how the replacement is done.
Part 3
Computer assisted game playing. The program assumes the role of the dealer while the
players are human. When the program does better replacement decisions than human,
it wins more bets, vice versa.
Logistics
The program uses ASCII numbers for coded data representation.
52 cards are reprensented as follows:
F: face value: S: suite value
F\S Arabic ASCII
0 1 2 3 0 1 2 3
----------- -------------
0 0 13 26 39 0 = J W 39
1 1 14 27 40 1 > K X 40
2 2 15 28 41 2 ? L Y 41
3 3 16 29 42 3 @ M Z 42
4 4 17 30 43 4 A N [ 43
5 5 18 31 44 5 B O \ 44
6 6 19 32 45 6 C P ] 45
7 7 20 33 46 7 D Q ^ 46
8 8 21 34 47 8 E R _ 47
9 9 22 35 48 9 F S ` 48
10 10 23 36 49 : G T a 49
11 11 24 37 50 ; H U b 59
12 12 25 38 51 < I V c 51
(Notice: the 52 ASCII numbers are consecutive.
Write arabic on top of the card, and the ASCII on the bottom.)
For the hand's score, use ASCII: d e f g h i j k l m n o p q
Arabic: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
Cards 0 = J W are counted the greatest value: q (13) except in hands which face values are 01234,
they are counted value d (0)
The first hand and score are: 01234lh...... It reads card 0,1,2,3,4, hand type l (8)
within type values h (4). 01235iqigfed 's type: i and within type value: qigfe (13,5,3,2,1).
The suite value: d (0): This d serves as a tie break when 2 hands have the same face value.
Hand Types
Straight Flush l (8) 40
Four Kind k (7) 624
Full House j (6) 3,744
Flush i (5) 5,108
Straight h (4) 10,200
Three Kind g (3) 54,912
Two Pairs f (2) 123,552
One Pair e (1) 1,098,240
High Card d (0) 1,302,540
Total: 2,598,960
Function Explanation:
Part 1 (Build a hand-score database):
A: Permulate all possible hands from 52 cards. Save the hands to a textfile named "2598959";
B: Determine all hands' types (d to l) and add one letter to each hand and save it as "2598959a"
C: Determine all hands' within-type scores and attach the scores to all hands.
D: Structure the 2,598,960 hands into 25989 lines (100 hands per line except last line has
only 60 hands);
E: Add a padder line "*********" to signal this is end line.
F: Name the file as "25990f". All hands are arranged in ascending order.
Part 2 (Play a million games):
A: Open "25990f.txt" and load data into 2 arrays: mHead(n) and mLine(n).
mHead(n) are 5-letter line head and mLine(n) are the whole line data (hand names and
their scores). Set up a function to receive a hand and to return a score;
The search is a dictionary- style 2-step data retrieval. An input hand passes through
a 0 to 25990 for loop, comparing the hand with the mHead(n). When the hand is lesser than
mHead(n), the loop breaks. We store mHead(n-1) into variable x. Then n1 = x.find(hand,0) and
Score = x.substr(n1,12). The first 5 letters are a hand's name. The 6th letter is hand type.
And the 7 to 12 letters are the within-type score.
B: Generate one million sets of shuffled 28 cards (The first 25 cards are playing cards
and the last 3 are replacement cards). The first 5 letters are the dealer's hand.
Save the data into "Game1M.txt"
C: Open "Game1M.txt" and load data to a variable line by line. Send the dealer's hand into a
replacement function. The function first retrieves the hand type: if the hand is stronger
than 3 kind, no replacement. If it is high card and one pair, replace 3 cards. 2 pairs - one
card and 3 kind - 2 cards. Insert the replaced hand after the original hand. Now we have
6 hands and scores per line. Save the 1 million lines data ro "Score1M.txt".
D: Load textfile "Score1M.txt". Each line is formated as below:
@LMV`egpmf..@CMQWegqkj..07;GPdqonkj.9HO^cdpomki.ABKTUdonihe.8DR\beloki..
It has 6 hand-scores.
@LMV`egpmf.. @CMQWegqkj.. 07;GPdqonkj. 9HO^cdpomki. ABKTUdonihe. 8DR\beloki..
@LMV` egpmf.. @CMQW egqkj.. 07;GP dqonkj. 9HO^c dpomki. ABKTU donihe. 8DR\b eloki..
dealer pri dealer post Player1 P2 P3 P3
First we compare hand1 against hand 3,4,5,6.
If H1 > P1 then Win count = Win count + 1: If H1 < P1 then Win count = Win count - 1:
Next we compare hand2 against hand3,4,5,6.
e.g. H1 (egpmf) > dqonkj and > dpomki and > donihe but < eloki, the Win count is 2
Part 1
string mName[] = {"2598959a.txt","2598959b.txt"};
string mNum[52],nNum[14];
void LineUp13() // Change a file of 2,598,959 lines into one with only 25990 lines.
{
int k1, k2, n1, n2;
string x1, x2,aMove[25991];
ifstream InFile("2598959b.txt", ios::in);
n1 = 99;
for (k2 = 0; k2 <= 25989; k2++)
{
if (k2 == 25989) n1 = 59;
x2 = "";
for (k1 = 0; k1 <= n1; k1++)
{
InFile >> x1;
x2 = x2 + x1;
}
aMove[k2] = x2;
}
InFile.close();
ofstream OutFile("25990f.txt", ios::out); //Change 2598959 lines to 25989 line
for (k1 = 0; k1 <= 25989; k1++)
OutFile << aMove[k1] << endl;
OutFile << "xxxxxxxxxxxx" << endl;
OutFile.close();
}
// Hand 01234, is the weakest Straight Flush: score 4 4
// and 09:;< is the strongest one: score 13 q
void Get8P12(int pFile)
{
int k1, k2, n1, n2 = 0;
string x1, aHand, aName, aFace[13], L1 = "l";
char c1[6];
aName = mName[pFile];
ifstream InFile(aName.c_str(), ios::in);
aName = mName[1-pFile];
ofstream OutFile(aName.c_str(), ios::out);
for (k2 = 0; k2 <= 2598959; k2++)
{
InFile >> aHand; aHand.copy(c1,6);
if (aHand.length() == 6 && aHand.substr(5,1) == L1)
{
for (k1 = 0; k1 <= 4; k1++)
{
n1 = (int(c1[k1]) - 48) % 13;
aFace[n1] = nNum[n1];
}
x1 = "";
for (k1 = 12; k1 >= 0; k1--)
{
x1 = x1 + aFace[k1]; aFace[k1] = "";
}
if (x1 == "ponmd")
x1 = "q";
else
x1 = x1.substr(0,1); // The card that has the strongest face value
aHand = aHand + x1 + ".....";
n2 = n2 + 1;
}
OutFile << aHand << endl; //Save non straight flush un-changed.
}
OutFile.close();
InFile.close();
cout << n2 << endl;
}
// For kind 4 hands, we only need the face value of one of kind 4ed card.
void Get7P11(int pFile)
{
int k1, k2, n1, n2 = 0, bFace[14] = {0};
string x1, aHand, aName, Ka = "k";
char c1[6];
aName = mName[pFile];
ifstream InFile(aName.c_str(), ios::in);
aName = mName[1-pFile];
ofstream OutFile(aName.c_str(), ios::out);
for (k2 = 0; k2 <= 2598959; k2++)
{
InFile >> aHand; aHand.copy(c1,6);
if (aHand.length() == 6 && aHand.substr(5,1) == Ka)
{
for (k1 = 0; k1 <= 4; k1++)
{
n1 = (int(c1[k1]) - 48) % 13;
if (n1 == 0) n1 = 13;
bFace[n1] = bFace[n1] + 1;
}
for (k1 = 13; k1 >= 1; k1--)
{
if (bFace[k1] == 4) x1 = nNum[k1];
bFace[k1] = 0;
}
aHand = aHand + x1 + ".....";
n2 = n2 + 1;
}
OutFile << aHand << endl;
}
OutFile.close();
InFile.close();
cout << n2 << endl;
}
// For Full House hands, we only need the face value of one of the trippled cards
void Get6P10(int pFile)
{
int k1, k2, n1, n2 = 0, bFace[14] = {0};
string x1, aHand, aName,j1 = "j";
char c1[6];
aName = mName[pFile];
ifstream InFile(aName.c_str(), ios::in);
aName = mName[1-pFile];
ofstream OutFile(aName.c_str(), ios::out);
for (k2 = 0; k2 <= 2598959; k2++)
{
InFile >> aHand; aHand.copy(c1,6);
if (aHand.length() == 6 && aHand.substr(5,1) == j1)
{
for (k1 = 0; k1 <= 4; k1++)
{
n1 = (int(c1[k1]) - 48) % 13;
if (n1 == 0) n1 = 13;
bFace[n1] = bFace[n1] + 1;
}
for (k1 = 13; k1 >= 1; k1--)
{
if (bFace[k1] == 3) x1 = nNum[k1];
bFace[k1] = 0;
}
aHand = aHand + x1 + ".....";
n2 = n2 + 1;
}
OutFile << aHand << endl;
}
OutFile.close();
InFile.close();
cout << n2 << endl;
}
void Get5P9(int pFile)
{
int k1, k2, n1, n2, n3 = 0;
string x1, aName,aHand, i1 = "i", aFace[14];
char c1[6];
aName = mName[pFile];
ifstream InFile(aName.c_str(), ios::in);
aName = mName[1-pFile];
ofstream OutFile(aName.c_str(), ios::out);
for (k2 = 0; k2 <= 2598959; k2++)
{
InFile >> aHand; aHand.copy(c1,6);
if (aHand.length() == 6 && aHand.substr(5,1) == i1)
{
for (k1 = 0; k1 <= 4; k1++)
{
n1 = (int(c1[k1]) - 48);
n2 = n1 % 13;
if (n2 == 0) n2 = 13;
aFace[n2] = nNum[n2];
}
n2 = n1 / 13;
// n2 is the suite value of the hand Flush. It serves as tie-breaker.
x1 = "";
for (k1 = 13; k1 >= 1; k1--)
{
x1 = x1 + aFace[k1];
aFace[k1] = "";
}
aHand = aHand + x1 + nNum[n2];
n3 = n3 + 1;
}
OutFile << aHand << endl;
}
OutFile.close();
InFile.close();
cout << n3 << endl;
}
// hand 01234 is the weakest and hand 09;;< is the strongest.
void Get4P8(int pFile)
{
int k1, k2, n1, n2 = 0;
string x1, aName,aHand, h1 = "h", aFace[14];
char c1[6];
aName = mName[pFile];
ifstream InFile(aName.c_str(), ios::in);
aName = mName[1-pFile];
ofstream OutFile(aName.c_str(), ios::out);
for (k2 = 0; k2 <= 2598959; k2++)
{
InFile >> aHand; aHand.copy(c1,6);
if (aHand.length() == 6 && aHand.substr(5,1) == h1)
{
for (k1 = 0; k1 <= 4; k1++)
{
n1 = (int(c1[k1]) - 48) % 13;
aFace[n1] = nNum[n1];
}
x1 = "";
for (k1 = 13; k1 >= 0; k1--)
{
x1 = x1 + aFace[k1];
aFace[k1] = "";
}
if (x1 == "ponmd") // ponmd = 09;;<. q = 13
x1 = "q";
else
x1 = x1.substr(0,1);
aHand = aHand + x1 + ".....";
n2 = n2 + 1;
}
OutFile << aHand << endl;
}
OutFile.close();
InFile.close();
cout << n2 << endl;
}
//To set a kind 3 hand apart from another kind 3 hand, we need only a trippled card's face value.
void Get3P7(int pFile)
{
int k1, k2, n1, n2 = 0,bFace[14] = {0};
string x1, aName,aHand, g1 = "g";
char c1[6];
aName = mName[pFile];
ifstream InFile(aName.c_str(), ios::in);
aName = mName[1-pFile];
ofstream OutFile(aName.c_str(), ios::out);
for (k2 = 0; k2 <= 2598959; k2++)
{
InFile >> aHand; aHand.copy(c1,6);
if (aHand.length() == 6 && aHand.substr(5,1) == g1)
{
for (k1 = 0; k1 <= 4; k1++)
{
n1 = (int(c1[k1]) - 48) % 13;
if (n1 == 0) n1 = 13;
bFace[n1] = bFace[n1] + 1;
}
x1 = "";
for (k1 = 13; k1 >= 1; k1--)
{
if (bFace[k1] == 3) x1 = nNum[k1];
bFace[k1] = 0;
}
aHand = aHand + x1 + ".....";
n2 = n2 + 1;
}
OutFile << aHand << endl;
}
OutFile.close();
InFile.close();
cout << n2 << endl;
}
void Get2P6(int pFile)
{
int k1, k2, n1, n2 = 0,bFace[14] = {0};
string x1, x2,aName,aHand, f1 = "f";
char c1[6];
aName = mName[pFile];
ifstream InFile(aName.c_str(), ios::in);
aName = mName[1-pFile];
ofstream OutFile(aName.c_str(), ios::out);
for (k2 = 0; k2 <= 2598959; k2++)
{
InFile >> aHand; aHand.copy(c1,6);
if (aHand.length() == 6 && aHand.substr(5,1) == f1)
{
for (k1 = 0; k1 <= 4; k1++)
{
n1 = (int(c1[k1]) - 48) % 13;
if (n1 == 0) n1 = 13;
bFace[n1] = bFace[n1] + 1;
}
x1 = ""; x2 = "";
for (k1 = 13; k1 >= 1; k1--)
{
if (bFace[k1] == 2) x1 = x1 + nNum[k1]; // 2 pairs' face value
if (bFace[k1] == 1) x2 = nNum[k1]; // 1 lone card's face value
bFace[k1] = 0;
}
aHand = aHand + x1 + x2 + "..."; // Use . padder to standardize score's length.
n2 = n2 + 1;
}
OutFile << aHand << endl;
}
OutFile.close();
InFile.close();
cout << n2 << endl;
}
void Get1P5(int pFile)
{
int k1, k2, n1, n2 = 0,bFace[14] = {0};
string x1, x2,aName,aHand, e1 = "e";
char c1[6];
aName = mName[pFile];
ifstream InFile(aName.c_str(), ios::in);
aName = mName[1-pFile];
ofstream OutFile(aName.c_str(), ios::out);
for (k2 = 0; k2 <= 2598959; k2++)
{
InFile >> aHand; aHand.copy(c1,6);
if (aHand.length() == 6 && aHand.substr(5,1) == e1)
{
for (k1 = 0; k1 <= 4; k1++)
{
n1 = (int(c1[k1]) - 48) % 13;
if (n1 == 0) n1 = 13;
bFace[n1] = bFace[n1] + 1;
}
x1 = ""; x2 = "";
for (k1 = 13; k1 >= 1; k1--)
{
if (bFace[k1] == 2) x1 = nNum[k1]; // The face value of the pair
if (bFace[k1] == 1) x2 = x2 + nNum[k1]; // The face value of the lone cards.
bFace[k1] = 0;
}
aHand = aHand + x1 + x2 + "..";
n2 = n2 + 1;
}
OutFile << aHand << endl;
}
OutFile.close();
InFile.close();
cout << n2 << endl;
}
void Get0P4(int pFile)
{
int k1, k2, n1, n2 = 0;
string x1, aName,aHand, aFace[14],d1 = "d"; // d represents high card type
char c1[6];
aName = mName[pFile];
ifstream InFile(aName.c_str(), ios::in);
aName = mName[1-pFile]; If an input file is file 0, then output file is 1. vice versa .
ofstream OutFile(aName.c_str(), ios::out);
for (k2 = 0; k2 <= 2598959; k2++)
{
InFile >> aHand; aHand.copy(c1,6); //A hand now is length 6. The tail letter is its type
if (aHand.substr(5,1) == d1)
{
for (k1 = 0; k1 <= 4; k1++)
{
n1 = (int(c1[k1]) - 48) % 13;
if (n1 == 0) n1 = 13; // Card Ace is labeled as the highest value 13.
aFace[n1] = nNum[n1];
}
// Compare 2 high card hands. First see what are their strongest cards,
// then the next, and the next. There is no tie- breaker.
x1 = "";
for (k1 = 13; k1 >= 1; k1--)
{
x1 = x1 + aFace[k1];
aFace[k1] = "";
}
n2 = n2 + 1;
aHand = aHand + x1 + ".";
}
OutFile << aHand << endl;
}
OutFile.close();
InFile.close();
cout << n2 << endl;
}
// Arabic 0 to 51 represent the 52 cards. Number % 13 = face value and n / 13 = suite value.
// Dissemble a hand into 5 cards, get their face and suite value, and determine its type.
void Type3()
{
int k1, k2, n1, n2,bFace[13] = {0}, aJoint, aPair;
string x1, aHand, bSui, aPoint,bStra, aFace[13],aSui = "00000 11111 22222 33333";
string aStra = "01234 09:;< 12345 23456 34567 45678 56789 6789: 789:; 89:;<";
char c1[5];
ifstream InFile("2598959.txt", ios::in);
ofstream OutFile("2598959a.txt", ios::out);
for (k2 = 0; k2 <= 2598959; k2++)
{
InFile >> aHand; aHand.copy(c1,5);
aPoint = "d"; bSui = "";
for (k1 = 0; k1 <= 4; k1++)
{
n1 = int(c1[k1]) - 48;
n2 = n1 % 13;
aFace[n2] = mNum[n2];
bFace[n2] = bFace[n2] + 1;
n2 = n1 / 13;
bSui = bSui + mNum[n2];
}
bStra = ""; aJoint = 0; aPair = 0;
for (k1 = 0; k1 <= 12; k1++)
{
bStra = bStra + aFace[k1];
if (bFace[k1] > 1) aJoint = aJoint + bFace[k1];
if (bFace[k1] == 2) aPair = aPair + 1;
aFace[k1] = "";
bFace[k1] = 0;
}
if (aPair == 2) aJoint = 20;
if (aStra.find(bStra,0) == -1 || bStra.length() != 5) bStra = "";
if (aSui.find(bSui,0) == -1) bSui = "";
if (bStra != "" && bSui != "")
aPoint = "l";
else if (aJoint == 4)
aPoint = "k";
else if (aJoint == 5)
aPoint = "j";
else if (bSui != "")
aPoint = "i";
else if (bStra != "")
aPoint = "h";
else if (aJoint == 3)
aPoint = "g";
else if (aJoint == 20)
aPoint = "f";
else if (aJoint == 2)
aPoint = "e";
x1 = aHand + aPoint;
OutFile << x1 << endl;
}
OutFile.close();
InFile.close();
}
void Hands2() //Generate all possible hands: 0 - 2598959;
{
int k1, k2, k3, k4, k5, aCount = -1;
string x1, x2, x3, x4, x5;
ofstream OutFile("2598959.txt", ios::out);
for (k5 = 0; k5<= 47; k5++)
{
x5 = mNum[k5];
for (k4 = k5 + 1; k4<= 48; k4++)
{
x4 = x5 + mNum[k4];
for (k3 = k4 + 1; k3<= 49; k3++)
{
x3 = x4 + mNum[k3];
for (k2 = k3 + 1; k2<= 50; k2++)
{
x2 = x3 + mNum[k2];
for (k1 = k2 + 1; k1<= 51; k1++)
{
x1 = x2 + mNum[k1];
OutFile << x1 << endl;
aCount = aCount + 1;
}
}
}
}
}
OutFile.close();
}
void SetUp1()
{
int k1;
string x1,x2;
for (k1 = 0; k1 <= 51; k1++)
mNum[k1] = char(k1+48); // ASCii representing 52 cards (0,1,2 -- a,b,c)
for (k1 = 0; k1 <= 13; k1++) nNum[k1] = char(k1+100); // for scores: d,e,f,g,h,i,j,k,l
}
void aMain()
{
SetUp1();
Hands2(); // Permutate all possible hands
Type3(); // Code all hands' types
// Code all hands' within-type scores (from 0 point -- high card to 8 p -- straight flush)
// Open "2598959a.txt", file 0, add scores and save to "2598959b.txt, file 1"
// Next open "2598959b.txt" and save data into "2598959a.txt". Alternating the 2 files
Get0P4(0); //Make 0 point hands (High Cards)
Get1P5(1); // One pair
Get2P6(0);
Get3P7(1);
Get4P8(0);
Get5P9(1);
Get6P10(0);
Get7P11(1);
Get8P12(0);
LineUp13(); // Finally, change "2598959b.txt" a hand per line to 100 hand per line.
// and save the file to "25990f.txt"
}
int main(int argc, char** argv)
{
int k1,k2,n1,n2;
string x1,x2;
aMain();
exit(0);
system("PAUSE");
return 0;
}
Part 2
string mNum[52], mHead[25991], mLine[25991];
void SumUp5(int pNum) // Open the textfile with a million games' scores
{
int k1, k2, n1, n2 = 0;
string x1, x2, aHand, aIndex[6];
ifstream InFile("Score1M.txt", ios::in);
for (k2 = 0; k2 <= 999999; k2++)
{
InFile >> aHand;
x1 = aHand.substr(0,12) + aHand.substr(24,48);
if (pNum == 1) x1 = aHand.substr(12,60);
n1 = 5;
for (k1 = 0; k1 <= 4; k1++)
{
aIndex[k1] = x1.substr(n1,7); n1 = n1 + 12;
}
x1 = aIndex[0];
for (k1 = 1; k1 <= 4; k1++)
{
if (x1 < aIndex[k1]) n2 = n2 - 1;
if (x1 > aIndex[k1]) n2 = n2 + 1;
}
}
x1 = "One million games (4 bets for each game), how many bets the dealer wins?";
if (pNum == 0)
cout << "1. Without card replacement for the dealer:" << endl;
else
cout << "2. With card replacement for the dealer:" << endl;
cout << "The count is " << n2 << endl;
}
//Input a hand and output its score.
string Score3a(string pHand)
{
int k1, n1;
string x1, x2;
for (k1 = 0; k1 <= 25990; k1++)
if (pHand < mHead[k1]) break;
// Dictionary stype's retrieval. First the line the hand is located, then the hand.
x1 = mLine[k1 - 1];
n1 = x1.find(pHand,0);
x2 = x1.substr(n1,12);
return x2;
}
// Replace 3 cards
string Swap3b(string pHand, string pPart, int pPoint)
{
int k1, k2, n1, n2;
string x1, x2, x3, s1[5], aFace[14];
char c1[5];
pHand.copy(c1,5);
for (k1 = 0; k1 <= 4; k1++)
{
x1 = pHand.substr(k1,1);
n1 = (int(c1[k1]) - 48) % 13;
if (n1 == 0) n1 = 13;
aFace[n1] = aFace[n1] + x1;
}
x1 = "";
if (pPoint == 0)
{
for (k1 = 13; k1 >= 1; k1--)
if (aFace[k1].length() == 1) x1 = x1 + aFace[k1];
x1 = x1.substr(0,2);
}
else if (pPoint == 1)
{
for (k1 = 13; k1 >= 1; k1--)
if (aFace[k1].length() == 2) x1 = aFace[k1];
}
else if (pPoint == 2)
{
for (k1 = 13; k1 >= 1; k1--)
if (aFace[k1].length() == 2) x1 = x1 + aFace[k1];
}
else if (pPoint == 3)
{
for (k1 = 13; k1 >= 1; k1--)
if (aFace[k1].length() == 3) x1 = aFace[k1];
}
n1 = 5 - x1.length();
x2 = x1 + pPart.substr(0,n1);
for (k1 = 0; k1 <= 4; k1++)
s1[k1] = x2.substr(k1,1);
x3 = "";
for (k2 = 0; k2 <= 4; k2++)
{
x1 = s1[k2];
for (k1 = k2 + 1; k1 <= 4; k1++)
if (x1 > s1[k1])
{
x2 = x1; x1 = s1[k1]; s1[k1] = x2;
}
x3 = x3 + x1;
}
return x3;
}
// Get one million hands' scores
void Score4()
{
int k1, k2, n1;
string x1, x2, x3, aHand;
ifstream InFile("Game1M.txt", ios::in);
ofstream OutFile("Score1M.txt", ios::out);
for (k2 = 0; k2 <= 999999; k2++)
{
InFile >> x1;
n1 = -5; aHand = "";
for (k1 = 0; k1 <= 5; k1++)
{
n1 = n1 + 5; x2 = x1.substr(n1,5);
x3 = Score3a(x2);
aHand = aHand + x3;
}
OutFile << aHand << endl;
}
OutFile.close();
InFile.close();
}
// Shuffle one million times of the 52 cards and randomly pick 28 cards
void Shuffle3()
{
int k1, k2, k3, k4, n1, n2,aCount;
string x1, x2, aHand, bHand,aCard[52], bCard[52], aPart;
char c1[6];
ofstream OutFile("Game1M.txt", ios::out);
for (k4 = 0; k4 <= 999999; k4++)
{
aHand = "";
for (k3 = 0; k3<= 51; k3++)
aCard[k3] = mNum[k3];
n2 = -1;
for (k3 = 51; k3>= 24; k3--)
{
n1 = rand() % (k3+1);
n2 = n2 + 1;
bCard[n2] = aCard[n1];
aCard[n1] = aCard[k3];
}
aPart = bCard[25] + bCard[26] + bCard[27];
aCount = -1;
for (k3 = 0; k3<= 4; k3++)
{
for (k2 = 0; k2<= 4; k2++)
{
aCount = aCount + 1;
aCard[k2] = bCard[aCount];
}
for (k2 = 0; k2<= 4; k2++)
{
x1 = aCard[k2];
for (k1 = k2 + 1; k1<= 4; k1++)
if (x1 > aCard[k1])
{
x2 = x1; x1 = aCard[k1]; aCard[k1] = x2;
}
aHand = aHand + x1;
}
}
bHand = aHand.substr(0,5);
x1 = Score3a(bHand);
x2 = x1.copy(c1,6);
n1 = int(c1[5]) - 100;
if (n1 < 4)
x2 = Swap3b(bHand, aPart, n1);
else
x2 = bHand;
bHand = bHand + x2;
x1 = bHand + aHand.substr(5,20);
OutFile << x1 << endl;
}
OutFile.close();
}
void Load2()
{
int k1;
string x1;
ifstream InFile("25990f.txt", ios::in);
for (k1 = 0; k1 <= 25990; k1++)
{
InFile >> x1;
mHead[k1] = x1.substr(0,5);
mLine[k1] = x1;
}
InFile.close();
}
void SetUp1()
{
int k1;
for (k1 = 0; k1 <= 51; k1++)
mNum[k1] = char(k1+48);
}
void aMain()
{
SetUp1();
Load2();
Shuffle3();
Score4();
SumUp5(0);
SumUp5(1);
}
int main(int argc, char** argv)
{
aMain(); srand(time(0));
exit(0);
system("PAUSE");
return 0;
}
// Part 3
string mNum[52],mRate[25991],nRate[25991];
//Replace 3 cards
string Swap3b(string pHand, string pCard, int pPoint)
{
int k1, k2, n1, n2;
string x1, x2, x3, s1[14], aHand;
char c1[5];
pCard = pCard.substr(0,3);
pHand.copy(c1,5);
for (k1 = 0; k1 <= 4; k1++)
{
x1 = pHand.substr(k1,1);
n1 = (int(c1[k1]) - 48) % 13;
if (n1 == 0) n1 = 13;
s1[n1] = s1[n1] + x1;
}
x1 = "";
for (k1 = 13; k1 >= 1; k1--)
{
if (s1[k1].length() == 2) x1 = x1 + s1[k1];
if (s1[k1].length() == 1) x2 = x2 + s1[k1];
if (s1[k1].length() == 3) x3 = s1[k1];
}
if (pPoint == 0)
aHand = x2.substr(0,2) + pCard;
else if (pPoint == 1)
aHand = x1 + pCard;
else if (pPoint == 2)
aHand = x1 + pCard.substr(0,1);
else if (pPoint == 3)
aHand = x3 + pCard.substr(0,2);
for (k1 = 0; k1 <= 4; k1++)
s1[k1] = aHand.substr(k1,1);
aHand = "";
for (k2 = 0; k2 <= 4; k2++)
{
x1 = s1[k2];
for (k1 = k2 + 1; k1 <= 4; k1++)
if (x1 > s1[k1])
{
x2 = x1; x1 = s1[k1]; s1[k1] = x2;
}
aHand = aHand + x1;
}
return aHand;
}
string Points3a(string pHand)// Retrieve a hand's score
{
int k1, n1;
string x1, x2;
for (k1 = 0; k1 <= 25990; k1++)
if (pHand < mRate[k1]) break;
x1 = nRate[k1-1];
n1 = x1.find(pHand,0);
x2 = x1.substr(n1,12);
return x2;
}
void PlayPoker3()
{
int k1, k2, n1, n2, rpCard, aPosit[5];
string x1, x2, x3, x4, aHand, kCard,bHand, aCard, s1[14], cHand[5], aPoint[5];
char c1[6];
//cout << "Enter the dealer's 5 cards now: ";
//cin >> aHand;
aHand = "6@MYa";
//aHand = "=JWbc";
x1 = Points3a(aHand);
x1.copy(c1,6);
n1 = int(c1[5]) - 100;
if (n1 < 4)
{
for (k1 = 0; k1 <= 4; k1++)
{
x1 = aHand.substr(k1,1);
n2 = (int(c1[k1]) - 48) % 13;
if (n2 == 0) n2 = 13;
s1[n2] = s1[n2] + x1;
}
x1 = ""; x2 = ""; x3 = "";
for (k1 = 13; k1 >= 1; k1--)
{
if (s1[k1].length() == 2) x1 = x1 + s1[k1];
if (s1[k1].length() == 1) x2 = x2 + s1[k1];
if (s1[k1].length() == 3) x3 = s1[k1];
s1[k1] = "";
}
if (n1 == 0)
kCard = x2.substr(0,2);
else if (n1 == 1)
kCard = x1.substr(0,2);
else if (n1 == 2)
kCard = x2.substr(0,4);
else if (n1 == 3)
kCard = x3.substr(0,3);
n2 = 5 - kCard.length();
//cout << "keep cards " + kCard + " and add " << n2 << " cards now" << endl;
//cout << "Input replacement cards now: ";
//cin >> x1;
x1 = "]V3";
aHand = kCard + x1;
}
for (k1 = 0; k1 <= 4; k1++)
s1[k1] = aHand.substr(k1,1);
aHand = "";
for (k2 = 0; k2 <= 4; k2++)
{
x1 = s1[k2];
for (k1 = k2 + 1; k1 <= 4; k1++)
if (x1 > s1[k1])
{
x2 = x1; x1 = s1[k1]; s1[k1] = x2;
}
aHand = aHand + x1;
}
cout << aHand << endl;
aHand = ">?@AK";
//cout << "Enter 4 players' cards (20,separated by a ,): " << endl;
x1 = "1234>,JWabc,1234C,RW`ac," + aHand;
n1 = 0;
for (k1 = 0; k1 <= 4; k1++)
{
x2 = x1.substr(n1,5);
cHand[k1] = x2;
x2 = Points3a(x2);
aPoint[k1] = x2.substr(5,7);
aPosit[k1] = k1;
cout << cHand[k1] + " " + aPoint[k1] + " " << aPosit[k1] << endl;
n1 = n1 + 6;
}
cout << endl;
for (k2 = 0; k2 <= 4; k2++)
{
x1 = cHand[k2]; x2 = aPoint[k2]; n1 = aPosit[k2];
for (k1 = k2 + 1; k1 <= 4; k1++)
if (x2 < aPoint[k1])
{
x4 = x2; x2 = aPoint[k1]; aPoint[k1] = x4;
x3 = x1; x1 = cHand[k1]; cHand[k1] = x3;
n2 = n1; n1 = aPosit[k1]; aPosit[k1] = n2;
}
cHand[k2] = x1; aPoint[k2] = x2; aPosit[k2] = n1;
cout << k2 << " " + cHand[k2] + " " + aPoint[k2] + " " << aPosit[k2] << endl;
}
cout << endl;
for (k2 = 0; k2 <= 4; k2++)
{
x1 = cHand[k2]; x2 = aPoint[k2]; n1 = aPosit[k2];
for (k1 = k2 + 1; k1 <= 4; k1++)
if (x2 == aPoint[k1])
cout << aPosit[k2] << " score - ties " << aPosit[k1] << endl;
}
}
void Load2()
{
int k1;
string x1;
ifstream InFile("25990f.txt", ios::in);
for (k1 = 0; k1 <= 25990; k1++)
{
InFile >> x1;
mRate[k1] = x1.substr(0,5);
nRate[k1] = x1;
}
InFile.close();
}
void SetUp1()
{
int k1,k2;
string x1,x2;
for (k1 = 0; k1 <= 51; k1++)
mNum[k1] = char(k1+48);
}
void aMain()
{
int k1,k2,n1,n2;
string x1,x2;
srand(time(0));
SetUp1();
Load2();
PlayPoker3();
}
int main(int argc, char** argv)
{
aMain();
exit(0);
system("PAUSE");
return 0;
}
Section 9: Print Out 1441 solutions for a difficult sudoku puzzle using BigData
Coding techniques to develop the algorithm and to do the coding.
The book: "Programming Sudoku" by Wei-Meng Lee, lists an extremely difficult
puzzle and its solution. The author does not know if the puzzle has other
solutions. The two programs, which I list below, independently show that it has
1441 solutions. The solutions, which Program A prints out, match exactly those
printed out by Program B.
The puzzle in 1-D form and in-D form(0 represents blanks needing filling.)
000008009050090000009004800002140003006000900400067100005900300000030070800400000
324718659758693412619524837582149763176385924493267185265971348941832576837456291
--- --8 --9
-5- -9- ---
--9 --4 8--
--2 14- --3
--6 --- 9--
4-- -67 1--
--5 9-- 3--
--- -3- -7-
8-- 4-- ---
ALGORITHM
Program A(Column to column solution):
Step 1: Permutating (1-9) Generates a list of 362880 (factorial 1 to 9)
int k1,k2,k3,n1,n2,aCount = 0,aLen;
string mNum[] = {"0","1","2","3","4","5","6","7","8","9"};
string x1,x2, aNum,aMove[40320],bMove[40320];
ofstream OutFile("362879.txt", ios::out); //Save data in a text file.
for (k3 = 1; k3 <= 9; k3++)
{
aNum = mNum[k3];
aLen = aCount; aCount = -1;
for (k2 = 0; k2 <= aLen; k2++)
{
aMove[k2] = bMove[k2];
for (k2 = 0; k2 <= aLen; k2++)
{
x1 = aMove[k2];
for (k1 = 0; k1 <= k3 -1; k1++)
{
x2 = x1;
x2.insert(k1,aNum);
aCount = aCount + 1;
if (k3 != 9)
bMove[aCount] = x2;
else
OutFile << x2 << endl;
}
}
}
}
OutFile.close();
// This function works as follows:
1. Copy bMove[n] to aMove[n]; aMove[0] = "";
2. Insert "1" to aMove[0] at position 0, bMove[0] = "1";
3. Copy bMove[n] to aMove[n]; aMove[0] = "1";
4. Insert "2" to aMove[0] at position 0, and bMove[0] = "21".
Insert "2" to aMove[0] at position 1, and bMove[1] = "12"
5. Continue to 3,4,5,6,7,8;
6. Continue to 9 and then save the list to a textfile.
The final loop: aMove[40319] = "87654321" becomes
876543219,876543291,876543921,876549321,876594321
876954321,879654321,897654321,987654321
Step 2: Create indices of Filter-in and Filter-0ut(mGet[n] and mCut[n])
1. Use consecutive ASCII to represent the sudoku-board(an array(0-80)
convert ASCII into Arabic:
x1 = ./0 123 456; x1.copy(char c1,9) n1 = int(c1[0]) - 46; n1 = 0
./0 123 456
789 :;< =>?
@AB CDE FGH
IJK LMN OPQ
RST UVW XYZ
[\] ^_` abc
def ghi jkl
mno pqr stu
vwx yz{ |}~
--- --8 --9
-5- -9- ---
--9 --4 8--
--2 14- --3
--6 --- 9--
4-- -67 1--
--5 9-- 3--
--- -3- -7-
8-- 4-- ---
2. Load the above puzzle into an array--nPuz[n] and create a Filter-in array mGet[n]
n1 = -1;
for (k2 = 0; k2<= 8; k2++) // Row 0 to Row 8
{
x2 = "";
for (k1 = 0; k1<= 8; k1++) // Position of row (0 to 8)
{
n1 = n1 + 1;
if (nPuz[n1] != "")
x2 = x2 + mNum[k1] + x1;
}
mGet[k2] = x2;
}
Row 0 = "5889". Odd numbers represent string positions. Even as values
"5889" means position 5 and value 8 + position 8 and value 9
Only those strings (123456789 to 987654321) that have 8 in position 5 and 9
in position 8 pass through.
Use 3 indices to represent the values of the 80-cell array (row, column and mini grid)
x1 = "111111111222222222333333333444444444555555555666666666777777777888888888999999999";
x2 = "123456789123456789123456789123456789123456789123456789123456789123456789123456789";
x3 = "111222333111222333111222333444555666444555666444555666777888999777888999777888999";
for (k1 = 0; k1<= 80; k1++)
{
Index1[k1] = x1.substr(k1,1);
Index2[k1] = x2.substr(k1,1);
Index3[k1] = x3.substr(k1,1);
}
for (k2 = 0; k2<= 80; k2++)
{
if (nPuz[k2] == "")
{
x1 = Index1[k2]; x2 = Index2[k2]; x3 = Index3[k2];
aMove = "";
for (k1 = 0; k1<= 80; k1++)
{
if (nPuz[k1] != "")
{
if (x1 != Index1[k1] && (x2 == Index2[k1] || x3 == Index3[k1]))
{
if (aMove.find(nPuz[k1],0) == -1)
aMove = aMove + nPuz[k1];
}
}
}
mCut[k2] = aMove; //Filter-out index[n]
}
}
//Delete duplicates
for (k3 = 0; k3<= 72; k3+= 9)
{
n1 = k3; n2 = n1 + 8;
for (k2 = n1; k2<= n2; k2++)
{
if (nPuz[k2] != "")
{
x1 = nPuz[k2];
for (k1 = n1; k1<= n2; k1++)
{
n3 = mCut[k1].find(x1,0);
if (n3 != -1) mCut[k1].erase(n3,1);
}
}
}
}
Each cell controls other 12 cells, e.g: Cell 0 controls the cells below:
9 10 11
18 19 21
27
36
45
54
63
72
--- --8 --9
-5- -9- ---
--9 --4 8--
--2 14- --3
--6 --- 9--
4-- -67 1--
--5 9-- 3--
--- -3- -7-
8-- 4-- ---
In summary, we start picking strings for row 0. We let strings, that have 8 in position 5
and 9 in position 8, pass through. We filter out those strings, that have 4 or 5 in position 0,
or that have 5 in position 1, or (2 or 6 in p3) and etc.
All these permutations and filter-in and filter-out follow the universal principle:
Pile up big number of data and then filter them down to small number.
Step 3: By filter-in and filter-out, we get all the possible row candidate strings:
First we open that text file that has 362879 strings(123456789 to 987654321).
We load the 10 strings to each aMove[n] (total 36287)
We set up 2 gates. mGet[n] gate, that kicks out unqualified
strings. mCut[n] gate, that also kicks out unqualified strings
(e.g. for pick up strings for row 0, each string must have 8, 9 in position 5 and 8,
and must not, in position 0, have 4 or 5, in position 1, have 4, ... in position 7,
have 7.)
Here is the program:
void Row3()
{
int k1, k2, k3, k4,n1, aPosit[19],aCount = -1, bCount[9], cCount = -1,aLen, aStart, aEnd;
string x1, x2, aMove[36288], bMove, aGet[19], aCut;
char c1[99];
ifstream InFile("362879.txt", ios::in);
n1 = -1;
for (k2 = 0; k2 <= 36287; k2++)
{
x1 = "";
for (k1 = 1; k1 <= 10; k1++)
{
n1 = n1 + 1;
InFile >> x2;
x1 = x1 + x2;
}
aMove[k2] = x1;
}
InFile.close();
ofstream OutFile("1127r.txt", ios::out);
for (k4 = 0; k4<= 8; k4++)
{
x1 = mGet[k4]; // Green light gate: row 0 is "5889"
aLen = x1.length(); x1.copy(c1,aLen); // convert char to arabic
for (k3 = 0; k3< aLen; k3+= 2)
{
aPosit[k3] = int(c1[k3]) - 48; // For row 0: aPosit[n] = 5,8.
aGet[k3] = x1.substr(k3 + 1,1);// For row 0: aGet[n1] = 8,9.
}
aStart = k4 * 9; aEnd = aStart + 8;
for (k3 = 0; k3<= 36287; k3++)
{
bMove = aMove[k3];
for (k2 = 0; k2 <= 81; k2+= 9)
{
x1 = bMove.substr(k2,9);
for (k1 = 0; k1< aLen; k1+= 2)
{
n1 = aPosit[k1];
x2 = x1.substr(n1,1);
if (x2 != aGet[k1]) goto aSkip; // For row 0, if x2 != 8,9, out
}
n1 = -1;
for (k1 = aStart; k1<= aEnd; k1++)
{
n1 = n1 + 1;
x2 = x1.substr(n1,1);
if (mCut[k1].find(x2,0) != -1) goto aSkip;
} // For row 0, if mCut[n] has the same number in it, out.
aCount = aCount + 1;
OutFile << x1 << endl; //Save the qualified strings to a text file.
aSkip: k1 = 0;
}
}
bCount[k4] = aCount; // The end count for each row-picks.
}
for (k4 = 0; k4<= 8; k4++)
OutFile << bCount[k4] << endl; // Attach the end-count to a file named 1127r.txt
OutFile.close();
}
The final number: 1127 (for all 9 rows)
We index those numbers (0 to 8) as follows(Row1: 0 - 499; Row8: 1062 - 1127)
499
623
829
836
891
899
977
1061
1127
Step 4: We hook up Row0 to Row1 and Row2 and get Section 0 candidates. (String length() = 27);
And 3 to 4 and 5 to get Section 1 and 6,7 8 to get Section 2.
String count section to section:17683 + 115 + 1695 = 19495
How to merge Row0 strings to Row1 strings?
Suppose string0 = "123456789" and string1 = "987654321". We load it into an array0[0-8];
array0[0] = "123"; array0[1] = 123; array0[2] = 123 ... array0[6] = 789 ...array0[8] = 789
We substring string1 into 9,8,7,6,5,4,3,2,1.
We line them up:
123 9 OK here
123 8 OK here
123 7 OK here
456 6 we kick this string out because there are 2 6s
456 5 we kick this string out because there are 2 5s
456 4 we kick this string out because there are 2 4s
789 3
789 2
789 1
All these string manipulations seems to be excessive. But they are basic and frequently
used processing techniques in what I call Bigdata Coding, a revolutionary theory and practice.
Any one, who sticks to the conventional coding, would find them quite anoying. But after you
have used them for several times, you will come to like them.
Step 5: We merge Section 0 to Section 1 and then Section 2. We get 1441 solutions.
Section to Section merge means column check.
Suppose we have a Section 0 string's positions:
00 01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26
Suppose we have a section 0 string's value as follow:
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
We line up the numbers by their columns and index the above string as follow:
Index[0] = 00 09 18 = 147
Index[1] = 01 10 19 = 258
Index[2] = 02 11 20 = 369
Index[3] = 03 12 21 = 471
Index[4] = 04 13 22 = 582
Index[5] = 05 14 23 = 693
Index[6] = 06 15 24 = 714
Index[7] = 07 16 25 = 825
Index[8] = 08 17 26 = 936
Index[9] = 00 09 18 = 147
Index[10] = 01 10 19 = 258
Index[11] = 02 11 20 = 369
Index[12] = 03 12 21 = 471
Index[13] = 04 13 22 = 582
Index[14] = 05 14 23 = 693
Index[15] = 06 15 24 = 714
Index[16] = 07 16 25 = 825
Index[17] = 08 17 26 = 936
Index[18] = 00 09 18 = 147
Index[19] = 01 10 19 = 258
Index[20] = 02 11 20 = 369
Index[21] = 03 12 21 = 471
Index[22] = 04 13 22 = 582
Index[23] = 05 14 23 = 693
Index[24] = 06 15 24 = 714
Index[25] = 07 16 25 = 825
Index[26] = 08 17 26 = 936
Suppose we have a Section 1 string as follow
9 8 7 6 5 4 3 2 1
6 5 4 3 2 1 9 8 7
1 2 3 9 8 7 3 2 1
We substr the above string and line them up:
0: 147 9
1: 258 8 there are 2 8s. Kick it out
We merge 1 to 2, we have a string 54 in length
The Index[n] has 6 numbers
Index[0] = 00 09 18 27 36 45
Index[26] = 08 17 26 35 44 53
Step 6: Verify the 1441 solutions
Check 1: a number shows up only once in the same row, same column and min grid.
Use 3 indices to represent the values of the 80-cell array (row, column and mini grid)
x1 = "111111111222222222333333333444444444555555555666666666777777777888888888999999999";
x2 = "123456789123456789123456789123456789123456789123456789123456789123456789123456789";
x3 = "111222333111222333111222333444555666444555666444555666777888999777888999777888999";
for (k1 = 0; k1<= 80; k1++)
{
Index1[k1] = x1.substr(k1,1);
Index2[k1] = x2.substr(k1,1);
Index3[k1] = x3.substr(k1,1);
}
aCount = -1;
for (k2 = 0; k2<= 80; k2++)
{
x1 = Index1[k2]; x2 = Index2[k2]; x3 = Index3[k2];
for (k1 = 0; k1<= 80; k1++)
{
if (k2 != k1)
{
if (x1 == Index1[k1] || x2 == Index2[k1] || x3 == Index3[k1])
{
aCount = aCount + 1;
mCheck[aCount] = k1;
}
}
}
}
Suppose the cell 0, in a solution string is 3:
aStart = 0 * 20: aEnd = aStart + 19: mCheck[0] to mCheck[19];
Cell 0 control the following 20 cells
1 2 3 4 5 6 7 8
9 10 11
18 19 20
27
36
45
54
64
72
Suppose the solution is as follows:
324718659
758693412
619524837
582149763
176385924
493267185
265971348
941832576
837456291
Cell 0 = 3
The values of the 20 cells it controls are as follows:
2 4 7 1 8 6 5 9
7 5 8
6 1 9
5
1
4
2
9
8
No 3 in all the 20 cells. The string is OK.
Check 2: No duplicate solution shows up within the 1441 solutions
The solution listed in the book must show up in the 1441 solution2.
Check 3: All solutions must match exactly the puzzle:
--- --8 --9
-5- -9- ---
--9 --4 8--
--2 14- --3
--6 --- 9--
4-- -67 1--
--5 9-- 3--
--- -3- -7-
8-- 4-- ---
e.g substr(72,1) must be 8 and substr(75,1) must be 4.
Here's the program
string mPuz = "000008009050090000009004800002140003006000900400067100005900300000030070800400000";
string mKey = "324718659758693412619524837582149763176385924493267185265971348941832576837456291";
string mNum[] = {"0","1","2","3","4","5","6","7","8","9"}, nPuz[81], mGet[9], mCut[81];
int mCheck[1620];
void Verify6()
{
int k1, k2, k3, n1, n2, n3;
string x1, x2, aMove[1441], aIndex[81];
ifstream InFile("1440.txt", ios::in);
for (k1 = 0;k1<= 1440; k1++)
InFile >> aMove[k1];
InFile.close();
//aMove[1440] = aMove[1439]; // This is for failure test. Function must pick it up.
for (k2 = 0; k2<= 1439; k2++)
{
x1 = aMove[k2];
for (k1 = k2 + 1; k1<= 1440; k1++)
if (x1 == aMove[k1]) cout << "Dup error in " << k1 << endl;
}
//x1 = aMove[1440]; aMove[1440] = "124359768" + x1.substr(9,72); // Failure test.
for (k2 = 0; k2<= 1440; k2++)
{
x1 = aMove[k2];
for (k1 = 0; k1<= 80; k1++)
if (nPuz[k1] != "")
{
x2 = x1.substr(k1,1);
if (nPuz[k1] != x2)
cout << "Key and puzzle unmatched in " << k2 << endl;
}
}
//aMove[1400] = aMove[1400].substr(0,80) + "2"; // Failure test
for (k3 = 0; k3<= 1440; k3++)
{
x1 = aMove[k3];
for (k2 = 0; k2<= 80; k2++)
aIndex[k2] = x1.substr(k2,1);
for (k2 = 0; k2<= 80; k2++)
{
n1 = k2 * 20; n2 = n1 + 19;
x1 = "";
for (k1 = n1; k1<= n2; k1++)
{
n3 = mCheck[k1]; x1 = x1 + aIndex[n3];
}
if (x1.find(aIndex[k2],0) != -1)
{
cout << "Rule violation in " << k3 << endl;
break;
}
}
}
}
void Hook5() //11215
{
int k1, k2, k3, n1, n2,aCount = -1, Start1[10], End1[9];
string x1, x2, Move1[29494], Move2, Move3[109999], aMove[45793], aFilter[27];
ifstream InFile("19495s.txt", ios::in);
for (k1 = 0;k1<= 19495; k1++)
InFile >> Move1[k1];
for (k1 = 0;k1<= 2; k1++)
{
InFile >> n1;
Start1[k1 + 1] = n1 + 1; End1[k1] = n1;
}
InFile.close();
Start1[0] = 0;
int aStart, aEnd, bStart, bEnd, bCount;
aStart = Start1[0]; aEnd = End1[0];
bStart = Start1[1]; bEnd = End1[1];
x1 = "";
for (k3 = bStart; k3<= bEnd; k3++)
x1 = x1 + Move1[k3];
n1 = x1.length() - 1;
for (k3 = 0; k3<= n1; k3++)
aMove[k3] = x1.substr(k3,1);
for (k3 = aStart; k3<= aEnd; k3++)
{
Move2 = Move1[k3];
for (k2 = 0; k2<= 8; k2++)
{
n1 = k2; x1 = "";
for (k1 = 1; k1<= 3; k1++)
{
x1 = x1 + Move2.substr(n1,1);
n1 = n1 + 9;
}
n1 = k2;
for (k1 = 1; k1<= 3; k1++)
{
aFilter[n1] = x1;
n1 = n1 + 9;
}
}
n1 = -27;
for (k2 = bStart; k2<= bEnd; k2++)
{
n1 = n1 + 27; n2 = n1;
for (k1 = 0; k1<= 26; k1++)
{
if (aFilter[k1].find(aMove[n2],0) != -1) goto aSkip;
n2 = n2 + 1;
}
aCount = aCount + 1;
Move3[aCount] = Move2 + Move1[k2];
aSkip: k1 = 0;
}
}
aEnd = aCount; aCount = -1;
bStart = Start1[2]; bEnd = End1[2];
x1 = "";
for (k3 = bStart; k3<= bEnd; k3++)
x1 = x1 + Move1[k3];
n1 = x1.length() -1;
for (k3 = 0; k3<= n1; k3++)
aMove[k3] = x1.substr(k3,1);
ofstream OutFile("1440.txt", ios::out);
for (k3 = 0; k3<= aEnd; k3++)
{
Move2 = Move3[k3];
for (k2 = 0; k2<= 8; k2++)
{
n1 = k2; x1 = "";
for (k1 = 1; k1<= 6; k1++)
{
x1 = x1 + Move2.substr(n1,1);
n1 = n1 + 9;
}
n1 = k2;
for (k1 = 1; k1<= 3; k1++)
{
aFilter[n1] = x1;
n1 = n1 + 9;
}
}
n1 = -27;
for (k2 = bStart; k2<= bEnd; k2++)
{
n1 = n1 + 27; n2 = n1;
for (k1 = 0; k1<= 26; k1++)
{
if (aFilter[k1].find(aMove[n2],0) != -1) goto bSkip;
n2 = n2 + 1;
}
aCount = aCount + 1;
x2 = Move2 + Move1[k2];
OutFile << x2 << endl;
bSkip: k1 = 0;
}
}
OutFile.close();
}
void Hook4() //17683 + 115 + 1695 = 19495
{
int k1, k2, k3, k4, n1, n2, n3,aCount, aLen, Start1[10], End1[9];
string x1, x2, Move1[1128], Move2,Move3[39999], Move4[99999],aMove[9999], aFilter[10];
ifstream InFile("1127r.txt", ios::in);
for (k1 = 0;k1<= 1127; k1++)
InFile >> Move1[k1];
for (k1 = 0;k1<= 8; k1++)
{
InFile >> n1;
Start1[k1 + 1] = n1 + 1; End1[k1] = n1;
}
Start1[0] = 0;
InFile.close();
int aStart, aEnd, bStart, bEnd, bCount = -1, cCount[7];
ofstream OutFile("19495s.txt", ios::out);
for (k4 = 0;k4<= 6; k4+= 3)
{
aStart = Start1[k4]; aEnd = End1[k4];
bStart = Start1[k4 + 1]; bEnd = End1[k4 + 1];
x1 = "";
for (k3 = bStart;k3<= bEnd; k3++)
x1 = x1 + Move1[k3];
aLen = x1.length() -1;
for (k3 = 0;k3<= aLen; k3++)
aMove[k3] = x1.substr(k3,1);
aCount = -1;
for (k3 = aStart;k3<= aEnd; k3++)
{
Move2 = Move1[k3]; x1 = "";
for (k2 = 0;k2<= 8; k2+= 3)
{
x1 = Move2.substr(k2,3);
for (k1 = k2;k1<= k2 + 2; k1++)
aFilter[k1] = x1;
}
n1 = -10;
for (k2 = bStart;k2<= bEnd; k2++)
{
n1 = n1 + 9; n2 = n1;
for (k1 = 0;k1<= 8; k1++)
{
n2 = n2 + 1;
if (aFilter[k1].find(aMove[n2], 0) != -1) goto aSkip;
}
aCount = aCount + 1;
Move3[aCount] = Move2 + Move1[k2];
aSkip: k1 = 0;
}
}
bStart = Start1[k4 + 2]; bEnd = End1[k4 + 2];
x1 = "";
for (k3 = bStart;k3<= bEnd; k3++)
x1 = x1 + Move1[k3];
aLen = x1.length() -1;
for (k3 = 0;k3<= aLen; k3++)
aMove[k3] = x1.substr(k3,1);
aLen = aCount; aCount = -1;
for (k3 = 0;k3<= aLen; k3++)
{
Move2 = Move3[k3];
for (k2 = 0;k2<= 8; k2+= 3)
{
x1 = Move2.substr(k2,3) + Move2.substr(k2 + 9,3);
for (k1 = k2;k1<= k2 + 2; k1++)
aFilter[k1] = x1;
}
n1 = -10;
for (k2 = bStart;k2<= bEnd; k2++)
{
n1 = n1 + 9; n2 = n1;
for (k1 = 0;k1<= 8; k1++)
{
n2 = n2 + 1;
if (aFilter[k1].find(aMove[n2],0) != -1) goto bSkip;
}
aCount = aCount + 1; bCount = bCount + 1;
Move4[aCount] = Move2 + Move1[k2];
OutFile << Move4[aCount] << endl;
bSkip: k1 = 0;
}
}
cCount[k4] = bCount;
}
for (k4 = 0;k4<= 6; k4+= 3)
OutFile << cCount[k4] << endl;
OutFile.close();
}
void Row3()
{
int k1, k2, k3, k4,n1, aPosit[19],aCount = -1, bCount[9], cCount = -1,aLen, aStart, aEnd;
string x1, x2, aMove[36288], bMove, aGet[19], aCut;
char c1[99];
ifstream InFile("362879.txt", ios::in);
n1 = -1;
for (k2 = 0; k2 <= 36287; k2++)
{
x1 = "";
for (k1 = 1; k1 <= 10; k1++)
{
n1 = n1 + 1;
InFile >> x2;
x1 = x1 + x2;
}
aMove[k2] = x1;
}
InFile.close();
ofstream OutFile("1127r.txt", ios::out);
for (k4 = 0; k4<= 8; k4++)
{
x1 = mGet[k4];
aLen = x1.length(); x1.copy(c1,aLen);
for (k3 = 0; k3< aLen; k3+= 2)
{
aPosit[k3] = int(c1[k3]) - 48;
aGet[k3] = x1.substr(k3 + 1,1);
}
aStart = k4 * 9; aEnd = aStart + 8;
for (k3 = 0; k3<= 36287; k3++)
{
bMove = aMove[k3];
for (k2 = 0; k2 <= 81; k2+= 9) //for (k2 = 0; k2 <= 81; k2+= 9)
{
x1 = bMove.substr(k2,9);
for (k1 = 0; k1< aLen; k1+= 2)
{
n1 = aPosit[k1];
x2 = x1.substr(n1,1);
if (x2 != aGet[k1]) goto aSkip;
}
n1 = -1;
for (k1 = aStart; k1<= aEnd; k1++)
{
n1 = n1 + 1;
x2 = x1.substr(n1,1);
if (mCut[k1].find(x2,0) != -1) goto aSkip;
}
aCount = aCount + 1;
OutFile << x1 << endl;
aSkip: k1 = 0;
}
}
bCount[k4] = aCount;
}
for (k4 = 0; k4<= 8; k4++)
OutFile << bCount[k4] << endl;
OutFile.close();
}
void Load2()
{
int k1, k2, k3, n1, n2, n3,aCount, aLen;
string x1, x2, x3, aMove, bMove,Index1[81], Index2[81], Index3[81];
n1 = -1;
for (k2 = 0; k2<= 8; k2++)
{
x2 = "";
for (k1 = 0; k1<= 8; k1++)
{
n1 = n1 + 1;
x1 = mPuz.substr(n1,1);
if (x1 != "0")
{
nPuz[n1] = x1;
x2 = x2 + mNum[k1] + x1;
}
}
mGet[k2] = x2;
}
x1 = "111111111222222222333333333444444444555555555666666666777777777888888888999999999";
x2 = "123456789123456789123456789123456789123456789123456789123456789123456789123456789";
x3 = "111222333111222333111222333444555666444555666444555666777888999777888999777888999";
for (k1 = 0; k1<= 80; k1++)
{
Index1[k1] = x1.substr(k1,1);
Index2[k1] = x2.substr(k1,1);
Index3[k1] = x3.substr(k1,1);
}
for (k2 = 0; k2<= 80; k2++)
{
if (nPuz[k2] == "")
{
x1 = Index1[k2]; x2 = Index2[k2]; x3 = Index3[k2];
aMove = "";
for (k1 = 0; k1<= 80; k1++)
{
if (nPuz[k1] != "")
{
if (x1 != Index1[k1] && (x2 == Index2[k1] || x3 == Index3[k1]))
{
if (aMove.find(nPuz[k1],0) == -1)
{
aMove = aMove + nPuz[k1];
}
}
}
}
mCut[k2] = aMove;
}
}
for (k3 = 0; k3<= 72; k3+= 9)
{
n1 = k3; n2 = n1 + 8;
for (k2 = n1; k2<= n2; k2++)
{
if (nPuz[k2] != "")
{
x1 = nPuz[k2];
for (k1 = n1; k1<= n2; k1++)
{
n3 = mCut[k1].find(x1,0);
if (n3 != -1) mCut[k1].erase(n3,1);
}
}
}
}
n1 = -1;
for (k2 = 0; k2 <= 80; k2++)
{
x1 = Index1[k2]; x2 = Index2[k2]; x3 = Index3[k2];
for (k1 = 0; k1 <= 80; k1++)
{
if (k2 != k1)
if (x1 == Index1[k1] || x2 == Index2[k1] || x3 == Index3[k1])
{
n1 = n1 + 1; mCheck[n1] = k1;
}
}
}
}
void SetUp1()
{
int k1,k2,k3,n1,n2,aCount = 0,aLen;
string x1,x2, aNum,aMove[40320],bMove[40320];
ofstream OutFile("362879.txt", ios::out);
for (k3 = 1; k3 <= 9; k3++)
{
aNum = mNum[k3];
aLen = aCount; aCount = -1;
for (k2 = 0; k2 <= aLen; k2++)
aMove[k2] = bMove[k2];
for (k2 = 0; k2 <= aLen; k2++)
{
x1 = aMove[k2];
for (k1 = 0; k1 <= k3 -1; k1++)
{
x2 = x1;
x2.insert(k1,aNum);
aCount = aCount + 1;
if (k3 != 9)
bMove[aCount] = x2;
else
OutFile << x2 << endl;
}
}
}
OutFile.close();
}
void aMain()
{
SetUp1();
Load2();
Row3();
Hook4();
Hook5();
Verify6();
}
int main(int argc, char** argv)
{
aMain();
exit(0);
system("PAUSE");
return 0;
}
Prgram B(Row to row solution):
C++ programs that print out all solutions for any sudoku puzzles
using BigData Coding techniques to develop the algorithm and the coding.
000008009050090000009004800002140003006000900400067100005900300000030070800400000
324718659758693412619524837582149763176385924493267185265971348941832576837456291
-----8--9
-5--9----
--9--48--
--214---3
--6---9--
4---671--
--59--3--
----3--7-
8--4-----
ALGORITHM
324718659758693412619524837582149763176385924493267185265971348941832576837456291
324 718 659
758 693 412
619 524 837
582 149 763
176 385 924
493 267 185
265 971 348
941 832 576
837 456 291
The group of numbers above represents a sudoku (in completed form in 2-D)
It is valu-based. We can read it as cell 0, value 3, cell 1, value 2.
Another representation: Position-based, ASCII consecutive characters.
2>ALRaio~/?DKY^dr|.ALRaio~ Value 1 Positions: cell 4,16,19,30,36,51,59,65,80
/?DKY^dr| Value 2 Positions
.= bStart && n2 <= bEnd) aPosit[n2] = 1;
}
}
for (k2 = bStart; k2<= bEnd; k2++)
{
if (aPosit[k2] == 0)
{
aCount = aCount + 1; bMove[aCount] = x1 + mNum[k2];
}
}
}
}
}
ofstream OutFile("46655.txt", ios::out); // 5184 * 9 -1 = 46655 items of 9-string
for (k1 = 0; k1 <= aCount; k1++)
OutFile << bMove[k1] << endl;
OutFile.close();
Step 3: Filter-in and Filter-out
Arabic ASCII
--- --8 --9 --- --3 --6
-5- -9- --- -8- -;- ---
--9 --4 8-- --B --E F--
--2 14- --3 --K LM- --Q
--6 --- 9-- --T --- X--
4-- -67 1-- [-- -_` a--
--5 9-- 3-- --f g-- j--
--- -3- -7- --- -q- -t-
8-- 4-- --- v-- y-- ---
for valued "1", the string: .> mMove[k1];
InFile.close();
ofstream OutFile("848Column.txt", ios::out);
for (k3 = 1; k3<= 9; k3++)
{
x1 = mGet[k3];
aLen = x1.length();
for (k2 = 0; k2< aLen; k2++)
aGet[k2] = x1.substr(k2,1);
x1 = mCut[k3];
bLen = x1.length();
for (k2 = 0; k2< bLen; k2++)
aCut[k2] = x1.substr(k2,1);
for (k2 = 0; k2<= 46655; k2++)
{
x1 = mMove[k2];
for (k1 = 0; k1< aLen; k1++)
if (x1.find(aGet[k1], 0) == -1) goto aSkip;
for (k1 = 0; k1< bLen; k1++)
if (x1.find(aCut[k1], 0) != -1) goto aSkip;
aCount = aCount + 1;
OutFile << x1 << endl;
aSkip: k1 = 0;
}
bCount[k3] = aCount;
}
for (k3 = 1; k3<= 9; k3++)
OutFile << bCount[k3] << endl;
OutFile.close();
}
After filtering, 46655 strings become 848 strings and access index attached at the end.
Step 4: Join colum 1 group to 2,3,4,5,6,7,8
Suppose x1 = "ABCDEFGHI" and x2 = "123456789"
Can we join x1 to x2? Yes. Because no single character in x1 is found in x2.
Suppose x1 = "ABCDEFGH1" and x2 = "123456789"
Can we join x1 to x2? No. Because one character "1" in x1 is found in x2.
After joining 1 to 2-9. 848 strings of 9 become 1440 strings of 81.
The 1440 solutions (column by column) must match 100 percent to those made in Program A.
Program B:
string mPuz = "000008009050090000009004800002140003006000900400067100005900300000030070800400000";
string mKey = "324718659758693412619524837582149763176385924493267185265971348941832576837456291";
int mIndex[486], mStart[72], mEnd[72], nIndex[810], nStart[80], nEnd[80];
int pStart[11], pEnd[10];
string mNum[81], mGet[10], mCut[10], nKey[81],nPuz[81], mMove[46656];
string mName[] = {"FileA.txt","FileB.txt"};
void Error8()
{
int k1, k2, k3, n1, n2,aStart, aEnd;
string x1, x2, aMove[1441], bMove, aIndex[81];
ifstream InFile("File1.txt", ios::in);
for (k2 = 0; k2 <= 1440; k2++)
InFile >> aMove[k2];
InFile.close();
//aMove[1440] = aMove[1439];
for (k2 = 0; k2 <= 1439; k2++) // Duplicity check
{
x1 = aMove[k2];
for (k1 = k2+1; k1 <= 1440; k1++)
if (x1 == aMove[k1]) cout << "Dup in " << k2 << " " << k1 << endl;
}
x1 = aMove[1440].substr(0,72) + "431875296";
//aMove[1440] = x1;
for (k2 = 0; k2 <= 1440; k2++) //Puzzle match check
{
x1 = aMove[k2];
for (k1 = 0; k1 <= 80; k1++)
{
if (nPuz[k1] != "")
{
x2 = x1.substr(k1,1);
if (nPuz[k1] != x2) cout << "Puz mis-m" << k2 << " " << k1 << endl;
}
}
}
//x1 = aMove[1440]; aMove[1440] = x1.substr(0,77) + "6529"; // Insert bad data
for (k3 = 0; k3 <= 1440; k3++) // Rules check
{
bMove = aMove[k3];
for (k2 = 0; k2<= 80; k2++)
aIndex[k2] = bMove.substr(k2,1);
for (k2 = 0; k2<= 79; k2++)
{
x1 = aIndex[k2]; x2 = "";
aStart = nStart[k2]; aEnd = nEnd[k2];
for (k1 = aStart; k1<= aEnd; k1++)
{
n1 = nIndex[k1];
x2 = x2 + aIndex[n1];
}
if (x2.find(x1,0) != -1)
{
cout << "Rule violated: " << k3 << " " << k2 << endl;
break;
}
}
}
}
void Decode7() // Convert ASCII to Arabic
{
int k1, k2, k3, n1, n2, aLen = -2, aIndex[81];
string x1, aMove, bIndex[81];
char c1[81];
ifstream aInFile("FileA.txt", ios::in);
do
{
aLen = aLen + 1;
aInFile >> x1;
} while (!aInFile.eof());
aInFile.close();
ifstream InFile("FileA.txt", ios::in);
ofstream OutFile("File1.txt", ios::out);
for (k3 = 0; k3 <= aLen; k3++)
{
InFile >> aMove;
aMove.copy(c1,81); //Convert string to char and then to integer
for (k2 = 0; k2 <= 80; k2++)
aIndex[k2] = int(c1[k2]) - 46;
n1 = -1;
for (k2 = 3; k2 <= 11; k2++)
{
x1 = mNum[k2];
for (k1 = 1; k1 <= 9; k1++)
{
n1 = n1 + 1;
n2 = aIndex[n1];
bIndex[n2] = x1;
}
}
x1 = "";
for (k2 = 0; k2 <= 80; k2++)
x1 = x1 + bIndex[k2];
OutFile << x1 << endl;
}
InFile.close();
OutFile.close();
//cout << mKey << endl;
//cout << x1 << endl;
//if (mKey == x1) cout << "Both keys are the same" << endl;
}
void Join6(int pLen) //Recursive processing: Open FileA, process, save to FileB, vice versa.
{
int k1, k2, k3, n1, n2, aCount = -1, bCount = 0, aLen, bLen,cLen = -2,aStart, aEnd;
string x1, x2, x3,aMove, bMove, cMove, aIndex[10];
aLen = pLen; bLen = aLen - 2;
n1 = aLen % 2;
n2 = 1 - n1;
x1 = mName[n1]; x2 = mName[n2];
ifstream InFile(x1.c_str(), ios::in); // Get the length() of the textfile
do
{
cLen = cLen + 1;
InFile >> x3;
} while (!InFile.eof());
InFile.close();
ifstream aInFile(x1.c_str(), ios::in);
ofstream OutFile(x2.c_str(), ios::out);
aStart = pStart[aLen]; aEnd = pEnd[aLen];
for (k3 = 0; k3 <= cLen; k3++)
{
aInFile >> aMove;
for (k2 = 0; k2 <= 8; k2++)
{
x1 = ""; n1 = k2;
for (k1 = 0; k1 <= bLen; k1++)
{
x1 = x1 + aMove.substr(n1,1);
n1 = n1 + 9;
}
aIndex[k2] = x1;
}
for (k2 = aStart; k2 <= aEnd; k2++)
{
bMove = mMove[k2];
for (k1 = 0; k1 <= 8; k1++)
{
x1 = bMove.substr(k1,1);
if (aIndex[k1].find(x1,0) != -1) goto aSkip;
}
aCount = aCount + 1;
cMove = aMove + bMove;
OutFile << cMove << endl;
aSkip: k1 = 0;
}
}
aInFile.close();
OutFile.close();
cout << aCount << endl;
}
void Join5()
{
int k1, n1, aLen = -2;
string x1;
pStart[1] = 0;
ifstream InFile("Column.txt", ios::in);
ifstream aInFile("Column.txt", ios::in);
do
{
aLen = aLen + 1;
InFile >> x1;
} while (!InFile.eof());
InFile.close();
aLen = aLen - 9;
for (k1 = 0; k1<= aLen; k1++)
aInFile >> mMove[k1];
for (k1 = 1; k1<= 9; k1++)
{
aInFile >> n1;
pStart[k1 + 1] = n1 + 1;
pEnd[k1] = n1;
}
aInFile.close();
n1 = pEnd[1];
ofstream OutFile("FileA.txt", ios::out);
for (k1 = 0; k1<= n1; k1++)
OutFile << mMove[k1] << endl;
OutFile.close();
}
void Column4()
{
int k1, k2, k3, n1, n2, aCount = -1, bCount[10], aLen, bLen;
string x1, x2, aGet[10], aCut[81];
ofstream OutFile("Column.txt", ios::out);
for (k3 = 1; k3<= 9; k3++)
{
x1 = mGet[k3];
aLen = x1.length();
for (k2 = 0; k2< aLen; k2++)
aGet[k2] = x1.substr(k2,1);
x1 = mCut[k3];
bLen = x1.length();
for (k2 = 0; k2< bLen; k2++)
aCut[k2] = x1.substr(k2,1);
for (k2 = 0; k2<= 46655; k2++)
{
x1 = mMove[k2];
for (k1 = 0; k1< aLen; k1++)
if (x1.find(aGet[k1], 0) == -1) goto aSkip;
for (k1 = 0; k1< bLen; k1++)
if (x1.find(aCut[k1], 0) != -1) goto aSkip;
aCount = aCount + 1;
OutFile << x1 << endl;
aSkip: k1 = 0;
}
bCount[k3] = aCount;
}
for (k3 = 1; k3<= 9; k3++)
OutFile << bCount[k3] << endl;
OutFile.close();
}
void LoadPuz3()
{
int k1, k2, n1, n2;
string x1, x2, x3;
ifstream InFile("46655M.txt", ios::in);
// 46655 universal column list. All puzzles have the same column list.
for (k1 = 0; k1 <= 46655; k1++)
InFile >> mMove[k1];
InFile.close();
for (k1 = 0; k1<= 80; k1++)
{
x1 = mPuz.substr(k1,1);
if (x1 != "0") nPuz[k1] = x1;
}
for (k2 = 1; k2<= 9; k2++)
{
x1 = mNum[k2 +2];
x2 = ""; x3 = "";
for (k1 = 0; k1<= 80; k1++)
{
if (nPuz[k1] == x1) x2 = x2 + mNum[k1];
if (nPuz[k1] != x1 && nPuz[k1] != "") x3 = x3 + mNum[k1];
}
mGet[k2] = x2;
mCut[k2] = x3;
}
/*
string aShow[81]; //Display a puzzle in 2-D
for (k1 = 0; k1 <= 80; k1++)
{
x1 = nPuz[k1];
if (x1 == "") x1 = "-";
aShow[k1] = x1;
}
n1 = -1;
for (k2 = 1; k2 <= 9; k2++)
{
for (k1 = 1; k1 <= 9; k1++)
{
n1 = n1 + 1;
cout << aShow[n1] + " ";
}
cout << endl;
}
*/
}
void Collum2()
{
int k1, k2, k3, k4, n1, n2,aCount, aLen, aStart, aEnd,bStart, bEnd, aPosit[81];
string x1, x2, x3, aMove[99999], bMove[99999];
char c1[10];
aCount = 8;
bStart = 0;
for (k4 = 0; k4 <= 8; k4++)
bMove[k4] = mNum[k4];
for (k4 = 0; k4 <= 7; k4++)
{
aLen = aCount; aCount = -1;
bStart = bStart + 9; bEnd = bStart + 8;
for (k3 = 0; k3<= aLen; k3++)
aMove[k3] = bMove[k3];
for (k3 = 0; k3<= aLen; k3++)
{
x1 = aMove[k3]; x1.copy(c1, k4 + 1);
for (k2 = bStart; k2<= bEnd; k2++)
aPosit[k2] = 0;
for (k2 = 0; k2<= k4; k2++)
{
n1 = int(c1[k2]) - 46;
aStart = mStart[n1]; aEnd = mEnd[n1];
for (k1 = aStart; k1<= aEnd; k1++)
{
n2 = mIndex[k1];
if (n2 >= bStart && n2 <= bEnd) aPosit[n2] = 1;
}
}
for (k2 = bStart; k2<= bEnd; k2++)
{
if (aPosit[k2] == 0)
{
aCount = aCount + 1; bMove[aCount] = x1 + mNum[k2];
}
}
}
}
ofstream OutFile("46655M.txt", ios::out);
for (k1 = 0; k1 <= aCount; k1++)
OutFile << bMove[k1] << endl;
OutFile.close();
}
void SetUp1()
{
int k1, k2, n1, n2, aCount = -1;
string x1, x2, x3, aIndex[81], bIndex[81], cIndex[81];
for (k1 = 0; k1 <= 80; k1++)
mNum[k1] = char(k1+46);
//x1: rows; x2: columns; x3: mini-grid
x1 = "111111111222222222333333333444444444555555555666666666777777777888888888999999999";
x2 = "123456789123456789123456789123456789123456789123456789123456789123456789123456789";
x3 = "111222333111222333111222333444555666444555666444555666777888999777888999777888999";
for (k1 = 0; k1 <= 80; k1++)
{
aIndex[k1] = x1.substr(k1,1);
bIndex[k1] = x2.substr(k1,1);
cIndex[k1] = x3.substr(k1,1);
}
for (k2 = 0; k2 <= 71; k2++)
{
mStart[k2] = aCount + 1;
x1 = aIndex[k2]; x2 = bIndex[k2]; x3 = cIndex[k2];
for (k1 = k2 + 1; k1 <= 80; k1++)
{
if (x1 != aIndex[k1] && (x2 == bIndex[k1] || x3 == cIndex[k1]))
{
aCount = aCount + 1; mIndex[aCount] = k1;
}
}
mEnd[k2] = aCount;
}
aCount = -1;
for (k2 = 0; k2 <= 79; k2++)
{
nStart[k2] = aCount + 1;
x1 = aIndex[k2]; x2 = bIndex[k2]; x3 = cIndex[k2];
for (k1 = k2 + 1; k1 <= 80; k1++)
{
if (x1 == aIndex[k1] || x2 == bIndex[k1] || x3 == cIndex[k1])
{
aCount = aCount + 1; nIndex[aCount] = k1;
}
}
nEnd[k2] = aCount;
}
}
void aMain()
{
int k1;
SetUp1();
Collum2();
LoadPuz3();
Column4();
Join5();
or (k1 = 2; k1 <= 9; k1++)
Join6(k1);
Decode7();
Error8();
}
int main(int argc, char** argv)
{ aMain();
exit(0);
system("PAUSE");
return 0; }
Section 10: Print 6 million knight's Tours
Section 10
An example of using dynamic permutation in PC (2 million Closed Tours).
Program A: Make a single closed tour.
Step 1 SetUp1():
a. Set up a 2-D representation for the chessboard
to filter out the out of bounds moves;
b. Index each cell's moves: mIndex[n]
c. Index each cell's acess point. Cell 0's access
point is 2, meaning a knight in that cell can
move to other 2 cells (Cell 10 and 17) and
Cell 1's access point is 3, meaning a knight in
that cell can move to other 3 cells.
Step 2 GetTour2():
Put the knight in the first cell (Cell 0). Now the The
tour's string is 0: The move is 0
The iteration:
a. Change the Cell 0's value from 0 to 99
b. Access the cell 0's moves(10,17: :A)
c. Cut one point from both cell 10 and 17's access points.
d. For the first move: Pick the cell that has the smallest
access point (cell 10). Now the tour's string: 0: (cell 0 and 10)
The move is :(10);
Spin the for loop for another 62 times. You get a full knight's closed tour:
0:4>O^oe_ndj`Q@1;5?ND39HYhblfU[JPakZiXI8BS]gmcTE6GVL=7FWM<2CR\KA(0 to 17)
1 16 59 22 3 18 49 54
40 23 2 17 58 53 4 19
15 64 41 60 21 48 55 50
24 39 32 63 52 57 20 5
33 14 61 42 47 30 51 56
38 25 36 31 62 43 6 9
13 34 27 46 11 8 29 44
26 37 12 35 28 45 10 7
Here is the program:
int mIndex[336], mStart[64], mEnd[64], mRate[64];
string mNum[64];
void GetTour2()
{
int k1, k2, n1, n2, aCount = -1,aMove, aStart, aEnd, aMin;
string x1, aTour,aNum[70];
char c1[64];
aMove = 0;
aTour = mNum[aMove];
for (k2 = 2; k2 <= 64; k2++)
{
mRate[aMove] = 99;
aStart = mStart[aMove]; aEnd = mEnd[aMove];
aMin = 99;
for (k1 = aStart; k1 <= aEnd; k1++)
{
n1 = mIndex[k1]; mRate[n1] = mRate[n1] - 1;
if (aMin > mRate[n1])
{
aMin = mRate[n1]; aMove = n1;
}
}
aTour = aTour + mNum[aMove];
}
cout << "Representaion of a Knight's Closed Tour:" << endl;
cout << aTour << endl;
for (k2 = 0; k2 <= 6; k2++)
{
x1 = mNum[k2];
if (k2 == 0) x1 = " ";
for (k1 = 0; k1 <= 9; k1++)
{
aCount = aCount + 1;
aNum[aCount] = x1 + mNum[k1];
}
}
aTour.copy(c1,64);
string aShow[64];
for (k1 = 0; k1 <= 63; k1++)
{
n1 = int(c1[k1]) - 48;
aShow[n1] = aNum[k1+1];
}
cout << endl;
aCount = -1;
for (k2 = 1; k2 <= 8; k2++)
{
for (k1 = 1; k1 <= 8; k1++)
{
aCount = aCount + 1;
cout << aShow[aCount] + " ";
}
cout << endl << endl;
}
}
void SetUp1()
{
int k1, k2, n1, n2, n3, aCount = -1, aFilter[64], bFilter[120];
int aStep[] = {12,-21,-19,21,-12,-8,19,8};
string x1, x2;
char c1[64];
for (k1 = 0; k1 <= 63; k1++)
mNum[k1] = char(k1+48);
for (k1 = 0; k1 <= 119; k1++)
bFilter[k1] = 64;
for (k2 = 21; k2 <= 91; k2+= 10)
{
for (k1 = k2; k1<= k2 + 7; k1++)
{
aCount = aCount + 1;
aFilter[aCount] = k1;
bFilter[k1] = aCount;
}
}
aCount = -1;
for (k2 = 0; k2<= 63; k2++)
{
n1 = aFilter[k2];
mStart[k2] = aCount + 1;
for (k1 = 0; k1<= 7; k1++)
{
n2 = n1 + aStep[k1];
n3 = bFilter[n2];
if (n3 != 64)
{
aCount = aCount + 1;
mIndex[aCount] = n3;
}
}
mEnd[k2] = aCount;
}
x1 = "2344443234666643468888644688886446888864468888643466664323444432";
x1.copy(c1,64);
for (k1 = 0; k1<= 63;k1++)
mRate[k1] = int(c1[k1]) - 48;
}
void aMain()
{
int k1,k2,n1,n2;
string x1,x2;
SetUp1();
GetTour2();
}
int main(int argc, char** argv)
{
int k1,k2,n1,n2;
string x1,x2;
aMain();
exit(0);
system("PAUSE");
return 0;
}
Program B: Print 6 million tours.
It takes about 45 minutes to run this program.
An example of using Brute Force in a PC
Algorithm
Using an incompleted knight tour (29 moves, Part 1) as a starting point to complete the rest
35 moves. I permutate the 35 moves and generate 6 million Part 2 tours.
I use ASCII to represent Part 1 moves (in Fuction SetUp1()):
"A0:4>O^oe_ndj`Q@1;5?ND39HYhbl" =
"17,0,10,4,14,31,46,63,53,47,62,52,58,48,33,16,1,11,5,15,30,20,3,9,24,41,56,50,60"
3 ways to represent the chessboard
1-D 2-D ASCII
0 1 2 3 4 5 6 7 21 22 23 24 25 26 27 28 0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15 31 32 33 34 35 36 37 38 8 9 : ; < = > ?
16 17 18 19 20 21 22 23 41 42 43 44 45 46 47 48 @ A B C D E F G
24 25 26 27 28 29 30 31 51 52 53 54 55 56 57 58 H I J K L M N O
32 33 34 35 36 37 38 39 61 62 63 64 65 66 67 68 P Q R S T U V W
40 41 42 43 44 45 46 47 71 72 73 74 75 76 77 78 X Y Z [ \ ] ^ _
48 49 50 51 52 53 54 55 81 82 83 84 85 86 87 88 ` a b c d e f g
56 57 58 59 60 61 62 63 91 92 93 94 95 96 97 98 h i j k l m n o
1 2 3 4 5 6 7 8
02 17 -- 23 04 19 -- -- 1
-- 24 03 18 -- -- 05 20 2
16 01 -- -- 22 -- -- -- 3
25 -- -- -- -- -- 21 06 4
-- 15 -- -- -- -- -- -- 5
-- 26 -- -- -- -- 07 10 6
14 -- 28 -- 12 09 -- -- 7
27 -- 13 -- 29 -- 11 08 8
Step 1 (SetUp1())
I compile acess index: mIndex(149), integer and nIndex(149), string
and acess retrieving index: mStart(63) and mEnd(63).
The first available cell is cell 2. Its acessible cells: 8,12,19 or 8 ?
@ A B C D E F G
H I J K L M N O
P Q R S T U V W
- - - [ - ] - -
- - - - - - f -
- - - - l - - -
I save the 168,272 tours into a textfile named move1.txt.
Step 3 (PileUp3())
Opening up the move1.txt,I first filter out the bad tours. The 168,272 tours are reduced about
90%. Then 10-moves tours pick up one move and I save the tours into move2.txt
Now I call PileUp3() again to pick up yet another move and save the tours into move1.txt.
What happens is: open move1, pick up a move and then save the tours into move2.txt
And open move2, pick up a move and then save the tours into move1.txt. I stop when
I get the 33 moves. Now I get 6 million tours. Notice that I do not use an array to
represent the tours. Instead, I load up a move, process it and then save it outside the
program.
Step 4 (PileUp4())
Now there is no more filtering operations. Just pick up another 2 moves.
The tours are completed (35 moves, 6 million tours)
void PileUp4(int pCount)
{
int k1, k2, k3, n1, n2, aCount = -1,aLen = -2, aStart, aEnd, aTail;
string x1, x2, aMove, bMove, aName,bName;
char c1[1];
aName = fName[pCount];
bName = fName[pCount+1];
ifstream aInFile(aName.c_str(), ios::in);
do
{
aLen = aLen + 1;
aInFile >> x1;
} while (!aInFile.eof()); // Find out the length of the text file.
aInFile.close();
ifstream InFile(aName.c_str(), ios::in);
ofstream OutFile(bName.c_str(), ios::out);
for (k2 = 0; k2 <= aLen; k2++)
{
InFile >> aMove;
bMove = aMove.substr(pCount -1,1);
bMove.copy(c1,1);
aTail = int(c1[0]) - 48;
aStart = mStart[aTail]; aEnd = mEnd[aTail];
for (k1 = aStart; k1 <= aEnd; k1++)
{
x1 = nIndex[k1];
if (aMove.find(x1,0) == -1)
{
aCount = aCount + 1;
x2 = aMove + x1;
OutFile << x2 << endl;
}
}
}
OutFile.close();
InFile.close();
cout << pCount << " " << aCount << " " << x2 << " " << x2.length() << endl;
}
void PileUp3(int pCount)
{
int k1, k2, k3, n1, n2, aCount = -1,aLen, aStart, aEnd, aTail,aPosit[64], bPosit[64];
string x1, x2, aMove, bMove, aName, bName;
char c1[35];
aName = fName[pCount];
bName = fName[pCount+1];
ifstream aInFile(aName.c_str(), ios::in);
aLen = -2;
do
{
aLen = aLen + 1;
aInFile >> x1;
} while (!aInFile.eof());
aInFile.close();
ifstream InFile(aName.c_str(), ios::in);
ofstream OutFile(bName.c_str(), ios::out);
for (k3 = 0; k3 <= aLen; k3++)
{
InFile >> aMove; aMove.copy(c1,pCount);
for (k2 = 0; k2<= 63; k2++)
{
aPosit[k2] = mPosit[k2]; bPosit[k2] = mPosit[k2];
}
for (k2 = 0; k2< pCount; k2++)
{
n1 = int(c1[k2]) - 48;
aPosit[n1] = 1; bPosit[n1] = 1;
}
aTail = n1;
bPosit[n1] = 0;
bPosit[17] = 0;
for (k2 = 0; k2<= 63; k2++)
{
if (aPosit[k2] == 0)
{
aStart = mStart[k2]; aEnd = mEnd[k2];
n1 = 0;
for (k1 = aStart; k1<= aEnd; k1++)
{
n2 = mIndex[k1]; n1 = n1 + (1 - bPosit[n2]);
}
if (n1 < 2) goto aSkip;
}
}
aStart = mStart[aTail]; aEnd = mEnd[aTail];
for (k2 = aStart; k2<= aEnd; k2++)
{
x1 = nIndex[k2];
if (aMove.find(x1,0) == -1)
{
aCount = aCount + 1;
x2 = aMove + x1;
OutFile << x2 << endl;
}
}
aSkip: k1 = 0;
}
OutFile.close();
InFile.close(); cout<< pCount << " " << aCount << " " << x2 << " " << x2.length() << endl;
}
void PileUp2()
{
int k1,k2, k3, n1, n2,n3,aCount = 2, aLen,aStart,aEnd, aTail;
string x1,x2,aMove[60840],bMove[168272];
char c1[10];
bMove[0] = "["; bMove[1] = "]";bMove[2] = "f";
for (k3 = 0; k3<= 8; k3++)
{
aLen = aCount; aCount = -1;
for (k2 = 0; k2<= aLen; k2++)
aMove[k2] = bMove[k2];
for (k2 = 0; k2<= aLen; k2++)
{
x1 = aMove[k2]; x2 = x1.substr(k3,1);
x2.copy(c1,1);
aTail = int(c1[0]) - 48;
aStart = mStart[aTail]; aEnd = mEnd[aTail];
for (k1 = aStart; k1<= aEnd; k1++)
{
x2 = nIndex[k1];
if (x1.find(x2,0) == -1)
{
aCount = aCount + 1;
bMove[aCount] = x1 + nIndex[k1];
}
}
}
}
ofstream OutFile("Move1.txt", ios::out);
for (k1 = 0; k1 <= aCount; k1++)
OutFile << bMove[k1] << endl;
OutFile.close();
}
void SetUp1()
{
int k1,k2, n1 = -1, n2,n3,aCount = -1, aFilter[64], bFilter[120];
int aStep[] = {-21,-19,-12,-8,8,12,19,21};
string x1,x2;
char c1[64];
for (k1 = 0; k1 <= 63; k1++)
mNum[k1] = char(k1+48);
for (k1 = 0; k1 <= 119; k1++)
bFilter[k1] = -1;
x1 = "A0:4>O^oe_ndj`Q@1;5?ND39HYhbl";
x1.copy(c1,29);
for (k1 = 0; k1<= 28; k1++)
{
n1 = int(c1[k1]) - 48;
mPosit[n1] = 1;
}
for (k2 = 21; k2<= 91; k2+= 10)
for (k1 = k2; k1<= k2 + 7; k1++)
{
aCount = aCount + 1;
aFilter[aCount] = k1;
if (mPosit[aCount] == 1)
bFilter[k1] = -1;
else
bFilter[k1] = aCount;
}
aCount = -1;
for (k2 = 0; k2<= 63; k2++)
{
if (mPosit[k2] == 0)
{
mStart[k2] = aCount + 1;
n1 = aFilter[k2];
for (k1 = 0; k1<= 7; k1++)
{
n2 = n1 + aStep[k1];
n3 = bFilter[n2];
if (n3 != -1)
{
aCount = aCount + 1;
mIndex[aCount] = n3;
nIndex[aCount] = mNum[n3];
}
}
}
mEnd[k2] = aCount;
}
x1 = "Move1.txt"; x2 = "Move2.txt";
for (k1 = 10; k1 <= 34; k1+= 2)
{
fName[k1] = x1; fName[k1 + 1] = x2;
}
}
void aMain()
{
int k1,k2,n1,n2;
string x1,x2;
SetUp1();
PileUp2();
for (k1 = 10; k1 <= 32; k1++)
PileUp3(k1);
PileUp4(33);
PileUp4(34);
}
int main(int argc, char** argv)
{
int k1,k2,n1,n2;
string x1,x2;
aMain();
exit(0);
system("PAUSE");
return 0;
}
Program C(processing Move2.txt):
After Program B I have a textfile named Move2.txt that is a list of 6 million knight's
tours, each one is 35 characters (35 move). It is time to check for errors
Algorithm
Check the 6 million tours for errors:
1.Duplicate tour (one tour shows up in the tour list more than once)
2.Duplicate move(64 in total) one move shows up more than once within the same tour).
3.Wrong move (a move is not a L-shaped).
1. Duplicate tour
Since the list of 6 million tours is already in correct order, any duplicate items
are next to each other. I only need to make 6 million comparisons: compare item 0 to
item 1 and item 1 to 2, so on.
2. Duplicate move
Each of the 6 million tours is the position variation of the string:
fU[JPakZiXI8BS]gmcTE6GVL=7FWM<2CR\K. I load up a tour and substr the tour one by one
and erase the substr item from the above string. At the end of delete, the string is
empty, meaning the tour passes.
3. Wrong move
I index each cell's acess moves: mIndex[n]. Suppose the first move falls on cell 2(2), and
second move is on 17(A). The move from 2 to 17 is L-shaped because mIndex[2] = 2O^oe_ndj`Q@1;5?ND39HYhbl" to the tours to form the
complete tours.
Here is the program:
string mNum[64],mIndex[64], mTour;
void Check6()
{
int k1;
string x1, x2, aMove, p1;
p1 = "0:4>O^oe_ndj`Q@1;5?ND39HYhbl";
ifstream InFile("Move2.txt", ios::in);
ofstream OutFile("6587629a.txt", ios::out);
for (k1 = 0; k1 <= 6587629; k1++)
{
InFile >> x1;
aMove = p1 + x1;
OutFile << aMove << endl;
}
OutFile.close();
InFile.close();
}
void Check5()
{
int k1;
string x1, aMove,aCheck ="2KPR";
ifstream InFile("Move2.txt", ios::in);
ofstream OutFile("2024129.txt", ios::out);
for (k1 = 0; k1 <= 6587629; k1++)
{
InFile >> aMove;
x1 = aMove.substr(34,1);
if (aCheck.find(x1,0) != -1)
OutFile << aMove << endl;
}
OutFile.close();
InFile.close();
}
void Check4()
{
int k1, k2, n1;
string x1, aMove;
char c1[35];
ifstream InFile("Move2.txt", ios::in);
for (k2 = 0; k2 <= 6587629; k2++)
{
InFile >> aMove;
aMove.copy(c1,35);
for (k1 = 0; k1 <= 33; k1++)
{
x1 = aMove.substr(k1,1);
n1 = int(c1[k1+1]) - 48;
if (mIndex[n1].find(x1,0) == -1)
{
cout << "Error in: " << k2 << endl;
}
}
}
InFile.close();
}
void Check3()
{
int k1, k2, n1, n2;
string x1, x2, aMove;
ifstream InFile("Move2.txt", ios::in);
for (k2 = 0; k2 <= 6587629; k2++)
{
InFile >> x1;
aMove = mTour;
for (k1 = 0; k1 <= 34; k1++)
{
x2 = x1.substr(k1,1);
n1 = aMove.find(x2,0);
aMove.erase(n1,1);
}
if (aMove != "") cout << k2 << " " << aMove << endl;
}
InFile.close();
}
void Check2()
{
int k1;
string x1,x2;
ifstream InFile("Move2.txt", ios::in);
for (k1 = 0; k1 <= 6587629; k1++)
{
InFile >> x1;
if (x1 <= x2) cout << x2 << " " << x1 << " " << k1 << endl;
x2 = x1;
}
InFile.close();
}
void SetUp1()
{
int k1,k2, n1 = -1, n2,n3,aCount = -1, aFilter[64], bFilter[120];
int aStep[] = {-21,-19,-12,-8,8,12,19,21}, aPosit[64] = {0};
string x1,x2;
char c1[64];
for (k1 = 0; k1 <= 63; k1++)
mNum[k1] = char(k1+48);
for (k1 = 0; k1 <= 119; k1++)
bFilter[k1] = -1;
x1 = "A0:4>O^oe_ndj`Q@1;5?ND39HYhbl";
x1.copy(c1,29);
for (k1 = 0; k1<= 28; k1++)
{
n1 = int(c1[k1]) - 48;
aPosit[n1] = 1;
}
for (k1 = 0; k1 <= 63; k1++)
if (aPosit[k1] == 0) mTour = mTour + mNum[k1];
for (k2 = 21; k2<= 91; k2+= 10)
for (k1 = k2; k1<= k2 + 7; k1++)
{
aCount = aCount + 1;
aFilter[aCount] = k1;
if (aPosit[aCount] == 1)
bFilter[k1] = -1;
else
bFilter[k1] = aCount;
}
aCount = -1;
for (k2 = 0; k2<= 63; k2++)
{
if (aPosit[k2] == 0)
{
n1 = aFilter[k2]; x1 = "";
for (k1 = 0; k1<= 7; k1++)
{
n2 = n1 + aStep[k1];
n3 = bFilter[n2];
if (n3 != -1)
x1 = x1 + mNum[n3];
}
}
mIndex[k2] = x1;
}
}
void aMain()
{
int k1,k2,n1,n2;
string x1,x2;
SetUp1();
Check5();
}
int main(int argc, char** argv)
{
int k1,k2,n1,n2;
string x1,x2;
aMain();
exit(0);
system("PAUSE");
return 0;
}