shlomif / black-hole-solitaire

Solvers and statistics for “Golf” solitaire, “Black Hole” solitaire, “All in a Row” solitaire and related card patience games.

Black Hole Solitaire Solver

Black Hole Solitaire Solver is an automated solver for the card Solitaire games “Golf”, “Black Hole”, and “All in a Row” .

Screenshots

Videos

Solving Black Hole in PySolFC

Guide to the code

The interesting code in C is under the black-hole-solitaire/c-solver/ directory and there’s also some older code in Perl under black-hole-solitaire/Games-Solitaire-BlackHole-Solver/ .

Some related links:

• Freecell Solver - a solver for Freecell and related solitaire games.

• Other patience solvers

CI Build+Tests

• https://travis-ci.org/shlomif/black-hole-solitaire

• https://ci.appveyor.com/project/shlomif/black-hole-solitaire

black-hole-solitaire's Issues

1.12.0: test suite is failing

Looks like something is wrong

+ /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/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
Running tests...
/usr/bin/ctest --force-new-ctest-process --output-on-failure
Test project /home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu
    Start 1: perl_run_tests
1/1 Test #1: perl_run_tests ...................***Failed    9.45 sec
make[1]: Entering directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
make[1]: warning: jobserver unavailable: using -j1.  Add '+' to parent make rule.
make[1]: Leaving directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
make[1]: Entering directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
make[2]: Entering directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
make[3]: Entering directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
Dependencies file "CMakeFiles/black_hole_solver.dir/can_move.c.o.d" is newer than depends file "/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu/CMakeFiles/black_hole_solver.dir/compiler_depend.internal".
Dependencies file "CMakeFiles/black_hole_solver.dir/fcs_hash.c.o.d" is newer than depends file "/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu/CMakeFiles/black_hole_solver.dir/compiler_depend.internal".
Dependencies file "CMakeFiles/black_hole_solver.dir/generated/lib.c.o.d" is newer than depends file "/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu/CMakeFiles/black_hole_solver.dir/compiler_depend.internal".
Dependencies file "CMakeFiles/black_hole_solver.dir/meta_alloc.c.o.d" is newer than depends file "/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu/CMakeFiles/black_hole_solver.dir/compiler_depend.internal".
Dependencies file "CMakeFiles/black_hole_solver.dir/rank_reach_prune.c.o.d" is newer than depends file "/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu/CMakeFiles/black_hole_solver.dir/compiler_depend.internal".
Consolidate compiler generated dependencies of target black_hole_solver
make[3]: Leaving directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
[ 53%] Built target black_hole_solver
make[3]: Entering directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
Dependencies file "CMakeFiles/bhs_rank_reach_prune.dir/rank_reach_prune.c.o.d" is newer than depends file "/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu/CMakeFiles/bhs_rank_reach_prune.dir/compiler_depend.internal".
Consolidate compiler generated dependencies of target bhs_rank_reach_prune
make[3]: Leaving directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
[ 66%] Built target bhs_rank_reach_prune
make[3]: Entering directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
Dependencies file "CMakeFiles/black-hole-solve.dir/single_board_main.c.o.d" is newer than depends file "/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu/CMakeFiles/black-hole-solve.dir/compiler_depend.internal".
Consolidate compiler generated dependencies of target black-hole-solve
make[3]: Leaving directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
[ 80%] Built target black-hole-solve
make[3]: Entering directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
Dependencies file "CMakeFiles/multi-bhs-solver.dir/multi_solver.c.o.d" is newer than depends file "/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu/CMakeFiles/multi-bhs-solver.dir/compiler_depend.internal".
Consolidate compiler generated dependencies of target multi-bhs-solver
make[3]: Leaving directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
[ 93%] Built target multi-bhs-solver
make[3]: Entering directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
make[3]: Leaving directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
[100%] Built target man_docs_pods
make[2]: Leaving directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
make[1]: Leaving directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
FCS_BIN_PATH = /home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu
FCS_SRC_PATH = /home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0
FCS_TEST_TAGS = <>
/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/all-in-a-row-output.t .......... ok
/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/black-hole-output.t ............ ok
/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/clang-format.t ................. skipped: Environment variable to check was set.
# [checked] run-tests.pl
# *** needs tidying

#   Failed test 'run-tests.pl is tidy'
#   at /home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/perltidy.t line 14.
# *** needs tidying
# [checked] t/black-hole-output.t
# *** needs tidying

#   Failed test 't/black-hole-output.t is tidy'
#   at /home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/perltidy.t line 14.
# *** needs tidying
# [checked] t/valgrind.t
# *** needs tidying

#   Failed test 't/valgrind.t is tidy'
#   at /home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/perltidy.t line 14.
# *** needs tidying
# [checked] t/all-in-a-row-output.t
# *** needs tidying

#   Failed test 't/all-in-a-row-output.t is tidy'
#   at /home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/perltidy.t line 14.
# *** needs tidying
# Looks like you failed 4 tests of 16.
/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/perltidy.t .....................
Dubious, test returned 4 (wstat 1024, 0x400)
Failed 4/16 subtests
/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/rank-reachability-prune.t ...... ok
/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/style-trailing-space.t ......... ok
/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/unit-max-num-cards-overflow.t .. ok
/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/valgrind.t ..................... ok

Test Summary Report
-------------------
/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/t/perltidy.t                   (Wstat: 1024 Tests: 16 Failed: 4)
  Failed tests:  1, 4-6
  Non-zero exit status: 4
Files=8, Tests=173,  9 wallclock secs ( 0.18 usr  0.03 sys +  7.43 cusr  1.48 csys =  9.12 CPU)
Result: FAIL


