Cette semaine, c'est Nicolas qui vous propose un #KataOfTheWeek : World's hardest sudoku
Briefing du Kata : Le sudoku est un jeux de combinaisons sur une grille de 9 par 9. Le but est de remplir l'intégralité de la grille avec des nombres allant de 1 à 9. Les règles sont simples chaque nombre ne peut apparaître qu'une fois par ligne / colonnes / bloque de 3 par 3.
Si dessous un liens vers le sudoku décrit comme le plus difficile au monde : https://www.telegraph.co.uk/multimedia/archive/02260/Untitled-1_2260717b.jpg
Le but du kata est d'écrire un Algorithme pour le résoudre. Voila les valeures de la grille : 8 . . . . . . . . . . 3 6 . . . . . . 7 . . 9 . 2 . . . 5 . . . 7 . . . . . . . 4 5 7 . . . . . 1 . . . 3 . . . 1 . . . . 6 8 . . 8 5 . . . 1 . . 9 . . . . 4 . .
et la solution que vous devez trouver :
8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 8 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2
Saurez-vous résoudre le problème ?
Bon courage !
Et voici une solution proposée par l'auteur :
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
}
}
}
Votre équipe TakiVeille
