shlomif / fc-solve

Freecell Solver - a C library for automatically solving Freecell and some other variants of card Solitaire

The Freecell Solver Repository Root README

Freecell Solver is an open source (distributed under the MIT/Expat licence) library, written in C, for attempting to solve several variants of card Solitaire/Patience, including Freecell , Baker’s Game , Seahaven Towers , and Simple Simon . Also contained are several command-line programs that use it, and the original project also span some other code for testing and for support.

Screenshots

Videos

Repository structure

fc-solve/source/

This contains the source of the solver itself. One can use CMake to build it.

cpan/Games-Solitaire-Verify/Games-Solitaire-Verify

This is the Games-Solitaire-Verify CPAN module. For more information see:

• Homepage
• MetaCPAN

Task-FreecellSolver-Testing

This is a CPAN module for installing the various test dependencies that are found on CPAN.

cpan/Task-FreecellSolver-Testing-MultiConfig

This is a CPAN module for installing the various test dependencies that are found on CPAN. More comprehensive.

fc-solve/arch_doc

The Freecell Solver Architecture Document. Somewhat out-of-date, but may be studied for general enlightenment.

fc-solve/presets

Some code that is used in order to calculate the built-in command-line presets, like “-l good-intentions” or “-l maliciously-obscure”. Not very documented. This code is written in parts in Perl, Bash and Mono.NET.

fc-solve/rejects

Contains code that is no longer used.

fc-solve/docs

Contains various documents that are not part of the main source distribution. Mostly specifications and planning documents.

fc-solve/benchmarks

Logs of various benchmarks of the code.

How to use the library

The external API, which is provided by freecell-solver/fcs_user.h , freecell-solver/fcs_cl.h and some other headers, is not documented, but it corresponds to the command line interface that is documented in the USAGE and the README documents, has some examples in the code, and should not be hard to use.

Related repositories and links

• Impossible 4-freecells and 5-freecells deals in Freecell Pro

• Freecell Pro 3 freecells impossible and intractable deals

• Finding zero freecells deals in the fc-pro range

• The minimal number of freecells needed to win for each deal in the original Microsoft FreeCell 32,000 deals.

• Lack of PGO investigation.

• Freecell Solver's Site Assets

• patsolve - a different Solitaire solver with interdependencies on this one.

• Haskell Freecell library

• PySol - an open source Solitaire game collection

• kpat

• solitaire.gg

fc-solve's Issues

sscanf safety check

Hello, as I've seen in all of your sscanf's(and other functions from this family) you are checking for return value and processing invalid data. There's only one exception there. It's this sscanf.

As you know much more about design of this tool I kindly ask you to check if it's ok.

You tried to plan twice

The test suite of Games-Solitaire-Verify-0.2301 fails on a few of my smoker systems:

You tried to plan twice at t/exception-newline.t line 11.
# Looks like your test exited with 2 before it could output anything.
t/exception-newline.t ..... 
Dubious, test returned 2 (wstat 512, 0x200)
Failed 2/2 subtests 

Extract some CMake macros out of duplicate "list (append" directives

There are some duplicate "list (APPEND" directives in the cmake list files - for the same variable. Extract them into their macros.

Convert cmake config to GNUInstallDirs

@a17r : hi, are you happy with the changes in this branch: https://github.com/shlomif/fc-solve/tree/cmake-gnu-install-dirs--feature-branch . Please review and tell me if you approve. Thanks!

depth_dbm_fc_solver / etc. should validate the input board as containing all the cards and exactly once

Currently the depth_dbm_fc_solver gives this when given an empty file as an input:

