Sudoku matrix is a unique Latin square-based mathematical structure, which may have several dimensions like 2D, 3D, etc. This structure has several applications in different domains of computer science. So, solving Sudoku and finding all its possible solutions are very important. Since 3D Sudoku has one extra dimension over 2D, it may give an edge to different applications of this puzzle game. Therefore, in this work, an effort has been made to explore all possible solutions of 3D Sudoku matrix. We have developed a permuted backtracking-based methodology to solve different 3D Sudoku instances. This method can solve an n × n× n Sudoku having n2 faces and provide all possible solutions for a valid Sudoku instance. © 2021, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.