Section 1: Play Hanoi Towers game
Section 2: Print commercial styled calendar (1776-2775)
Section 3: Breaking Enigma Message
Section 4: Computer-assisted Poker Playing
Section 5: Print Out 1441 solutions for a difficult sudoku puzzle
Section 6: Print Out 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
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.
Section 2:
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 3
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 4: 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 5: 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 5: Print 6 million knight's Tours
Section 6
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;
}