# 13014 - Happy A to B

The 8-puzzle problem is a classic problem in artificial intelligence that involves a 3x3 board with 8 numbered tiles and one empty space. The objective is to place the numbers on tiles to match the final configuration using the empty space. There are several algorithms to solve this problem, including depth-first search (DFS), breadth-first search (BFS), and branch and bound. DFS and BFS are brute-force algorithms that can be used to solve the problem, but they are not efficient for large problems. Branch and bound is an intelligent algorithm that uses a ranking function to avoid searching in sub-trees that do not contain an answer node. The cost function is useful for determining the next E-node. The next E-node is the one with the least cost. The cost function is defined as C (X) = g (X) + h (X) where g (X) = cost of reaching the current node from the root h (X) = cost of reaching an answer node from X. The ideal Cost function for an 8-puzzle Algorithm : We assume that moving one tile in any direction will have a 1 unit cost. Keeping that in mind, we define a cost function for the 8-puzzle algorithm as below: c (x) = f (x) + h (x) where f (x) is the length of the path from root to x (the number of moves so far) and h (x) is the number of non-blank tiles not in their goal position (the number of misplaced tiles). There are at least h (x) moves to transform state x to a goal state ¹.

Source: Conversation with Bing, 11/26/2023
(1) 8 puzzle Problem using Branch And Bound - GeeksforGeeks. https://www.geeksforgeeks.org/8-puzzle-problem-using-branch-and-bound/.
(2) What can be the efficient approach to solve the 8 puzzle problem?. https://stackoverflow.com/questions/1395513/what-can-be-the-efficient-approach-to-solve-the-8-puzzle-problem.
(3) 8-Puzzle Solver - Deniz. https://deniz.co/8-puzzle-solver/.
(4) How to check if an instance of 8 puzzle is solvable?. https://www.geeksforgeeks.org/check-instance-8-puzzle-solvable/.

## Problem
Let's call a grid 8-puzzle board if the gridsize is 3 x 3 and there is exactly one cell is 'x' and others are '1' or '0'.

In one operation, you can exchange the 'x' cell of a 8-puzzle board with any cell which is adjacent to the 'x' cell. The cell (i, j) is adjacent to the cell (i-1, j), (i, j-1), (i, j+1) and (i+1, j).

Now you need to solve T tasks. In each task, you are given two 8-puzzle boards A, B and one integer K. You need to answer whether it's possible to make A into B in at most K operations.

Let's take an example. In the first task of Sample, you can make A into B in the following 2 operations:


**Input**
The first line contains an integer T (1 ≤ T ≤ 10) – the number of tasks you need to solve.

And for each task, first you are given one integer K (0 ≤ K ≤ 9) – the maximum number of operations you can execute. Then you are given A and B. Both of them are in 3 lines of 3 characters. Please refer to Sample Input.

**Output**
For each task output "Yes" if it's possible to make A into B in K operations. Otherwise output "No". Then print a newline('\n').

> **Sample Input:**
> 2
> 2
> 0x0
> 101
> 011
> 001
> 10x
> 011
> 3
> 0x0
> 101
> 000
> 000
> x01
> 100
>
> **Sample Output:**
> Yes
> No

## Solution

#include <stdio.h>
#include <string.h>

#define SIZE 3

char A[SIZE][SIZE];
char B[SIZE][SIZE];
int maxMoves, sol;

int compare(){
    for(int i = 0; i < SIZE; i++){
        for(int j = 0; j < SIZE; j++){
            if(A[i][j] != B[i][j])
                return 0;
        }
    }
    return 1;
}

void jigsaw(int row, int col, int moves){
    /* Handler 1: Check moves within limit */
    if(moves > maxMoves)
        return;

    /* Handler 2: Compare target vs current */
    if(compare()){
        sol++;
        return;
    }

    /* Computation: Iterate through all 4 possible Moves recursively */
    //Left, Right, Up, Down
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    for(int i = 0; i < 4; i++){
        int X = row + dx[i];
        int Y = col + dy[i];

        //Check legal
        if(X >= 0 && X <= SIZE && Y >= 0 && Y < SIZE){
            //Preserve original
            char temp = A[row][col];

            //Swap
            A[row][col] = A[X][Y];
            A[X][Y] = temp; //to produce new variants based on the iterations

            //Inject to the recursive
            jigsaw(X, Y, moves+1);

            //UnSwap if solution illegal
            A[X][Y] = A[row][col];
            A[row][col] = temp;
        }
    }
}

int main(){
    int task;
    scanf("%d", &task);

    while(task--){
        int row, col;

        //re-initiate global var
        sol = 0;
        scanf("%d", &maxMoves);

        for(int i = 0; i < SIZE; i++){
            for(int j = 0; j < SIZE; j++){
                scanf(" %c", &A[i][j]);
                if(A[i][j] == 'x'){
                    row = i;
                    col = j;
                }
            }
        }

        for(int i = 0; i < SIZE; i++){
            for(int j = 0; j < SIZE; j++){
                scanf(" %c", &B[i][j]);
            }
        }

        jigsaw(row, col, 0);

        if(sol){
            //printf("Possible solution is %d\n", sol);
            printf("Yes\n");
        }else{
            printf("No\n");
        }

    }
}

###### tags:
`NTHUOJ` `I2P` `Recursion`