Solving Sudokus with RapidMiner

Share on twitter
Share on facebook
Share on linkedin

This year’s RCOMM live data mining challenge, “Who wants to be a data miner?”, was a tricky yet fun task for the competitors. The task was to (partially) solve a Sudoku puzzle with RapidMiner. The solution shows that you can achieve virtually any data analysis task you can think of only by using standard RapidMiner processes.

The input data set consisted of examples of the form (x,y,v) where x and y indicated the column and row inside the puzzle and v was the number predefined at this cell. The path to the solution was split into three subtasks:

  1. Task one was to generate the space of all combinations of cells and numbers that were possible if there were no predefined numbers in the Sudoku.This task could be solved by starting with a simple data set only containing the numbers one to nine and applying two Cartesian Product operators to generate all combinations of these numbers for x, y, and v. In addition to that, we also generate a new attribute z, which indicates the 3×3-sub-table in which the cell (x,y) lies, using a Generate Attributes operator.
  2. This additional attribute z is useful for Subtask 2 which was to eliminate all combinations which are impossible, given a single predefined cell value from the input data set. This was possible by using a combination of a Generate Attributes operator and a Filter Examples operator to identify those combinations (from the set of all combinations generated in Subtask 1) where v and at least one of x, y, or z match a number defined in the input.
  3. The resulting process of Subtask 2 could be re-used in Subtask 3 to eliminate all combinations whose impossibility could be inferred from looking at all predefined cell values in the input data set. This could be achieved by using a Loop Examples operator to iterate over all cells and using a nested Execute Process to re-use the process generated in Subtask 2. Finally, by looking at those cells where only one possible number remains, we can identify a new value that can be inserted into the Sudoku for sure. These cells can be identified by using an Aggregate operator to group the remaining possibilities by x, y, and z and find those groups with a count of exactly one.
  4. As a bonus process, we can repeat the process from Subtask 3, iteratively Appending the inferred numbers to the predefined ones. Thus, the data set grows up to a size of 81 which means the 9×9 Sudoku is complete. Finally, we use the Pivot operator and do some polishing to make the result look like this, a completely solved Sudoku:

Solution of the Sudoku puzzle in RapidMiner

All the processes mentioned above are accessible from myExperiment as a pack which you can use from within RapidMiner by using the Community Extension. The processes can be directly opened in RapidMiner, but when saving make sure to name them as they are named in myExperiment since an Execute Process operator in a later process may expect it under this name. Process 0 in this pack downloads the initial data from the Web.

Ingo Mierswa

Ingo Mierswa

Ingo Mierswa is the founder and president of RapidMiner and an industry-veteran data scientist since starting to develop RapidMiner at the Artificial Intelligence Division of the TU Dortmund University in Germany. Mierswa, the scientist, has authored numerous award-winning publications about predictive analytics and big data. Mierswa, the entrepreneur, is the founder of RapidMiner. Under his leadership RapidMiner has grown up to 300% per year over the first seven years. In 2012, he spearheaded the go-international strategy with the opening of offices in the US as well as the UK and Hungary. After two rounds of fundraising, the acquisition of Radoop, and supporting the positioning of RapidMiner with leading analyst firms like Gartner and Forrester, Ingo takes a lot of pride in bringing the world’s best team to RapidMiner.