Maze

/*
 * Mark Klingberg
 * m2615919
 * 11/13/2013
 *
 * This program generates and solves a maze
 */

public class Maze {

    private static boolean endFound;

    public static char [][] create(int width, int height){

        int numCells = width*height, unionedCount = 0, rand, temp, i, j=0, k=0,
                setx, sety, x, y, numWalls = 2*(width-1)*(height-1)+width+height-2;
        int[] walls = new int[numWalls];
        int[] parent = new int[numCells];
        int[] rank = new int[numCells];
        boolean[] wallExsits = new boolean[numWalls];
        char[][] maze = new char[2*height+1][2*width+1];

        //make set
        for(i=0; i<parent.length; i++){
            parent[i] = i;
            rank[i] = 0;
        }

        //initialize walls
        for(i=0; i<walls.length; i++){
            walls[i] = i;
            wallExsits[i] = true;
        }

        //shuffle walls
        for(i=0; i<walls.length; i++){

            rand = (int)((Math.random() * 1000000) % walls.length);

            temp = walls[i];
            walls[i] = walls[rand];
            walls[rand] = temp;

        }

        i=0;
        while((unionedCount < numCells) && (i<walls.length)){

            //find x and y
            temp = walls[i] % (2*width-1);
            if(temp < width-1){
                x = temp + (walls[i]/(2*width-1)*width);
                y = x+1;
            }
            else{
                x = temp + (walls[i]/(2*width-1)*width) - (width-1);
                y = x + width;
            }

            //if w divides two cells, x and y, that are in disjoint sets
            if(findset(x, parent)!=findset(y, parent)){

                //remove w
                wallExsits[walls[i]] = false;

                //union(x, y)
                setx = findset(x, parent);
                sety = findset(y, parent);

                if (rank[setx] < rank[sety])
                    parent[setx] = sety;
                else if (rank[sety] < rank[setx])
                    parent[sety] = setx;
                else
                {
                    parent[sety] = setx;
                    rank[setx]++;
                }

                unionedCount++;
            }

            i++;

        }

        //translate from bool array to 2d char array
        //filling in outer boundries
        for(i=0; i<2*width+1; i++){
            maze[0][i] = '#';
            maze[2*height][i] = '#';
        }
        for(i=0; i<2*height+1; i++){
            maze[i][0] = '#';
            maze[i][2*width] = '#';
        }

        //filling in the middle
        for(j=0; j<(2*height-1); j++){
            for(i=0; i<(2*width-1); i++){

                if((j%2)==0){
                    //even row, even column
                    if((i%2)==0){
                        maze[j+1][i+1]=' ';
                    }
                    //even row, odd column
                    else{
                        if(wallExsits[k])
                            maze[j+1][i+1]='#';
                        else
                            maze[j+1][i+1]=' ';
                        k++;
                    }
                }
                else{
                    //odd row, even column
                    if((i%2)==0){
                        if(wallExsits[k])
                            maze[j+1][i+1]='#';
                        else
                            maze[j+1][i+1]=' ';
                        k++;
                    }
                    //odd row, odd column
                    else{
                        maze[j+1][i+1]='#';
                    }
                }

            }
        }

        //add start and exit markers
        maze[1][1] = 's';
        maze[2*height-1][2*width-1] = 'e';

        return maze;
    }

    private static int findset(int x, int[] parent){

       if (parent[x] == x)
           return x;

        parent[x] = findset(parent[x], parent);
        return parent[x];

    }

    public static char[][] solve(char [][] maze){

        endFound = false;

        maze = solver(maze, 1, 1);

        //fix the s
        if(maze[1][1] != 'e')
            maze[1][1] = 's';

        return maze;

    }

    //function is recursively called in the order up, right, down, left. only recurses if it sees a ' ' or an 'e'.
    private static char[][] solver(char [][] maze, int i, int j){

        //end found, set flag
        if(maze[i][j] == 'e'){
            endFound = true;
            return maze;
        }

        //recurse up
        if(maze[i][j-1]==' ' || maze[i][j-1]=='e'){
            maze[i][j]='.';
            maze = solver(maze, i, j-1);
            //return without backtracking and removing period
            if(endFound==true)
                return maze;
        }

        //recurse right
        if(maze[i+1][j]==' ' || maze[i+1][j]=='e'){
            maze[i][j]='.';
            maze = solver(maze, i+1, j);
            //return without backtracking and removing period
            if(endFound==true)
                return maze;
        }

        //recurse down
        if(maze[i][j+1]==' ' || maze[i][j+1]=='e'){
            maze[i][j]='.';
            maze = solver(maze, i, j+1);
            //return without backtracking and removing period
            if(endFound==true)
                return maze;
        }

        //recurse left
        if(maze[i-1][j]==' ' || maze[i-1][j]=='e'){
            maze[i][j]='.';
            maze = solver(maze, i-1, j);
            //return without backtracking and removing period
            if(endFound==true)
                return maze;
        }

        //if backtracking, remove period
        maze[i][j] = ' ';
        return maze;
    }

    public static double difficultyRating(){

        return 2.0;
    }

    public static double hoursSpent(){

        return 10.0;
    }

    public static void print(char[][] maze){

        for(int i=0; i<maze.length; i++){
            for(int j=0; j<maze[i].length; j++){
                System.out.printf("%c", maze[i][j]);
            }
            System.out.println();
        }

    }

    public static void main(String args[]){

        print(solve(create(10, 10)));

    }
}