moving from one point of the matrix to the location of zero

user_13752197 0
Viewed 114

I am supposed to program this with both recursive and iterative. My recursive code is posted at the bottom. MagicBoard is a 1-player game using a chess-like board consisting of d×d squares with d between 5 and 20, and each square contains an integer between 0 and d -1. The rules of the game are simple. The circle marks the start position on the board. The integer (n) in the circled square indicates that the circle can move n squares on the board. In one step the circle can move either n squares east or west or north or south. At each step the chosen direction is fixed. The circle cannot move off the board. The only legal start positions are the four corner squares. The board must contain exactly one goal square with zero as value that can be located anywhere on the board, but its position cannot be identical to the start position. enter image description here For instance, in the above example the circle can move either 4 squares east or south. All other moves are illegal. The objective of the game is to move the circle to the goal square containing the zero value. In the configuration given below, you can solve the game by making the following sequence of steps: enter image description here

The next example shows that in some situations, the goal square cannot be reached from the given start position enter image description here

Here is my code which does not work:


import java.util.Scanner;

public class A2Rcs {
    
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        System.out.println("\nEnter board size: ");
        int size = input.nextInt();
        
        int[][]board = new int[size][size];
        for (int i = 0; i<size; i++) {
            System.out.println("\nEnter the row: ");
            for (int j = 0; j<size; j++) {
                board[i][j] = input.nextInt();
            }
        }
        
        System.out.println("\nData you entered: ");
        for(int x = 0; x< size; x++){
            for(int y = 0 ; y< size; y++){ 
                System.out.print(board[x][y]);
            } 
            System.out.println(); 
        }
        
        System.out.println("\nEnter starting position: ");
        int p1 = input.nextInt();
        int p2 = input.nextInt();
        
        if (magicBoard(p1, p2, board, size))
            System.out.println("Solvable");     
    }
    
    public static Boolean magicBoard(int p1, int p2, int[][] board, int size) {
        boolean result = false;
        int temp;

        while(!result) {
            if(board[p1][p2] == 0) {
                System.out.println("Reached 0.");
                result = true;
                break;
            }           
            
            //can only down
            if((p1+board[p1][p2]) < size && (p1-board[p1][p2]) < 0 && ((p2+board[p1][p2]) > size && (p2-board[p1][p2]) < 0)) {
                temp = board[p1+board[p1][p2]][p2];

                if(board[p1][p2] == temp) {
                    System.out.print("The MagicBoard is unsolvable");
                    result = false;
                    break;
                }
                // If don't go back and forth, then we continue
                else {
                    p1 = p1+board[p1][p2];
                    System.out.print("Move south " + board[p1][p2] + ", ");
                    magicBoard(p1, p2, board, size);
                }
            }
            //can only up
            else if((p1+board[p1][p2]) > size && (p1-board[p1][p2]) > 0 && ((p2+board[p1][p2]) > size && (p2-board[p1][p2]) < 0)){
                temp = board[p1-board[p1][p2]][p2];
                if(board[p1][p2] == temp) {
                    System.out.print("The MagicBoard is unsolvable");
                    result = false;
                    break;
                }
                else {
                    p1 = p1-board[p1][p2];
                    System.out.print("Move north " + board[p1][p2] + ", ");
                    magicBoard(p1, p2, board, size);
                }
            }
            //can only up right
            else if((p2+board[p1][p2])<size && (p2-board[p1][p2])<0 && ((p1+board[p1][p2])>size && (p1-board[p1][p2])<0)) {
                temp = board[p1][p2+board[p1][p2]];
                if(board[p1][p2] == temp) {
                    System.out.print("The MagicBoard is unsolvable");
                    result = false;
                    break;
                }
                else {
                    p2 = p2+board[p1][p2];
                    System.out.print("Move east " + board[p1][p2] + ", ");
                    magicBoard(p1, p2, board, size);
                }
            }
            //can only left
            else if((p2+board[p1][p2]) > size && (p2-board[p1][p2])> 0 && ((p1+board[p1][p2])>size && (p1-board[p1][p2])<0)) {
                temp = board[p1][p2-board[p1][p2]];
                if(board[p1][p2] == temp) {
                    System.out.print("The MagicBoard is unsolvable");
                    result = false; 
                    break;
                }
                else {
                    p2 = p2-board[p1][p2];
                    System.out.print("Move west " + board[p1][p2] + ", ");
                    magicBoard(p1, p2, board, size);
                }
            }

            // can any direction
            else {
                // try moving south
                SOUTH:
                    if(p1-board[p1][p2] < 0 && p1-board[p1][p2] > -size) {
                        temp = board[p1+board[p1][p2]][p2];
                        // Verify if we go back and forth if we go south, if we do, then we the result will be 
                        if(board[p1][p2] == temp) {
                            break SOUTH;
                        }
                        else {
                            p1 = p1+board[p1][p2];
                            System.out.print("Move south " + board[p1][p2] + ", ");
                            magicBoard(p1, p2, board, size);
                        }
                    }
                NORTH: 
                    if(p1-board[p1][p2] > 0 && p1-board[p1][p2] < size) {
                        temp = board[p1-board[p1][p2]][p2];
                        if(board[p1][p2] == temp) {
                            break NORTH;
                        }
                        else {
                            p1 = p1-board[p1][p2];
                            System.out.print("Move north " + board[p1][p2] + ", ");
                            magicBoard(p1, p2, board, size);
                        }
                    }
                    
                    // try moving east
                EAST:
                    if(p2-board[p1][p2] < 0 ) {
                        temp = board[p1][p2+board[p1][p2]];
                        // If will go back and forth at that position, then we exit the EAST label and we go to the next label
                        if(board[p1][p2] == temp) {
                            System.out.print("The MagicBoard is unsolvable");
                            break EAST;
                        }
                        else {
                            p2 = p2+board[p1][p2];
                            System.out.print("Move east " + board[p1][p2] + ", ");
                            magicBoard(p1, p2, board, size);
                        }
                    }
                    // Try moving west  
                WEST:
                    if(p2-board[p1][p2] > 0) {
                        temp = board[p1][p2-board[p1][p2]];
                        // If we go back and forth in that position, then we exit the EAST label
                        if(board[p1][p2] == temp) {
                            System.out.print("The MagicBoard is unsolvable");
                            result = false;
                            break WEST;
                        }
                    else {
                        p2 = p2-board[p1][p2];
                        System.out.print("Move west " + board[p1][p2] + ", ");
                        magicBoard(p1, p2, board, size);
                    }
                }
            }
        }

        return result;
    }
}

