This work demonstrates that deep neural networks (DNNs) can solve a combinatorial problem merely through self-supervised learning. While researchers have employed explicit logic, heuristics, and reinforcement learning to tackle combinatorial problems, such methods are often complex and costly to implement, requiring lots of knowledge, coding, and adjustments. Hence, in the present study, I propose a robust and straightforward method of self-supervised learning to solve a combinatorial problem. Specifically, taking Rubik's Cube as an example, this work shows that a DNN can implicitly learn convoluted probability distributions of optimal choices from randomly generated combinations. Tested on $1,000$ Rubik's Cube instances, a DNN successfully solved all of them near-optimally. Although the proposed method is validated only on Rubik's Cube, it is potentially useful for other problems and real-world applications with its simplicity, stability, and robustness.