kotlin 解数独，“容易”、“初级”均已解开，“高级”尚未测试，“高级+”没解开
数独链接：
https://www.sudoku-cn.com/
class NineTablePlay {
companion object {
val defaultNum = mutableListOf<Int>(
6, 1, 9, 3, 0, 0, 0, 0, 0,
0, 7, 0, 9, 0, 0, 0, 0, 5,
0, 0, 0, 4, 0, 0, 6, 1, 0,
0, 3, 0, 0, 0, 9, 5, 0, 0,
1, 0, 0, 7, 0, 0, 2, 0, 0,
7, 0, 0, 0, 8, 5, 0, 3, 0,
5, 2, 7, 0, 6, 0, 0, 0, 0,
0, 0, 0, 0, 9, 4, 0, 0, 7,
0, 0, 1, 0, 0, 0, 0, 2, 6
)
//key是值 ，value是index
var rowHashList = mutableListOf<HashMap<Int, Int>>()
var volHashList = mutableListOf<HashMap<Int, Int>>()
var centerHashList = mutableListOf<HashMap<Int, Int>>()
// key 是 index,value是 第几个hashMap
var centerDefaultHashMap = HashMap<Int, Int>()
var possibleHashMap = HashMap<Int, MutableList<Int>>()
var impossibleHashMap = HashMap<Int, MutableList<Int>>()
@JvmStatic
fun main(args: Array<String>) {
printList()
//数据确定没问题，下面开始推算
//1.算出每一位可能的数字
//2.算出每一位不肯能的数字
//3.做交集
//4.判断结果长度是否为1
//5.不断循环，直至默认数组都不为0或者循环了10000次也没得到结果
var i = 10000
while (defaultNum.contains(0) && i > 1) {
i--
rowHashList.clear()
volHashList.clear()
centerHashList.clear()
centerDefaultHashMap.clear()
possibleHashMap.clear()
impossibleHashMap.clear()
//每一行都有1-9
addRow()
//每一列都有1-9
addVol()
//每3*3 都有1-9
addCenter()
setImpossibleList()
// 得到第一步的 可能结果
removeImpossible()
// 将可能的结果 与每行、每列、每9方格做并集
checkImpossible()
}
print("\n\n\n======**********=========")
printList()
}
/**
* 假设可能是3、6,那就检查 每一行里面是不是除了它，其他的都不可能为3、6
*/
private fun checkImpossible() {
doCheckImpossible(rowHashList)
doCheckImpossible(volHashList)
doCheckImpossible(centerHashList)
}
private fun doCheckImpossible(hashList: MutableList<HashMap<Int, Int>>) {
for ((i, list) in hashList.withIndex()) {
list.forEach { t, u ->
var pList = possibleHashMap.get(t)
if (pList!!.size > 1) {//遍历所有的可能结果 ，与所有的不可能对比
for ((k, p) in pList.withIndex()) {
var count = 0
list.forEach { innerT, innerU ->
var impList = impossibleHashMap.get(innerT)
if (impList!!.contains(p)) {
count++
}
}
if (count == 8) {
possibleHashMap.put(t, mutableListOf(p))
defaultNum[t] = p
}
}
}
}
}
}
/**
* 将不可能去掉，留下可能与不可能作比较
*/
private fun removeImpossible() {
for ((index, num) in defaultNum.withIndex()) {
var defaultHashSet = getDefaultHashSet()
var imList = impossibleHashMap.get(index)?.toMutableSet()!!
defaultHashSet.removeAll(imList)
possibleHashMap.put(index, defaultHashSet.toMutableList())
if (defaultHashSet.size == 1) {
defaultNum[index] = defaultHashSet.first()
}
}
}
private fun setImpossibleList() {
for ((index, num) in defaultNum.withIndex()) {
//先判断是否为定值
if (num > 0) {
var defaultHashSet = getDefaultHashSet()
defaultHashSet.remove(num)
impossibleHashMap.put(index, defaultHashSet.toMutableList())
} else {
//当前的数字 与之相关的行、列、9格子等
var aimList = relatedRowImpossible(index).toMutableSet()
aimList.addAll(relatedVolImpossible(index).toMutableSet())
aimList.addAll(relatedCenterImpossible(index).toMutableSet())
impossibleHashMap.put(index, aimList.toMutableList())
}
}
}
//=============================================================================================
//凡是存在的值，就是不可能的值
private fun relatedRowImpossible(index: Int): MutableSet<Int> {
var oneRowList = rowHashList.get(index / 9)
return getImpossibleSet(oneRowList)
}
private fun relatedVolImpossible(index: Int): MutableSet<Int> {
var oneVolList = volHashList.get(index % 9)
return getImpossibleSet(oneVolList)
}
private fun relatedCenterImpossible(index: Int): MutableSet<Int> {
var oneCenterList = centerHashList.get(centerDefaultHashMap.get(index)!!)
return getImpossibleSet(oneCenterList)
}
private fun getImpossibleSet(oneRowList: HashMap<Int, Int>): MutableSet<Int> {
var mutableSet = mutableSetOf<Int>()
oneRowList.forEach { t, u ->
mutableSet.add(u)
}
return mutableSet
}
//===========================================================================================
//==========================列、行、九格子单独拿出来===============================================
private fun addRow() {
addHashList(rowHashList)
}
private fun addVol() {
addHashList(volHashList)
}
private fun addCenter() {
for (i in 0..8) {
var hashMap = HashMap<Int, Int>()
centerHashList.add(hashMap)
}
var L = -1
for (m in 0..54 step 27) {//0--27--54
for (n in 0..6 step 3) {//0--3--6
L++
for (i in 0..18 step 9) {//0--9--18
for (k in 0..2) {//0--1--2
centerDefaultHashMap.put(m + n + i + k, L)
centerHashList[L].put(m + n + i + k, defaultNum[m + n + i + k])
}
}
}
}
}
private fun addHashList(hashList: MutableList<HashMap<Int, Int>>) {
for (i in 0..8) {
var hashMap = HashMap<Int, Int>()
hashList.add(hashMap)
}
for ((index, num) in defaultNum.withIndex()) {
hashList[index / 9].put(index, num)
}
}
//===============================打印============================================================
private fun printHashList(hashList: MutableList<HashMap<Int, Int>>) {
for ((index, hashMap) in hashList.withIndex()) {
println()
hashMap.keys.forEach {
print(" ${hashMap[it]} ")
}
}
}
private fun printList() {
for ((index, elm) in defaultNum.withIndex()) {
if (index % 9 == 0) {
println()
}
if (index % 27 == 0) {
println()
}
if (index % 3 == 0) {
print(" ")
}
print("${elm},")
}
}
//=========================获取默认的1-9 用于去除impossible========================================
private fun getDefaultHashSet(): MutableSet<Int> {
var defaultHashSet = mutableSetOf<Int>()
for (i in 1..9) {
defaultHashSet.add(i)
}
return defaultHashSet
}
}
//（1,1）（2,2）
fun setData(row: Int, col: Int, num: Int) {
defaultNum[(row - 1) * 9 + col - 1] = num
}
}
