Rosetta Code

Sudoku: Difference between revisions

← Older editNewer edit →
Content deleted Content added
→‎{{header|Groovy}}: improved speed
Line 2,446:
 
=={{header|Groovy}}==
'''Adaptive "Non-guessing Then Guessing" Solution'''
Brute Force Solution:
 
Non-guessing part is iterative. Guessing part is recursive. Implementation uses exception handling to back out of bad guesses.
<lang groovy>final CELL_VALUES = ('1'..'9')
 
Line 2,467 ⟶ 2,469:
}
 
def nextEmptyassignCandidates = { grid, empties ->
empties.each { empty ->
def jTries = grid.collect { row -> (0..8).find { ! (row[it] in CELL_VALUES) } }▼
def checkValsunavailable = (gridRow(grid, ij[0]empty.i, ij[1]empty.j) + gridCol(grid, ij[0]empty.i, ij[1]empty.j) + gridBox(grid, ij[0]empty.i, ij[1]empty.j)) as Set▼
def i = (0..8).find { jTries[it] != null }
empty.candidates = CELL_VALUES - unavailable
i == null ? null : [i, jTries[i]]
}
empties.sort { - it.candidates.size() }
if (empties && ! empties[-1].candidates) {
throw new GridException('Invalid Sudoku Grid')
}
empties
}
 
def emptyList = { grid ->
▲ def jTriesempties = grid(0..8).collect { rowi -> (0..8).findfindAll { j -> ! (rowgrid[i][itj] in CELL_VALUES) } }\
.collect {j -> [i: i, j: j] } }.flatten()
assignCandidates(grid, empties)
}
 
Line 2,477 ⟶ 2,491:
def solve
solve = { grid ->
def ijempties = nextEmptyemptyList(grid)
if (! ijempties) { return grid }
while (empties[-1].candidates.size() == 1) {
▲ def checkVals = (gridRow(grid, ij[0], ij[1]) + gridCol(grid, ij[0], ij[1]) + gridBox(grid, ij[0], ij[1])) as Set
def empty = empties.pop()
CELL_VALUES.each {▼
grid[empty.i][empty.j] = empty.candidates[0]
if (! (it in checkVals || isSolved(grid))) {▼
if (! empties) { return grid }
assignCandidates(grid, empties)
}
if (! empties) { return grid }
def empty = empties.pop()
▲ CELL_VALUESempty.candidates.each {
▲ if (! (it in checkVals || isSolved(grid))) {
try {
grid[ij[0]][ij[1]]def sGrid = itgrid.collect { row -> row.collect { cell -> cell } }
gridsGrid[empty.i][empty.j] = solve(grid)it
grid = solve(sGrid)
} catch (GridException ge) {
grid[ij[0]empty.i][ij[1]empty.j] = '.'
}
}
Line 2,497 ⟶ 2,519:
 
Test:
<lang groovy>def sudokus = [
<lang groovy>def sudoku = '4......6.5...8.9..3....1....2.7....1.9.....4.8....3.5....2....7..6.5...8.1......6',
def grid = string2grid(sudoku)▼
'....839..1......3...4....7..42.3....6.......4....7..1..2........8...92.....25...6']
println 'PUZZLE'▼
gridsudokus.each { printlnsudoku it }->
▲ def grid = string2grid(sudoku)
 
println '\nSOLUTIONnPUZZLE'
solution grid.each { println it }▼
def start = System.currentTimeMillis()▼
def solution = solve(grid)▼
▲ println 'PUZZLE\nSOLUTION'
def elapsed = (System.currentTimeMillis() - start)/1000▼
▲ def start = System.currentTimeMillis()
▲solution.each { println it }
▲ def solution = solve(grid)
println "\nELAPSED: ${elapsed} seconds"</lang>▼
▲ def elapsed = (System.currentTimeMillis() - start)/1000
solution.each { println it }
▲ println "\nELAPSED: ${elapsed} seconds"</lang>
}</lang>
 
Output:
Line 2,530 ⟶ 2,556:
[9, 5, 8, 2, 1, 6, 4, 3, 7]
[7, 3, 6, 4, 5, 9, 2, 1, 8]
[2, 1, 4, 8, 3, 7, 5, 9, 6]</pre>
 
ELAPSED: 0.506 seconds
 
PUZZLE
[., ., ., ., 8, 3, 9, ., .]
[1, ., ., ., ., ., ., 3, .]
[., ., 4, ., ., ., ., 7, .]
[., 4, 2, ., 3, ., ., ., .]
[6, ., ., ., ., ., ., ., 4]
[., ., ., ., 7, ., ., 1, .]
[., 2, ., ., ., ., ., ., .]
[., 8, ., ., ., 9, 2, ., .]
[., ., ., 2, 5, ., ., ., 6]
 
SOLUTION
[7, 6, 5, 4, 8, 3, 9, 2, 1]
[1, 9, 8, 7, 2, 6, 4, 3, 5]
[2, 3, 4, 9, 1, 5, 6, 7, 8]
[8, 4, 2, 5, 3, 1, 7, 6, 9]
[6, 1, 7, 8, 9, 2, 3, 5, 4]
[3, 5, 9, 6, 7, 4, 8, 1, 2]
[9, 2, 6, 1, 4, 7, 5, 8, 3]
[5, 8, 1, 3, 6, 9, 2, 4, 7]
[4, 7, 3, 2, 5, 8, 1, 9, 6]
 
ELAPSED: 33.43 seconds</pre>
 
=={{header|Haskell}}==
Retrieved from "https://rosettacode.org/wiki/Sudoku"