shlomif[fcs]:$trunk/fc-solve/build$ mkdir offload                      [41/1818]
shlomif[fcs]:$trunk/fc-solve/build$ echo -n > empty.board                       
shlomif[fcs]:$trunk/fc-solve/build$ ./depth_dbm_fc_solver --num-threads 1 --offl
oad-dir-path `pwd`/offload/ ./empty.board
instance_run_all_threads start
Running threads for curr_depth=0
instance_run_solver_thread start
instance_run_solver_thread end
Finished running threads for curr_depth=0
Start mark-and-sweep cleanup for curr_depth=0
Finish mark-and-sweep cleanup for curr_depth=0
Running threads for curr_depth=1
instance_run_solver_thread start
instance_run_solver_thread end
Finished running threads for curr_depth=1
Start mark-and-sweep cleanup for curr_depth=1
Finish mark-and-sweep cleanup for curr_depth=1
Running threads for curr_depth=2
instance_run_solver_thread start
instance_run_solver_thread end
Finished running threads for curr_depth=2
Start mark-and-sweep cleanup for curr_depth=2
Finish mark-and-sweep cleanup for curr_depth=2
Running threads for curr_depth=3
instance_run_solver_thread start
instance_run_solver_thread end
Finished running threads for curr_depth=3
Start mark-and-sweep cleanup for curr_depth=3
Finish mark-and-sweep cleanup for curr_depth=3
Running threads for curr_depth=4
instance_run_solver_thread start
instance_run_solver_thread end
Finished running threads for curr_depth=4
instance_run_all_threads end
handle_and_destroy_instance_solution start
Reached 34 ; States-in-collection: 82 ; Time: 1479851982.791426
>>>Queue Stats: inserted=82 items_in_queue=48 extracted=34
Success!
--------
Foundations: H-6 C-9 D-5 S-7
Freecells:  8H  9S
: KS
: KH QS JH
: TC 9D
:
:
:
:
:

==
Column 2 -> Column 7
--------
Foundations: H-T C-3 D-5 S-7
Freecells:  4C  5C
: KS
: KH QS JH
: TC 9D
:
:
:
:
:

==
Column 2 -> Column 7
--------
Foundations: H-T C-3 D-5 S-7
Freecells:  4C  5C
: KS
: KC QD
: QH JC
: TD
: 9S
: 9D 8C 7D
: 7C
: 6C

==
Column 7 -> Column 5
--------
Foundations: H-4 C-Q D-J S-0
Freecells:  2S  3S
: KS
: KC
: KH
: QD
:
:
:
:

==
Column 3 -> Column 1
--------
Foundations: H-/ C-c D-- S-s
Freecells:  2C  6C
: KD
: JS
: TS
: TD
: TC
: 9D
: 8D
: 5C

==
END
handle_and_destroy_instance_solution end

or worse - it exits with an obscure exception . It should validate the board for extra/missing cards and not start the solving process if the board does not validate. With a regression test!

On the automated solver page, clarify that it can solve other games besides Freecell

freecell-solver-6.6.0: test suite is failing

Yeah .. looks like somethiong is wrong

+ cd freecell-solver-6.6.0
+ /usr/bin/make -O -j48 V=1 VERBOSE=1 -C x86_64-redhat-linux-gnu test ARGS=--output-on-failure
make: Entering directory '/home/tkloczko/rpmbuild/BUILD/freecell-solver-6.6.0/x86_64-redhat-linux-gnu'
Running tests...
/usr/bin/ctest --force-new-ctest-process --output-on-failure
Test project /home/tkloczko/rpmbuild/BUILD/freecell-solver-6.6.0/x86_64-redhat-linux-gnu
    Start 1: perl_run_tests
1/1 Test #1: perl_run_tests ...................***Failed    0.18 sec
dbm-fc-solver
Open failed: No such file or directory at /home/tkloczko/rpmbuild/BUILD/freecell-solver-6.6.0/run-tests.pl line 126.
bin dbm-fc-solver dbm-fc-solver
bin dbm-fc-solver linux-vdso.so.1


0% tests passed, 1 tests failed out of 1

Total Test time (real) =   0.18 sec

The following tests FAILED:
          1 - perl_run_tests (Failed)
Errors while running CTest

Eliminate the cmake make stage "Circular dependency" warnings

Currently make after cmake with DBM gives this:

make[2]: Circular CMakeFiles/pseudo_dfs_fc_solver <- pseudo_dfs_fc_solver dependency dropped.
make[2]: Circular pseudo_dfs_fc_solver <- pseudo_dfs_fc_solver dependency dropped.

Get rid of it.

Number the steps in solution

Sequentially number the steps in the solution. Easy to get lost when scrolling.

Convert depth_dbm_solver.c to use condition variables instead of a busy/sleep loop

Make a wise use of condition variables in the depth_dbm_solver instead of a busy/usleep() loop to wake up threads for further processing. The basic idea is:

1. A worker thread will signal the condvar when new data is available in the queue to wake up a single thread.

2. A thread will broadcast the condvar to terminate the process completely.

Please use a feature branch for that.

Extract an fprintf(stderr, fmt, ...);+exit(-1); function

