User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

peg-solitaire solver (all configurations)

Sat Dec 26, 2020 11:53 pm

Years ago I had written a peg-solitaire game for playing in browser:
https://stamm-wilbrandt.de/en/xsl-list/peg-solitaire/
Image

Among the 5 selectable games, for the simplest "English" variant the board consist of 33 positions, for the biggest "Wiegleb" board consists of 45 positions.

I just wrote a solver for peg-solitaire, that represents an n-position board by a n-bit number, so used uint64_t datatype.
All 2^n possible positions (a field can have a peg or not) are stored in an array of size 2^(n-3).

Solving the 33 position board completely did only take 2:52min on Pi400, writing the 1GB result to SD card another minute.

On my 32GB 1.9GHz Intel i7 quad core (with hytper threading) Linux laptop it took 47 seconds in total.

Code: Select all

$ time ./pegsol 2>English
76
done(1)
done(2)
done(3)
done(4)
done(5)
done(6)
done(7)
done(8)
done(9)
done(10)
done(11)
done(12)
done(13)
done(14)
done(15)
done(16)
done(17)
done(18)
done(19)
done(20)
done(21)
done(22)
done(23)
done(24)
done(25)
done(26)
done(27)
done(28)
done(29)
done(30)
done(31)
done(32)
33

real	0m47.321s
user	0m46.347s
sys	0m0.968s
$

Finally, on my 96GB 3GHz Xeon hex core (with hyperthreading) dev workstation in company it took 69 seconds in total.

The generated 1GB file "English" for the Englisch board has 1bit for all board configuration, that allow for a sequence of moves that end with a single peg in center of board and a 0bit for configurations that do not allow for that. From solver pegsol.c (that is work in progress and will be shown in a later posting), this is input board for English, the x specifies where final peg should end, and it is the start of bottom up breadth first generation of all possible 1bit configurations:

Code: Select all

char B[9][9]={
#if 1
".........",  /* English */
"...ooo...",
"...ooo...",
".ooooooo.",
".oooxooo.",
".ooooooo.",
"...ooo...",
"...ooo...",
"........."
#else
".........",  /* French */
"...ooo...",
"..ooooo..",
".oooxooo.",
".ooooooo.",
".ooooooo.",
"..ooooo..",
"...ooo...",
"........."
#endif
};

Board sizes:

Code: Select all

33 English
37 French
39 3-3-2-2
41 Diamond
45 Wiegleb

Besides the 2^(n-3) byte array, the solver uses two 2^(n-6) compressed arrays for fast access. Therefore pegsol.c needs 1.25*2^(n-3) bytes contiguous memory.

English needs 1.25GB, can be solved at least on all 4GB or 8GB Raspberries, perhaps on 2GB as well.
French needs 20GB, cannot be solved on any Rapberry Pi, but on my i7 laptop and dev workstation.
Workstation allows to allocate 80GB, with single array of size 64GB, I already tested that.
That is 2 bits more than French, so 3-3-2-2 board can be solved as well ... only question is how long that will take ;-)


This is English board hash:

Code: Select all

$ sha256sum English 
dac1c655d0e64dfbf253b77753ef090f40d3d4f1b8a3fad0a74a4e9f006aa2c9  English
$

Why do I show that?
Because I have uploaded it to my personal website:
https://stamm-wilbrandt.de/peg/English

I have 1Gbit connection at home with 50Mbit upload.
Upload was done with slightly more than 30Mbit/s:

Code: Select all

1073741824 bytes sent in 277 secs (3879.10 Kbytes/sec)
Test download was done in 51 seconds -- will take longer for slower connections:

Code: Select all

100%[====================================>] 1,073,741,824 20.5MB/s   in 51s    

2020-12-26 23:48:54 (20.3 MB/s) - ‘English.1’ saved [1073741824/1073741824]

I thought on replacing the 1GB array for post processing by binary search tree (eg. heap) consisting of all good positions. I used this simple bit counter for input from stdin (really found no Linux tool for that):

Code: Select all

$ cat bwc.c
#include <stdio.h>
#include <stdlib.h>

int bits8[256];

int main()
{
  int i,j,k,b,d;
  u_int64_t cnt=0;

  for(i=0; i<(1<<8); ++i)
  {
    bits8[i]=0;
    for(j=0; j<8; ++j)
      if (i & (1<<j))
        ++bits8[i];
  }

  while (!feof(stdin))
  {
    int c = getchar();
    if (c != EOF)
      cnt += bits8[c];
  } 
      
  printf("%d\n",cnt);

  return 0;
}
$ 



A 33bit number needs 5 bytes, with the many 1bit positions in 1GB file the resulting length makes nearly no difference, so going with the 1GB file is easier:

Code: Select all

$ ./bwc < English 
187636299
$ 
$ echo "187636299*5" | bc
938181495
$ 

I wrote a simple debug code that takes as input any configuration as uint64 value and shows a solution down to single peg determined from that 1GB file. Here is the code as is, so you can use it after downloading the 1GB file yourself to play with English board:

Code: Select all

$ cat sol.c 
/* gcc -O6 -Wall -pedantic -Wextra sol.c -Wno-long-long -o sol */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <inttypes.h>
#include <unistd.h>


char B[9][9]={
#if 1
".........",  /* English */
"...ooo...",
"...ooo...",
".ooooooo.",
".oooxooo.",
".ooooooo.",
"...ooo...",
"...ooo...",
"........."
#else
".........",  /* French */
"...ooo...",
"..ooooo..",
".oooxooo.",
".ooooooo.",
".ooooooo.",
"..ooooo..",
"...ooo...",
"........."
#endif
};

int N[9][9];

int m,cnt;
uint64_t M[7*9*2*2];
uint64_t D[7*9*2*2];
uint64_t P[7*9*2*2];

void draw(uint64_t u, int p)
{
  int i,j;
  printf("\x1b[2J");
  for(i=0; i<9; ++i)
  {
    for(j=0; j<9; ++j)
      printf("%s", N[i][j]==255 ? "." : (u & (1LL<<N[i][j])) ? 
                   ((N[i][j]==p) ? "\x1b[7mo\x1b[0m" : "o") : " ");
    printf("\n");
  }
  usleep(p==255 ? 900000 : 600000);
}

