数独のソルバーを深さ優先で再帰で作ったからそのノリで作ってみました。3x3、4x4、5x5 と一応対応しております。
シャッフルして問題も供給する形にしました。
package main
import (
"fmt"
"math"
"math/rand"
"slices"
"strings"
"time"
)
const goal = "123456780"
func main() {
var count = 7
q := repeatShuffle(count)
size := sqrtInt(len(goal))
fmt.Println("shuffle:", count)
start := time.Now()
count = 10
fmt.Println("count:", count)
l:
checkSlice := []string{q}
checkSlice, ok := calc(checkSlice, 1, count)
if !ok {
count += 10
fmt.Println("count:", count)
goto l
} else {
t := time.Since(start)
fmt.Println("q.")
for i := range size {
fmt.Println("q", q[i*size:(i+1)*size])
}
fmt.Println("\nans.")
for i, c := range checkSlice {
for j := range size {
fmt.Println(i, c[j*size:(j+1)*size])
}
fmt.Println()
}
fmt.Println(t)
}
}
func sqrtInt(i int) int {
return int(math.Sqrt(float64(i)))
}
func calc(checkSlice []string, l int, count int) ([]string, bool) {
size := sqrtInt(len(goal))
if l > count {
return checkSlice, false
}
q := strings.Split(checkSlice[len(checkSlice)-1], "")
index := slices.Index(q, "0")
rows, columns := index/size, index%size
movementSlice := []int{}
if rows == 0 {
movementSlice = append(movementSlice, 2)
} else if rows == size-1 {
movementSlice = append(movementSlice, 0)
} else {
movementSlice = append(movementSlice, 0, 2)
}
if columns == 0 {
movementSlice = append(movementSlice, 1)
} else if columns == size-1 {
movementSlice = append(movementSlice, 3)
} else {
movementSlice = append(movementSlice, 1, 3)
}
for _, move := range movementSlice {
if len(checkSlice) > l {
checkSlice = checkSlice[:l]
}
after := -1
if move == 0 {
after = index - size
} else if move == 1 {
after = index + 1
} else if move == 2 {
after = index + size
} else if move == 3 {
after = index - 1
}
q[index] = q[after]
q[after] = "0"
s := strings.Join(q, "")
if slices.Contains(checkSlice, s) {
q[after] = q[index]
q[index] = "0"
continue
}
checkSlice = append(checkSlice, s)
if s == goal {
return checkSlice, true
}
checkSlice, ok := calc(checkSlice, l+1, count)
if ok {
return checkSlice, true
}
q[after] = q[index]
q[index] = "0"
}
return checkSlice, false
}
func repeatShuffle(count int) string {
q := strings.Split(goal, "")
prev := 0
for range count {
q, prev = shuffle(q, prev)
}
return strings.Join(q, "")
}
func shuffle(s []string, prev int) ([]string, int) {
size := sqrtInt(len(goal))
index := slices.Index(s, "0")
rows, columns := index/size, index%size
movementSlice := []int{}
if rows == 0 {
movementSlice = append(movementSlice, 2)
} else if rows == size-1 {
movementSlice = append(movementSlice, 0)
} else {
movementSlice = append(movementSlice, 0, 2)
}
if columns == 0 {
movementSlice = append(movementSlice, 1)
} else if columns == size-1 {
movementSlice = append(movementSlice, 3)
} else {
movementSlice = append(movementSlice, 1, 3)
}
i := (prev + 2) % 4
ii := slices.Index(movementSlice, i)
if ii > -1 {
movementSlice = slices.Delete(movementSlice, ii, ii+1)
}
move := movementSlice[rand.Intn((len(movementSlice)))]
after := -1
if move == 0 {
after = index - size
} else if move == 1 {
after = index + 1
} else if move == 2 {
after = index + size
} else if move == 3 {
after = index - 1
}
s[index] = s[after]
s[after] = "0"
return s, move
}
表示は
shuffle: 7
count: 10
q.
q 412
q 753
q 806
ans.
0 412
0 753
0 806
1 412
1 753
1 086
2 412
2 053
2 786
3 012
3 453
3 786
4 102
4 453
4 786
5 120
5 453
5 786
6 123
6 450
6 786
7 123
7 456
7 780
556.5µs
こんな感じで。
試しにやってみたスマホアプリのくじ付きスライドパズルは僕の環境だと3x3は時間内に回答が出て入力できるけれど、4x4は時間内に回答が出ませんでした。
