AI Projects: Solving the 15 Puzzle Problem and 6x6 Futoshiki Puzzles
15 Puzzle Problem
Problem Description
There is a 4x4 board with 15 tiles numbered from 1 to 15 and a blank tile. A tile can slide into the blank position if it is horizontally, vertically, or diagonally adjacent to the blank position. Given a start board configuration and a goal board configuration, find a sequence of moves to reach the goal configuration from the start configuration.
Algorithms / Techniques Used
- Informed (Heuristic) Search: A* Search Algorithm with Graph Search
- Heuristic function: sum of chessboard distances of tiles from their goal positions, where chessboard distance is the maximum of the horizontal and vertical distances
Want to try it out yourself?
15 Puzzle Game(For this game, there is only one goal configuration: the cells will be ordered from 1 to 15. Diagonal moves are also not allowed.)
Interested in using or learning more about this code?
6x6 Futoshiki Puzzles
Problem Description
Given an initial board configuration with numbers already assigned to some cells and inequality relationships, complete the board such that all the constraints are satisfied.
Constraints
- All inequality relationships between adjacent cells must be satisfied.
- A digit can only appear once in every row and column.
Algorithms / Techniques Used
- Backtracking Algorithm
- Forward Checking
- Minimum Remaining Values (MRV) Heuristic + Degree Heuristic - determine which variable to assign next