On se retrouve aujourd'hui pour la solution du précédent #KataOfTheWeek proposé par Nicolas en début de semaine !

Il existe plusieurs façon de résoudre le problème. La plus intuitive que je vais détailler est celle par "Brute-force" :)

Je vous ai codé la solution en kotlin.

On traduit le problème par un tableau de deux dimensions avec des 0 pour les nombres manquants. La fonction solve() itère sur le tableau et va checker chaque case pour trouver une solution valide. Ensuite les trois fonctions rowConstraint() columnConstraint() subsectionConstraint() verifient les contraintes du sodoku. Ces trois fonctions appellent la fonction checkConstraint() qui vérifie que chaque valeur n'apparaît qu'une seule fois. Quand toutes les cases sont remplies, isValid() return true et il ne nous reste plus qu'à afficher la solution.

class KataKotlin {

    companion object {
        @JvmStatic
        fun main(args: Array<String>) {
            println("Hello takima !")

            val board = arrayOf(
                    intArrayOf(8, 0, 0, 0, 0, 0, 0, 0, 0),
                    intArrayOf(0, 0, 3, 6, 0, 0, 0, 0, 0),
                    intArrayOf(0, 7, 0, 0, 9, 0, 2, 0, 0),
                    intArrayOf(0, 5, 0, 0, 0, 7, 0, 0, 0),
                    intArrayOf(0, 0, 0, 0, 4, 5, 7, 0, 0),
                    intArrayOf(0, 0, 0, 1, 0, 0, 0, 3, 0),
                    intArrayOf(0, 0, 1, 0, 0, 0, 0, 6, 8),
                    intArrayOf(0, 0, 8, 5, 0, 0, 0, 1, 0),
                    intArrayOf(0, 9, 0, 0, 0, 0, 4, 0, 0))

            solve(board)

            println("Here is the solution : \n")

            for (row in 0..8) {
                for (column in 0..8) {
                    print(board[row][column].toString() + " ")
                }
                println()
            }
        }

        private fun solve(board: Array<IntArray>): Boolean {
            for (row in 0..8) {
                for (column in  0..8) {
                    if (board[row][column] == 0) { // 0 is when we don't have any values
                        for (k in 1..9) {
                            board[row][column] = k
                            if (isValid(board, row, column) && solve(board)) {
                                return true
                            }
                            board[row][column] = 0
                        }
                        return false
                    }
                }
            }

            return true
        }

        private fun isValid(board: Array<IntArray>, row: Int, column: Int): Boolean {
            return (rowConstraint(board, row)
                    && columnConstraint(board, column)
                    && subsectionConstraint(board, row, column))
        }

        private fun rowConstraint(board: Array<IntArray>, row: Int): Boolean {
            val constraint = BooleanArray(9)
            return (0..8).all { checkConstraint(board, row, constraint, it) }
        }

        private fun columnConstraint(board: Array<IntArray>, column: Int): Boolean {
            val constraint = BooleanArray(9)
            return (0..8).all { checkConstraint(board, it, constraint, column) }

        }

        private fun subsectionConstraint(board: Array<IntArray>, row: Int, column: Int): Boolean {
            val constraint = BooleanArray(9)
            val subsectionRowStart: Int = row / 3 * 3
            val subsectionRowEnd: Int = subsectionRowStart + 3
            val subsectionColumnStart: Int = column / 3 * 3
            val subsectionColumnEnd: Int = subsectionColumnStart + 3

            for (r in subsectionRowStart until subsectionRowEnd) {
                for (c in subsectionColumnStart until subsectionColumnEnd) {
                    if (!checkConstraint(board, r, constraint, c)) return false
                }
            }
            return true
        }

        private  fun checkConstraint(
                board: Array<IntArray>,
                row: Int,
                constraint: BooleanArray,
                column: Int): Boolean {
            if (board[row][column] != 0) {
                if (!constraint[board[row][column] - 1]) {
                    constraint[board[row][column] - 1] = true
                } else {
                    return false
                }
            }
            return true
        }

    }
}

A bientôt pour un nouveau #KataOfTheWeek !