I've been working on this for a week and still cannot figure it out. I am not sure if it is proper to post it here but any type of assistance is appreciated

edit Errors are here: enter image description here

recursion algorithm java
2 Answers

We could write less code, which would make it easier to think about and consider its logic. First, it seems clear we don't need to visit a cell more than once. We can use a backtracking routine, marking and unmarking visited cells. I'm not versed in Java so I hope this JavaScript code is easy to translate:

function backtrack(M, i, j, visited){
  // Reached the goal!
  if (M[i][j] == 0)
    return true;

  const d = M.length;
  const move = M[i][j];

  // Try visiting all directions
  if (i + move < d && !visited[i + move][j]){
    visited[i + move][j] = true;
    if (backtrack(M, i + move, j, visited))
      return true;
    visited[i + move][j] = false;
  }
  if (i - move >= 0 && !visited[i - move][j]){
    visited[i - move][j] = true;
    if (backtrack(M, i - move, j, visited))
      return true;
    visited[i - move][j] = false;
  }
  if (j + move < d && !visited[i][j + move]){
    visited[i][j + move] = true;
    if (backtrack(M, i, j + move, visited))
      return true;
    visited[i][j + move] = false;
  }
  if (j - move >= 0 && !visited[i][j - move]){
    visited[i][j - move] = true;
    if (backtrack(M, i, j - move, visited))
      return true;
    visited[i][j - move] = false;
  }
  return false;
}

function f(M, start_i, start_j){
  const d = M.length;
  const visited = new Array(d);
  for (let i=0; i<d; i++)
    visited[i] = new Array(d).fill(false);
  visited[start_i][start_j] = true;
  return backtrack(M, start_i, start_j, visited);
}

var board_1 = [
  [4, 2, 1, 3, 1],
  [2, 3, 2, 1, 4],
  [3, 2, 3, 1, 4],
  [1, 3, 4, 2, 3],
  [3, 3, 1, 2, 0]
];

var board_2 = [
  [1, 4, 1, 3, 1],
  [4, 3, 2, 1, 4],
  [3, 2, 3, 1, 4],
  [1, 3, 4, 2, 3],
  [3, 4, 1, 2, 0]
];

console.log(f(board_1, 0, 0));
console.log(f(board_2, 0, 0));

Here's a version that also gets the moves for the first valid path found:

function backtrack(M, i, j, visited){
  // Reached the goal!
  if (M[i][j] == 0)
    return [[i,j]];

  const d = M.length;
  const move = M[i][j];

  // Try visiting all directions
  if (i + move < d && !visited[i + move][j]){
    visited[i + move][j] = true;
    const ms = backtrack(M, i + move, j, visited)
    if (ms.length)
      return [[i,j]].concat(ms);
    visited[i + move][j] = false;
  }
  if (i - move >= 0 && !visited[i - move][j]){
    visited[i - move][j] = true;
    const ms = backtrack(M, i - move, j, visited)
    if (ms.length)
      return [[i,j]].concat(ms);
    visited[i - move][j] = false;
  }
  if (j + move < d && !visited[i][j + move]){
    visited[i][j + move] = true;
    const ms = backtrack(M, i, j + move, visited)
    if (ms.length)
      return [[i,j]].concat(ms);
    visited[i][j + move] = false;
  }
  if (j - move >= 0 && !visited[i][j - move]){
    visited[i][j - move] = true;
    const ms = backtrack(M, i, j - move, visited)
    if (ms.length)
      return [[i,j]].concat(ms);
    visited[i][j - move] = false;
  }
  return [];
}