Extract a function to do fprintf(stderr, fmt, args and then exit(-1);. Make it _Noreturn.

Add a screenshot and some text to clarify which cards are lying on the carpet in the README.html

Add a compile-time option for the offloading queue to use Amazon S3 instead of a local disk

See https://en.wikipedia.org/wiki/Amazon_S3 - this should be cheper than allocating extra hard disk space locally at Amazon EC2 instances. Now the question is where to find a good API for C or C++.

Build fails: missing Shlomif_Common.cmake

cmake fails with:
`$ cmake .
CMake Error at CMakeLists.txt:5 (INCLUDE):
INCLUDE could not find load file:

Shlomif_Common

CMake Error at CMakeLists.txt:7 (SHLOMIF_COMMON_SETUP):
Unknown CMake command "SHLOMIF_COMMON_SETUP".
`
The needed file is ignored in .gitignore but after digging through the git history I found it in your bitbucket. Cloning that and copying the needed file, and now I have a different problem, perl dependencies.

"fc-solve -g eight_board" segfaults on Mageia v6

"fc-solve -g eight_board" segfaults on Mageia v6. Look into fixing it. (eight_board is a non existent preset).

Cannot compile on non-glibc POSIX systems: sys/cdefs.h is a glibc-specific header

The file fc-solve/source/sys/tree.h contains an include of sys/cdefs.h, which is a GNU-C-library-internal header that should not be used in external code:

fc-solve/fc-solve/source/sys/tree.h

Line 33 in 90163fe

#include <sys/cdefs.h>

Because of this, fc-solve cannot be compiled e.g. on systems using the musl libc, which doesn't expose this header. Compilation fails with the following error:

FAILED: CMakeFiles/split_fcc_fc_solver.dir/split_fcc_solver.c.o 
/usr/bin/powerpc-gentoo-linux-musl-gcc -DFCS_COMPILE_DEBUG_FUNCTIONS=1 -DFCS_DBM_RECORD_POINTER_REPR=1 -DFCS_DBM_USE_LIBAVL=1 -DFCS_DBM_WITHOUT_CACHES=1 -DFCS_DBM__VAL_IS_ANCESTOR=1 -DFCS_DEBONDT_DELTA_STATES=1 -DFCS_LIBAVL_STORE_WHOLE_KEYS=1 -DFCS_SPLIT_FCC_SOLVER=1 -DXXH_CPU_LITTLE_ENDIAN=0 -D_GNU_SOURCE="1 -D_PO
SIX_C_SOURCE=200809L" -I/var/tmp/portage/dev-games/freecell-solver-6.8.0/work/freecell-solver-6.8.0/fcs-libavl -I/var/tmp/portage/dev-games/freecell-solver-6.8.0/work/freecell-solver-6.8.0_build -I/var/tmp/portage/dev-games/freecell-solver-6.8.0/work/freecell-solver-6.8.0_build/include -I/var/tmp/portage/dev-games/
freecell-solver-6.8.0/work/freecell-solver-6.8.0 -I/var/tmp/portage/dev-games/freecell-solver-6.8.0/work/freecell-solver-6.8.0/include -I/var/tmp/portage/dev-games/freecell-solver-6.8.0/work/freecell-solver-6.8.0/patsolve/patsolve/include -I/var/tmp/portage/dev-games/freecell-solver-6.8.0/work/freecell-solver-6.8.0
/patsolve/patsolve -I/var/tmp/portage/dev-games/freecell-solver-6.8.0/work/freecell-solver-6.8.0/xxHash-wrapper -I/var/tmp/portage/dev-games/freecell-solver-6.8.0/work/freecell-solver-6.8.0/xxHash-wrapper/xxHash-0.8.1  -O2 -ggdb -mcpu=7450 -mvrsave -pipe -std=gnu11   -Wall -Werror=implicit-function-declaration -Wol
d-style-declaration -Wmissing-prototypes -Wformat-nonliteral -Wcast-align -Wpointer-arith -Wbad-function-cast -Wstrict-prototypes -Wmissing-declarations -Wundef -Wnested-externs -Wcast-qual -Wshadow -Wwrite-strings -Wunused -Wold-style-definition -fvisibility=hidden -MD -MT CMakeFiles/split_fcc_fc_solver.dir/split_
fcc_solver.c.o -MF CMakeFiles/split_fcc_fc_solver.dir/split_fcc_solver.c.o.d -o CMakeFiles/split_fcc_fc_solver.dir/split_fcc_solver.c.o -c /var/tmp/portage/dev-games/freecell-solver-6.8.0/work/freecell-solver-6.8.0/split_fcc_solver.c
In file included from /var/tmp/portage/dev-games/freecell-solver-6.8.0/work/freecell-solver-6.8.0/split_fcc_solver.c:18:
/var/tmp/portage/dev-games/freecell-solver-6.8.0/work/freecell-solver-6.8.0/sys/tree.h:33:10: fatal error: sys/cdefs.h: No such file or directory
   33 | #include <sys/cdefs.h>
      |          ^~~~~~~~~~~~~
compilation terminated.

As far as I can see, the header is unused and removing the include allows the program to compile successfully.

[depth_dbm_freecell_solver] Implement extracted items batches of a user-specified size

This is an attempt to improve the depth_dbm_fc_solver's multi-threading scalability which is currently very poor. In an attempt to reduce the amount of locking and increase CPU utilisation per thread, we want to:

1. Define a --batch-size argument which can specify an arbitrarily large count of elements that each thread will extract from the queue at a time.

2. In each thread, extract these items, and without locking: decode them, calculate their derived positions (segregated in an array per irreversible-move-depth). Then, lock the states collections and insert them all into the central depth collections. Repeat.

This is instead of extracting one item from the queue at a time.

Most of this should be done in https://github.com/shlomif/fc-solve/blob/master/fc-solve/source/depth_dbm_solver.c for now. Please use a new feature git branch.

«The command line parameter "(null)" requires an argument and was not supplied with one.»

shlomif[fcs]:$trunk/fc-solve/B$ ./fc-solve -g 
The command line parameter "(null)" requires an argument and was not supplied with one.
shlomif[fcs]:$trunk/fc-solve/B$ ./fc-solve -l
The command line parameter "(null)" requires an argument and was not supplied with one.

should not be NULL.

six usage

You are using six on few places, is that necessary?

fc-solve/scripts/analyse-deals-range-prelude-stage-execution.py:from six import print_
fc-solve/scripts/generate-summary-length-improvements/summarizer-v2.py:from six.moves import range
fc-solve/source/board_gen/find-freecell-deal-index.py:from six.moves import range

An improper locking due to the unreleased lock before program exit

Hi developers, in the below codes, the lock instance->fcc_exit_points_output_lock could be not released before program's exit abort();. I think it is better to write fcs_lock_unlock(&instance->fcc_exit_points_output_lock); before the abort(); for better resource management and code symmetry. Thanks!

fc-solve/fc-solve/source/split_fcc_solver.c

Lines 455 to 478 in 45efed2

	fcs_lock_lock(&instance->fcc_exit_points_output_lock);
	// instance->storage_lock is already locked in
	// instance_check_multiple_keys and we should not lock it here.
	calc_trace(token, &trace, &trace_num);
	{
	FccEntryPointNode fcc_entry_key;
	fcc_entry_key.kv.key.key = trace[trace_num - 1];
	FccEntryPointNode *val_proto = RB_FIND(FccEntryPointList,
	&(instance->fcc_entry_points), &fcc_entry_key);
	if (!val_proto)
	{
	goto cleanup;
	}
	const long location_in_file =
	val_proto->kv.val.location_in_file;
	fseek(instance->fingerprint_fh, location_in_file, SEEK_SET);
	#ifdef HAVE_GETLINE
	if (getline(&(instance->fingerprint_line),
	&(instance->fingerprint_line_size),
	instance->fingerprint_fh) <= 0)
	{
	abort();
	}

Best,

Convert to TypeScript: https://github.com/shlomif/fc-solve/blob/master/fc-solve/site/wml/src/js/web-fc-solve-tests--fcs-validate.js

The file https://github.com/shlomif/fc-solve/blob/master/fc-solve/site/wml/src/js/web-fc-solve-tests--fcs-validate.js is currently written in JavaScript, but converting it to TypeScript won't hurt much. Note that it is part of the Freecell Solver site whose build procedure is relatively complex and underdocumented. (I'd like to document it better).

tidyall cache files pollute the released tarballs

I didn't notice them before but they were already present in the 6.8 release and are still in the released tarball from https://fc-solve.shlomifish.org/download.html

# du -h freecell-solver-6.10.0/.tidyall.d 
0       freecell-solver-6.10.0/.tidyall.d/backups
56K     freecell-solver-6.10.0/.tidyall.d/cache/0
80K     freecell-solver-6.10.0/.tidyall.d/cache/b
72K     freecell-solver-6.10.0/.tidyall.d/cache/4
76K     freecell-solver-6.10.0/.tidyall.d/cache/3
72K     freecell-solver-6.10.0/.tidyall.d/cache/f
44K     freecell-solver-6.10.0/.tidyall.d/cache/c
52K     freecell-solver-6.10.0/.tidyall.d/cache/7
100K    freecell-solver-6.10.0/.tidyall.d/cache/a
72K     freecell-solver-6.10.0/.tidyall.d/cache/5
72K     freecell-solver-6.10.0/.tidyall.d/cache/d
44K     freecell-solver-6.10.0/.tidyall.d/cache/2
80K     freecell-solver-6.10.0/.tidyall.d/cache/1
80K     freecell-solver-6.10.0/.tidyall.d/cache/e
72K     freecell-solver-6.10.0/.tidyall.d/cache/9
88K     freecell-solver-6.10.0/.tidyall.d/cache/6
92K     freecell-solver-6.10.0/.tidyall.d/cache/8
1,2M    freecell-solver-6.10.0/.tidyall.d/cache
1,2M    freecell-solver-6.10.0/.tidyall.d

cpanratings.perl.org no longer exists

This distribution has a link to CPAN Ratings at cpanratings.perl.org, but this address now redirects to https://metacpan.org/

compile with brew for OSX

I am trying to write a brew recipe to compile the freecell-solver on OSX.

cmake fails without an error.
can you tell me what options I need to add?

class FreecellSolver < Formula
  desc "Solitaire Solver library"
  homepage "https://fc-solve.shlomifish.org/"
  url "https://fc-solve.shlomifish.org/downloads/fc-solve/freecell-solver-6.0.1.tar.xz"
  # https://fc-solve.shlomifish.org/downloads/fc-solve/freecell-solver-5.24.0.tar.xz
  sha256 "9f1a4c6d5c8ac54c6619b3b988efb5562d460cd048d33345e52a0c849fd0d9df"
  revision 1
  
  def install
    args = std_cmake_args
    args << "-DBUILD_TESTING=OFF"
    args << "-DKDE_INSTALL_QMLDIR=lib/qt5/qml"
    args << "-DKDE_INSTALL_PLUGINDIR=lib/qt5/plugins"
    args << "-DCMAKE_INSTALL_BUNDLEDIR=#{bin}"

    mkdir "build" do
      system "cmake", "..", *args
      system "make"
      system "make", "install"
      prefix.install "install_manifest.txt"
    end
  end
end

Convert libavl/avl.{c,h} to rb.{c,h} from the libavl-2.0.3 distribution

Convert libavl/avl.{c,h} to rb.{c,h} from the libavl-2.0.3 distribution . We applied some changes to the avl.[ch] files only to discover that their AVL balancing factor required all values from -3 to 3. rb.[ch] on the other hand requires only a 1-bit enum of RED/BLACK for that. So it will allow storing it as the low bits of the pointers. "Plan to throw one away.".

missing source file in 6.0.0

6.0.0 fails to configure with a missing source file error

CMake Error at CMakeLists.txt:587 (ADD_LIBRARY):
  Cannot find source file:

    fcs_is_ss_true_parent.c

  Tried extensions .c .C .c++ .cc .cpp .cxx .cu .m .M .mm .h .hh .h++ .hm
  .hpp .hxx .in .txx

Change the wordy X11/Expat licence in the Perl files to the "refer to the COPYING" blurb like in C

ag sublicense

quite a few occurrences there - see state.h for a good example.

Suggestions about error handlings for locking

Hi, developers, I have a suggestion about error handlings for locking. Would it be better to handle the possible errors that return from pthread_mutex_lock.

For example, this example does not check the value returned by pthread_mutex_lock() for errors. If pthread_mutex_lock() cannot acquire the mutex for any reason, the function may introduce a race condition into the program (CWE-413).

The manners of error handlings could be flagging any warnings or returning before accessing the critical region.

void f(pthread_mutex_t *mutex) {
pthread_mutex_lock(mutex);

/* access shared resource */


pthread_mutex_unlock(mutex);
}

fc-solve/fc-solve/source/lock.h

Lines 71 to 74 in 45efed2

	static inline void fcs_lock_lock(fcs_lock *const lock)
	{
	pthread_mutex_lock(lock);
	}