Sudoku: Difference between revisions
Content deleted Content added
Updated D version |
|||
Line 4,006:
|826|419|735|
+---+---+---+</pre>
The implementation above doesn't work so effective for sudokus like Bracmat version, therefore I implemented a second version inspired by Java section:
{{works with|Scala|2.9.1}}
<lang scala>object SudokuSolver extends App {
object Solver {
var solution = new Array[Int](81)
val fap: (Int, Int) => Int = (row, col) => (row)*9+col //function array position
def solve(listOfFields: List[Int]): List[Int] = {
solution = listOfFields toArray
val mRowSubset = new Array[Boolean](81)
val mColSubset = new Array[Boolean](81)
val mBoxSubset = new Array[Boolean](81)
def initSubsets: Unit = {
for (row <- 0 to 8) {
for (col <- 0 to 8) {
val value = solution(fap(row, col))
if (value != 0)
setSubsetValue(row, col, value, true)
}
}
}
def setSubsetValue(r: Int, c: Int, value: Int, present: Boolean): Unit = {
mRowSubset(fap(r, value - 1)) = present
mColSubset(fap(c, value - 1)) = present
mBoxSubset(fap(computeBoxNo(r, c), value - 1)) = present
}
def computeBoxNo(r: Int, c: Int): Int = {
val boxRow = r / 3
val boxCol = c / 3
return boxRow * 3 + boxCol
}
def isValid(r: Int, c: Int, value: Int): Boolean = {
val vVal = value - 1
val isPresent = mRowSubset(fap(r, vVal)) || mColSubset(fap(c, vVal)) || mBoxSubset(fap(computeBoxNo(r, c), vVal))
return !isPresent
}
def solve(row: Int, col: Int): Boolean = {
var r = row
var c = col
if (r == 9) {
r = 0
c += 1
if (c == 9)
return true
}
if(solution(fap(r,c)) != 0)
return solve(r+1,c)
for(value <- 1 to 9)
if(isValid(r, c, value)) {
solution(fap(r,c)) = value
setSubsetValue(r, c, value, true)
if(solve(r+1,c))
return true
setSubsetValue(r, c, value, false)
}
solution(fap(r,c)) = 0
return false
}
def checkSol: Boolean = {
initSubsets
if ((mRowSubset.exists(_==false)) || (mColSubset.exists(_==false)) || (mBoxSubset.exists(_==false))) return false
true
}
initSubsets
val ret = solve(0,0)
if (ret)
if (checkSol) return solution.toList else Nil
else
return Nil
}
}
val f2Str: List[Int] => String = fields => {
val f2Stri: List[Int] => String = fields => {
val sepLine = "+---+---+---+"
val sepPoints = Set(2,5,8)
val fs: (Int, Int) => String = (i, v) => v.toString.replace("0"," ")+(if (sepPoints.contains(i%9)) "|" else "")
val s = sepLine+"\n"+(0 to fields.size-1).map(i => (if (i%9==0) "|" else "")+fs(i,fields(i))+(if (i%9==8) if (sepPoints.contains(i/9)) "\n"+sepLine+"\n" else "\n" else "")).foldRight("")(_+_)
s
}
val s = fields match {case Nil => "no solution!!!" case _ => f2Stri(fields)}
s
}
val elapsedtime: (=> Unit) => Long = f => {val s = System.currentTimeMillis; f; (System.currentTimeMillis - s)/1000}
var sol = List[Int]()
val sudokus = List(
("riddle used in Ada section:",
"394..267....3..4..5..69..2..45...9..6.......7..7...58..1..67..8..9..8....264..735"),
("riddle used in Bracmat section:",
"..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9"),
("riddle from Groovy section: 4th exceptionally difficult example in Wikipedia: ~80 seconds",
"..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5.."),
("riddle used in Ada section with incorrect modifactions - it should fail:",
"3943.267....3..4..5..69..2..45...9..6.......7..7...58..1..67..8..9..8....264..735"),
("riddle constructed with mess - it should fail too:",
"123456789456789123789123456.45..89..6.......72.7...58.31..67..8..9..8....264..735"))
for (sudoku <- sudokus) {
val desc = sudoku._1
val riddle = sudoku._2.replace(".","0").toList.map(_.toString.toInt)
println(desc+"\n"+f2Str(riddle)+"\n"
+"elapsed time: "+elapsedtime(sol = Solver.solve(riddle))+" sec"+"\n"+"solution:"+"\n"+f2Str(sol)
+("\n"*2))
}
}</lang>
output:
<pre>riddle used in Ada section:
+---+---+---+
|394| 2|67 |
| |3 |4 |
|5 |69 | 2 |
+---+---+---+
| 45| |9 |
|6 | | 7|
| 7| |58 |
+---+---+---+
| 1 | 67| 8|
| 9| 8| |
| 26|4 |735|
+---+---+---+
elapsed time: 0 sec
solution:
+---+---+---+
|394|852|671|
|268|371|459|
|571|694|823|
+---+---+---+
|145|783|962|
|682|945|317|
|937|126|584|
+---+---+---+
|413|567|298|
|759|238|146|
|826|419|735|
+---+---+---+
riddle used in Bracmat section:
+---+---+---+
| | | |
| | 3| 85|
| 1| 2 | |
+---+---+---+
| |5 7| |
| 4| |1 |
| 9 | | |
+---+---+---+
|5 | | 73|
| 2| 1 | |
| | 4 | 9|
+---+---+---+
elapsed time: 43 sec
solution:
+---+---+---+
|987|654|321|
|246|173|985|
|351|928|746|
+---+---+---+
|128|537|694|
|634|892|157|
|795|461|832|
+---+---+---+
|519|286|473|
|472|319|568|
|863|745|219|
+---+---+---+
riddle from Groovy section: 4th exceptionally difficult example in Wikipedia: ~80 seconds
+---+---+---+
| 3| | |
|4 | 8 | 36|
| 8| |1 |
+---+---+---+
| 4 | 6 | 73|
| |9 | |
| | 2| 5|
+---+---+---+
| 4| 7 | 68|
|6 | | |
|7 |6 |5 |
+---+---+---+
elapsed time: 3 sec
solution:
+---+---+---+
|123|456|789|
|457|189|236|
|968|327|154|
+---+---+---+
|249|561|873|
|576|938|412|
|831|742|695|
+---+---+---+
|314|275|968|
|695|814|327|
|782|693|541|
+---+---+---+
riddle used in Ada section with incorrect modifactions - it should fail:
+---+---+---+
|394|3 2|67 |
| |3 |4 |
|5 |69 | 2 |
+---+---+---+
| 45| |9 |
|6 | | 7|
| 7| |58 |
+---+---+---+
| 1 | 67| 8|
| 9| 8| |
| 26|4 |735|
+---+---+---+
elapsed time: 0 sec
solution:
no solution!!!
riddle constructed with mess - it should fail too:
+---+---+---+
|123|456|789|
|456|789|123|
|789|123|456|
+---+---+---+
| 45| 8|9 |
|6 | | 7|
|2 7| |58 |
+---+---+---+
|31 | 67| 8|
| 9| 8| |
| 26|4 |735|
+---+---+---+
elapsed time: 0 sec
solution:
no solution!!!</pre>
=={{header|Tcl}}==
| |||