int main(int argc, char *argv[])
{
  uint64_t u;
  uint8_t *A;
  FILE *src;

  int i,d;
  uint64_t j,n;

  assert(argc==2);
  sscanf(argv[1],"%"SCNx64,&u);

  m=0;
  for(i=0; i<9; ++i)
  {
    for(j=0; j<9; ++j)
    {
      N[i][j] = (B[i][j]!='.') ? cnt++ : 255;

      if (i>1)
        if (N[i][j]!=255 && N[i-1][j]!=255 && N[i-2][j]!=255)
        {
          M[m]   = (1LL<<N[i-2][j]);
          P[m]   = N[i][j];
          D[m++] = (1LL<<N[i][j]) | (1LL<<N[i-1][j]);
          M[m]   = (1LL<<N[i][j]);
          P[m]   = N[i-2][j];
          D[m++] = (1LL<<N[i-1][j]) | (1LL<<N[i-2][j]);
        }  

      if (j>1)
        if (N[i][j]!=255 && N[i][j-1]!=255 && N[i][j-2]!=255)
        {
          M[m]   = (1LL<<N[i][j-2]);
          P[m]   = N[i][j];
          D[m++] = (1LL<<N[i][j]) | (1LL<<N[i][j-1]);
          M[m]   = (1LL<<N[i][j]);
          P[m]   = N[i][j-2];
          D[m++] = (1LL<<N[i][j-1]) | (1LL<<N[i][j-2]);
        }  
    }
  }

  assert( (A = malloc(1<<(cnt-3))) );
  assert( (src=fopen("English","rb")) );
  assert(1 == fread(A, 1<<(cnt-3), 1, src));
  fclose(src);

  assert(A[u>>3] & 1<<(u%8));

  for(;;)
  {
/*    printf("%"PRIx64"\n",u); */
    draw(u, 255);

    n=0;
    for(d=0; d<m; ++d)
    {
      if (!(u & M[d]) && ((u & D[d]) == D[d]))
      {
        n = u^(M[d]|D[d]);
        if (A[n>>3] & 1<<(n%8))
          break;
      }
    }

    if (n==0)
      break;

    draw(u, P[d]);

    u=n;
  }

  free(A);  

  return 0;
}
$

The output for initial board with 32 pegs and single blank field in center (0x1FFFEFFFF), recorded with "peek" screen recorder (only 62893(!) bytes for 1 minute of recording):
Peek_2020-12-26_23-23.gif
Peek_2020-12-26_23-23.gif
Peek_2020-12-26_23-23.gif (61.42 KiB) Viewed 1009 times
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Sun Dec 27, 2020 11:31 pm

pegsol.c is still not final, but I gave it a try on the 96GB dev workstation as is.
It took less than 23 minutes to compute 37 field French board!
Resident size of pegsol was 20GB during that time:

Code: Select all

$ du -b French 
17179869184	French
$ echo "2^(37-3)" | bc
17179869184
$ 

sol.c did need few monifications, first board needed to be switched to French:

Code: Select all

$ diff sol.c.old sol.c
10c10
< #if 1
---
> #if 0

Next, (16GB) French array need to be read.
Finally the "1" constants were not 64bit, which led to crash for 37-3=34 bits:

Code: Select all

97,99c97,99
<   assert( (A = malloc(1<<(cnt-3))) );
<   assert( (src=fopen("English","rb")) );
<   assert(1 == fread(A, 1<<(cnt-3), 1, src));
---
>   assert( (A = malloc(1LL<<(cnt-3))) );
>   assert( (src=fopen("French","rb")) );
>   assert(1 == fread(A, 1LL<<(cnt-3), 1, src));
$

I never knew a solution for 37 field French board, and never found one trying myself
(I did know a solution for English board, learned it in the 70s from my father).
Here is the French solution read out by sol.c:
Peek_2020-12-27_23-41.gif
Peek_2020-12-27_23-41.gif
Peek_2020-12-27_23-41.gif (37.58 KiB) Viewed 947 times

P.S:
Hash computation complexity is linear, 16GB takes 16x the time of 1GB:

Code: Select all

$ time sha256sum English 
dac1c655d0e64dfbf253b77753ef090f40d3d4f1b8a3fad0a74a4e9f006aa2c9  English

real	0m4.590s
user	0m4.438s
sys	0m0.147s
$ 
$ time sha256sum French
1d3c697f2077bce6f52cb8ed5bd8f20f81903d43ebc8ad79d584a9c9e3595bde  French

real	1m12.770s
user	1m10.208s
sys	0m2.550s
$ 

P.P.S:
2,990,375,067 bits set in 16GB French file (so many positions can be played to only one peg left):

Code: Select all

$ time ./bwc <French
2990375067

real	4m12.587s
user	4m7.885s
sys	0m4.675s
$

1,869,912,952 non-0x00 bytes in French file:

Code: Select all

$ echo "2^(37-3)-15309956232" | bc
1869912952
$
$ time ./bsc <French | grep -v " 0"
00 15309956232
01 109321125
04 301129478
08 135017864
18 314983677
20 4203835
24 228163113
40 135017864
42 314983677
80 64760671
81 262331648

real	4m18.053s
user	4m13.453s
sys	0m4.575s
$
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Mon Dec 28, 2020 4:19 am

No need to write C code to test for all possible single empty field start positions ending with single peg at same end position "x":

Code: Select all

#else
".........",  /* French */
"...ooo...",
"..ooooo..",
".oooxooo.",
".ooooooo.",
".ooooooo.",
"..ooooo..",
"...ooo...",
"........."
#endif

Arbitrary precision calculator "bc" computes the 37bit hexadecimal numbers and prints the commands to be executed. bash just executes those commands. sol aborts in less than 10 seconds for an invalid start position, so grepping all "Terminated" statements identifies the start positions of interest (they have started showing a solution, against /dev/null):

Code: Select all

$ echo 'obase=16; for(i=0; i<37; ++i) print "./sol ",2^37-1-2^i,">/dev/null &\
> p=$! && sleep 10 && kill $p\n"' | bc | bash 2>&1 | grep Terminated
bash: line 7: 27506 Terminated              ./sol 1FFFFFFFDF > /dev/null
bash: line 24: 27741 Terminated              ./sol 1FFFBFFFFF > /dev/null
bash: line 27: 27779 Terminated              ./sol 1FFDFFFFFF > /dev/null
bash: line 30: 27809 Terminated              ./sol 1FEFFFFFFF > /dev/null
$ 

For completeness the three other solutions for French besides 1FFDFFFFFF:
Peek_2020-12-28_05-03.gif
Peek_2020-12-28_05-03.gif
Peek_2020-12-28_05-03.gif (40.75 KiB) Viewed 911 times
Peek_2020-12-28_05-08.gif
Peek_2020-12-28_05-08.gif
Peek_2020-12-28_05-08.gif (40.48 KiB) Viewed 911 times
Peek_2020-12-28_05-09.gif
Peek_2020-12-28_05-09.gif
Peek_2020-12-28_05-09.gif (39.24 KiB) Viewed 911 times
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Mon Dec 28, 2020 10:03 pm

Today I did run "time ./pegsol 2> 3-2-3-2" for the 39 fields 3-3-2-2 board.
Program had 80GB of resident memory during whole execution, of 101(!) minutes length.

I tried to use sol.c in order to see a solution presented.
But unlike reading 16GB file before, which took a few seconds, the startup phase for 64GB file was more than 3 minutes!
Most likely 16GB did fit into some kind of cache, otherwise I could not explain this drastic reduction in startup speed.

I wrote a new sol2.c, that did not read the 64GB (or less) file.
Instead it does open the file, and use fseek() to position on the byte of interest efficiently.
Fore 3-3-2-2 board, maximally 92 moves are possible for a position.
With 38 moves until only one peg is left, less than 3500 fseek()s are needed.

This is sol2.c, modified from solc.c:
https://gist.github.com/Hermann-SW/4153 ... 2544df420a

Compile instructions name change, and adding new 3-3-2-2 board in addition to English and French boards:

Code: Select all

$ diff sol.c.old sol2.c 
1c1
< /* gcc -O6 -Wall -pedantic -Wextra sol.c -Wno-long-long -o sol */
---
> /* gcc -O6 -Wall -pedantic -Wextra sol2.c -Wno-long-long -o sol2 */
20c20
< #else
---
> #elif 0

