RDBMS for puzzle solving

Can you use a Relational Database to solve a Rubiks Cube or Pyraminx or Sudoku? Does it require a brute force approach? What are the maximum number of moves required to solve a puzzle, and how much disk space and memory will you need to solve it? This talk leverages the relational nature of an RDBMS to solve many classic puzzles, but more importantly, will make you think about the way you encode and retrieve large data sets, as storing every possible state a puzzle can be in can start get unwieldy.