sudoku-solver.dart (2798B)
1 //Given a matrix that is a sudoku problem that is possible to solve 2 //return the matrix of the completed sudoku. For each spot 3 //I checked all other values in the same row and column as well as same square 4 //and for each value in them assuimng they are not . (which is the value for not set) 5 //I removed them from the list of options (unused set) then for each value still remaining 6 //I called the function again substituting that value for the current. If the current 7 //position is 9,10 that means the function reached the end and thus has a completed sudoku puzzle 8 //so from there I returned the complete board. Otherwise I return [] meaning that the current 9 //permutation of the board is not completable given the previous values that have been used. 10 //Time: 357ms Beats: 13.33% 11 //Memory: 175.9MB Beats: 6.67% 12 13 class Solution { 14 void solveSudoku(List<List<String>> board) { 15 List<List<String>> board2 = solve(board, [0,0]); 16 for(int i = 0 ; i < board2.length ; ++i){ 17 board[i] = List.from(board2[i]); 18 } 19 } 20 List<List<String>> solve(List<List<String>> board, List<int> current_pos){ 21 if(current_pos[1] == 8 && current_pos[0] == 9){ 22 return board; 23 } 24 if(current_pos[0] == 9){ 25 current_pos[0] = 0; 26 current_pos[1] = current_pos[1] + 1; 27 } 28 if(board[current_pos[0]][current_pos[1]] != '.'){ 29 List<List<String>> curr = solve(board, [current_pos[0] + 1 , current_pos[1]]); 30 if(curr.length != 0){ 31 return curr; 32 } 33 else{ 34 return []; 35 } 36 } 37 Set<String> unused = {'1','2','3','4','5','6','7','8','9'}; 38 int currentx = current_pos[0]; 39 int currenty = current_pos[1]; 40 //horz search 41 for(int i = 0 ; i < 9 ; ++i){ 42 if(board[currentx][i] != '.'){ 43 unused.remove(board[currentx][i]); 44 } 45 } 46 //vert search 47 for(int x = 0 ; x < 9; ++x){ 48 if(board[x][currenty] != '.'){ 49 unused.remove(board[x][currenty]); 50 } 51 } 52 //check same square 53 int start_row = ((currentx / 3).toInt() * 3).toInt(); 54 int start_val = ((currenty/3).toInt() * 3).toInt(); 55 for(int i = start_row ; i <= start_row + 2 ; ++i){ 56 for(int x = start_val ; x <= start_val + 2; ++x ){ 57 unused.remove(board[i][x]); 58 } 59 } 60 for(var num in unused){ 61 List<List<String>> new_board = []; 62 for(int i = 0 ; i < board.length ; ++i){ 63 new_board.add(List.from(board[i])); 64 } 65 new_board[currentx][currenty] = num; 66 List<List<String>> curr = solve(new_board, [currentx + 1 , currenty]); 67 if(curr.length != 0){ 68 return curr; 69 } 70 } 71 return []; 72 } 73 }