New 3-3-2.2 board:

Code: Select all

29a30,39
> #else
> "...ooo...",  /* 3-3-2-2 */
> "...ooo...",
> "...ooo...",
> ".oooooooo",
> ".oooxoooo",
> ".oooooooo",
> "...ooo...",
> "...ooo...",
> "........."

Utility function fgtc() reads character from specified offset and returns it:

Code: Select all

53a64,73
> uint8_t fgtc(FILE *src, uint64_t u)
> {
>   int c;
>   rewind(src);
>   assert(0 == fseek(src, u, SEEK_SET));
>   c = fgetc(src);
>   assert(c != EOF);
>   return c;
> }
> 

No big array A anymore, and no long read:

Code: Select all

57d76
<   uint8_t *A;
97,100c116
<   assert( (A = malloc(1LL<<(cnt-3))) );
<   assert( (src=fopen("French","rb")) );
<   assert(1 == fread(A, 1LL<<(cnt-3), 1, src));
<   fclose(src);
---
>   assert( (src=fopen("3-3-2-2","rb")) );

Instead of checking bit against some byte of big array, read the byte and check:

Code: Select all

102c118,119
<   assert(A[u>>3] & 1<<(u%8));
---
>   i = fgtc(src, u>>3);
>   assert(i & 1<<(u%8));

Same here:

Code: Select all

115c132,134
<         if (A[n>>3] & 1<<(n%8))
---
>         
>         i = fgtc(src, n>>3);
>         if (i & 1<<(n%8))
127,128d145
< 
<   free(A);  
$

Like last night I did determine possible starting empty fields.
These are the 5 locations of free field, allowing to reah single bread on board:

Code: Select all

$ echo 'obase=16; for(i=0; i<39; ++i) print "./sol2 ",2^39-1-2^i,">/dev/null &\
> p=$! && sleep 4 && kill $p\n"' | bc | bash 2>&1 | grep Terminated
bash: line 6: 29001 Terminated              ./sol2 7FFFFFFFEF > /dev/null
bash: line 19: 29080 Terminated              ./sol2 7FFFFDFFFF > /dev/null
bash: line 22: 29096 Terminated              ./sol2 7FFFEFFFFF > /dev/null
bash: line 25: 29114 Terminated              ./sol2 7FFF7FFFFF > /dev/null
bash: line 39: 29198 Terminated              ./sol2 5FFFFFFFFF > /dev/null
$ 
Vizualization of the 5 positions:
3-3-2-2.initial_positions.jpg
3-3-2-2.initial_positions.jpg
3-3-2-2.initial_positions.jpg (18.02 KiB) Viewed 862 times


This is the solution with center start empty field:
Peek_2020-12-28_22-45.gif
Peek_2020-12-28_22-45.gif
Peek_2020-12-28_22-45.gif (36.65 KiB) Viewed 862 times

Next step is cleanup of pegsol.c code and publish here.


P.S:
11,622,136,678 bits set in 64GB 3-3-2-2 file (so many positions can be played to only one peg left):

Code: Select all

$ time ./bwc <3-3-2-2
11622136678

real	16m53.037s
user	16m31.853s
sys	0m21.083s
$

Hash of 64GB file:

Code: Select all

$ time sha256sum 3-3-2-2 
a2483423cc556ac8ff6682edfbf6994ddfda2c9bad99901567a22415fe7e026d  3-3-2-2

real	5m46.089s
user	5m5.330s
sys	0m24.891s
$
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Thu Dec 31, 2020 12:30 am

I am pretty much done with cleaning up pegsol.c for posting here.

But an unexpected opportunity arose with my personal website (stamm-wilbrandt.de).
I am using an old webhosting product that allowed for 6GB webspace.
Minimal current product of my webhoster has 75GB webspace and is even cheaper.
My webspace got upgraded to 75GB sometime in the past.

I upgraded to the next higher hosting product, which does cost 1€/month more than currently, but has 150GB(!!) webspace.
And it includes "Lets Encrypt", so that I do not need to buy an SSL cert for 12€/year as the years before.
So effectively I do pay exactly what I paid until today, but will have 150GB webspace shortly.

Current webspace (75GB) nearly got exhausted today by me uploading "3-3-2-2" board 64GB solution file:
peg.dir.jpg
peg.dir.jpg
peg.dir.jpg (20.01 KiB) Viewed 797 times

So why did I upload that?
Not only for sharing (sha256sum is a2483423cc556ac8ff6682edfbf6994ddfda2c9bad99901567a22415fe7e026d).
As you can see there is "sol2w" executable in "peg" directory as well.


Minimal change for different filename and selecting 3-3-2-2 board:

Code: Select all

$ diff sol2.c sol2w.c
1c1
< /* gcc -O6 -Wall -pedantic -Wextra sol2.c -Wno-long-long -o sol2 */
---
> /* gcc -O6 -Wall -pedantic -Wextra sol2w.c -Wno-long-long -o sol2w */
20c20
< #elif 1
---
> #elif 0

Since clearscreen ansi escape sequence does not work in browser, an empty line is output.
Highligting is done by using 'X' instead of inverted 'o', and no sleep is needed in browser since all solutions are output at once:

Code: Select all

53c53
<   printf("\x1b[2J");
---
>   printf("\n");
58c58
<                    ((N[i][j]==p) ? "\x1b[7mo\x1b[0m" : "o") : " ");
---
>                    ((N[i][j]==p) ? "X" : "o") : " ");
61c61
<   usleep(p==255 ? 900000 : 600000);
---
> /*  usleep(p==255 ? 900000 : 600000); */

Finally filename has to be changed as well:

Code: Select all

116c116
<   assert( (src=fopen("French","rb")) );
---
>   assert( (src=fopen("3-3-2-2","rb")) );
$

This is simple cgi-bin Perl script calling sol2w:

Code: Select all

#!/usr/bin/perl

print "Content-type: text/html; charset=UTF-8\n\n";

$input=$ENV{QUERY_STRING};
if ($input eq "")  { $input = "1FFDFFFFFF"; }

print "<pre>";
print `cd /var/www/vhosts/web..............dogado.de/httpdocs/peg; ./sol2w $input`;
print "</pre>";

I never have thought that I could do such computations (backed by 64GB data file) on my webserver!

Here you can try, these URLs generate solutions for the 5 possible 36peg start positions on 3-3-2-2 board (from last posting):
https://stamm-wilbrandt.de/cgi-bin/sol2w.pl?7FFFFFFFEF
https://stamm-wilbrandt.de/cgi-bin/sol2w.pl?7FFFFDFFFF
https://stamm-wilbrandt.de/cgi-bin/sol2w.pl?7FFFEFFFFF
https://stamm-wilbrandt.de/cgi-bin/sol2w.pl?7FFF7FFFFF
https://stamm-wilbrandt.de/cgi-bin/sol2w.pl?5FFFFFFFFF


Of course you can play on 3-3-2-2 board:
https://stamm-wilbrandt.de/en/xsl-list/ ... 3-2-2.html

And at any position determine the hex encoding of the position (fields are numbered starting with 0, from left to right, top to bottom, add powers of 2 for all fields with peg), and then append that hex number after question mark of above URLs. Not the simplest form of configuration input, but works.


This is <pre>...</pre> output from https://stamm-wilbrandt.de/cgi-bin/sol2w.pl?7FFFFFFFEF:

