https://stamm-wilbrandt.de/en/xsl-list/peg-solitaire/
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)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 (61.42 KiB) Viewed 1009 times
