Dancing links

Kotlin implementation of dancing links based on:
https://www.codingame.com/playgrounds/156252/algorithm-x/introduction

It's made such that is as close as possible to Python implementation used in mentioned tutorial. So practical examples can be found there. Huge kudos to author of a playground.

Base class of DLX Solver can be found in src/dlx_solver.kt

DLXSolver usage in Kotlin

Constructor of DLXSolver<Requirement, Action> class accepts following required attributes:

1. requirements - List of requirements of Requirement type
2. actions - Map in which key is Action and value is list of satisfied requirements (or optionalRequirements)
3. optionalRequirements - List similar to requirements but these requirements are optional and by default empty.

In order to use DLXSolver you have to extend it, instantiate it and call its solve() function. solve function by default finds every solution. Since it may take some time to compute all solutions, you have to override either one of these functions:

1. processSolution(solution) function - gives you solutions one by one in solution attribute. You may return true if solution is processed in order to break the execution of solve() function
2. onFinished(solutions) function - gives you all solutions ever found

solution is always List of Actions that leads to solution of given problem. So if you properly describe actions, you should be able to reconstruct steps to find solution.

Recommended usage

If you are not interested in reading and/or you know Kotlin, you can simply Check Paving with bricks implementation to understand the approach I'm about to describe.

Specify requirements and actions classes

Best option to specify requirements is to create sealed interface and extend it using data classes, and same goes for actions.

sealed interface Requirement {  
    data class CellCovered(val x: Int, val y: Int) : Requirement
    data class Requirement2(val value: String) : Requirement        // just for demonstration purposes
}

sealed interface Action {
    data class PlaceTile(val x: Int, val y: Int, val shape: Shape) : Action
}

If you want to fully follow mentioned tutorial, you can pass simple Strings as well. I've found my approach more suitable for decoding solutions.

However, if you are using only one type of actions (or requirements) you don't need sealed interface. So your Action class might look like this:

data class PlaceTile(val x: Int, val y: Int, val shape: Shape)

Extend DLXSolver

Now you need to extend DLXSolver and implement either onFinished or processSolution function. For example if you need to know how many solutions there are for given problem, you can simply use this implementation:

class MySolver(  
    requirements: List<Requirement>,  
    actions: Map<PlaceTile, List<Requirement>>,
    optionalRequirements: List<Requirement>
) : DLXSolver<Requirement, PlaceTile>(requirements, actions, optionalRequirements) {  
    override fun onFinished(solutions: List<List<PlaceTile>>) {  
        println(solutions.size)  
    }  
}

Feed your solver

Instantiate your solver with necessary attributes, like this:

fun createSolver(...) : MySolver {  
    val requirements = mutableListOf<Requirement>()  
    val actions = mutableMapOf<PlaceTile, List<Requirement>>()
    val optionalRequirements = mutableListOf<Requirement>()     // just for demonstration purposes

    // create requirements
    requirements += Requirement.CellCovered(x, y)
    optionalRequirements += Requirement.Requirement2("")        // just for demonstration purposes

	actions[PlaceTile(x, y, shape)] = listOf(
	    Requirement.CellCovered(...),
	    Requirement.CellCovered(...), 
	    ...
	)
	
    
    return MySolver(requirements, actions, optionalRequirements)  
}

Solve

And politely ask DLX solver to solve your problem:

fun main() {  
    createSolver(...).solve()  
}

Solved puzzles

1. Mrs. Knuth 1
2. Sudoku 25x25
3. Constrained Latin Squares
4. Literary Alfabet Soupe
5. Shikaku Solver
6. Dominoes solver
7. Paving with bricks
8. Mrs. Knuth 2
9. n Queens
10. Finish 8 queens
11. Einstein's Riddle Solver
12. Three little piggies
13. Who Dunnit
14. Mrs. Knuth 3
15. Futoshiki Solver
16. Suguru Solver
17. Dumbells
18. High-rise buildings
19. Nonogram inversor - Redundand - problem-space reduction fully solved it
20. Polyominos
21. Tetrasticks