Code: Select all

...ooo...
...o o...
...ooo...
.oooooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...ooo...
...o o...
...ooo...
.oooXoooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...ooo...
...ooo...
...o o...
.ooo oooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...oXo...
...ooo...
...o o...
.ooo oooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...o o...
...o o...
...ooo...
.ooo oooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...o o...
...o o...
...ooo...
.oXo oooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...o o...
...o o...
...ooo...
.o  ooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...o o...
...X o...
...ooo...
.o  ooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...o o...
...  o...
... oo...
.o oooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...o o...
...  o...
... oX...
.o oooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...o o...
...  o...
...o  ...
.o oooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...o X...
...  o...
...o  ...
.o oooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...o  ...
...   ...
...o o...
.o oooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...o  ...
...   ...
...o o...
.o Xooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...o  ...
...o  ...
...  o...
.o  ooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...X  ...
...o  ...
...  o...
.o  ooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...   ...
...   ...
...o o...
.o  ooooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...   ...
...   ...
...o o...
.o  oXooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...o  ...
.o  o ooo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...o  ...
.o  o oXo
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...o  ...
.o  oo  o
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...o  ...
.o  oX  o
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...o  ...
.o o    o
.oooooooo
.oooooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...o  ...
.o o    o
.oooooooo
.oXoooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...o  ...
.ooo    o
.o oooooo
.o oooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...o  ...
.oXo    o
.o oooooo
.o oooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...o  ...
.o  o   o
.o oooooo
.o oooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...o  ...
.o  o   o
.o oXoooo
.o oooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...oo ...
.o      o
.o o oooo
.o oooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...Xo ...
.o      o
.o o oooo
.o oooooo
...ooo...
...ooo...
.........

...   ...
...  o...
...  o...
.o      o
.o o oooo
.o oooooo
...ooo...
...ooo...
.........

...   ...
...  X...
...  o...
.o      o
.o o oooo
.o oooooo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.o   o  o
.o o oooo
.o oooooo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.o   o  o
.o o oooo
.o oXoooo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.o   o  o
.o o oooo
.oo  oooo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.o   o  o
.o o oooo
.Xo  oooo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.o   o  o
.o o oooo
.  o oooo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.X   o  o
.o o oooo
.  o oooo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.    o  o
.  o oooo
.o o oooo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.    o  o
.  o oooo
.o o oXoo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.    oo o
.  o o oo
.o o o oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.    Xo o
.  o o oo
.o o o oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.      oo
.  o o oo
.o o o oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.      oX
.  o o oo
.o o o oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.     o  
.  o o oo
.o o o oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.     o  
.  o o oX
.o o o oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.     o  
.  o oo  
.o o o oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.     X  
.  o oo  
.o o o oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.        
.  o o   
.o o oooo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.        
.  o o   
.o o oXoo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.        
.  o o   
.o oo  oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.        
.  o o   
.o oX  oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.        
.  o o   
.oo    oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.        
.  o o   
.Xo    oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.        
.  o o   
.  o   oo
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.        
.  o o   
.  o   oX
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.        
.  o o   
.  o  o  
...ooo...
...ooo...
.........

...   ...
...   ...
...   ...
.        
.  o o   
.  o  o  
...ooo...
...ooX...
.........

...   ...
...   ...
...   ...
.        
.  o o   
.  o oo  
...oo ...
...oo ...
.........

...   ...
...   ...
...   ...
.        
.  o X   
.  o oo  
...oo ...
...oo ...
.........

...   ...
...   ...
...   ...
.        
.  o     
.  o  o  
...ooo...
...oo ...
.........

...   ...
...   ...
...   ...
.        
.  o     
.  o  o  
...ooo...
...Xo ...
.........

...   ...
...   ...
...   ...
.        
.  o     
.  o  o  
...ooo...
...  o...
.........

...   ...
...   ...
...   ...
.        
.  o     
.  o  o  
...ooo...
...  X...
.........

...   ...
...   ...
...   ...
.        
.  o     
.  o oo  
...oo ...
...   ...
.........

...   ...
...   ...
...   ...
.        
.  o     
.  o oX  
...oo ...
...   ...
.........

...   ...
...   ...
...   ...
.        
.  o     
.  oo    
...oo ...
...   ...
.........

...   ...
...   ...
...   ...
.        
.  o     
.  oo    
...oX ...
...   ...
.........

...   ...
...   ...
...   ...
.        
.  oo    
.  o     
...o  ...
...   ...
.........

...   ...
...   ...
...   ...
.        
.  oX    
.  o     
...o  ...
...   ...
.........

...   ...
...   ...
...   ...
.        
. o      
.  o     
...o  ...
...   ...
.........

...   ...
...   ...
...   ...
.        
. o      
.  o     
...X  ...
...   ...
.........

...   ...
...   ...
...   ...
.        
. oo     
.        
...   ...
...   ...
.........

...   ...
...   ...
...   ...
.        
. Xo     
.        
...   ...
...   ...
.........

...   ...
...   ...
...   ...
.        
.   o    
.        
...   ...
...   ...
.........
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Thu Dec 31, 2020 10:03 pm

I wanted to get this posted in 2020, shorter than planned, more details later.
I enhanced my peg-solitaire game with a "Cheat" link, that does integrate with the solution presenter from yesterday:
https://stamm-wilbrandt.de/en/xsl-list/peg-solitaire/
peg-solitaire.cheat.jpg
peg-solitaire.cheat.jpg
peg-solitaire.cheat.jpg (52.67 KiB) Viewed 742 times

"English" and "3-3-2-2" boardsb have working "Cheat".
"French" (16GB) will come soon (ran out of webspace after uploading 1GB+64GB yesterday).
"Diamond" (256GB) migh come later, "Wiegleb" (4TB) is unlikely.

Clicking on "Cheat" will present solution in either new tab, or new window when "Shift" is pressed as well.
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Fri Jan 01, 2021 11:15 am

I enhanced Cheat feature a bit further.

When board gets displayed, now the solution presenter is called each time from JavaScript.
In case there is a solution (left), heavy check mark indicator is shown, with "Cheat" link in addition.
In case there is no solution starting from current position, negative squared cross mark is shown (right).
(I created that position using board editor bottom right)
peg-solitaire.cheat.2a.jpg
peg-solitaire.cheat.2a.jpg
peg-solitaire.cheat.2a.jpg (44.54 KiB) Viewed 695 times
The positive/negative indicator allow you to take back a move without looking into cheat solution.
There is no "undo last move" function, but you can use board editor bottom right to undo last move.

There are two more possibilities:
If there has been no solution file computed (or uploaded like 16GB French file), "Info" link is shown.
In case you use board editor to go to a board different to the 5 predefined, nothing is shown.
peg-solitaire.cheat.2b.jpg
peg-solitaire.cheat.2b.jpg
peg-solitaire.cheat.2b.jpg (50.92 KiB) Viewed 695 times



This was the Javascript code piece responsible for drawing new page originally, the work was done in browser XSLT with XML processing:

Code: Select all

  // code for Mozilla, Firefox, Opera, etc.
  else if (document.implementation)
  {
    with (document) { open(); write("<html><body><div id='example'></div></body></html>"); close(); }

    xsltproc = new XSLTProcessor();
    xsltproc.importStylesheet(xsl);
    result = xsltproc.transformToFragment(xml, document);
    document.getElementById("example").appendChild(result);
  }

