Finding if a Valid Rummikub Solution exist from selected Tiles

Question

I'm currently making a rummikub "game" so that when I make a Mistake I am able to get the board back easily to what it was before.

Currently in need to find out for a given number of tiles if a solution exists and what the solution is.

Example

Elements Selected are {Red1, Red1, Blue1, Black1, Orange1, Orange1}

And a solution would be {Red1, Blue1, Orange1} and {Red1, Black1, Orange1}

I can currently determine which groups and runs are possible ({Red1, Blue1, Black1, Orange1} being a valid group that wouldn't appear in the valid solution). I need a solution that can go the next step and tell me which of the groups/runs can exist together and make sure each tile is used once. If no such solution exist, it needs to be able to report that. The solution does not have to be optimal (ie use the smallest number of groups/run), it just has to be valid.

Answer 1

If you have a method of determining what groups and runs are possible, why don't you modify your algorithm to remove tiles that you have already used, and make the function recursive. Here is some pseudo-code:

array PickTiles(TileArray) {

    GroupsArray = all possible groups/runs;

    foreach Group in GroupsArray {
         newTileArray = TileArray;
         remove Group from newTileArray;

         if(newTileArray.length() == 0) {
               return array(Group);
         }

         result = PickTiles(newTileArray);
         if(result.length() > 0) {
               return result.append(array(Group));
         }
    }

    return array();
}