====== "English Sixteen" puzzle ======
https://www.jaapsch.net/puzzles/swappegs.htm
{{pajek:data:pics:ang16.png?500}} {{pajek:data:pics:ang16sol.png?240}}
# https://rdrr.io/github/42n4/dmr.util/src/R/r-utility-binary-integer.R
## convert an integer number to a binary vector, assuming the specified maximum value to determine t
int2binvec <- function(v, max=255) { as.integer(intToBits(v))[1:(floor(log2(max))+1)] }
## convert a binary vector to an integer number
binvec2int <- function(v) { packBits(as.integer(c(v, rep(0, 32-length(v)%%32))), type="i") }
> r <- 3; n <- 5
> a <- 1:r
> i <- r; s <- 0
> while (a[1]<=n-r+1) {
+ s <- s+1
+ while (i>0 && a[i]==n-r+i) i <- i-1
+ cat(s,":",a,"\n")
+ if(i<=0) break
+ a[i] <- a[i] + 1
+ while (i20) break
+ }
1 : 1 2 3
2 : 1 2 4
3 : 1 2 5
4 : 1 3 4
5 : 1 3 5
6 : 1 4 5
7 : 2 3 4
8 : 2 3 5
9 : 2 4 5
10 : 3 4 5
> setwd("C:/Users/vlado/work2/ang16")
> cat("started:",as.character(Sys.time()),"\n")
> T <- matrix(0,nrow=9,ncol=9)
> T[3:5,3:5] <- 1:9; T[5:7,5:7] <- 9:17
> rc <- which(T>0,arr.ind = TRUE)
> net <- file("eng16.net","w")
> lam <- 0; M <- 2**17
> r <- 8; n <- 17
> a <- 1:r
> i <- r; comb <- 0; edge <- 0
> while (a[1]<=n-r+1) {
+ comb <- comb+1
+ while (i>0 && a[i]==n-r+i) i <- i-1
+ # use combination a
+ C <- rep(0,17); C[a] <- 1
+ K <- setdiff(1:17,a)
+ for(k in K){
+ tk <- rc[k,]
+ lab <- k*M + binvec2int(C)
+ lam <- max(lam,lab)
+ for(s in 1:8){
+ ts <- tk+d[s,]
+ is <- T[ts[1],ts[2]]
+ if(is > 0){
+ Cs <- C; Cs[k] <- C[is]; Cs[is] <- 0
+ las <- is*M + binvec2int(Cs)
+ lam <- max(lam,las); edge <- edge+1
+ cat(lab,las,1+(s>4),"\n",file=net)
+ }
+ }
+ }
+ # end use
+ if(i<=0) break
+ a[i] <- a[i] + 1
+ while (i close(net)
> cat("comb =",comb," edges =",edge," max =",lam,"\n")
> cat("finished:",as.character(Sys.time()),"\n")
started: 2022-10-02 23:27:48
comb = 24310 edges = 978120 max = 2293504
finished: 2022-10-02 23:28:22
> for(over in 0:1)
+ for(move in 0:1)
+ for(color in 0:1)
+ for(direc in 0:3) {
+ rel <- ((over*2+move)*2+color)*4+direc
+ cat(over,move,color,direc,":",rel,"\n")
+ }
0 0 0 0 : 0
0 0 0 1 : 1
0 0 0 2 : 2
0 0 0 3 : 3
0 0 1 0 : 4
0 0 1 1 : 5
0 0 1 2 : 6
0 0 1 3 : 7
0 1 0 0 : 8
0 1 0 1 : 9
0 1 0 2 : 10
0 1 0 3 : 11
0 1 1 0 : 12
0 1 1 1 : 13
0 1 1 2 : 14
0 1 1 3 : 15
1 0 0 0 : 16
1 0 0 1 : 17
1 0 0 2 : 18
1 0 0 3 : 19
1 0 1 0 : 20
1 0 1 1 : 21
1 0 1 2 : 22
1 0 1 3 : 23
1 1 0 0 : 24
1 1 0 1 : 25
1 1 0 2 : 26
1 1 0 3 : 27
1 1 1 0 : 28
1 1 1 1 : 29
1 1 1 2 : 30
1 1 1 3 : 31
==============================================================================
3. Extracting N2 according to C1 [1-*] (218790)
==============================================================================
Number of vertices (n): 218790
----------------------------------------------------------
Arcs Edges
----------------------------------------------------------
Number of lines with value=1 0 308880
Number of lines with value#1 0 180180
----------------------------------------------------------
Total number of lines 0 489060
----------------------------------------------------------
Number of loops 0 0
Number of multiple lines 0 0
----------------------------------------------------------
Average Degree = 4.47058824
==============================================================================
Searching paths
==============================================================================
Working...
Distance is: 46.0000
Time spent: 0:00:00
==============================================================================
Searching paths
==============================================================================
Working...
Distance is: 46.0000.
Time spent: 0:00:00
==============================================================================
6. All shortest Paths (lines) in N3 from 102961 to 115830 (15152)
==============================================================================
Number of vertices (n): 15152
----------------------------------------------------------
Arcs Edges
----------------------------------------------------------
Number of lines with value=1 0 8264
Number of lines with value#1 0 10592
----------------------------------------------------------
Total number of lines 0 18856
----------------------------------------------------------
Number of loops 0 0
Number of multiple lines 0 0
----------------------------------------------------------
Average Degree = 2.48891235
==============================================================================
Searching paths
==============================================================================
Working...
Distance is: 72.0000
Time spent: 0:00:06
==============================================================================
Saving network to file --- C:\Users\vlado\work2\ang16\pathw46.net
==============================================================================
Time spent: 0:00:00
> state <- function(m,lab){
+ D <- matrix(" ",nrow=9,ncol=9)
+ pos <- lab%/%M; a <- int2binvec(lab%%M,max=M-1)
+ for(s in 1:17) D[rc[s,1],rc[s,2]] <- a[s]
+ D[rc[pos,1],rc[pos,2]] <- "*"
+ cat("\n",m,":",pos,lab,"\n")
+ for(s in 3:7) cat(paste(D[s,3:7],sep=""),"\n")
+ }
> S<-c(1179903,1310975,1049215,1180287,1573503,789087,658031,1051247,920239,
+ 1182383,1968815,2099887,1345711,1738927,1609903,825487,432299,1218731,
+ 2005163,1626283,841867,579747,972963,1235107,1497251,1890467,1634467,
+ 850051,1243267,1374339,1112579,326273,195202,981634,1243778,1505922,
+ 2292354,2194050,1439874,1178114,391808,522880,1309312,1571456,1440896,
+ 1179136,1310208)
> m <- 0
> for(lab in S) {m <- m+1; state(m,lab)}
1 : 9 1179903 13 : 10 1345711 25 : 11 1497251 37 : 17 2292354
1 1 1 1 1 0 1 0 0 0 0 0
1 1 1 1 0 1 1 0 1 1 0 1
1 1 * 0 0 1 1 0 1 0 0 1 0 1 1 0 0 0 1 1
0 0 0 * 0 1 0 1 1 1 1 1
0 0 0 0 0 0 * 0 0 0 1 *
2 : 10 1310975 14 : 13 1738927 26 : 14 1890467 38 : 16 2194050
1 1 1 1 1 0 1 0 0 0 0 0
1 1 1 1 0 1 1 0 1 1 0 1
1 1 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 0 1 1
* 0 0 0 * 1 0 1 1 1 1 *
0 0 0 0 0 0 0 * 0 0 1 1
3 : 8 1049215 15 : 12 1609903 27 : 12 1634467 39 : 10 1439874
1 1 1 1 1 0 1 0 0 0 0 0
1 1 * 1 0 1 1 0 1 1 0 1
1 1 0 0 0 1 1 0 * 0 0 1 0 * 1 0 0 0 1 1
1 0 0 0 1 1 0 1 1 * 1 1
0 0 0 0 0 0 0 1 0 0 1 1
4 : 9 1180287 16 : 6 825487 28 : 6 850051 40 : 8 1178114
1 1 1 1 1 0 1 0 0 0 0 0
1 1 0 1 0 1 1 0 1 1 0 *
1 1 * 0 0 1 * 0 1 0 0 * 0 1 1 0 0 0 1 1
1 0 0 0 1 1 0 1 1 1 1 1
0 0 0 0 0 0 0 1 0 0 1 1
5 : 12 1573503 17 : 3 432299 29 : 9 1243267 41 : 2 391808
1 1 1 1 1 0 1 0 0 0 0 0
1 1 0 1 0 1 1 0 1 * 0 1
1 1 0 * 0 * 1 0 1 0 0 0 * 1 1 0 0 0 1 1
1 0 0 0 1 1 0 1 1 1 1 1
0 0 0 0 0 0 0 1 0 0 1 1
6 : 6 789087 18 : 9 1218731 30 : 10 1374339 42 : 3 522880
1 1 1 1 1 0 1 0 0 0 0 0
1 1 0 1 0 1 1 0 1 0 0 1
1 * 0 1 0 0 1 * 1 0 0 0 0 1 1 * 0 0 1 1
1 0 0 0 1 1 * 1 1 1 1 1
0 0 0 0 0 0 0 1 0 0 1 1
7 : 5 658031 19 : 15 2005163 31 : 8 1112579 43 : 9 1309312
1 1 1 1 1 0 1 0 0 0 0 0
1 * 0 1 0 1 1 0 * 0 0 1
1 1 0 1 0 0 1 0 1 * 0 0 0 1 1 0 0 * 1 1
1 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 0 0 1 1
8 : 8 1051247 20 : 12 1626283 32 : 2 326273 44 : 11 1571456
1 1 1 1 1 0 1 0 0 0 0 0
1 0 * 1 0 1 * 0 1 0 0 1
1 1 0 1 0 0 1 0 * 1 0 0 0 1 1 0 0 0 1 1
1 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 0 * 1 1
9 : 7 920239 21 : 6 841867 33 : 1 195202 45 : 10 1440896
1 1 * 1 1 0 * 0 0 0 0 0
1 0 1 1 0 1 1 0 1 0 0 1
1 1 0 1 0 0 * 0 1 1 0 0 0 1 1 0 0 0 1 1
1 0 0 0 1 1 1 1 1 * 1 1
0 0 0 0 0 0 0 1 0 1 1 1
10 : 9 1182383 22 : 4 579747 34 : 7 981634 46 : 8 1179136
1 1 0 1 * 0 0 0 * 0 0 0
1 0 1 1 0 1 1 0 1 0 0 *
1 1 * 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 1 1
1 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 0 1 1 1
11 : 15 1968815 23 : 7 972963 35 : 9 1243778 47 : 9 1310208
1 1 0 1 0 * 0 0 0 0 0 0
1 0 1 1 0 1 1 0 1 0 0 0
1 1 0 1 * 0 1 0 1 1 0 0 * 1 1 0 0 * 1 1
1 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 0 1 1 1
12 : 16 2099887 24 : 9 1235107 36 : 11 1505922
1 1 0 1 0 0 0 0 0
1 0 1 1 0 1 1 0 1
1 1 0 1 0 0 1 * 1 1 0 0 0 1 1
1 0 * 0 1 1 1 1 1
0 0 0 0 0 0 * 1 0
- http://www.robspuzzlepage.com/jumping.htm
- https://www.mathematik.ch/puzzle/SixteenPuzzle/
- https://proofwiki.org/wiki/Henry_Ernest_Dudeney/Puzzles_and_Curious_Problems
- https://proofwiki.org/wiki/Book:Books#Recreational_Mathematics
- https://sites.google.com/site/boardandpieces/list-of-games/fore-and-aft-puzzle
- Anany Levitin and Maria Levitin: Algorithmic Puzzles
- Sam Loyd's Cyclopedia of 5000 Puzzles, Tricks, and Conundrums. Sam Loyd. 1914.
-