These lines were just inserted below last appendChild() for adding "Cheat" feature.

New anchor element is created, and computation for determining hex position encoding is started:

Code: Select all

	let a = document.createElement('a');
    a.innerHTML = 'Cheat';
	  i=xmlStr;
	  p=i.substring(i.lastIndexOf('<position>'),i.lastIndexOf('</position>'));
	  rs=p.substring(p.indexOf('<row>'));
	  r='';

For dealing with numbers longer than 2bit, BigInt has to be used.
Determin next field in board XML string encoding:

Code: Select all

	  h=BigInt(0); t=BigInt(1); o=BigInt(1);
	  while (rs.indexOf('/')!=-1)
      {
        rs=rs.substring(rs.indexOf('/')-1);
        c=rs.charAt(0);
        rs=rs.substring(2);
        if (c=='<')  c=rs.charAt(0);
        r=r+c;


Depending on what is found, bit (t) needs to be moved left, and added in case of peg on field:

Code: Select all

        switch (c) {
          case 'f':
          case 'r': break;
          case 'm':
          case 'p': h+=t;
          case 'h': t<<=o; break;
        }
      }

Now anchor URL is set, and it is determined whether one of predefined boards is found:

Code: Select all

    a.href='https://stamm-wilbrandt.de/cgi-bin/sol.'
	found=true;
	switch (t) {
	  case o<<BigInt(33): a.href+='English'; break;
	  case o<<BigInt(37): a.href+='French'; break;
	  case o<<BigInt(39): a.href+='3-3-2-2'; break;
	  case o<<BigInt(41): a.href+='Diamond'; break;
	  case o<<BigInt(45): a.href+='Wiegleb'; break;
      default: found=false;		
	}		
    a.href+='.pl?'+h.toString(16);

Make link opne in new tab/window.
Prepare to send HTTP request against solution presenter:

Code: Select all

	a.setAttribute("target","_blank");
    var req;
    req = new XMLHttpRequest();
    

When HTTP request finished, do what is needed for Cheat feature.
Part 1:

Code: Select all

    req.onreadystatechange = function() {
      if (this.readyState == 4) {
	    if ((this.status == 200) && this.responseText.startsWith("<pre>"))
		{
		  if (!this.responseText.startsWith("<pre><"))
		  {
            var t = document.createTextNode("✅ ");
	        document.getElementById("example").appendChild(t);	  
	        document.getElementById("example").appendChild(a);
		  }


Part 2:

Code: Select all

		  else
		  {
            var t = document.createTextNode("❎ no move sequence with single central peg left");
	        document.getElementById("example").appendChild(t);
		  }
		}
		else if (found)
		{
          a.innerHTML = 'Info';
          document.getElementById("example").appendChild(a);

Send the request:

Code: Select all

		}
      }
    }      
    req.open("GET", a.href, true);
    req.send();


Besides those additions, I had to add one change to the cgi-bin Perl scripts.
I had to return Access-Control-Allow-Origin response header, otherwise cross site origin error happened:

Code: Select all

#!/usr/bin/perl

print "Content-type: text/html; charset=UTF-8\nAccess-Control-Allow-Origin: *\n\n";

$input=$ENV{QUERY_STRING};
if ($input eq "")  { $input = "1FFDFFFFFF"; }

print "<pre>";
print `cd /var/www/vhosts/.../httpdocs/peg; ./sol.3-3-2-2 $input`;
print "</pre>";


Have fun playing "English" and "3-3-2-2" board with valid/invalid indicators (with or without cheating):
https://stamm-wilbrandt.de/en/xsl-list/peg-solitaire
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Sat Jan 02, 2021 10:25 pm

I just added finalized pegsol.c to my gists:
https://gist.github.com/Hermann-SW/91ad ... 7134ab0c4c

In case you are not interested on pegsol.c details, you might want to jump to end of this posting for instruction on how to take back a move on online peg solitaire board:
Peek_2021-01-02_22-59.gif
Peek_2021-01-02_22-59.gif
Peek_2021-01-02_22-59.gif (43 KiB) Viewed 643 times

After cleanup I used uint64_t constants and variables defined inside for loop, "-std=c99" avoided related warnings:

Code: Select all

// gcc -O6 -Wall -pedantic -Wextra -std=c99 pegsol.c -o pegsol 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <assert.h>

These are the board definitions for English/French/3-3-2-2 boards with 33/37/39 fields.
English is the only board that can be computed on any Pi (because next French needs 20GB arrays).
Needed is only 9x9, but initializeing with strings needs space for the trailinng '\0':

Code: Select all

char B[9][9+1]={
#if 1
".........",  /* English */
"...ooo...",
"...ooo...",
".ooooooo.",
".oooxooo.",
".ooooooo.",
"...ooo...",
"...ooo...",
"........."
#elif 0
".........",  /* French */
"...ooo...",
"..ooooo..",
".oooxooo.",
".ooooooo.",
".ooooooo.",
"..ooooo..",
"...ooo...",
"........."
#else
"...ooo...",  /* 3-3-2-2 */
"...ooo...",
"...ooo...",
".oooooooo",
".oooxoooo",
".oooooooo",
"...ooo...",
"...ooo...",
"........."
#endif
};

Function bits called for uint64_t uses 16bit lookup table for efficiently computing number of bits set.
pow2() generates power of 2 as uint64_t:

Code: Select all

unsigned bits16[1<<16];

inline uint64_t pow2(unsigned exp)  { return UINT64_C(1) << exp; }

Since this is called billions (really) of times, being correct for only 48 bits is better (even biggest board Wiegleb with 45 fields would be able to compute -- in case you have a computer with 5TB(!) of free memory for the arrays):

Code: Select all

unsigned bits(uint64_t u) // correct for < pow2(48)
{
  uint16_t *p = (uint16_t*)&u;
#if   __BYTE_ORDER == __LITTLE_ENDIAN
#elif __BYTE_ORDER == __BIG_ENDIAN
  ++p;
#else
#error unsupported endianness
#endif
  return bits16[p[0]] + bits16[p[1]] + bits16[p[2]];
}

"void init_bits16()" just fills array bits16.
The fields from board B[][] are scanned from left to right, top to bottom, and found fields are numbered consecutively in N[][].
M/D are 3/2 bits bitmasks for all possible moves inside 9x9 area, m is the number of moves possible.
A is unit8_t array of size 2^(n-3), storing a bit for each of the 2^n possible positions on n field board (possible/impossible to solve).
In order to not always having to iterate over 2^(n-3) uint8_t values of A, S[old] array of size 2^(n-6) has a 1bit for each A byte with a newly added 1bit allowing for faster iteration over A, S[new] gets 1bits for next round of computation:

Code: Select all

unsigned N[9][9];

unsigned m, cnt, final;
uint64_t M[7*9*2*2];
uint64_t D[7*9*2*2];

uint8_t *A;
uint8_t *S[2];

