Problem skoczka szachowego

Czym jest problem skoczka szachowego? To problem dość prosty do zrozumienia, mianowicie skoczek (koń) szachowy musi przejść całą (kwadratową) planszę szachownicy, stając na każdym polu tylko jeden raz oraz nie wychodząc poza szachownicę.

Do napisania tego programu zastosowany język stworzony w 2012 roku przez firmę Google, to jest język Go. Jest to szybki i prosty w użyciu język, dlatego jest on idealnym rozwiązaniem do tego celu. Sposobem na rozwiązanie tego zadania jest iteracja przez każdy możliwy ruch skoczka szachowego. To rozwiązanie działa, ale istnieje pewien problem.

Mianowicie, program sprawdza każdy dostępny ruch, bez użycia priorytetów oraz nie sortując kolejki. Brute-force to sposób na znalezienie rozwiązania. Jednak przy większych planszach (a nawet przy planszach standardowych 8×8) może to powodować pewne przeciążenia i powolne znajdowanie możliwości.

Jednym z głównych wad tego rozwiązania (jeżeli oczywiście chodzi o szybkość) jest backtracking, czyli funkcja pozwalająca programowi cofnąć ruch, jeżeli ten się zablokował. Przez to algorytm musiałby iterować przez te same pola niesamowicie wiele razy. Co gorsza jest ponad 19 trylionów rozwiązań dla tego problemu (i jeszcze więcej możliwych ruchów). Fakt ten jeszcze bardziej spowalnia działanie programu opartego na Brute-force (praktycznie robi go niemożliwym do rozwiązania).

Oprócz iteracji, innym sposobem na rozwiązanie problemu skoczka szachowego jest Algorytm Warndorff-a. Założenia algorytmu są proste. Skanując dostępne ruchy, ma on wybrać ruch, po którym będzie najmniej dostępnych ruchów.

Dodatkowo w notacji dużego O, Algorytm Warndorff-a ma O(n^2) złożoności obliczeniowej w porównaniu do metody z Brute-force-em która ma złożoność obliczeniową o wartości O(8(n2)).

Zostały zadeklarowane wszystkie potrzebne zmienne:

1 // Deklaracja potrzebnych globalnych zmiennych
2 var x int
3 var y int
4 var plansza [ ][ ]int
5 var NextXmove, NextYMove int
6 var n int

7 func main() {

8 var input string

9 // Pobieranie od użytkownika wymiaru planszy
10 fmt.Print(„Podaj wymiar planszy: „)
11 fmt.Scan(&input)

12 var err error
13 n, err = strconv.Atoi(input)
14 if err != nil {
15 fmt.Println(„Nie podałeś liczby!”)
16 return
17 }

18 // Utworzenie planszy
19 plansza = make([ ][ ]int, n)
20 for i := range plansza {
21 plansza[i] = make([ ]int, n)
22 }

23 // Pobieranie od użytkownika pozycji skoczka
24 fmt.Print(„Podaj pozycję skoczka x: „)
25 fmt.Scan(&input)
26 x, err = strconv.Atoi(input)
27 if err != nil {
28 fmt.Println(„Nie podałeś liczby!”)
29 return
30 }

31 // Pobieranie od użytkownika pozycji skoczka
32 fmt.Print(„Podaj pozycję skoczka y: „)
33 fmt.Scan(&input)

34 y, err = strconv.Atoi(input)
35 if err != nil {
36 fmt.Println(„Nie podałeś liczby!”)
37 return
38 }

39 tura := 1
40 fmt.Println(„Plansza:”)
41 answer := Warnsdorff(n, plansza, [2]int{x, y}, tura)

42 // Wypianie końcowego wyniku
43 for _, row := range answer {
44 fmt.Println(row)
45 }
46 }

Poniższa funkcja, która podlicza dostępne ruchy z danej pozycji:

1 func count_moves(plansza [ ][ ]int, position [2]int, n int) int {
2 // tablice dostępnych ruchów
3 Ymoveset := [8]int{-1, 1, 2, 2, –2, –2, –1, 1}
4 Xmoveset := [8]int{-2, –2, –1, 1, –1, 1, 2, 2}
5 counter := 0
6 for i := 1; i <= 8; i++ {
7 // Deklaracja następnej pozycji w kolejce na podstawie starej pozycji i dostępnych ruchów
8 NextXmove := position[0] + Xmoveset[i–1]
9 NextYmove := position[1] + Ymoveset[i–1]
10 // Jeżeli można wykonać ruch, podlicz go
11 if NextXmove <= n && NextXmove >= 1 && NextYmove <= n && Nex12 tYmove >= 1 && plansza[NextYmove–1] [NextXmove–1] == 0 {
13 counter++
14 }
15 }
16 return counter
17 }

Następna funkcja, która jest “sercem” całego algorytmu.

W poniższym kodzie zastosowano rekurencję ale jest też możliwość użycia iteracji (iterując przez liczbę maksymalnych ruchów, w tym przypadku 8*8=64).

