# Question : A* algorithm 2D snake with obstacles max route

## Answer : A* algorithm 2D snake with obstacles max route

##### Ok, my two ideas are:* move only if you can still reach the whole board* move only if you won't create a dead endHere's the code, it works pretty well, unless solution does not exist in which case it tries all start positions, before concluding that. I doubt it can be done better. ```1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165: ``` ```/* * Przemyslaw Horban (nr. albumu: 262940) * Uniwersystet Warszawski */ package labrunner; import java.util.ArrayList; import java.util.List; /** * * @author Przemyslaw Horban <[email protected]> */ public class LabRunner { char[][] map; int w, h; private int[] ox = {-1, 1, 0, 0}, oy = {0, 0, 1, -1}; private char[] stepChar = {'<', '>', 'v', '^'}; int dirCh; private boolean walk(int x, int y) { if(checkDeadEnds(x, y) && checkReachability(x, y)) { boolean wayToGo = false; for(int i = 0; i < 4; i++) { int nx = x + ox[i], ny = y + oy[i]; if(nx >= 0 && nx < w && ny >= 0 && ny < h && map[ny][nx] == '.') { wayToGo = true; map[y][x] = stepChar[i]; if(walk(nx, ny)) return true; map[y][x] = '.'; } } if(!wayToGo) return true; } return false; } private boolean checkDeadEnds(int x, int y) { int deadEnds = 0; for(int py = 0; py < h; py++) for(int px = 0; px < w; px++) { if(!(x == px && y == py) && map[py][px] == '.') { int blockedWays = 4; for(int i = 0; i < 4; i++) { int newX = px + ox[i], newY = py + oy[i]; if(newX >= 0 && newX < w && newY >= 0 && newY < h && map[newY][newX] == '.') blockedWays--; } if(blockedWays == 4) return false; if(blockedWays == 3) { deadEnds++; if(deadEnds > 1) return false; } } } return true; } class Pt { int x, y; Pt(int x, int y) { this.x = x; this.y = y; } } private boolean checkReachability(int x, int y) { List<Pt> toVisit = new ArrayList<Pt>(); boolean[][] visited = new boolean[h][w]; toVisit.add(new Pt(x, y)); visited[y][x] = true; while(!toVisit.isEmpty()) { Pt p = toVisit.get(toVisit.size() - 1); toVisit.remove(toVisit.size() - 1); for(int i = 0; i < 4; i++) { int newX = p.x + ox[i], newY = p.y + oy[i]; if(newX >= 0 && newX < w && newY >= 0 && newY < h && map[newY][newX] == '.' && visited[newY][newX] == false) { visited[newY][newX] = true; toVisit.add(new Pt(newX, newY)); } } } for(int py = 0; py < h; py++) for(int px = 0; px < w; px++) if(!visited[py][px] && map[py][px] == '.') return false; return true; } public String[] findPath(String[] lab) { h = lab.length; w = lab[0].length(); map = new char[h][w]; for(int py = 0; py < h; py++) for(int px = 0; px < w; px++) map[py][px] = lab[py].charAt(px); int py=0, px=0; boolean solutionExists = false; outer: for(py = 0; py < h; py++) for(px = 0; px < w; px++) if(map[py][px] == '.' && walk(px, py)) { solutionExists = true; break outer; } if(!solutionExists) throw new RuntimeException("Puzzle has no solution!"); String[] ret = new String[h+1]; ret[0] = "Start at x="+px+" y="+py; for(int y = 0; y < h; y++) ret[y+1] = new String(map[y]); return ret; } /** * @param args the command line arguments */ public static void main(String[] args) { LabRunner lr = new LabRunner(); String[] lab = { ".....x....", ".....x....", ".....x....", "...xxxxx..", ".....x....", ".....x....", ".....x....", "..x..x....", "..x.......", "..x.....xx", "..x.....xx", "..x.....xx", "..x..x..xx", "..x..x..xx"}; String[] sol = lr.findPath(lab); for (int i = 0; i < sol.length; i++) { System.out.println(sol[i]); } } } ```
 Random Solutions