Stack Overflow
Stack Overflow

Questions tagged [sliding-tile-puzzle]

For algorithm or programming questions about sliding puzzles (such as the 8-puzzle or 15-puzzle), where the player is challenged to slide randomized, numbered tiles along certain routes on a board in order to arrive at a certain end configuration. There is one tile missing, in order to facilitate movement.

For algorithm or programming questions about sliding puzzles, such as the 8-puzzle or 15-puzzle, which challenge the player to slide randomized, numbered tiles along the playing surface in order to arrive at a certain end configuration. There is one tile missing, in order to facilitate movement of other tiles across the board.

Commonly, such puzzles are solved with an A* algorithm.

166 questions
33
votes
1 answer

How many possible states does the 8-puzzle have?

The classical 8-puzzle belongs to the family of sliding blocks. My book (Artificial intelligence A modern approach by Stuart Russell and peter Norwig) says that the 8-puzzle has 9!/2 possible states. But WHY the /2 ? How do you get this?
Ghost
  • 1,777
  • 6
  • 31
  • 44
19
votes
6 answers

What can be the efficient approach to solve the 8 puzzle problem?

The 8-puzzle is a square board with 9 positions, filled by 8 numbered tiles and one gap. At any point, a tile adjacent to the gap can be moved into the gap, creating a new gap position. In other words the gap can be swapped with an adjacent…
Ravindra S
  • 6,302
  • 12
  • 70
  • 108
8
votes
3 answers

Solving 8-Puzzle using DFS

I am looking for code in java that implement DFS and BFS for the 8-puzzle game by given initial state : 1 2 3 8 0 4 7 6 5 and Goal state 2 8 1 0 4 3 7 6 5 I need to print the solution path from initial to goal state (Not done yet) This is the code…
RK2015
  • 397
  • 1
  • 3
  • 15
8
votes
3 answers

8 puzzle: Solvability and shortest solution

I have built a 8 puzzle solver using Breadth First Search. I would now want to modify the code to use heuristics. I would be grateful if someone could answer the following two questions: Solvability How do we decide whether an 8 puzzle is solvable ?…
Ranjith
  • 1,623
  • 3
  • 21
  • 34
8
votes
2 answers

Manhattan distance in A*

I am implementing a NxN puzzle solver using A* search algorithm and using Manhattan distance as a heuristic and I've run into a curious bug (?) which I can't wrap my head around. Consider these puzzles (0 element being blank space): (initial) 1 0…
quantum
  • 3,000
  • 5
  • 41
  • 56
6
votes
2 answers

Creating a tree without duplicates

I am trying to create a tree with the different possible states of the well-known sliding puzzle In case you don't know it, it's the one like: [3 5 2] [4 1] [8 6 7] Where you have to make it like this: [1 2 3] [4 5 6] [7 8 ] Basically, every…
Jahir Fiquitiva
  • 1,459
  • 3
  • 23
  • 47
5
votes
3 answers

5x5 Sliding Puzzle Fast & Low-Move Solution

I am trying to find a way to programmatically solve a 24-piece sliding puzzle in a reasonable amount of time and moves. Here is an example of the solved state in the puzzle I am describing: I have already found that the IDA* algorithm works fairly…
Bob Smith
  • 220
  • 4
  • 21
5
votes
2 answers

Check if 15 puzzle is solvable

I'm trying to test whether a 15 puzzle is solvable. I wrote a method which is working for most puzzles, but for some not. For example this puzzle can be solved with two moves (0, 11), (0, 12) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 11, 13, 14, 15,…
Eknoes
  • 349
  • 4
  • 6
  • 17
5
votes
2 answers

What is wrong with my A* search for 8-Puzzle?

I am trying to use A* search with these heuristics to solve 8-Puzzle: - h1: number of misplaced tiles - h2: total manhattan distance - h3: sum of the above The moving tile is known as 0. My goal is to solve these sets: 4 1 2 5 8 3 7 0 6 and 8 6 7 2…
Alx
  • 651
  • 1
  • 9
  • 26
4
votes
2 answers

Can linear conflict heuristic cause more nodes to be created and explored than Manhattan heuristic with A-Star for 15-Puzzle?

I have coded A-star Algorithm for 15-puzzle using just Manhattan Heuristic and Manhattan and linear conflict heuristic. My question is, can for some specific puzzle instances linear conflict cause more nodes to be created and explored than Manhattan…
PhoenixDD
  • 121
  • 1
  • 2
  • 12
4
votes
1 answer

Why does my 8-puzzle solution runs faster when I create an array twice

I wrote an algorithm to solve N-puzzle problem using breadth-first search. In trying to make things faster I decided to allocate a large array up front instead of repeatedly pushing and shifting values to an empty array. By chance I noticed an odd…
hisabimbola
  • 196
  • 3
  • 14
4
votes
2 answers

Ideas for an efficient way of hashing a 15-puzzle state

I am implementing a 15-puzzle solver by Ant Colony Optimization, and I am thinking a way of efficiently hashing each state into a number, so I waste the least amount of bytes. A state is represented by a list of 16 numbers, from 0 to 15 (0 is the…
Alfonso Embid-Desmet
  • 3,561
  • 3
  • 32
  • 45
4
votes
2 answers

How to enumerate all states in the 8-puzzle?

I am solving the 8-puzzle. It is a problem which looks like this: Image courtesy of: https://ece.uwaterloo.ca/~dwharder/aads/Algorithms/N_puzzles/ (you can also see there for a more detailed description of the 8-puzzle). The user can move a square…
ziutek
  • 585
  • 1
  • 4
  • 12
4
votes
2 answers

Solve 8-puzzle game

I'm trying to code a 8-puzzle game solver in C++, but I'm having a lot of problems while doing it. The program is currently working, but it takes too much steps to solve the puzzle. I mean, sometimes it can find the optimal solution, sometimes it…
pluralism
  • 1,487
  • 2
  • 16
  • 22
4
votes
2 answers

8-puzzle has a solution in prolog using manhattan distance

The 8-puzzle will be represented by a 3x3 list of lists positions where the empty box will be represented by the value 9, as shown below: [[9,1,3],[5,2,6],[4,7,8]] Possibility Solution: Only half of the initial positions of the 8-puzzle are…
franvergara66
  • 10,524
  • 20
  • 59
  • 101
1
2 3
…
11 12