0% tests passed, 1 tests failed out of 1

Total Test time (real) =   9.45 sec

The following tests FAILED:
          1 - perl_run_tests (Failed)
Errors while running CTest
make: *** [Makefile:94: test] Error 8
make: Leaving directory '/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu'
``
cmake settings
```console
[tkloczko@devel-g2v x86_64-redhat-linux-gnu]$ cmake -L
CMake Warning:
  No source or binary directory provided.  Both will be assumed to be the
  same as the current working directory, but note that this warning will
  become a fatal error in future CMake releases.


CMake Error: The source directory "/home/tkloczko/rpmbuild/BUILD/black-hole-solver-1.12.0/x86_64-redhat-linux-gnu" does not appear to contain CMakeLists.txt.
Specify --help for usage, or press the help button on the CMake GUI.
-- Cache values
BHS_STATE_STORAGE:STRING=BHS_STATE_STORAGE_INTERNAL_HASH
BUILD_STATIC_LIBRARY:BOOL=OFF
CMAKE_BUILD_TYPE:STRING=RelWithDebInfo
CMAKE_INSTALL_PREFIX:PATH=/usr
DISABLE_APPLYING_RPATH:BOOL=ON
ENABLE_DISPLAYING_MAX_NUM_PLAYED_CARDS:BOOL=OFF
FCS_AVOID_TCMALLOC:BOOL=OFF
FCS_IA_PACK_SIZE:STRING=64
FCS_WITH_TEST_SUITE:BOOL=ON
IA_STATE_PACKS_GROW_BY:STRING=32
LINK_TO_STATIC:BOOL=OFF
Rinutils_DIR:PATH=/usr/lib64/cmake/Rinutils
USE_SYSTEM_XXHASH:BOOL=ON
_PYTHON3:FILEPATH=/usr/bin/python3

Binary Star variant?

One Black Hole variant I've seen around is Binary Star. These are the differences in the rules:

• It is played with two decks rather than one.
• At the start of the game, each pile contains six cards rather than just three.
• There is a second foundation, started with a king of hearts. To win the game, the cards have to be moved to one of the two foundations - it does not matter how many cards are in each foundation.

Would this game be compatible with the Black Hole solver? I am planning to create a PySol implementation of Binary Star and want to confirm how to correctly handle the Solver_Class.

Thanks.

dllimport cannot be applied to non-inline function definition

Windows 10 64 bit, Clang GCC-like compiler with Windows SDK

This error happens also on lib.c file.

FAILED: CMakeFiles/bhs_rank_reach_prune.dir/rank_reach_prune.c.obj
D:\llvm\bin\clang.exe -DXXH_CPU_LITTLE_ENDIAN=1 -Dbhs_rank_reach_prune_EXPORTS -IE:/_/1d56ee4/black-hole-solver-1.12.0/include -IE:/_/1d56ee4/build/generated/include -IE:/_/1d56ee4/build/generated -IE:/_/1d56ee4/build -IE:/_/1d56ee4/black-hole-solver-1.12.0 -IE:/_/1d56ee4/black-hole-solver-1.12.0/xxHash-wrapper -IE:/_/1d56ee4/black-hole-solver-1.12.0/xxHash-wrapper/xxHash-0.8.1 -isystem E:/kde-build/include -O2 -g -DNDEBUG -Xclang -gcodeview -D_DLL -D_MT -Xclang --dependent-lib=msvcrt   -fvisibility=hidden -Wno-unknown-pragmas -MD -MT CMakeFiles/bhs_rank_reach_prune.dir/rank_reach_prune.c.obj -MF CMakeFiles\bhs_rank_reach_prune.dir\rank_reach_prune.c.obj.d -o CMakeFiles/bhs_rank_reach_prune.dir/rank_reach_prune.c.obj -c E:/_/1d56ee4/black-hole-solver-1.12.0/rank_reach_prune.c
E:/_/1d56ee4/black-hole-solver-1.12.0/rank_reach_prune.c:18:35: error: dllimport cannot be applied to non-inline function definition
DLLEXPORT enum RANK_REACH_VERDICT bhs_find_rank_reachability(
                                  ^
1 error generated.

Add a unit test for the max_num_cards_in_stacks buffer overflow

See 733e929 and 535c9d1 .

Add support for the golf variants to the verifier

See https://github.com/shlomif/black-hole-solitaire/tree/master/black-hole-solitaire/all-in-a-row-verifier . It currently supports only All in a Row but I'd like it to support the three variants of https://en.wikipedia.org/wiki/Golf_(patience) that the solver supports too.

[Optimization] Try using lookup tables (implemented as generated arrays) to determine if a move is valid

See

black-hole-solitaire/black-hole-solitaire/c-solver/black_hole_solver.c

Lines 717 to 720 in 9eedc1e

	const_AUTO(diff, abs(card - foundations));
	if ((foundations == -1) ||
	(diff == 1 || (wrap_ranks && (diff == RANK_K))))
	{

.

Cannot build program

I'm having trouble building the software, perhaps due to my pristine, unsullied ignorance of CMake. I cloned the repo and made a folder black-hole-solitaire/black-hole-solitaire/c-solver/build. Then

cd build
cmake-gui ..

I told it that the source was in c-solver and that the program should be built in build. It gave a message, "Configuring incomplete, errors occurred, and the only thing I could see specifically was "Rinutils_DIR-NOTFOUND". So, I configured Rinutils-DIR to be c-solver/rinutils, but I got the same error. I looked in CMakeOutput.log, but I didn't see anything that looked like an error, but I'm attaching in it case I've overlooked something.

I'm using CMake version 3.16.3.

Please give me any guidance you can.

CMakeOutput.log