Commits

Shlomi Fish committed eacc3af

Add the patsolve-3.0.2 sources.

Comments (0)

Files changed (40)

patsolve/CMakeLists.txt

+CMAKE_MINIMUM_REQUIRED (VERSION 2.6)
+
+INCLUDE( "${CMAKE_CURRENT_SOURCE_DIR}/Common.cmake" )
+INCLUDE(CheckCCompilerFlag)
+
+# This is the equivalent to perform a "make dist"/"make distdir" etc.
+SET(CPACK_PACKAGE_NAME "patsolve-shlomif")
+SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY "Patsolve - a solver for some Solitaire (Patience) variants")
+SET(CPACK_PACKAGE_VENDOR "Shlomi Fish")
+SET(CPACK_PACKAGE_DESCRIPTION_FILE "${CMAKE_CURRENT_SOURCE_DIR}/README")
+SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_CURRENT_SOURCE_DIR}/COPYING")
+
+# Process and extract the version number.
+FILE( READ "ver.txt" VERSION)
+
+CHOMP (VERSION)
+
+STRING (REGEX MATCHALL "([0-9]+)" VERSION_DIGITS "${VERSION}")
+
+LIST(GET VERSION_DIGITS 0 CPACK_PACKAGE_VERSION_MAJOR)
+LIST(GET VERSION_DIGITS 1 CPACK_PACKAGE_VERSION_MINOR)
+LIST(GET VERSION_DIGITS 2 CPACK_PACKAGE_VERSION_PATCH)
+
+SET(CPACK_PACKAGE_INSTALL_DIRECTORY "${CPACK_PACKAGE_DESCRIPTION_SUMMARY} ${CPACK_PACKAGE_VERSION_MAJOR}.${CPACK_PACKAGE_VERSION_MINOR}.${CPACK_PACKAGE_VERSION_PATCH}")
+
+SET(CPACK_SOURCE_PACKAGE_FILE_NAME "${CPACK_PACKAGE_NAME}-${CPACK_PACKAGE_VERSION_MAJOR}.${CPACK_PACKAGE_VERSION_MINOR}.${CPACK_PACKAGE_VERSION_PATCH}")
+
+SET(CPACK_SOURCE_IGNORE_FILES
+    "/_CPack_Packages/"
+    "/CMakeFiles/"
+    "/.deps/"
+    "patsolve-shlomif-[0-9]+\\\\.[0-9]+\\\\.[0-9]+(-Source|-Linux|)(/|\\\\.(sh|tar\\\\.(gz|bz2|Z|lzma|xz))$)"
+    "\\\\.o$"
+    "~$"
+    "/(patsolve)$"
+    "/lib(fcs|freecell-solver)\\\\.(a|la)$"
+    "\\\\.so(\\\\.[0-9]+)*$"
+    "/\\\\.svn/"
+    "/t/t/.*\\\\.exe$"
+    "/t/Presets"
+    "/CMakeCache\\\\.txt$"
+    "/Makefile$"
+    "/CTestTestfile\\\\.cmake$"
+    "/cmake_install\\\\.cmake$"
+    "/CPackConfig\\\\.cmake$"
+    "/CPackSourceConfig\\\\.cmake$"
+    "/tags$"
+    "/freecell-solver-config$"
+    "/([0-9]+)\\\\.board$"
+    "/install_manifest\\\\.txt$"
+    "/t/card-test-(parse|render)\\\\.c$"
+    "/Testing/"
+)
+
+IF(WIN32 AND NOT UNIX)
+    # There is a bug in NSI that does not handle full unix paths properly. Make
+    # sure there is at least one set of four (4) backlasshes.
+    SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}\\\\dondorf-king.bmp")
+    SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\fc-solve.exe")
+    SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\fc-solve.berlios.de")
+    SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\fc-solve.berlios.de")
+    SET(CPACK_NSIS_DISPLAY_NAME "Patsolve")
+    SET(CPACK_NSIS_CONTACT "shlomif@iglu.org.il")
+    SET(CPACK_NSIS_MODIFY_PATH ON)
+    # Setting for NSIS :
+    SET(CPACK_NSIS_MUI_ICON "${CMAKE_CURRENT_SOURCE_DIR}\\\\fc-solve.ico")
+    SET(CPACK_NSIS_MUI_UNIICON ${CPACK_NSIS_MUI_ICON})
+    SET(CPACK_PACKAGE_ICON ${CPACK_NSIS_MUI_ICON})
+    SET(CPACK_NSIS_MODIFY_PATH "ON")
+ELSE(WIN32 AND NOT UNIX)
+  SET(CPACK_STRIP_FILES "patsolve")
+  SET(CPACK_SOURCE_STRIP_FILES "")
+ENDIF(WIN32 AND NOT UNIX)
+
+SET(CPACK_PACKAGE_EXECUTABLES
+    "patsolve" "Patsolve"
+)
+
+### This is to set the RPATH correctly, so when installed under a prefix
+### the executables will find the libraries.
+### 
+### See:
+###
+### http://www.cmake.org/Wiki/CMake_RPATH_handling
+###
+### (Taken from that wiki page)
+
+# use, i.e. don't skip the full RPATH for the build tree
+SET(CMAKE_SKIP_BUILD_RPATH  FALSE)
+
+# when building, don't use the install RPATH already
+# (but later on when installing)
+SET(CMAKE_BUILD_WITH_INSTALL_RPATH FALSE) 
+
+# the RPATH to be used when installing
+SET(CMAKE_INSTALL_RPATH "${CMAKE_INSTALL_PREFIX}/lib")
+
+# add the automatically determined parts of the RPATH
+# which point to directories outside the build tree to the install RPATH
+SET(CMAKE_INSTALL_RPATH_USE_LINK_PATH TRUE)
+
+INCLUDE(CPack)
+
+ADD_EXECUTABLE(patsolve 
+    patmain.c param.c pat.c patsolve.c tree.c util.c msdealsub.c
+    )
+
+SET(COMPILER_FLAGS_TO_CHECK "-Wall" "-Werror=implicit-function-declaration")
+
+IF (CPU_ARCH)
+    LIST(APPEND COMPILER_FLAGS_TO_CHECK "-march=${CPU_ARCH}")
+ENDIF(CPU_ARCH)
+
+IF (OPTIMIZATION_OMIT_FRAME_POINTER)
+    LIST(APPEND COMPILER_FLAGS_TO_CHECK "-fomit-frame-pointer")
+ENDIF(OPTIMIZATION_OMIT_FRAME_POINTER)
+
+FOREACH (CFLAG_TO_CHECK ${COMPILER_FLAGS_TO_CHECK})
+    CHECK_C_COMPILER_FLAG(${CFLAG_TO_CHECK} FLAG_EXISTS)
+    IF (${FLAG_EXISTS})
+        ADD_DEFINITIONS(${CFLAG_TO_CHECK})
+    ENDIF (${FLAG_EXISTS})
+ENDFOREACH(CFLAG_TO_CHECK)
+
+# Settings for Freecell
+# TODO: allow customisations.
+ADD_DEFINITIONS("-DSAME_SUIT=0")
+ADD_DEFINITIONS("-DNWPILES=8")
+
+TARGET_LINK_LIBRARIES (patsolve "m")
+		    GNU GENERAL PUBLIC LICENSE
+		       Version 2, June 1991
+
+ Copyright (C) 1989, 1991 Free Software Foundation, Inc.
+                       59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+
+			    Preamble
+
+  The licenses for most software are designed to take away your
+freedom to share and change it.  By contrast, the GNU General Public
+License is intended to guarantee your freedom to share and change free
+software--to make sure the software is free for all its users.  This
+General Public License applies to most of the Free Software
+Foundation's software and to any other program whose authors commit to
+using it.  (Some other Free Software Foundation software is covered by
+the GNU Library General Public License instead.)  You can apply it to
+your programs, too.
+
+  When we speak of free software, we are referring to freedom, not
+price.  Our General Public Licenses are designed to make sure that you
+have the freedom to distribute copies of free software (and charge for
+this service if you wish), that you receive source code or can get it
+if you want it, that you can change the software or use pieces of it
+in new free programs; and that you know you can do these things.
+
+  To protect your rights, we need to make restrictions that forbid
+anyone to deny you these rights or to ask you to surrender the rights.
+These restrictions translate to certain responsibilities for you if you
+distribute copies of the software, or if you modify it.
+
+  For example, if you distribute copies of such a program, whether
+gratis or for a fee, you must give the recipients all the rights that
+you have.  You must make sure that they, too, receive or can get the
+source code.  And you must show them these terms so they know their
+rights.
+
+  We protect your rights with two steps: (1) copyright the software, and
+(2) offer you this license which gives you legal permission to copy,
+distribute and/or modify the software.
+
+  Also, for each author's protection and ours, we want to make certain
+that everyone understands that there is no warranty for this free
+software.  If the software is modified by someone else and passed on, we
+want its recipients to know that what they have is not the original, so
+that any problems introduced by others will not reflect on the original
+authors' reputations.
+
+  Finally, any free program is threatened constantly by software
+patents.  We wish to avoid the danger that redistributors of a free
+program will individually obtain patent licenses, in effect making the
+program proprietary.  To prevent this, we have made it clear that any
+patent must be licensed for everyone's free use or not licensed at all.
+
+  The precise terms and conditions for copying, distribution and
+modification follow.
+
+		    GNU GENERAL PUBLIC LICENSE
+   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+  0. This License applies to any program or other work which contains
+a notice placed by the copyright holder saying it may be distributed
+under the terms of this General Public License.  The "Program", below,
+refers to any such program or work, and a "work based on the Program"
+means either the Program or any derivative work under copyright law:
+that is to say, a work containing the Program or a portion of it,
+either verbatim or with modifications and/or translated into another
+language.  (Hereinafter, translation is included without limitation in
+the term "modification".)  Each licensee is addressed as "you".
+
+Activities other than copying, distribution and modification are not
+covered by this License; they are outside its scope.  The act of
+running the Program is not restricted, and the output from the Program
+is covered only if its contents constitute a work based on the
+Program (independent of having been made by running the Program).
+Whether that is true depends on what the Program does.
+
+  1. You may copy and distribute verbatim copies of the Program's
+source code as you receive it, in any medium, provided that you
+conspicuously and appropriately publish on each copy an appropriate
+copyright notice and disclaimer of warranty; keep intact all the
+notices that refer to this License and to the absence of any warranty;
+and give any other recipients of the Program a copy of this License
+along with the Program.
+
+You may charge a fee for the physical act of transferring a copy, and
+you may at your option offer warranty protection in exchange for a fee.
+
+  2. You may modify your copy or copies of the Program or any portion
+of it, thus forming a work based on the Program, and copy and
+distribute such modifications or work under the terms of Section 1
+above, provided that you also meet all of these conditions:
+
+    a) You must cause the modified files to carry prominent notices
+    stating that you changed the files and the date of any change.
+
+    b) You must cause any work that you distribute or publish, that in
+    whole or in part contains or is derived from the Program or any
+    part thereof, to be licensed as a whole at no charge to all third
+    parties under the terms of this License.
+
+    c) If the modified program normally reads commands interactively
+    when run, you must cause it, when started running for such
+    interactive use in the most ordinary way, to print or display an
+    announcement including an appropriate copyright notice and a
+    notice that there is no warranty (or else, saying that you provide
+    a warranty) and that users may redistribute the program under
+    these conditions, and telling the user how to view a copy of this
+    License.  (Exception: if the Program itself is interactive but
+    does not normally print such an announcement, your work based on
+    the Program is not required to print an announcement.)
+
+These requirements apply to the modified work as a whole.  If
+identifiable sections of that work are not derived from the Program,
+and can be reasonably considered independent and separate works in
+themselves, then this License, and its terms, do not apply to those
+sections when you distribute them as separate works.  But when you
+distribute the same sections as part of a whole which is a work based
+on the Program, the distribution of the whole must be on the terms of
+this License, whose permissions for other licensees extend to the
+entire whole, and thus to each and every part regardless of who wrote it.
+
+Thus, it is not the intent of this section to claim rights or contest
+your rights to work written entirely by you; rather, the intent is to
+exercise the right to control the distribution of derivative or
+collective works based on the Program.
+
+In addition, mere aggregation of another work not based on the Program
+with the Program (or with a work based on the Program) on a volume of
+a storage or distribution medium does not bring the other work under
+the scope of this License.
+
+  3. You may copy and distribute the Program (or a work based on it,
+under Section 2) in object code or executable form under the terms of
+Sections 1 and 2 above provided that you also do one of the following:
+
+    a) Accompany it with the complete corresponding machine-readable
+    source code, which must be distributed under the terms of Sections
+    1 and 2 above on a medium customarily used for software interchange; or,
+
+    b) Accompany it with a written offer, valid for at least three
+    years, to give any third party, for a charge no more than your
+    cost of physically performing source distribution, a complete
+    machine-readable copy of the corresponding source code, to be
+    distributed under the terms of Sections 1 and 2 above on a medium
+    customarily used for software interchange; or,
+
+    c) Accompany it with the information you received as to the offer
+    to distribute corresponding source code.  (This alternative is
+    allowed only for noncommercial distribution and only if you
+    received the program in object code or executable form with such
+    an offer, in accord with Subsection b above.)
+
+The source code for a work means the preferred form of the work for
+making modifications to it.  For an executable work, complete source
+code means all the source code for all modules it contains, plus any
+associated interface definition files, plus the scripts used to
+control compilation and installation of the executable.  However, as a
+special exception, the source code distributed need not include
+anything that is normally distributed (in either source or binary
+form) with the major components (compiler, kernel, and so on) of the
+operating system on which the executable runs, unless that component
+itself accompanies the executable.
+
+If distribution of executable or object code is made by offering
+access to copy from a designated place, then offering equivalent
+access to copy the source code from the same place counts as
+distribution of the source code, even though third parties are not
+compelled to copy the source along with the object code.
+
+  4. You may not copy, modify, sublicense, or distribute the Program
+except as expressly provided under this License.  Any attempt
+otherwise to copy, modify, sublicense or distribute the Program is
+void, and will automatically terminate your rights under this License.
+However, parties who have received copies, or rights, from you under
+this License will not have their licenses terminated so long as such
+parties remain in full compliance.
+
+  5. You are not required to accept this License, since you have not
+signed it.  However, nothing else grants you permission to modify or
+distribute the Program or its derivative works.  These actions are
+prohibited by law if you do not accept this License.  Therefore, by
+modifying or distributing the Program (or any work based on the
+Program), you indicate your acceptance of this License to do so, and
+all its terms and conditions for copying, distributing or modifying
+the Program or works based on it.
+
+  6. Each time you redistribute the Program (or any work based on the
+Program), the recipient automatically receives a license from the
+original licensor to copy, distribute or modify the Program subject to
+these terms and conditions.  You may not impose any further
+restrictions on the recipients' exercise of the rights granted herein.
+You are not responsible for enforcing compliance by third parties to
+this License.
+
+  7. If, as a consequence of a court judgment or allegation of patent
+infringement or for any other reason (not limited to patent issues),
+conditions are imposed on you (whether by court order, agreement or
+otherwise) that contradict the conditions of this License, they do not
+excuse you from the conditions of this License.  If you cannot
+distribute so as to satisfy simultaneously your obligations under this
+License and any other pertinent obligations, then as a consequence you
+may not distribute the Program at all.  For example, if a patent
+license would not permit royalty-free redistribution of the Program by
+all those who receive copies directly or indirectly through you, then
+the only way you could satisfy both it and this License would be to
+refrain entirely from distribution of the Program.
+
+If any portion of this section is held invalid or unenforceable under
+any particular circumstance, the balance of the section is intended to
+apply and the section as a whole is intended to apply in other
+circumstances.
+
+It is not the purpose of this section to induce you to infringe any
+patents or other property right claims or to contest validity of any
+such claims; this section has the sole purpose of protecting the
+integrity of the free software distribution system, which is
+implemented by public license practices.  Many people have made
+generous contributions to the wide range of software distributed
+through that system in reliance on consistent application of that
+system; it is up to the author/donor to decide if he or she is willing
+to distribute software through any other system and a licensee cannot
+impose that choice.
+
+This section is intended to make thoroughly clear what is believed to
+be a consequence of the rest of this License.
+
+  8. If the distribution and/or use of the Program is restricted in
+certain countries either by patents or by copyrighted interfaces, the
+original copyright holder who places the Program under this License
+may add an explicit geographical distribution limitation excluding
+those countries, so that distribution is permitted only in or among
+countries not thus excluded.  In such case, this License incorporates
+the limitation as if written in the body of this License.
+
+  9. The Free Software Foundation may publish revised and/or new versions
+of the General Public License from time to time.  Such new versions will
+be similar in spirit to the present version, but may differ in detail to
+address new problems or concerns.
+
+Each version is given a distinguishing version number.  If the Program
+specifies a version number of this License which applies to it and "any
+later version", you have the option of following the terms and conditions
+either of that version or of any later version published by the Free
+Software Foundation.  If the Program does not specify a version number of
+this License, you may choose any version ever published by the Free Software
+Foundation.
+
+  10. If you wish to incorporate parts of the Program into other free
+programs whose distribution conditions are different, write to the author
+to ask for permission.  For software which is copyrighted by the Free
+Software Foundation, write to the Free Software Foundation; we sometimes
+make exceptions for this.  Our decision will be guided by the two goals
+of preserving the free status of all derivatives of our free software and
+of promoting the sharing and reuse of software generally.
+
+			    NO WARRANTY
+
+  11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
+FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT WHEN
+OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
+PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
+OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS
+TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE
+PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
+REPAIR OR CORRECTION.
+
+  12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
+WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
+REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
+INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
+OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
+TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
+YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
+PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGES.
+
+		     END OF TERMS AND CONDITIONS
+
+	    How to Apply These Terms to Your New Programs
+
+  If you develop a new program, and you want it to be of the greatest
+possible use to the public, the best way to achieve this is to make it
+free software which everyone can redistribute and change under these terms.
+
+  To do so, attach the following notices to the program.  It is safest
+to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least
+the "copyright" line and a pointer to where the full notice is found.
+
+    <one line to give the program's name and a brief idea of what it does.>
+    Copyright (C) 19yy  <name of author>
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program; if not, write to the Free Software
+    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+
+Also add information on how to contact you by electronic and paper mail.
+
+If the program is interactive, make it output a short notice like this
+when it starts in an interactive mode:
+
+    Gnomovision version 69, Copyright (C) 19yy name of author
+    Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
+    This is free software, and you are welcome to redistribute it
+    under certain conditions; type `show c' for details.
+
+The hypothetical commands `show w' and `show c' should show the appropriate
+parts of the General Public License.  Of course, the commands you use may
+be called something other than `show w' and `show c'; they could even be
+mouse-clicks or menu items--whatever suits your program.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the program, if
+necessary.  Here is a sample; alter the names:
+
+  Yoyodyne, Inc., hereby disclaims all copyright interest in the program
+  `Gnomovision' (which makes passes at compilers) written by James Hacker.
+
+  <signature of Ty Coon>, 1 April 1989
+  Ty Coon, President of Vice
+
+This General Public License does not permit incorporating your program into
+proprietary programs.  If your program is a subroutine library, you may
+consider it more useful to permit linking proprietary applications with the
+library.  If this is what you want to do, use the GNU Library General
+Public License instead of this License.
+3.0.2: (2009-07-25):
+    - eliminated several warnings in latest gcc's - signed vs. unsigned char
+    pointer, and too large integer constants.
+
+3.0.1:
+    - First release by Shlomi Fish.
+    - Converted to CMake and got the build to work flawlessly.

patsolve/Common.cmake

+include(CheckIncludeFile)
+include(CheckIncludeFiles)
+include(CheckFunctionExists)
+include(FindPerl)
+IF (NOT PERL_FOUND)
+    MESSAGE ( FATAL_ERROR "perl must be installed")
+ENDIF(NOT PERL_FOUND)
+
+# Taken from http://www.cmake.org/pipermail/cmake/2007-March/013060.html
+MACRO(REPLACE_FUNCTIONS sources)
+  FOREACH(name ${ARGN})
+    STRING(TOUPPER have_${name} SYMBOL_NAME)
+    CHECK_FUNCTION_EXISTS(${name} ${SYMBOL_NAME})
+    IF(NOT ${SYMBOL_NAME})
+      SET(${sources} ${${sources}} ${name}.c)
+    ENDIF(NOT ${SYMBOL_NAME})
+  ENDFOREACH(name)
+ENDMACRO(REPLACE_FUNCTIONS)
+
+MACRO(CHECK_MULTI_INCLUDE_FILES)
+  FOREACH(name ${ARGN})
+    STRING(TOUPPER have_${name} SYMBOL_NAME)
+    STRING(REGEX REPLACE "\\." "_" SYMBOL_NAME ${SYMBOL_NAME})
+    STRING(REGEX REPLACE "/" "_" SYMBOL_NAME ${SYMBOL_NAME})
+    CHECK_INCLUDE_FILE(${name} ${SYMBOL_NAME})
+  ENDFOREACH(name)
+ENDMACRO(CHECK_MULTI_INCLUDE_FILES)
+
+MACRO(CHECK_MULTI_FUNCTIONS_EXISTS)
+  FOREACH(name ${ARGN})
+    STRING(TOUPPER have_${name} SYMBOL_NAME)
+    CHECK_FUNCTION_EXISTS(${name} ${SYMBOL_NAME})
+  ENDFOREACH(name)
+ENDMACRO(CHECK_MULTI_FUNCTIONS_EXISTS)
+
+MACRO(PREPROCESS_PATH_PERL SOURCE DEST)
+    SET(PATH_PERL ${PERL_EXECUTABLE})
+    ADD_CUSTOM_COMMAND(
+        OUTPUT ${DEST}
+        COMMAND ${PATH_PERL}
+        ARGS "-e"
+        "open I, qq{<\$ARGV[0]}; open O, qq{>\$ARGV[1]}; while(<I>){s{\\@PATH_PERL\\@}{\$ARGV[2]}g;print O \$_;} close(I); close(O);"
+        ${SOURCE}
+        ${DEST}
+        ${PATH_PERL}
+        COMMAND chmod ARGS "a+x" ${DEST}
+        DEPENDS ${SOURCE}
+        VERBATIM
+    )
+    # The custom command needs to be assigned to a target.
+    ADD_CUSTOM_TARGET(
+        process_perl ALL
+        DEPENDS ${DEST}
+    )
+ENDMACRO(PREPROCESS_PATH_PERL)
+
+MACRO(RUN_POD2MAN SOURCE DEST SECTION CENTER RELEASE)
+    SET(PATH_PERL ${PERL_EXECUTABLE})
+    ADD_CUSTOM_COMMAND(
+        OUTPUT ${DEST}
+        COMMAND ${PATH_PERL}
+        ARGS "-e"
+        "my (\$src, \$dest, \$sect, \$center, \$release) = @ARGV; my \$pod = qq{Hoola.pod}; use File::Copy; copy(\$src, \$pod); system(qq{pod2man --section=\$sect --center=\"\$center\" --release=\"\$release\" \$pod > \$dest}); unlink(\$pod)"
+        ${SOURCE}
+        ${DEST}
+        ${SECTION}
+        "${CENTER}"
+        "${RELEASE}"
+        MAIN_DEPENDENCY ${SOURCE}
+        VERBATIM
+    )
+    ADD_CUSTOM_TARGET(
+        POD_${DEST} ALL
+        DEPENDS ${DEST}
+    )
+ENDMACRO(RUN_POD2MAN)
+
+MACRO(CHOMP VAR)
+    STRING(REGEX REPLACE "[\r\n]+$" "" ${VAR} "${${VAR}}")
+ENDMACRO(CHOMP)
+
+MACRO(INSTALL_MAN SOURCE SECTION)
+    INSTALL(
+        FILES
+            ${SOURCE}
+        DESTINATION
+            "share/man/man${SECTION}"
+   )
+ENDMACRO(INSTALL_MAN)
+
+
+# Configure paths.
+SET (DATADIR "${CMAKE_INSTALL_PREFIX}/share"
+    CACHE PATH "The data dir"
+)
+
+SET (PKGDATADIR "${DATADIR}/freecell-solver")

patsolve/Makefile.win32

+all: patsolve.exe
+
+CC = cl
+OFLAGS = /Og2 /DWIN32
+INCLUDES = config.h pat.h tree.h util.h param.h fnv.h
+OBJECTS = patmain.obj param.obj pat.obj patsolve.obj tree.obj util.obj msdealsub.obj
+
+patmain.obj: patmain.c $(INCLUDES)
+	$(CC) /c /Fopatmain.obj $(OFLAGS) patmain.c
+
+param.obj: param.c $(INCLUDES)
+	$(CC) /c /Foparam.obj $(OFLAGS) param.c
+
+pat.obj: pat.c $(INCLUDES)
+	$(CC) /c /Fopat.obj $(OFLAGS) pat.c
+
+patsolve.obj: patsolve.c $(INCLUDES)
+	$(CC) /c /Fopatsolve.obj $(OFLAGS) patsolve.c
+
+tree.obj: tree.c $(INCLUDES)
+	$(CC) /c /Fotree.obj $(OFLAGS) tree.c
+
+util.obj: util.c $(INCLUDES)
+	$(CC) /c /Foutil.obj $(OFLAGS) util.c
+
+msdealsub.obj: msdealsub.c $(INCLUDES)
+	$(CC) /c /Fomsdealsub.obj $(OFLAGS) msdealsub.c
+
+patsolve.exe: $(OBJECTS)
+	$(CC) /Fepatsolve.exe $(OBJECTS)
+

patsolve/Manifest

+COPYING                 GPL version 2
+Makefile
+Makefile.win32
+Parameters              some notes on weighting parameters
+README
+check_layout            sh script for error-checking layout files
+config.h
+convert_layout          tcl script that converts patience-1.9 files
+convert_tower           same but for a PalmOS version
+convert_vert            same for hands laid out vertically
+fnv.h
+ga/                     genetic algorithm code used to find parameter sets
+msdeal.c                shuffling code from MS Freecell
+msdeal.unsolve          list of unsolvable -f mode games
+msdealsub.c
+param.c
+param.dat               result of GA runs
+param.h
+param.py                creates param.[ch] from param.dat
+pat.c
+pat.h
+patience-1.9.patch      patch to make patience-1.9 dump hands
+patmain.c
+patsolve.c
+patsolve.exe            MS Windows PE 32-bit Intel 80386 console executable
+tree.c
+tree.h
+util.c
+util.h
+xpat2-1.04.patch        patch to make xpat2 dump hands

patsolve/Parameters

+Special Freecell Automove rule:
+
+Sometimes, we don't want to take a card out, even though we can.  For
+example, if this is the 3S, and either the 2D or 2H are still around, then
+the 3S could be considered active.  There are two rules that have been
+proposed, Horne's and Raymond's.  We use the latter, since it has better
+average performance.
+
+Horne: All 'A's play home immediately, all '2's play home if the same-suit
+'A' is already there, an 'N' plays home if the same-suit 'N-1' and both
+'N-1's of the opposite color are already home.
+
+Raymond:
+N plays home if:
+same-suit N-1 is already home
+AND
+{both opposite-color (N-1)s are already home
+ OR
+ {both opposite-color (N-2)s are already home
+  AND
+  same-color other-suit (N-3) is already home}
+}
+
+Horne's rule:
+	if (!Same_suit) {
+		for (i = 1 - (o & 1); i < 4; i += 2) {
+			if (O[i] < rank(card) - 1) {
+				w_can_out[w] = 0;
+				break;
+			}
+		}
+	}
+
+Xparam[]
+0       removing a card from a pile containing a needed card
+1       additional priority if the needed card is being uncovered
+2       penalty for covering a needed card
+3       W -> empty W
+4       W -> non-empty W
+5       T -> non-empty W
+6       T -> empty W
+7       W -> T
+8       irreducible move
+9       boolean; negative => newer piles first
+
+Some possible additional parameters (from Atkinson and Holstege's paper):
+king from either T or W -> empty W (in both -k and -a variants)
+	(while W -> empty W might have a negative weight, this could
+	be positive; it might help in some cases)
+king -> non-empty W
+removing a card from a column with one card in it
+Solve patience games -- by Dr. Tom <tomh@po.crl.go.jp>
+
+Patsolve is a hybrid DFS/BFS/prioritized-queue search in which moves are
+weighted using a set of parameters according to which game mode you choose.
+
+There are two basic modes, the default "best solution" and "speed mode".
+Speed mode (obtained with the -S flag) is fast but produces highly
+non-optimal solutions.  It is mostly useful for answering the question "is
+there a solution?".  In the default (non -S) mode, solutions are optimized
+to be as short as possible, moving single cards at a time (not stacks).
+
+This version does a kind of round-robin prioritized queue, so low priority
+positions still get some attention (they sometimes lead to better
+solutions).  Thus it is not guaranteed to find the optimal solution, but it
+will find much better solutions than the -S mode.
+
+In either mode, Patsolve can play Seahaven or Freecell, with different
+numbers of work and temp piles.  The default is Freecell with 8 work piles
+and 4 temp cells (the default can be changed, see the Makefile).
+
+The result is left in the file "win" if the game is solvable.
+
+Usage: patsolve [-s|f] [-k|a] [-w<n>] [-t<n>] [-E] [-S] [-q|v] [layout]
+-s Seahaven (same suit), -f Freecell (red/black)
+-k only Kings start a pile, -a any card starts a pile
+-w<n> number of work piles, -t<n> number of free cells
+-E don't exit after one solution; continue looking for better ones
+-S speed mode; find a solution quickly, rather than a good solution
+-q quiet, -v verbose
+-s implies -aw10 -t4, -f implies -aw8 -t4
+
+A layout file looks like this (the famous unsolvable Freecell game #11982):
+
+AH 3D KD JC 6C JD KC
+AS 3H 6H 5D 2C 7D 8D
+4H QS 5S 5C TH 8H 2S
+AC QC 4D 8C QH 9C 3S
+2D 8S 9H 9D 6D 2H
+6S 7H JH TD TC QD
+TS AD 9S KH 4S 4C
+JS KS 3C 7C 7S 5H
+
+The work piles go from left to right, bottom card to visible card.  Thus the
+AH is buried, and the KC is available for movement.
+
+If there is one more line in the layout file than the number of work piles,
+those cards are pre-loaded into the temp cells, so for example a Seahaven
+game with 10 piles looks like this:
+
+4d 5c 4s 6h tc
+td as ks 7h 8d
+qs 7c jc 4h kc
+jd 5s 8s 7d 9h
+6d ah qd 2h 2d
+8h ts th kd 4c
+ad 9d 6c qh js
+2c 3c jh 9s 8c
+ac 6s 7s 3h 5d
+kh 9c qc 3s 2s
+5h 3d
+
+The 5H and 3D are loaded into two of the four temp cells (either upper or
+lower case may be used).  A further line gets loaded into the home cells.
+
+Patches to Xpat2 1.04 and Patience-1.9 are included that dump hands
+in useful formats (you also need convert_layout for Patience-1.9).
+
+In -E mode the program will continue until it runs out of memory.
+
+Additional undocumented flags:
+-M<meg> controls the amount of memory used, default 50 meg.
+-X, -Y set weights for moves, see Parameters.
+-P pick a non-default parameter set, see Parameters and param.h.
+-c<n> another parameter, BFS/DFS cutoff
+-N<start> <end> range solving mode
+
+e.g., "patsolve -fS -M20 -N0 1000" plays the first 1000 games using the
+MS Freecell numbering in speed mode with a 20 meg limit.
+
+Dr. Tom
+July 4, 1998
+Tsukuba, Japan
+Updated November 23, 2000
+Kobe, Japan
+Updated February 27, 2002
+Kobe, Japan

patsolve/check_layout

+#! /bin/sh
+
+# make sure a layout file has all the cards and no more
+
+x=/tmp/$$
+rm -f $x
+
+tr ' ' '\012' < "$1" | tr '[A-Z]' '[a-z]' | sort > $x
+
+diff $x - <<+
+2c
+2d
+2h
+2s
+3c
+3d
+3h
+3s
+4c
+4d
+4h
+4s
+5c
+5d
+5h
+5s
+6c
+6d
+6h
+6s
+7c
+7d
+7h
+7s
+8c
+8d
+8h
+8s
+9c
+9d
+9h
+9s
+ac
+ad
+ah
+as
+jc
+jd
+jh
+js
+kc
+kd
+kh
+ks
+qc
+qd
+qh
+qs
+tc
+td
+th
+ts
++
+
+rm -f $x

patsolve/config.h

+/* Patsolve can be configured to solve a variety of games.  The default here
+is Seahaven (same suit, not red-black-red-black) with any card allowed on
+empty work piles.  Define SAME_SUIT=0 for Freecell, and define KING_ONLY=1
+to only allow kings on empty work piles (see the Makefile). */
+
+#ifndef CONFIG_H
+#define CONFIG_H
+
+#ifndef SAME_SUIT
+#define SAME_SUIT 1
+#endif
+#ifndef KING_ONLY
+#define KING_ONLY 0
+#endif
+
+#ifndef NWPILES
+#define NWPILES 10      /* number of W piles */
+#endif
+#ifndef NTPILES
+#define NTPILES 4       /* number of T cells */
+#endif
+
+#ifdef __GNUC__
+#define INLINE inline
+#else
+#define INLINE
+#endif
+
+#define DEBUG 0
+
+#ifdef WIN32
+typedef unsigned char u_char;
+typedef unsigned __int64 u_int64_t;
+typedef unsigned __int32 u_int32_t;
+#endif
+
+#endif

patsolve/convert_layout

+#! /usr/bin/env tcl
+
+# read the position information dumped from patience-1.9
+# 10 work piles, 2 temp
+
+set hand [read [open "/tmp/hand" "r"]]
+
+proc formatcard {c} {
+	set rank [string range $c 0 0]
+	set suit [string range $c 1 1]
+	if {$rank == "0"} {set rank "t"}
+	if {$rank == "b"} {set rank "j"}
+	if {$rank == "d"} {set rank "q"}
+	if {$suit == "c"} {set suit "d"}
+	if {$suit == "k"} {set suit "c"}
+	if {$suit == "p"} {set suit "s"}
+	return "$rank$suit"
+}
+
+set npiles 10
+#set npiles 8
+
+for {set pile 0} {$pile < $npiles} {incr pile} {
+	set p ""
+	set ncards 5
+#        if {$pile < 4} {
+#                set ncards 7
+#        } else {
+#                set ncards 6
+#        }
+
+	for {set card 0} {$card < $ncards} {incr card} {
+		set idx [expr {51 - $pile - $card * $npiles}]
+		set c [lindex $hand $idx]
+		append p [formatcard $c]
+		if {$card != [expr {$ncards - 1}]} {
+			append p " "
+		}
+	}
+	echo $p
+}
+
+# Temp cells:
+set p "[formatcard [lindex $hand 0]] "
+append p [formatcard [lindex $hand 1]]
+echo $p
+

patsolve/convert_tower

+#! /usr/bin/env tcl
+
+# Read the position information dumped from PalmOS Patience/Tower games.
+# 2 temp, 10 work piles
+
+#system {pilot-xfer -f PatGame}
+system {dd if=PatGame.pdb bs=88 skip=1 of=/tmp/moo}
+set hand [read [open "/tmp/moo" "r"]]
+
+set npiles 10
+
+for {set pile 0} {$pile < $npiles} {incr pile} {
+	set p ""
+	set ncards 5
+	for {set card 0} {$card < $ncards} {incr card} {
+		set idx [expr {$card + $pile * $ncards + 2}]
+		set c [lindex $hand $idx]
+		append p $c
+		if {$card != [expr {$ncards - 1}]} {
+			append p " "
+		}
+	}
+	echo $p
+}
+
+# Temp cells:
+set p "[lindex $hand 0] "
+append p [lindex $hand 1]
+echo $p
+

patsolve/convert_vert

+#! /usr/bin/env tcl
+
+# Read positions in vertical column mode
+
+set hand [read [open [lindex $argv 0] "r"]]
+
+set npiles 8
+
+set n 0
+foreach card $hand {
+	lappend pile($n) $card
+	set n [expr {($n + 1) % $npiles}]
+}
+
+for {set n 0} {$n < $npiles} {incr n} {
+	echo $pile($n)
+}

patsolve/dondorf-king.bmp

Added
New image

patsolve/fc-solve.ico

Added
New image
+/* This is a 32 bit FNV hash.  For more information, see
+http://www.isthe.com/chongo/tech/comp/fnv/index.html */
+
+#ifndef FNV_H
+#define FNV_H
+
+#include <sys/types.h>
+#include "config.h"
+
+#define FNV1_32_INIT 0x811C9DC5
+#define FNV_32_PRIME 0x01000193
+
+#define fnv_hash(x, hash) (((hash) * FNV_32_PRIME) ^ (x))
+
+/* Hash a buffer. */
+
+static INLINE u_int32_t fnv_hash_buf(u_char *s, int len)
+{
+	int i;
+	u_int32_t h;
+
+	h = FNV1_32_INIT;
+	for (i = 0; i < len; i++) {
+		h = fnv_hash(*s++, h);
+	}
+
+	return h;
+}
+
+/* Hash a 0 terminated string. */
+
+static INLINE u_int32_t fnv_hash_str(u_char *s)
+{
+	u_int32_t h;
+
+	h = FNV1_32_INIT;
+	while (*s) {
+		h = fnv_hash(*s++, h);
+	}
+
+	return h;
+}
+
+#endif

patsolve/ga/README

+This isn't quite all here, there's also some code you need to find the
+-Y parameters.  I can't distribute that code for license reasons but
+you can easily solve the equation yourself.  The "move squashing" function
+is a cubic given by three values at 0, 25, and 50; the -Y flag takes the
+coefficients a, b, and c for the equation a * x * x + b * x + c.  Email
+me if you want to know more.  Other bits of ga.py are fairly easy to
+figure out.  Note that actually running this program to generate a new
+set of parameters takes days or even weeks.  I can generate parameters on
+request, too.

patsolve/ga/findfit.py

+#! /usr/bin/env python
+
+import sys, re, string
+from util import *
+
+usage("""[-n <n>] filename ...""")
+
+N = 10
+
+optlist, args = parseargs("n:")
+
+for opt, arg in optlist:
+	if opt == '-n':
+		N = int(arg)
+
+if len(args) < 1:
+	printusage()
+	sys.exit(1)
+
+parse = re.compile(r"running (.*) fitness = ([-+0-9.e]+)")
+
+def sgn(x):
+	if x < 0: return -1
+	return 1
+
+fit = {}
+
+for filename in args:
+	f = open(filename, 'r')
+	for line in f.xreadlines():
+		p = parse.match(line)
+		if p:
+			s = string.split(p.group(1))
+			s[11] = str(sgn(int(s[11])))
+			s = string.join(s)
+			if fit.has_key(s):
+				fit[s].append(float(p.group(2)))
+			else:
+				fit[s] = [float(p.group(2))]
+	f.close()
+
+def add(a, b):
+	return a + b
+
+m = []
+
+for id in fit.keys():
+	l = fit[id]
+	avg = reduce(add, l, 0) / float(len(l))
+	m.append((avg, id, len(l)))
+
+m.sort(lambda x, y: sgn(x[0] - y[0]))
+#m.sort(lambda x, y: sgn(y[2] - x[2]))
+for i in xrange(N):
+	print m[i][1], 'fitness =', m[i][0], '(%d)' % m[i][2]

patsolve/ga/ga.py

+#! /usr/bin/env python
+
+import sys, os, time, string, re, rng
+from rng import torat
+from util import *
+
+usage("[-c crossprob] [-m mutateprob] [-n Npop] [-l #games] [pop]")
+
+crossprob = .1
+mutateprob = .1
+Npop = 100
+Start = 0
+Len = 20
+Gen = 0
+Opts = '-skS -M20'
+Mem = 10 * 1000 * 1000
+
+optlist, args = parseargs("c:m:n:l:")
+
+for opt, arg in optlist:
+	if opt == '-c':
+		crossprob = float(arg)
+	elif opt == '-m':
+		mutateprob = float(arg)
+	elif opt == '-n':
+		Npop = int(arg)
+	elif opt == '-l':
+		Len = int(arg)
+
+if len(args) > 1:
+	printusage()
+	sys.exit(1)
+
+seed = int((time.time() * 10000.) % (1<<30))
+rng.seed(seed)
+
+def mutate(l, p):
+	"""mutate(list, probability) -> list
+
+	Given a list of integers and a mutation probability, mutate the list
+	by either adding or subtracting from some of the elements.  The
+	mutated list is returned."""
+
+	(p, q) = torat(p)
+	m = [1] * 24 + [2] * 12 + [3] * 6 + [4] * 3 + [5] * 2 + [6] * 1
+	def flip(x, p = p, q = q, m = m):
+		if rng.flip(p, q):
+			y = m[rng.random() % len(m)]
+			if rng.flip(1, 2):
+				return x + y
+			return x - y
+		return x
+
+	return map(flip, l)
+
+def cross(l1, l2, p):
+	"""cross(list, list, probability) -> list
+
+	Take elements from one list until a crossover is made, then take
+	elements from the other list, and so on, with the given probability
+	of a crossover at each position.  The initial list is chosen at
+	random from one of the two lists with equal probability.  The lists
+	must be the same length."""
+
+	l = [0] * len(l1)
+	x = map(None, l1, l2)
+	j = rng.random() % 2
+	(p, q) = torat(p)
+	for i in xrange(len(l1)):
+		if rng.flip(p, q):
+			j = 1 - j
+		l[i] = x[i][j]
+
+	return l
+
+def breed(l1, l2):
+	"""breed(list, list) -> list
+
+	Given two individuals, cross them and mutate the result."""
+
+	return mutate(cross(l1, l2, crossprob), mutateprob)
+
+def initpop(nl = None):
+	"""The initial population is a list of length Npop of lists of
+	length Nparam."""
+
+	global Npop, Nparam
+
+	if nl:
+		l = []
+		f = open(nl[0], 'r')
+		for s in f.readlines():
+			if s[0] != '#':
+				m = map(int, string.split(s))
+				l.append(m)
+		f.close()
+		Npop = len(l)
+		Nparam = len(l[0])
+	else:
+		oldcanon = [5, 4, 6, 0, 0, 0, 0, 0, 0, 0, 1, 3, 0, 1]
+		canon0 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
+		canon1 = [2, 6, 2, 0, -5, -9, -5, -11, 3, 1, -5, 2, 2, 0]
+		canon2 = [1, 1, 6, -2, -1, -2, -2, -3, 0, -1, 2, 4, 6, 1]
+		Nparam = len(canon1)
+		l = [breed(canon1, canon2) for x in xrange(Npop)]
+#                l = [mutate(canon0, .9) for x in xrange(Npop)]
+
+	return l
+
+def newpop(result):
+	"""The result of a generation is a list of pairs, where each
+	pair consists of the fitness value and the individual that
+	generated it.  Construct a new population (formatted as a
+	list of lists) using the following steps:
+		1. Sort by the fitness value (smallest first).
+		2. Replace the last half of the sorted population with
+		   new individuals bred from pairs chosen at random
+		   from the first half.
+	The new population is returned."""
+
+	result.sort()
+	printf('%d: %g, %s\n', Gen, result[0][0], result[0][1])
+	pop = [0] * Npop
+	cut = int(Npop * .5)
+	for i in xrange(cut):
+		pop[i] = result[i][1]
+	for i in xrange(cut, Npop):
+		a = rng.random() % cut
+		b = rng.random() % cut
+		pop[i] = breed(result[a][1], result[b][1])
+
+	return pop
+
+def sgn(x):
+	if x < 0: return -1
+	return 1
+
+def refill(pop):
+	"""Get rid of duplicates."""
+
+	for l in pop:
+		l[9] = sgn(l[9])
+		l[-1] = abs(l[-1])
+	pop.sort()
+
+	newpop = [0] * Npop
+	i = 0
+	last = None
+	for l in pop:
+		if l != last:
+			newpop[i] = l
+			i += 1
+		last = l
+	for j in xrange(i, Npop):
+		a = rng.random() % i
+		b = rng.random() % i
+		newpop[j] = breed(newpop[a], newpop[b])
+
+	return newpop
+
+def run(pop):
+	"""Test each member of the population and save it with its
+	fitness value."""
+
+	result = [0] * Npop
+	i = 0
+	for l in pop:
+		result[i] = (fitness(l), l)
+		i += 1
+
+	return result
+
+def get_ycoeff(l):
+	"""Find the quadratic through (0, l[0]), (25, l[1]), and (50, l[2]).
+	Return the coefficients as a string, e.g., '.5 1.2 2.'"""
+
+	f = open('/tmp/x', 'w')
+	fprintf(f, '0 %d\n', l[0])
+	fprintf(f, '25 %d\n', l[1])
+	fprintf(f, '50 %d\n', l[2])
+	f.close()
+	os.system('fit/dofit /tmp/x > /tmp/coeff')
+	f = open('/tmp/coeff', 'r')
+	l = f.readlines()
+	f.close()
+	return string.join(map(str, map(float, l)))
+
+move = re.compile(r"([0-9]+) moves.")
+pos = re.compile(r"([0-9]+) positions generated.")
+upos = re.compile(r"([0-9]+) unique positions.")
+memrem = re.compile(r"Mem_remain = ([0-9]+)")
+malloc = re.compile(r".*memory.*")
+
+def fitness(l):
+	"""Run the individual and return the fitness value."""
+
+	nx = Nparam - 4
+	param = '-c%d ' % (abs(l[-1]) + 1)
+	param += '-X%d %s ' % (nx, string.join(map(str, l[:nx])))
+	s = get_ycoeff(l[-4:-1])
+	param += '-Y %s' % s
+	resname = 'res'
+
+	cmd = '/home/tomh/src/patsolve/xpatsolve %s -N%d %d %s > %s'
+	cmd %= (Opts, Start, Start + Len, param, resname)
+
+	printf('running %s ', param)
+	sys.stdout.flush()
+	t0 = os.times()[2]
+	os.system(cmd)
+	t1 = os.times()[2]
+
+	f = open(resname, 'r')
+	sum = 0
+	n = 0
+	mem = 0
+	for s in f.xreadlines():
+		x = move.findall(s)
+#                x = pos.findall(s)
+#                x = memrem.findall(s)
+		if x:
+			m = int(x[-1])
+			sum += m
+			n += 1
+		elif malloc.match(s):
+			sum += 1000
+			mem += 1
+			n += 1
+	f.close()
+
+	if n == 0:
+		printf('no result\n')
+		return 1000000
+#        fit = Mem - float(sum) / n
+#        fit = float(sum) / n
+	fit = (t1 - t0) / Len
+	if mem > 0:
+		printf('fitness = %g, oom = %d\n', fit, mem)
+	else:
+		printf('fitness = %g\n', fit)
+	return fit
+
+def ga():
+	"""Run the GA over many generations."""
+
+	global Start, Gen
+
+	pop = initpop(args)
+	while 1:
+		f = open('curpop', 'w')
+		fprintf(f, '# %s\n', Opts)
+		for l in pop:
+			fprintf(f, '%s\n', string.join(map(str, l)))
+		f.close()
+		pop = refill(pop)
+		result = run(pop)
+		pop = newpop(result)
+#                Start = Start + Len
+		Start = rng.random() % 1000000000
+		Gen += 1
+
+ga()

patsolve/ga/mt19937.c

+/* This is the ``Mersenne Twister'' random number generator MT19937, which
+generates pseudorandom integers uniformly distributed in 0..(2^32 - 1)
+starting from any odd seed in 0..(2^32 - 1).  This version is a recode by
+Shawn Cokus (Cokus@math.washington.edu) on March 8, 1998 of a version by
+Takuji Nishimura (who had suggestions from Topher Cooper and Marc Rieffel in
+July-August 1997).
+
+Effectiveness of the recoding (on Goedel2.math.washington.edu, a DEC Alpha
+running OSF/1) using GCC -O3 as a compiler: before recoding: 51.6 sec. to
+generate 300 million random numbers; after recoding: 24.0 sec. for the same
+(i.e., 46.5% of original time), so speed is now about 12.5 million random
+number generations per second on this machine.
+
+According to the URL <http://www.math.keio.ac.jp/~matumoto/emt.html> (and
+paraphrasing a bit in places), the Mersenne Twister is ``designed with
+consideration of the flaws of various existing generators,'' has a period of
+2^19937 - 1, gives a sequence that is 623-dimensionally equidistributed, and
+``has passed many stringent tests, including the die-hard test of G.
+Marsaglia and the load test of P. Hellekalek and S. Wegenkittl.'' It is
+efficient in memory usage (typically using 2506 to 5012 bytes of static
+data, depending on data type sizes, and the code is quite short as well).
+It generates random numbers in batches of 624 at a time, so the caching and
+pipelining of modern systems is exploited.  It is also divide- and mod-free.
+
+This library is free software; you can redistribute it and/or modify it
+under the terms of the GNU Library General Public License as published by
+the Free Software Foundation (either version 2 of the License or, at your
+option, any later version).  This library is distributed in the hope that it
+will be useful, but WITHOUT ANY WARRANTY, without even the implied warranty
+of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library
+General Public License for more details.  You should have received a copy of
+the GNU Library General Public License along with this library; if not,
+write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
+Boston, MA 02111-1307, USA.
+
+The code as Shawn received it included the following notice:
+
+  Copyright (C) 1997 Makoto Matsumoto and Takuji Nishimura.  When you use
+  this, send an e-mail to <matumoto@math.keio.ac.jp> with an appropriate
+  reference to your work.
+
+It would be nice to CC: <Cokus@math.washington.edu> when you write. */
+
+/* uint32 must be an unsigned integer type capable of holding at least 32
+bits; exactly 32 should be fastest, but 64 is better on an Alpha with GCC at
+-O3 optimization so try your options and see what's best for you. */
+
+typedef unsigned long uint32;
+
+#define N             (624)                /* length of state vector */
+#define M             (397)                /* a period parameter */
+#define L             (N-M+1)
+#define K1            (0x9908B0DFU)        /* magic constants */
+#define K2            (0x9D2C5680U)
+#define K3            (0xEFC60000U)
+#define hiBit(u)      ((u) & 0x80000000U)  /* mask all but highest   bit of u */
+#define loBit(u)      ((u) & 0x00000001U)  /* mask all but lowest    bit of u */
+#define loBits(u)     ((u) & 0x7FFFFFFFU)  /* mask     the highest   bit of u */
+#define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */
+
+static uint32 state[N+1];   /* state vector + 1 extra to not violate ANSI C */
+static uint32 *next;        /* next random value is computed from here */
+static int left = -1;       /* can *next++ this many times before reloading */
+
+/* We initialize state[0..(N-1)] via the generator
+
+  x_new = (69069 * x_old) mod 2^32
+
+from Line 15 of Table 1, p. 106, Sec. 3.3.4 of Knuth's
+_The Art of Computer Programming_, Volume 2, 3rd ed.
+
+Notes (SJC): I do not know what the initial state requirements
+of the Mersenne Twister are, but it seems this seeding generator
+could be better.  It achieves the maximum period for its modulus
+(2^30) iff x_initial is odd (p. 20-21, Sec. 3.2.1.2, Knuth); if
+x_initial can be even, you have sequences like 0, 0, 0, ...;
+2^31, 2^31, 2^31, ...; 2^30, 2^30, 2^30, ...; 2^29, 2^29 + 2^31,
+2^29, 2^29 + 2^31, ..., etc. so I force seed to be odd below.
+
+Even if x_initial is odd, if x_initial is 1 mod 4 then
+
+  the          lowest bit of x is always 1,
+  the  next-to-lowest bit of x is always 0,
+  the 2nd-from-lowest bit of x alternates      ... 0 1 0 1 0 1 0 1 ...,
+  the 3rd-from-lowest bit of x 4-cycles        ... 0 1 1 0 0 1 1 0 ...,
+  the 4th-from-lowest bit of x has the 8-cycle ... 0 0 0 1 1 1 1 0 ...,
+  ...
+
+and if x_initial is 3 mod 4 then
+
+  the          lowest bit of x is always 1,
+  the  next-to-lowest bit of x is always 1,
+  the 2nd-from-lowest bit of x alternates      ... 0 1 0 1 0 1 0 1 ...,
+  the 3rd-from-lowest bit of x 4-cycles        ... 0 0 1 1 0 0 1 1 ...,
+  the 4th-from-lowest bit of x has the 8-cycle ... 0 0 1 1 1 1 0 0 ...,
+  ...
+
+The generator's potency (min. s>=0 with (69069-1)^s = 0 mod 2^32) is
+16, which seems to be alright by p. 25, Sec. 3.2.1.3 of Knuth.  It
+also does well in the dimension 2..5 spectral tests, but it could be
+better in dimension 6 (Line 15, Table 1, p. 106, Sec. 3.3.4, Knuth).
+
+Note that the random number user does not see the values generated
+here directly since reloadMT() will always munge them first, so maybe
+none of all of this matters.  In fact, the seed values made here could
+even be extra-special desirable if the Mersenne Twister theory says
+so-- that's why the only change I made is to restrict to odd seeds. */
+
+void seedMT(uint32 seed)
+{
+	register uint32 x = (seed | 1U) & 0xFFFFFFFFU, *s = state;
+	register int j;
+
+	left = 0;
+	for (*s++ = x, j = N; --j; *s++ = (x *= 69069U) & 0xFFFFFFFFU) {
+	}
+}
+
+static uint32 reloadMT(void)
+{
+	register uint32 *p0 = state, *p2 = state + 2, *pM = state + M, s0, s1;
+	register int j;
+
+	left = N - 1;
+	next = state + 1;
+
+	for (s0 = state[0], s1 = state[1], j = L; --j; s0 = s1, s1 = *p2++) {
+		*p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K1 : 0U);
+	}
+	for (pM = state, j = M; --j; s0 = s1, s1 = *p2++) {
+		*p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K1 : 0U);
+	}
+	s1 = state[0];
+	*p0 = *pM ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K1 : 0U);
+
+	s1 ^= (s1 >> 11);
+	s1 ^= (s1 <<  7) & K2;
+	s1 ^= (s1 << 15) & K3;
+	return (s1 ^ (s1 >> 18));
+}
+
+uint32 randomMT(void)
+{
+	uint32 y;
+
+	if (--left < 0) {
+		return (reloadMT());
+	}
+	y  = *next++;
+	y ^= (y >> 11);
+	y ^= (y <<  7) & K2;
+	y ^= (y << 15) & K3;
+	return (y ^ (y >> 18));
+}

patsolve/ga/rng.i

+%module rng
+
+%include typemaps.i
+
+%typemap(python,out) unsigned long
+{
+	$target = PyLong_FromUnsignedLong($source);
+}
+
+%name(seed) extern void seedMT(unsigned long seed);
+%name(random) extern unsigned long randomMT(void);
+
+int flip(long p, long q);
+void torat(double x, long *T_OUTPUT, long *T_OUTPUT);
+
+%{
+
+static long gcd(long a, long b)
+{
+	long q;
+
+	while (b != 0) {
+		q = a % b;
+		a = b;
+		b = q;
+	}
+	return a;
+}
+
+void torat(double x, long *p, long *q)
+{
+	long i, g;
+	double f;
+
+	f = x;
+	i = 1;
+	while (i < (1<<30)) {
+		if (fabs(floor(f + .5) - f) < 1e-6) {
+			break;
+		}
+		f *= 10.;
+		i *= 10;
+	}
+	x *= i;
+	g = gcd((long)floor(x + .5), i);
+	*p = (long)floor(x / g + .5);
+	*q = (long)floor(i / g + .5);
+}
+
+/* Return true with probability p / q. */
+
+int flip(long p, long q)
+{
+	unsigned long r;
+
+	r = randomMT();
+	return (r % q) < p;
+}
+
+%}

patsolve/msdeal.c

+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/types.h>
+#include <string.h>
+
+typedef u_int64_t LONG;
+typedef void VOID;
+typedef u_int32_t UINT;
+typedef int CARD;
+
+#define NUM_CARDS 52
+
+LONG seedx;
+
+VOID srandp(UINT s)
+{
+	seedx = (LONG) s;
+}
+
+UINT randp()
+{
+	seedx = seedx * 214013L + 2531011L;
+	return (seedx >> 16) & 0xffff;
+}
+
+VOID srando(UINT s)
+{
+	seedx = (LONG) s;
+}
+
+UINT rando()
+{
+	seedx = seedx * 214013L + 2531011L;
+	return (seedx >> 16) & 0x7fff;
+}
+
+char Rank[] = "A23456789TJQK";
+char Suit[] = "CDHS";
+
+int Nwpiles = 8;
+
+int main(int argc, char **argv)
+{
+	int i, j, c;
+	int wLeft = NUM_CARDS;  // cards left to be chosen in shuffle
+	CARD deck[NUM_CARDS];
+	CARD pos[10][10];
+	LONG gnGameNumber;
+
+	if (argc > 2 && argv[1][0] == 's') {
+		Nwpiles = 10;
+		argv++;
+		argc--;
+	}
+
+	if (argc != 2) {
+		fprintf(stderr, "usage: %s number\n", argv[0]);
+		exit(1);
+	}
+	gnGameNumber = strtoul(argv[1], NULL, 10);
+
+	memset(pos, 0, sizeof(pos));
+	for (i = 0; i < NUM_CARDS; i++) {
+		deck[i] = i + 1;
+	}
+
+	if (gnGameNumber < 0x100000000) {
+		srando((UINT) gnGameNumber);
+	} else {
+		srandp((UINT) (gnGameNumber - 0x100000000));
+	}
+	for (i = 0; i < NUM_CARDS; i++) {
+		if (gnGameNumber < 0x100000000) {
+			if (gnGameNumber < 0x80000000) {
+				j = rando() % wLeft;
+			} else {
+				j = (rando() | 0x8000) % wLeft;
+			}
+		} else {
+			j = (randp() + 1) % wLeft;
+		}
+		pos[i % Nwpiles][i / Nwpiles] = deck[j];
+		deck[j] = deck[--wLeft];
+		if (Nwpiles == 10 && i == 49) {
+			break;
+		}
+	}
+	for (i = 0; i < Nwpiles; i++) {
+		j = 0;
+		while (pos[i][j]) {
+			c = pos[i][j] - 1;
+			j++;
+			printf("%c%c ", Rank[c / 4], Suit[c % 4]);
+		}
+		putchar('\n');
+	}
+	/* leftover cards to temp */
+	c = -1;
+	for (i = 0; i < 4; i++) {
+		if (wLeft) {
+			j = --wLeft;
+			c = deck[j] - 1;
+			printf("%c%c ", Rank[c / 4], Suit[c % 4]);
+		}
+	}
+	if (c >= 0) putchar('\n');
+	return 0;
+}

patsolve/msdeal.unsolve

+11982
+146692
+186216
+455889
+495505
+512118
+517776
+781948
+1155215
+1254900
+1387739
+1495908
+1573069
+1631319
+1633509
+1662054
+2022676
+2070322
+2166989
+2167029
+2501890
+2607073
+2681284
+2712622
+2843443
+2852003
+2855691
+2923820
+3163790
+3172889
+3194539
+3217820
+3225183
+3366617
+3376982
+3402716
+3576395
+3595299
+3878212
+3946538
+4055965
+4207758
+4266168
+4269635
+4324282
+4334954
+4440758
+4446355
+4765843
+4863685
+4910222
+5046726
+5050537
+5086829
+5225172
+5244797
+5260342
+5401675
+5478410
+5611185
+5672090
+5817697
+6020049
+6099064
+6100919
+6234527
+6314799
+6332629
+6416342
+6749792
+6761220
+6768658
+6844210
+6895558
+6898316
+7035805
+7261039
+7334559
+7360592
+7400819
+7484159
+7497878
+7530003
+7536454
+7801943
+7814345
+7825750
+7863486
+7887312
+7923001
+7965413
+8000527
+8046431
+8076134
+8104908
+8105324
+8114984
+8119415
+8121228
+8237732
+8267373
+8354257
+8381178
+8527378
+8608154
+8712426
+8719444
+8736337
+9093368
+9110337
+9190487
+9222830
+9262134
+9414989
+9415104
+9435589
+9452398
+9626317
+9647001
+9660366
+9747437
+9771903
+9830419
+9855268
+9861848
+9917279
+10049729
+10200611
+10285261
+10383596
+10408059
+10427651
+10639480
+10747405
+10784666
+10855026
+11021564
+11030426
+11091063
+11118676
+11234171
+11340468
+11455814
+11480555
+11507408
+11532111
+11554651
+11600582
+11713066
+11729265
+11731619
+11796771
+11817767
+11867940
+11953120
+11997207
+12160722
+12264257
+12343019
+12401544
+12421023
+12443641
+12462744
+12785719
+13039384
+13239798
+13350624
+13380013
+13391819
+13420011
+13465851
+13485071
+13551683
+13606290
+13715550
+13772241
+13802907
+13941273
+14194581
+14198031
+14451766
+14465585
+14468914
+14544794
+14640740
+14720822
+14762201
+14879662
+14921552
+15022364
+15109850
+15183326
+15268939
+15282983
+15427907
+15577175
+15641490
+15646459
+15652176
+15742683
+15931868
+15935472
+15953033
+15960435
+15995200
+16134792
+16166570
+16287335
+16325452
+16407856
+16428088
+16654990
+16720442
+16785765
+16845563
+16893049
+16912304
+16912539
+17100337
+17186505
+17325708
+17355981
+17359531
+17372524
+17408303
+17433814
+17557373
+17697137
+17813681
+17914625
+18002026
+18068249
+18112425
+18155239
+18202976
+18244527
+18247434
+18253970
+18341126
+18398657
+18449153
+18585679
+18667482
+18679314
+18739641
+18763252
+18863336
+18913979
+19141762
+19231085
+19231830
+19275361
+19324668
+19497549
+19617733
+19646464
+19719570
+19800050
+19840317
+19842962
+19875930
+19896595
+19984661
+20001314
+20071907
+20189056
+20320311
+20385961
+20406513
+20433342
+20518564
+20708407
+20793961
+20822616
+21129951
+21142208
+21222789
+21537381
+21805363
+21929423
+21942519
+22114810
+22163461
+22200703
+22201670
+22269191
+22422348
+22558888
+22696127
+22871243
+22916800
+22923064
+22934678
+23154641
+23475247
+23699849
+23759201
+23796844
+23859543
+23892853
+23904084
+24032064
+24121426
+24150534
+24155427
+24359967
+24389334
+24423283
+24485481
+24504750
+24555726
+24575738
+24626162
+24704507
+24878221

patsolve/msdealsub.c

+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/types.h>
+#include <string.h>
+
+#ifdef WIN32
+typedef void VOID;
+typedef unsigned __int64 LONG;
+typedef unsigned __int32 UINT;
+typedef int CARD;
+typedef unsigned char card_t;
+#else
+typedef void VOID;
+typedef u_int64_t LONG;
+typedef u_int32_t UINT;
+typedef int CARD;
+typedef u_char card_t;
+#endif
+
+#define NUM_CARDS 52
+
+static LONG seedx;
+
+static VOID srandp(UINT s)
+{
+	seedx = (LONG) s;
+}
+
+static UINT randp()
+{
+	seedx = seedx * 214013L + 2531011L;
+	return (seedx >> 16) & 0xffff;
+}
+
+static VOID srando(UINT s)
+{
+	seedx = (LONG) s;
+}
+
+static UINT rando()
+{
+	seedx = seedx * 214013L + 2531011L;
+	return (seedx >> 16) & 0x7fff;
+}
+
+#define PS_DIAMOND 0x00         /* red */
+#define PS_CLUB    0x10         /* black */
+#define PS_HEART   0x20         /* red */
+#define PS_SPADE   0x30         /* black */
+static int Suit[] = { PS_CLUB, PS_DIAMOND, PS_HEART, PS_SPADE };
+
+#define MAXTPILES       8       /* max number of piles */
+#define MAXWPILES      13
+extern card_t W[MAXWPILES][52]; /* the workspace */
+extern card_t *Wp[MAXWPILES];   /* point to the top card of each work pile */
+extern int Wlen[MAXWPILES];     /* the number of cards in each pile */
+extern card_t T[MAXTPILES];     /* one card in each temp cell */
+extern card_t O[4];             /* output piles store only the rank or NONE */
+
+extern int Nwpiles;
+
+void msdeal(LONG gnGameNumber)
+{
+	int i, j, c;
+	int wLeft = NUM_CARDS;  // cards left to be chosen in shuffle
+	CARD deck[NUM_CARDS];
+	CARD pos[MAXWPILES][NUM_CARDS+1];
+
+	memset(pos, 0, sizeof(pos));
+	for (i = 0; i < NUM_CARDS; i++) {
+		deck[i] = i + 1;
+	}
+
+	if (gnGameNumber < 0x100000000LL) {
+		srando((UINT) gnGameNumber);
+	} else {
+		srandp((UINT) (gnGameNumber - 0x100000000LL));
+	}
+
+	for (i = 0; i < NUM_CARDS; i++) {
+		if (gnGameNumber < 0x100000000LL) {
+			if (gnGameNumber < 0x80000000) {
+				j = rando() % wLeft;
+			} else {
+				j = (rando() | 0x8000) % wLeft;
+			}
+		} else {
+			j = (randp() + 1) % wLeft;
+		}
+		pos[i % Nwpiles][i / Nwpiles] = deck[j];
+		deck[j] = deck[--wLeft];
+		if (Nwpiles == 10 && i == 49) {
+			break;
+		}
+	}
+	for (i = 0; i < Nwpiles; i++) {
+		j = 0;
+		while (pos[i][j]) {
+			c = pos[i][j] - 1;
+			W[i][j] = Suit[c % 4] + (c / 4) + 1;
+			j++;
+		}
+		Wp[i] = &W[i][j - 1];
+		Wlen[i] = j;
+	}
+	/* leftover cards to temp */
+	for (i = 0; i < MAXTPILES; i++) {
+		T[i] = 0;
+		if (wLeft) {
+			j = --wLeft;
+			c = deck[j] - 1;
+			T[i] = Suit[c % 4] + (c / 4) + 1;
+		}
+	}
+	for (i = 0; i < 4; i++) {
+		O[i] = 0;
+	}
+}
+/* This file was generated by param.py.  Do not edit. */
+
+#include "param.h"
+
+XYparam_t XYparam[] = {
+ {{ 4, 1, 8, -1, 7, 11, 4, 2, 2, 1, 2, }, { 0.0032, 0.32, -3.0, }},
+ {{ 3, 4, 7, -4, -2, 1, 0, -4, 4, -1, 1, }, { -0.0008, 0.14, -1.0, }},
+ {{ 2, 4, 7, -2, -2, 1, 0, -5, 4, -1, 1, }, { -0.0024, 0.22, 0.0, }},
+ {{ 1, 3, 2, 2, 2, 3, -2, 2, 2, -1, 1, }, { 0.0008, 0.02, -4.0, }},
+ {{ 2, 2, 4, 0, 1, 2, 1, 1, 2, -1, 1, }, { -0.0008, 0.18, -5.0, }},
+ {{ 1, 1, 6, -2, -1, -2, -2, -3, 0, -1, 2, }, { 0.0, 0.08, 2.0, }},
+ {{ 2, 6, 2, 0, -5, -9, -5, -11, 3, 1, 1, }, { -0.0056, 0.42, -5.0, }},
+ {{ 2, 2, 5, -3, -1, -3, -3, -4, 4, 1, 3, }, { -0.0032, 0.24, 2.0, }},
+};

patsolve/param.dat

+# Parameters for the different modes.  Modes are numbered, and the
+# parameters are set during argument parsing using these numbers.  For
+# convenience, the modes have names here that get #defined (see param.h).
+# A user can also request a specific mode by using the -P flag along with
+# the mode's number (not name).  Specific parameter sets that are not
+# defined here can be tried using the -X and -Y arguments, and the default
+# mode (0) can be specified with just '-P'.
+
+# This file is translated into param.[ch] by param.py.
+
+# -fS
+FreecellSpeed 4 1 8 -1 7 11 4 2 2 1 2 0.0032 0.32 -3.0
+# -f
+FreecellBest 3 4 7 -4 -2 1 0 -4 4 -1 1 -0.0008 0.14 -1.0
+# -f (faster, uses less memory)
+FreecellBestA 2 4 7 -2 -2 1 0 -5 4 -1 1 -0.0024 0.22 0.0
+# -s
+SeahavenBest 1 3 2 2 2 3 -2 2 2 -1 1 0.0008 0.02 -4.0
+# -s (faster, uses less memory)
+SeahavenBestA 2 2 4 0 1 2 1 1 2 -1 1 -0.0008 0.18 -5.0
+# -sS
+SeahavenSpeed 1 1 6 -2 -1 -2 -2 -3 0 -1 2 0.0 0.08 2.0
+# -sk
+SeahavenKing 2 6 2 0 -5 -9 -5 -11 3 1 1 -0.0056 0.42 -5.0
+# -skS
+SeahavenKingSpeed 2 2 5 -3 -1 -3 -3 -4 4 1 3 -0.0032 0.24 2.0