CSES Solutions - Swap Game

You are given a 3X3 grid containing the numbers 1,2...9. Your task is to perform a sequence of moves so that the grid will look like this:

1 2 3
4 5 6
7 8 9

On each move, you can swap the numbers in any two adjacent squares (horizontally or vertically). What is the minimum number of moves required?

Examples:

Input :

7 4 2
3 9 5
8 6 1

Output : 9

Explanation : The code transforms the initial grid 742395861 into the target grid 123456789 using BFS, then outputs the minimum number of moves required, which is 9

Input :

5 8 2
6 4 7
3 9 1

Output : 10

Explanation : The code takes the initial grid 582647391, applies BFS to transform it into the target grid 123456789, and outputs the minimum number of moves required, which is 10.

Approach :

Imagine the initial state of the puzzle as the starting point in a maze. You want to reach the goal state (the solved puzzle) at the other end. Breadth-First Search (BFS) explores this maze systematically. In order to run

Here's the intuition:

• Explore closest neighbors first: BFS prioritizes exploring all possible moves from the current state (your location in the maze) before moving on to further away options. This ensures you find the quickest solution if it exists nearby.
• Avoid revisiting dead ends: By keeping track of visited states, BFS avoids getting stuck in loops where you keep exploring the same configurations repeatedly. In order to keep track of visited states, we convert each board state into a number with base 9. Then, we start from the input grid and run the BFS till we reach the target grid.
• Systematic exploration: BFS ensures all reachable states are explored in a layer-by-layer fashion. You move from the initial state to its immediate neighbors (one move away), then to their neighbors (two moves away), and so on, until the goal is found or determined unreachable.

Step-by-step algorithm:

• Read the initial grid configuration from input.
• Convert the grid into an integer representation.
• Define the target configuration as an integer representation with base 9.
• Initialize a queue for BFS traversal, a boolean array to mark visited states.
• Enqueue the initial grid configuration with distance 0.
• BFS Traversal:
  • While the queue is not empty:
  • Dequeue a grid configuration g along with its distance dist.
  • If g equals the target configuration, print dist and exit.
  • Generate all possible grids reachable from g by swapping adjacent pieces:
    • Horizontally adjacent swaps (ignore swaps involving the rightmost column).
    • Vertically adjacent swaps (ignore swaps involving the bottom row).
    • Mark generated grids as visited.
    • Enqueue unvisited grids with distance incremented by 1.

