【golang】8puzzle のソルバーを再帰で作ってみた

数独のソルバーを深さ優先で再帰で作ったからそのノリで作ってみました。3x3、4x4、5x5 と一応対応しております。

シャッフルして問題も供給する形にしました。

package main

import (
	"fmt"
	"math"
	"math/rand"
	"slices"
	"strings"
	"time"
)

const goal = "123456780"

// const goal = "123456789abcdef0"

// const goal = "123456789abcdefghijklmno0"

func main() {
	// fmt.Println(len(goal))

	// パズルをシャッフルする回数
	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

	// 0を動かす方向　上右下左　0123
	// 移動できる方向のスライスを作る
	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
		// 0を動かす方向　上右下左　0123
		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

	// 0を動かす方向　上右下左　0123
	// 移動できる方向のスライスを作る。
	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
	// 0を動かす方向　上右下左　0123
	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
}

表示は

こんな感じで。

試しにやってみたスマホアプリのくじ付きスライドパズルは僕の環境だと3x3は時間内に回答が出て入力できるけれど、4x4は時間内に回答が出ませんでした。

19日に更新してた

アフィリエイトはないよ

【golang】8puzzle のソルバーを再帰で作ってみた