1 func (n int, Warnsdorff plansza [][]int, position [2]int, tura int)[][]in{
2 // Jeżeli liczba wykonanych ruchów równa się liczbie wszystkich pól planszy zwróć rozwiązaną planszę
3 if tura == n*n {
4 plansza[position[1]-1][position[0]-1] = tura
5 return plansza
6 }
7 // Największa liczba 64 bitowa
8 min_counter := math.MaxInt
9 // tablice dostępnych ruchów
10 Ymoveset := [8]int{-1, 1, 2, 2, –2, –2, –1, 1}
11 Xmoveset := [8]int{-2, –2, –1, 1, –1, 1, 2, 2}
12 // Zaznaczenie w komórce na której skoczek się znajduję, który to jest ruch
13 plansza[position[1]-1][position[0]-1] = tura
14 for i := 1; i <= 8; i++ {
15 // tymczasowe wartości x i y
16 temp_x := position[0] + Xmoveset[i–1]
17 temp_y := position[1] + Ymoveset[i–1]
18 // liczba możliwych ruchów dla tymczasowych pozycji
19 count := count_moves(plansza, [2]int{temp_x, temp_y}, n)
20 // Sprawdzenie czy ruch można wykonać
21 if temp_x <= n && temp_x >= 1 && temp_y <= n && temp_y >= 1 && plansza[temp_y–1][temp_x–1] == 0 {
22 // Jeżeli liczba możliwych ruchów jest większa od najnowszej minimalnej liczby możliwych ruchów nadpisz pozycję i NOWE tymczasowe pozycję
23 if count < min_counter {
24 min_counter = count
25 // tymczasowe NOWE pozycje skoczka
26 NextXmove = temp_x
27 NextYMove /span>= temp_y
28 }
29 } else {
30 continue
31 }

32 }
33 // Zmiana pozycji skoczka
34 position[0] = NextXmove
35 position[1] = NextYMove
36 // Inkrementacja tury
37 tura++
38 Warnsdorff(n, plansza, position, tura)
39 return plansza
40 }

Przykładowe rozwiązanie

Zrzut ekranu terminala, gdzie program wypisuję tablice w terminalu, liczby w nich oznaczają kolejny ruch (1 to jest pozycja startowa skoczka, 64 to pozycja końcowa).

Zrzut ekranu terminala, gdzie program wypisuję tablice w terminalu, liczby w nich oznaczają kolejny ruch (1 to jest pozycja startowa skoczka, 25 to pozycja końcowa).

Cały kod…

1 package main
2 import (
3 „fmt”
4 „math”
5 „strconv”
6 )

7 var x int
8 var y int
9 var plansza [][]int
10 var n int
11 var NextXmove, NextYMove int

12 func main( ) {

13 var input string

14 fmt.Print(„Podaj wymiar planszy: „)
15 fmt.Scan(&input)

16 var err error
17 n, err = strconv.Atoi(input)
18 if err != nil {
19 fmt.Println(„Nie podałeś liczby!”)
20 return
21 }

22 plansza = make([ ][ ]int, n)
23 for i := range plansza {
24 plansza[ i ] = make([ ]int, n)
25 }

26 fmt.Print(„Podaj pozycję skoczka x: „)
27 fmt.Scan(&input)
28 x, err = strconv.Atoi(input)
29 if err != nil {
30 fmt.Println(„Nie podałeś liczby!”)
31 return
32 }

33 fmt.Print(„Podaj pozycję skoczka y: „)
34 fmt.Scan(&input)

35 y, err = strconv.Atoi(input)
36 if err != nil {
37 fmt.Println(„Nie podałeś liczby!”)
38 return
39 }
40 tura := 1
41 fmt.Println(„Plansza:”)
42 answer := Warnsdorff(n, plansza, [2]int{x, y}, tura)
43 for _, row := range answer {
44 fmt.Println(row)
45 }
46 }
47 func count_moves(plansza [][]int, position [2]int, n int) int {
48 Ymoveset := [8]int{-1, 1, 2, 2, –2, –2, –1, 1}
49 Xmoveset := [8]int{-2, –2, –1, 1, –1, 1, 2, 2}
50 counter := 0
51 for i := 1; i <= 8; i++ {
52 NextXmove := position[0] + Xmoveset[i–1]
53 NextYmove := position[1] + Ymoveset[i–1]
54 if NextXmove <= n && NextXmove >= 1 && NextYmove <= n && Nex55 tYmove >= 1 && plansza[NextYmove–1][NextXmove–1] == 0 {
56 counter++
57 }
58 }
59 return counter
60 }
61 func Warnsdorff(n int, plansza [ ][ ]int, position [2]int, tura int) [ ][ ]int {
62 if tura == n*n {
63 plansza[position[1]-1][position[0]-1] = tura
64 return plansza
65 }
66 min_counter := math.MaxInt

67 Ymoveset := [8]int{-1, 1, 2, 2, –2, –2, –1, 1}
68 Xmoveset := [8]int{-2, –2, –1, 1, –1, 1, 2, 2}
69 plansza[position[1]-1][position[0]-1] = tura
70 for i := 1; i <= 8; i++ {
71 temp_x := position[0] + Xmoveset[i–1]
72 temp_y := position[1] + Ymoveset[i–1]
73 count := count_moves(plansza, [2]int{temp_x, temp_y}, n)
74 if temp_x <= n && temp_x >= 1 && temp_y <= n && temp_y >= 1 && plansza[temp_y–1][temp_x–1] == 0 {
75 if count < min_counter {
76 min_counter = count
77 NextXmove = temp_x
78 NextYMove = temp_y
79 }
80 } else {
81 continue
82 }
83 }
84 position[0] = NextXmove
85 position[1] = NextYMove
86 tura++
87 Warnsdorff(n, plansza, position, tura)
88 return plansza
89 }

Autor: Piotr Łopatecki