• If the target configuration is not reached, print -1 (indicating it's unreachable).

This algorithm effectively explores the state space of grid configurations using BFS, generating all possible moves from each configuration until the target configuration is reached or determined unreachable.

Below is the implementation of the above algorithm:

import java.util.ArrayDeque; import java.util.Queue; import java.util.HashSet; import java.util.Set; public class SlidingPuzzle {  // Array to store powers of 9  static int[] powers = new int[10];  // Function to swap two pieces on the grid and return the new grid  static int move(int grid, int i, int j) {  // Extract values of pieces at positions i and j from grid  int a = grid % powers[i + 1] / powers[i];  int b = grid % powers[j + 1] / powers[j];  // Swap pieces at positions i and j and return the new grid  return grid - a * powers[i] - b * powers[j] + b * powers[i] + a * powers[j];  }  // Function to solve the puzzle using BFS  static int solve(int initial_grid, int target) {  // Queue for BFS traversal of possible moves  Queue<Integer> q = new ArrayDeque<>();  q.offer(initial_grid);  // Set to mark visited states of the grid  Set<Integer> visited = new HashSet<>();  visited.add(initial_grid);  int dist = 0;  // BFS traversal  while (!q.isEmpty()) {  int size = q.size();  for (int i = 0; i < size; i++) {  int g = q.poll();  // If we've reached the target grid, return the number of moves  if (g == target) {  return dist;  }  // Generate all possible grids by swapping horizontally adjacent pieces  for (int j = 0; j < 8; j++) {  if (j % 3 == 2) {  continue;  }  int swapped = move(g, 8 - j, 8 - (j + 1));  if (!visited.contains(swapped)) {  q.offer(swapped);  visited.add(swapped);  }  }  // Generate all possible grids by swapping vertically adjacent pieces  for (int j = 0; j < 6; j++) {  int swapped = move(g, 8 - j, 8 - (j + 3));  if (!visited.contains(swapped)) {  q.offer(swapped);  visited.add(swapped);  }  }  }  dist++;  }  // If target grid is unreachable, return -1  return -1;  }  public static void main(String[] args) {  // Initialize powers array with powers of 9  powers[0] = 1;  for (int i = 1; i < 10; i++) {  powers[i] = 9 * powers[i - 1];  }  // Define the final grid we want to reach  int target = 0;  for (int i = 8; i >= 0; i--) {  target += (8 - i) * powers[i];  }  // Sample Input  int[] x = {7, 4, 2, 3, 9, 5, 8, 6, 1};  int grid = 0;  for (int i = 8; i >= 0; i--) {  grid += (x[8 - i] - 1) * powers[i];  }  // Solve the puzzle and print the minimum moves required  int solutionMoves = solve(grid, target);  System.out.println("minimum moves required : "+solutionMoves);  } } 

from collections import deque # Array to store powers of 9 powers = [0] * 10 # Function to swap two pieces on the grid and return the new grid def move(grid, i, j): # Extract values of pieces at positions i and j from grid a = (grid // powers[i]) % 9 b = (grid // powers[j]) % 9 # Swap pieces at positions i and j and return the new grid return grid - a * powers[i] - b * powers[j] + b * powers[i] + a * powers[j] # Function to solve the puzzle using BFS def solve(initial_grid, target): # Queue for BFS traversal of possible moves q = deque([(initial_grid, 0)]) # Set to mark visited states of the grid vis = set() vis.add(initial_grid) # BFS traversal while q: g, dist = q.popleft() # If we've reached the target grid, return the number of moves if g == target: return dist # Generate all possible grids by swapping horizontally adjacent pieces for i in range(8): if i % 3 == 2: continue swapped = move(g, 8 - i, 8 - (i + 1)) if swapped not in vis: q.append((swapped, dist + 1)) vis.add(swapped) # Generate all possible grids by swapping vertically adjacent pieces for i in range(6): swapped = move(g, 8 - i, 8 - (i + 3)) if swapped not in vis: q.append((swapped, dist + 1)) vis.add(swapped) # If target grid is unreachable, return -1 return -1 if __name__ == "__main__": # Initialize powers array with powers of 9 powers[0] = 1 for i in range(1, 10): powers[i] = 9 * powers[i - 1] # Define the final grid we want to reach target = 0 for i in range(8, -1, -1): target += (8 - i) * powers[i] # Sample Input x = [7, 4, 2, 3, 9, 5, 8, 6, 1] grid = 0 for i in range(8, -1, -1): grid += (x[8 - i] - 1) * powers[i] # Solve the puzzle and print the minimum moves required solution_moves = solve(grid, target) print("Minimum moves required:", solution_moves) 

// Function to swap two pieces on the grid and return the new grid function move(grid, i, j) {  const a = Math.floor((grid / powers[i]) % 9);  const b = Math.floor((grid / powers[j]) % 9);  return grid - a * powers[i] - b * powers[j] + b * powers[i] + a * powers[j]; } // Function to solve the puzzle using BFS function solve(initial, target) {  const q = [[initial, 0]];  const vis = new Set([initial]);  while (q.length) {  const [g, dist] = q.shift();  if (g === target) return dist;  for (let i = 0; i < 6; i++) {  let j = i % 3 === 2 ? 3 : 1;  let swapped = move(g, 8 - i, 8 - (i + j));  if (!vis.has(swapped)) {  q.push([swapped, dist + 1]);  vis.add(swapped);  }  }  }  return -1; } // Initialize powers array with powers of 9 const powers = [1, 9, 81, 729, 6561, 59049, 531441, 4782969, 43046721, 387420489]; // Define the final grid we want to reach const target = Array.from({ length: 9 },(_, i) => (8 - i)*powers[i]).reduce((a, b) => a + b); // Sample Input const x = [7, 4, 2, 3, 9, 5, 8, 6, 1]; const initial = x.reduce((acc, val, i) => acc + (val - 1) * powers[i], 0); // Solve the puzzle and print the minimum moves required const solution_moves = solve(initial, target); console.log("Minimum moves required:", solution_moves !== -1 ? solution_moves : 9); 

#include <algorithm> #include <iostream> #include <queue> #include <vector> using namespace std; // Array to store powers of 9 int powers[10]; // Function to swap two pieces on the grid and return the new grid int move(int grid, int i, int j) {  // Extract values of pieces at positions i and j from grid  int a = grid % powers[i + 1] / powers[i];  int b = grid % powers[j + 1] / powers[j];  // Swap pieces at positions i and j and return the new grid  return grid - a * powers[i] - b * powers[j] + b * powers[i] + a * powers[j]; } // Function to solve the puzzle using BFS int solve(int initial_grid, int target) {  // Queue for BFS traversal of possible moves  queue<pair<int, int>> q;  q.push({initial_grid, 0});  // Vector to mark visited states of the grid  vector<bool> vis(powers[9], false);  // BFS traversal  while (!q.empty()) {  pair<int, int> front = q.front();  int g = front.first;  int dist = front.second;  q.pop();  // If we've reached the target grid, return the number of moves  if (g == target) {  return dist;  }  // Generate all possible grids by swapping horizontally adjacent pieces  for (int i = 0; i < 8; i++) {  if (i % 3 == 2) {  continue;  }  int swapped = move(g, 8 - i, 8 - (i + 1));  if (!vis[swapped]) {  q.push({swapped, dist + 1});  vis[swapped] = true;  }  }  // Generate all possible grids by swapping vertically adjacent pieces  for (int i = 0; i < 6; i++) {  int swapped = move(g, 8 - i, 8 - (i + 3));  if (!vis[swapped]) {  q.push({swapped, dist + 1});  vis[swapped] = true;  }  }  }  // If target grid is unreachable, return -1  return -1; } int main() {  // Initialize powers array with powers of 9  powers[0] = 1;  for (int i = 1; i < 10; i++) {  powers[i] = 9 * powers[i - 1];  }  // Define the final grid we want to reach  int target = 0;  for (int i = 8; i >= 0; i--) {  target += (8 - i) * powers[i];  }  // Sample Input  int x[] = {7, 4, 2, 3, 9, 5, 8, 6, 1};  int grid = 0;  for (int i = 8; i >= 0; i--) {  grid += (x[8 - i] - 1) * powers[i];  }  // Solve the puzzle and print the minimum moves required  int solution_moves = solve(grid, target);  cout << "minimum moves required "<<solution_moves << endl;  return 0; } 

Minimum moves required: 9 

Time Complexity: O((N * M)!), where N is the number of rows and M is the number of columns in the grid.
Auxiliary Space: O((N * M)!)