============================================== PCPSolver Version 0.0.3 README ============================================== PCPSolver is a program to solve instances of the Post's Correspondence Problem (PCP). It can also randomly search for hard instances with small sizes and widths, and systematically scan PCP subclasses. Use option '-h' to get online help. 0. About the new version Ver 0.0.3.1: (Oct 31, 2006) - Fixed a few bugs that prevent the first optimal solution from being output. Ver 0.0.3: (Nov 16, 2003) - During experiments with different depth increment in IDA*, more functionalities were fully tested, resulting in several minor bugs removed. Ver 0.0.2: (April 25, 2003) - The speed of the solver has been improved by roughly 20% in several different hardware/software platforms. - Source code was almost completely refined to improve readability, modularity and usability (including a textual interface). Ver 0.0.1: (March 7, 2003) - Finally, the source code was released :) 1. Format of PCP instance a. An instance starts at a line whose first letter is a digit ('0'-'9'). All other lines are considered as comments b. The first line of an instance contains the size and width of the instance. The data for size must start from the first letter in the line. Depending on the readmode, the first line can include more information, e.g., the optimal solution length and solution number. See the definition of READWRITEMODE in "readwrite.h". By default, the output instance will have its size, width, optimal solution length, # of optimal solutions and the solving time in the first line. c. The next two lines contain the instance's pairs. Only 0, 1, space, tab, and line break are allowed in the lines. d. Input of instances ends when the file ends or read a line starting with digit '0'. 2. Test suite (in subdirectory TestSuit) a. 200HardInstances.txt - 200 hard instances. b. PCP[3,4]Unsolved.txt - 3,170 unsolved instances in PCP[3,4] c. PCP[3,4]Unsolved.txt - 13,923 unsolved instances in PCP[4,3] *note: You can generate all instances in PCP[3,3] to test the program to prove instances unsolvable. 3. Portability The program has been tested on Visual C++ 6.0 on Windows 2000 with Pentium Processor 600Mhz, gcc 2.96 on Linux with Pentium Processor 600Mhz, and SGI CC on SGI machines. This program is expected to run correctly on all platforms with a standard C++ compiler. 4. Update & Bug report ... The latest version of PCPSolver will be put at http://www.cs.ualberta.ca/~zhao/PCP/PCPSolver/. Welcome to visit my webpage for PCP: http://www.cs.ualberta.ca/~zhao/PCP/. If you find bugs in the program, or have a better idea to improve the program, please feel free to contact me at zhao at cs.ualberta.ca. If you would like to thank the author for writing this program painfully, you can send me a post card to express your gratitude. My mail address is: Ling Zhao Department of Computing Science University of Alberta Edmonton, Alberta, T6G 2E8. Enjoy the PCP world. :) Ling Zhao (zhao at cs.ualberta.ca) Nov 16, 2003