"void init_moves()" instantiates the move bit patterns for a given board, here is the code for horizontal moves. Fields inside 2nd of two nested loops handles fields [i⁠][j-2..j] on board. Two moves are possible when all three fields are part of board (!=255). This is for increasing the number of pegs by 1, going reverse from x peg position to x+1 position. If M[a]&p!=0 for position p, then a move might be possible. If in addtiotion D[a]&p==0, then two of the fields are empty, and the third non-middle field has a peg, allowing to create new x+1 pegs position p^M[a]:

Code: Select all

...
      if (i>1)
        if (N[i][j]!=255 && N[i-1][j]!=255 && N[i-2][j]!=255)
        {
          M[m]   = pow2(N[i][j])   | pow2(N[i-1][j]) | pow2(N[i-2][j]);
          D[m++] = pow2(N[i][j])   | pow2(N[i-1][j]);
          M[m]   = pow2(N[i][j])   | pow2(N[i-1][j]) | pow2(N[i-2][j]);
          D[m++] = pow2(N[i-1][j]) | pow2(N[i-2][j]);
        }  
...

This macro iterates over all moves for a given position v. v is passed as argument because it is used in code passed as "blk" as well. As described before the first test checks whether move is possible, then va computes new position and executes blk:

Code: Select all

#define forall_possible_moves(v, va, blk)  { uint64_t c=v;   \
  for(unsigned d=0; d<m; ++d)                                \
    if ((c & M[d]) && !(c & D[d]))                           \
    { uint64_t va = c^M[d]; blk }                            \
}

This macro iterates over all bits of array a of size m (done on array S[old] described before). For a set bit, corresponding position in array A is determined in variable v, and blk gets executed:

Code: Select all

#define forall_bits_set(a, m, v, blk)     \
  for(uint64_t j=0; j<m; ++j)             \
    if (a[j])                             \
      for(unsigned k=0; k<8; ++k)         \
        if (a[j] & (1<<k))                \
        { uint64_t v = (j<<3) + k; blk }

After byte l in array A has been computed, the bits with "pgs" pegs need to be traversed. By construction difference pgs-bits(l) is in range 0..3, and the default assert guarantees this. There are only 1 bit for differences 0 and 3, so no for loop is needed. Iterating over 1 bits set positions is easy (1,2,4), iteration of 2bits set positions in 0..7 is tricky (3,5,6). I was not sure whether this code helps at all over just doing "for(b=0; b<8; ++b)", but it reduced computation time a bit:

Code: Select all

#define forall_matching_bits_set(pgs, l, b, blk)  { unsigned b;            \
  switch (pgs - bits(l)) {                                                 \
    case 0:  b=0;                       if (A[l] & (1<<b))  { blk } break; \
    case 1:  for(b=1; b<=4; b<<=1)      if (A[l] & (1<<b))  { blk } break; \
    case 2:  for(b=3; b<7; b+=(2-b/4))  if (A[l] & (1<<b))  { blk } break; \
    case 3:  b=7;                       if (A[l] & (1<<b))  { blk } break; \
    default: assert(!"should not happen"); break;                          \
  }                                                                        \
}

First bits16 array gets initialized, then all possible moves bitmasks get determined, as well as number of fields "cnt" and final position of single peg "final". Then the three big arrays get allocated, and success gets asserted:

Code: Select all

int main()
{
  init_bits16();
  init_moves();
  printf("m=%d  cnt=%d\n",m,cnt);

  assert( (A    = malloc(pow2(cnt-3))) );
  assert( (S[0] = malloc(pow2(cnt-6))) );
  assert( (S[1] = malloc(pow2(cnt-6))) );

Here whole array A gets zeroed, as well as S[old]. Then single bit for "final" position in A gets set, and corresponding bit in S[old] gets set:

Code: Select all

  unsigned old=0;
  memset(A,      0, 1<<(cnt-3));
  memset(S[old], 0, pow2(cnt-6));

  A     [pow2(final)>>3] |= 1<<(pow2(final) % 8);
  S[old][pow2(final)>>6] |= 1<<((pow2(final)>>3) % 8);

This is main iteration, computing all positions with "pegs+1" pegs from all positions with "pegs" pegs. New positions get store in S[new], which gets zeroed initially:

Code: Select all

  for(unsigned pegs=1; pegs<cnt; ++pegs)
  {
    unsigned new=1-old;
    memset(S[new], 0, pow2(cnt-6));

This does the main work, utilizing the three macros defined before. The statements passed as last argument of inner loop add newly found position "n" with pegs+1 bits set in arrays A and S[new]:

Code: Select all

    forall_bits_set(S[old], pow2(cnt-6), l,
      forall_matching_bits_set(pegs, l, b,
        forall_possible_moves((l<<3) + b, n,
          A[n>>3]      |= 1<<(n%8);
          S[new][n>>6] |= 1<<((n>>3) % 8);
        )
      )
    )

At end of main loop, S[new] becomes S[old] for next iteration, and action indicator is printed. After main loop completed, the whole array A ets written to stderr, allowing to call this program with "./pegsol 2>foobar" and see action indicator output on stdout:

Code: Select all

    old = new;
    printf("done(%d)\n",pegs); 
  }

  fwrite(A, pow2(cnt-3), 1, stderr);
    
  return 0;
}


Now that generator that was capable of computing 1GB/16GB/64GB solution files is fully described, I want to clarify on how you can "take back a wrong move using board editor bottom right". The starting position is good, and I did a move that ends in a position that does not allow the game to end completely. After clicking on bottom right suqare icon, editor mode is entered and play icon gets visible. First I removed peg from new position after last move, two clicks are necessary to bring field back. Then clicking on both other fields of last move brings pegs back. Finally clicking play symbol bottom right returnes to play mode:
Peek_2021-01-02_22-59.gif
Peek_2021-01-02_22-59.gif
Peek_2021-01-02_22-59.gif (43 KiB) Viewed 643 times
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Mon Jan 04, 2021 9:17 pm