function f(M, start_i, start_j){
  const d = M.length;
  const visited = new Array(d);
  for (let i=0; i<d; i++)
    visited[i] = new Array(d).fill(false);
  visited[start_i][start_j] = true;
  return backtrack(M, start_i, start_j, visited);
}

var board_1 = [
  [4, 2, 1, 3, 1],
  [2, 3, 2, 1, 4],
  [3, 2, 3, 1, 4],
  [1, 3, 4, 2, 3],
  [3, 3, 1, 2, 0]
];

var board_2 = [
  [1, 4, 1, 3, 1],
  [4, 3, 2, 1, 4],
  [3, 2, 3, 1, 4],
  [1, 3, 4, 2, 3],
  [3, 4, 1, 2, 0]
];

console.log(JSON.stringify(f(board_1, 0, 0)));
console.log(JSON.stringify(f(board_2, 0, 0)));

user_20347870

The search is a classic Breadth-first search (BFS) and can be solved by recursive BFS.
The following is an mre (1) of a BFS solution for the MagicBoard:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class A2Rcs {

    private static int[][] board1 = {//test case 1
                   {4, 2, 1, 3, 1},
                   {2, 3, 2, 1, 4},
                   {3, 2, 3, 1, 4},
                   {1, 3, 4, 2, 3},
                   {3, 3, 1, 2, 0}
                 };

    private static int[][] board2 = {//test case 2
                   {1, 4, 1, 3, 1},
                   {4, 3, 2, 1, 4},
                   {3, 2, 3, 1, 4},
                   {1, 3, 4, 2, 3},
                   {3, 4, 1, 2, 0}
                 };

    private static boolean[][] visited; //mark visited nodes
    //bfs uses queue. In this case each entry (List) in the queue represents an entire path.
    //such path is represented by a list of row, column pairs
    private static Queue<List<int[]>> queue;

    public static void main(String[] args) {
        magicBoard(0, 0, board1);
        magicBoard(0, 0, board2);
    }

    public static Boolean magicBoard(int row, int col, int[][] board) {

        List<int[]> path = new ArrayList<>(); //construct an empty path
        path.add(new int[]{row,col}); //add starting point to the path
        queue = new LinkedList<>(); //initialize queue
        queue.add(path);//add path to queue

        visited = new boolean[board.length][board[0].length]; //initialize visited
        for (int i=0; i<visited.length ; i++){
            for (int j=0; j<visited[0].length ; j++){
                visited[i][j] = false;
            }
        }

        visited[row][col] = true;//mark origin as visited

        boolean result = magicBoardBFS(board); //run search
        if (! result) {
            System.out.println("\nPath not found.");
        }
        return result;
    }

    public static Boolean magicBoardBFS(int[][] board) {

        List<int[]>path = queue.poll(); //pull head (first entered) entry from queue
        if(path == null) return false;  //no more entries to process and target not found so return false
        if(targetFound(board, path)) return true; //check if target reached

        int[] rowColumnPair = path.get(path.size()-1); //last row, col pair in path
        //get next reachable positions
        List<int[]>neighbors = getNeighbors(board, rowColumnPair[0], rowColumnPair[1]);
        //add neighbors to queue
        for(int[] rowColPair : neighbors){
            List<int[]>newPath = new ArrayList<>(path); //copy path
            //and neighbor (next reachable position) to the path
            newPath.add(rowColPair);
            queue.add(newPath); //add new path to queue
        }
         return magicBoardBFS(board);
    }

    //check if last pair in path is the target
    private static boolean targetFound(int[][] board,List<int[]>path ) {

        int[] rowColPair = path.get(path.size()-1); //last row, col pair in path
        int row = rowColPair[0], col = rowColPair[1];
        if(board[row][col] == 0 ){//target found
            System.out.println("Path found: ");
            printPath(path);
            return true;
        }
        return false;
    }

    private static List<int[]> getNeighbors(int[][] board, int row, int col) {

        List<int[]>neighbors = new ArrayList<>();
        int move = board[row][col];
        //todo : assert that move is > 0

        int[][] newRowColPairs = {{row + move, col},{row - move, col},  {row , col + move},{row , col - move} };
        for(int[] rowColPair: newRowColPairs){

            int newRow = rowColPair[0], newCol =rowColPair[1];
            if(newRow < board.length && newRow >= 0
                    && newCol < board[0].length && newCol >=0) { //valid row col
                if(!visited[newRow][newCol]) { //unvisited
                    neighbors.add(new int[]{newRow, newCol});
                    visited[newRow][newCol] = true;
                }
            }
        }

        return neighbors;
    }

    private static void printPath(List<int[]> path) {
        if(path == null) return;
        for(int[] rowColPair : path){
            System.out.print(Arrays.toString(rowColPair) +" ");
        }
        System.out.println();
    }
}
(1) Always consider mre when posting a question or an answer
user_39929390
Related