Fifteen Puzzle Optimal Solver

depth

states

depth

states

0

1

41

83,099,401,368

1

2

42

115,516,106,664

2

4

43

156,935,291,234

3

10

44

208,207,973,510

4

24

45

269,527,755,972

5

54

46

340,163,141,928

6

107

47

418,170,132,006

7

212

48

500,252,508,256

8

446

49

581,813,416,256

9

946

50

657,076,739,307

10

1,948

51

719,872,287,190

11

3,938

52

763,865,196,269

12

7,808

53

784,195,801,886

13

15,544

54

777,302,007,562

14

30,821

55

742,946,121,222

15

60,842

56

683,025,093,505

16

119,000

57

603,043,436,904

17

231,844

58

509,897,148,964

18

447,342

59

412,039,723,036

19

859,744

60

317,373,604,363

20

1,637,383

61

232,306,415,924

21

3,098,270

62

161,303,043,901

22

5,802,411

63

105,730,020,222

23

10,783,780

64

65,450,375,310

24

19,826,318

65

37,942,606,582

25

36,142,146

66

20,696,691,144

26

65,135,623

67

10,460,286,822

27

116,238,056

68

4,961,671,731

28

204,900,019

69

2,144,789,574

29

357,071,928

70

868,923,831

30

613,926,161

71

311,901,840

31

1,042,022,040

72

104,859,366

32

1,742,855,397

73

29,592,634

33

2,873,077,198

74

7,766,947

34

4,660,800,459

75

1,508,596

35

7,439,530,828

76

272,198

36

11,668,443,776

77

26,638

37

17,976,412,262

78

3,406

38

27,171,347,953

79

70

39

40,271,406,380

80

17

40

58,469,060,820