Webspace on my personal website (https://stamm-wilbrandt.de) got increased to 150GB.
Now there is space for the 16GB French solution file in addition to 1GB English and 64GB 3-3-2-2 board solution files.
I just uploaded French board, and French board solution presenter -- 1GB+16GB+64GB is 81GB in total:
peg-solitaire.81GB.png
peg-solitaire.81GB.png
peg-solitaire.81GB.png (34.28 KiB) Viewed 587 times


French board is different to the other boards:
https://stamm-wilbrandt.de/en/xsl-list/ ... rench.html

There is no single peg left solution with empty field in center start position.
And in addition, there is no solution for any other empty field start position with single peg left on same field.
Start position is with empty field just one below center field.
End position is single peg left just one field above center field, as indicated by leftmost bottom French board icon:
(2,990,375,067 bits set in 16GB French file, that many positions can be played to single peg left on target field)
peg-solitaire.French_different.png
peg-solitaire.French_different.png
peg-solitaire.French_different.png (10.32 KiB) Viewed 587 times


Next board wrt size would be 41 pegs Diamond board, and that needs 320GB memory for the arrays during solution computation.
Currently I do not have access to such a computer (what I have access to is double memory size of current workstation, 192GB).
Even if I would get it computed (perhaps in 4x the time of 3-3-2-2 board, less than 7h?), solution file size for all possible 2^41 positions is 256GB ...
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Thu Jan 07, 2021 7:13 pm

I thought I was done with peg-solitaire, at least with 33/37/39 fields English/French/3-3-2-2 boards.
Knowing the (big) numbers of disticnt positions allowing move sequence ending with single peg on target field is good.
But how many can be reached from start position of a board?
This is the extended message that now is shown in peg-solitaire game, based on the answers to the question:
https://stamm-wilbrandt.de/en/xsl-list/peg-solitaire/
peg-solitaire.extendedInfo.English.jpg
peg-solitaire.extendedInfo.English.jpg
peg-solitaire.extendedInfo.English.jpg (45.69 KiB) Viewed 530 times


So I wrote a program to count those positions that allow for a single peg on target field, and can be reached from starting position:
https://gist.github.com/Hermann-SW/0915 ... 820927ba22

Program reads the 1GB/16GB/64GB solution file completely, because that way all precomputed good positions are marked with 1-bits.
Any search is fine to count, this time I chose DFS (Depth First Search) because it is so much easier because of recursion.
dfs() gets called for 1-bits only, so assert() is OK.
First thing is to set that bit to 0 in order to reduce runtime (when position is tested from another part of dfs search again).
Count variable cnt is initialized to 1 because of this already "found" position:

Code: Select all

uint64_t dfs(uint64_t u, uint8_t *A)
{
  uint64_t cnt=1;

  assert(A[u>>3] & 1<<(u%8));
  A[u>>3] ^= 1<<(u%8);


Again all m moves are tested on whether they are possible for position u.
If so, new position n after doing the move (and reduce the number of pegs by 1 because of top-down) gets computed.
In case there is a 1-bit for n, dfs() gets called recursively, and the count gets increased by number determined.
Finally count value cnt is returned to caller:

Code: Select all

  for(int d=0; d<m; ++d)
  {
    if (!(u & M[d]) && ((u & D[d]) == D[d]))
    {
      uint64_t n = u^(M[d]|D[d]);
      if (A[n>>3] & 1<<(n%8))
        cnt += dfs(n, A);
    }
  }

  return cnt;
}

I did run this for French/English/3-3-2-2 board on workstation, and computations took 8s/3:16min/30:22min.
So I tried English board on Pi400, and it took 40 seconds.
I attached a SSD and copied the 1GB English file and cnt.dfs over, now it took 20 seconds only, not bad:

Code: Select all

pi@raspberrypi400:/media/pi/543e7fdc-3cdc-4ff2-aa12-e8c371ca63b5/home/hermann $ time \
> ./cnt.dfs English 1FFFEFFFF
13428122

real	0m20.455s
user	0m16.286s
sys	0m3.742s
pi@raspberrypi400:/media/pi/543e7fdc-3cdc-4ff2-aa12-e8c371ca63b5/home/hermann $ 

I added to the informational messages of peg-solitaire game.
Percentage is quite different, 1.4%/4.5%/11.8% of all good positions for English/French/3-3-2-2 board are reachable from start:
(the remaining positions can be setup on board using board editor bottom right)
938,181,495 positions on 33 field English board allow for sequence of moves ending with single peg on (white, center) target field. 13,428,122 of those positions can be reached from intial position by sequence of moves.
2,990,375,067 positions on 37 field French board allow for sequence of moves ending with single peg on (white, above center) target field. 134,668,550 of those positions can be reached from intial position by sequence of moves.
11,622,136,678 positions on 39 field 3-3-2-2 board allow for sequence of moves ending with single peg on (white, center) target field. 1,370,219,912 of those positions can be reached from intial position by sequence of moves.

P.S:
In the gist code I had commented out last fwrite() that does save modified array, 1GB for English.
I removed comment and compiled, then did run again.

This is the start of English file in hex:

Code: Select all

$ head --bytes 256 English | od -Ax -tx1 | head -6
000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000010 00 00 00 42 00 00 00 00 00 00 00 00 00 00 00 00
000020 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000030 00 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00
*
000050 00 00 00 00 00 00 18 00 00 00 00 42 00 00 00 00
$ 

Written file with 13,428,122 bits zeroed looks different:

Code: Select all

$ head --bytes 256 erre | od -Ax -tx1
000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
*
000070 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00 00
000080 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
*
000100
$ 

All bits remaining in that file correspond to positions that allow for finish on target field, but are not reachable from start position by sequence of moves. Lets take the very first 1-bit in the file.
4 in byte 0x77 is bit 2 (1<<2), so position encoded is 0x3BA:

Code: Select all

$ bc -ql
ibase=16
obase=10
8*77+2
3BA

I used board editor to setup the position encoded by 3BA, you can see in URL shown while mouse cursor is over "Cheat" link:
peg-solitaire.English.not_reachable_from_start_but_solvable.position.jpg
peg-solitaire.English.not_reachable_from_start_but_solvable.position.jpg
peg-solitaire.English.not_reachable_from_start_but_solvable.position.jpg (21.23 KiB) Viewed 505 times

P.P.S:
Found a machine with 192GB memory, just not enough for 41 peg Diamond board needed 320GB ... :-(

Code: Select all

Installed memory: 201326592 kilobytes
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Sat Jan 09, 2021 4:31 pm

I got temporary access to a machine with 236GB RAM, which does not suffice for 41 field Diamond board.
So I just removed the most bottom field, and to indicate that the board is named "Diamon" with missing last character.
The 160GB for the three arrays did easily fit in that machine.

Very small diff, basically only the new board needed to be added to pegsol.c:
https://gist.github.com/Hermann-SW/91ad ... 7134ab0c4c

Code: Select all

...
> #else
> "....o....",  /* Diamon */
> "...ooo...",
> "..ooooo..",
> ".ooooooo.",
> "ooooxoooo",
> ".ooooooo.",
> "..ooooo..",
> "...ooo...",
> "........."
$

Computation took 95 minutes only and the hash of generated 128GB file "Diamon" is:

Code: Select all

$ time sha256sum Diamon
0a19dcfcf919290de2dee91f01418b7147cda75cf3460d3c71dc58bbc8821c0f  Diamon

real	12m30.015s
user	10m37.022s
sys	0m45.022s
$ 

I did compute all hex values of 40 bits with a single 0-bit, and tested the positions that allowed for solution with single peg on center field:

Code: Select all

$ echo 'obase=16; for(i=39; i>=0; --i) print "# ",i,"\n./sol.Diamon ",\
> 2^40-1-2^i," | head -1\n "' | bc | bash 2>/dev/null
ff7fffffff
fffdffffff
ffffffffbf
$ 

These are the positions encoded:
peg-solitaire.Diamon.initial.jpg
peg-solitaire.Diamon.initial.jpg
peg-solitaire.Diamon.initial.jpg (76.85 KiB) Viewed 483 times
As example, here is solution for the last:

Code: Select all

$ ./sol.Diamon ffffffffbf
ffffffffbf

....o....
...ooo...
..oo oo..
.ooooooo.
ooooooooo
.ooooooo.
..ooooo..
...ooo...
.........

....X....
...ooo...
..oo oo..
.ooooooo.
ooooooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...o o...
..ooooo..
.ooooooo.
ooooooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...o o...
..ooooo..
.oooXooo.
ooooooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...ooo...
..oo oo..
.ooo ooo.
ooooooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...ooo...
..Xo oo..
.ooo ooo.
ooooooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...ooo...
..  ooo..
.ooo ooo.
ooooooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...oXo...
..  ooo..
.ooo ooo.
ooooooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...o o...
..   oo..
.ooooooo.
ooooooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...o o...
..   oo..
.ooooooo.
oooXooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...o o...
.. o oo..
.oo oooo.
ooo ooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...X o...
.. o oo..
.oo oooo.
ooo ooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.ooooooo.
ooo ooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.ooooooo.
oXo ooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.ooooooo.
o  oooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.ooooooo.
o  Xooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...  o...
.. o oo..
.oo oooo.
o   ooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...  o...
.. o oo..
.Xo oooo.
o   ooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...  o...
.. o oo..
.  ooooo.
o   ooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...  o...
.. X oo..
.  ooooo.
o   ooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.   oooo.
o  oooooo
.ooooooo.
..ooooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.   oooo.
o  oooooo
.ooooooo.
..Xoooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.   oooo.
o ooooooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.   oooo.
o oXooooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.   oooo.
oo  ooooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.   oooo.
Xo  ooooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.   oooo.
  o ooooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.   oooo.
  o oXooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.   oooo.
  oo  ooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..   Xo..
.   oooo.
  oo  ooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..    o..
.   o oo.
  oo oooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..    o..
.   o oX.
  oo oooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..    o..
.   oo  .
  oo oooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..    o..
.   oo  .
  oo Xooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  o...
..   oo..
.   o   .
  oo  ooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...  X...
..   oo..
.   o   .
  oo  ooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..    o..
.   oo  .
  oo  ooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..    o..
.   Xo  .
  oo  ooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..    o..
.     o .
  oo  ooo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..    o..
.     o .
  oo  oXo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..    o..
.     o .
  oo o  o
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..    X..
.     o .
  oo o  o
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.       .
  oo oo o
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.       .
  oo Xo o
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.       .
  oo   oo
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.       .
  oo   oX
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.       .
  oo  o  
.o ooooo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.       .
  oo  o  
.o oooXo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.     o .
  oo     
.o ooo o.
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.     o .
  oo     
.o oXo o.
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.     o .
  oo     
.o o  oo.
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.     o .
  oo     
.o o  oX.
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.     o .
  oo     
.o o o  .
.. oooo..
...ooo...
.........

.... ....
...   ...
..     ..
.     o .
  oo     
.o o o  .
.. oooo..
...oXo...
.........

.... ....
...   ...
..     ..
.     o .
  oo     
.o ooo  .
.. o oo..
...o o...
.........

.... ....
...   ...
..     ..
.     o .
  oo     
.o oXo  .
.. o oo..
...o o...
.........

.... ....
...   ...
..     ..
.     o .
  oo     
.o o  o .
.. o oo..
...o o...
.........

.... ....
...   ...
..     ..
.     o .
  oo     
.o o  o .
.. o oX..
...o o...
.........

.... ....
...   ...
..     ..
.     o .
  oo  o  
.o o    .
.. o o ..
...o o...
.........

.... ....
...   ...
..     ..
.     X .
  oo  o  
.o o    .
.. o o ..
...o o...
.........

.... ....
...   ...
..     ..
.       .
  oo     
.o o  o .
.. o o ..
...o o...
.........

.... ....
...   ...
..     ..
.       .
  oo     
.o o  o .
.. o o ..
...o X...
.........

.... ....
...   ...
..     ..
.       .
  oo     
.o o oo .
.. o   ..
...o  ...
.........

.... ....
...   ...
..     ..
.       .
  oo     
.o o oX .
.. o   ..
...o  ...
.........

.... ....
...   ...
..     ..
.       .
  oo     
.o oo   .
.. o   ..
...o  ...
.........

.... ....
...   ...
..     ..
.       .
  oo     
.o oX   .
.. o   ..
...o  ...
.........

.... ....
...   ...
..     ..
.       .
  oo     
.oo     .
.. o   ..
...o  ...
.........

.... ....
...   ...
..     ..
.       .
  oo     
.oo     .
.. o   ..
...X  ...
.........

.... ....
...   ...
..     ..
.       .
  oo     
.ooo    .
..     ..
...   ...
.........

.... ....
...   ...
..     ..
.       .
  oX     
.ooo    .
..     ..
...   ...
.........

.... ....
...   ...
..     ..
.       .
  o      
.oo     .
.. o   ..
...   ...
.........

.... ....
...   ...
..     ..
.       .
  o      
.Xo     .
.. o   ..
...   ...
.........

.... ....
...   ...
..     ..
.       .
  o      
.  o    .
.. o   ..
...   ...
.........

.... ....
...   ...
..     ..
.       .
  o      
.  o    .
.. X   ..
...   ...
.........

.... ....
...   ...
..     ..
.       .
  oo     
.       .
..     ..
...   ...
.........

.... ....
...   ...
..     ..
.       .
  Xo     
.       .
..     ..
...   ...
.........

.... ....
...   ...
..     ..
.       .
    o    
.       .
..     ..
...   ...
.........
$ 
Peek_2021-01-09_17-44.gif
Peek_2021-01-09_17-44.gif
Peek_2021-01-09_17-44.gif (28.41 KiB) Viewed 475 times


I tried to find a position with two empty fields that allows a real game from original 41 field board, but found none:

Code: Select all

$ echo 'obase=16; for(i=39; i>=0; --i) for(j=i-1; j>=0; --j) \
> print "# ",i," ",j,"\n./sol.Diamon ",2^40-1-2^i-2^j," |\
>  head -1\n "' | bc | bash 2>/dev/null
bfffff7fff
bffffffdff
bffffffffe
fbffefffff
ffbfffffef
ffd7ffffff
ffdffffeff
fff7ffffef
fffbfffeff
ffff7f7fff
ffff7ffdff
ffff7ffffe
ffffef7fff
ffffeffdff
ffffeffffe
fffffd7fff
fffffdfdff
fffffdfffe
ffffff7ffb
fffffffdfb
fffffffe7f
fffffffeef
ffffffffcf
fffffffffa
$ 

It is nice that 128GB 40bit solution file was easy to generate on that big RAM machine, but since it is not the solution file of the "real" 41 field Diamond board, I will not try to get it onty my personal webserver like the other 33/37/39 boards.
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Mon Jan 11, 2021 8:16 pm

Ooops, I got notified by my webhosting provider that my website was used by spammers.
And I found that I was responsible, using PERL scripts without input validation and even posting them in this thread ...
It did not take long for spammers to make use of my fault, the added exit line seems to avoid misuse and allows needed use:

Code: Select all

...
$input=$ENV{QUERY_STRING};
if ($input eq "")  { $input = "1FFDFFFFFF"; }

exit 1 if not $input =~ /^[0-9A-F]+$/i;

print "<pre>";
print `cd /var/www/vhosts/web...dogado.de/httpdocs/peg; ./sol.English $input`;
...
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

User avatar
HermannSW
Posts: 3467
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: peg-solitaire solver (all configurations)

Wed Jan 20, 2021 7:40 pm

Still trying to get solutions for 41 field Diamond board from 40 field Diamon board 128GB all configurations file.
From Wikipedia I know that this must be possible, since Diamond board (5) allows for center field survivor:
https://en.wikipedia.org/wiki/Peg_solit ... d_variants
Image


Recently realized that Diamon board data size 128GB is 1Tbit -- 1Tbit (Tera bit) sounds cool:
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/working_with_FPGAs

Return to “C/C++”