Sudoku: Difference between revisions
Content deleted Content added
→{{header|Perl}}: shorter version (not parsing file on command line) |
→{{header|Groovy}}: new solution |
||
Line 2,444: | Line 2,444: | ||
8 2 6 | 4 1 9 | 7 3 5 |
8 2 6 | 4 1 9 | 7 3 5 |
||
</pre> |
</pre> |
||
=={{header|Groovy}}== |
|||
Brute Force Solution: |
|||
<lang groovy>final CELL_VALUES = ('1'..'9') |
|||
class GridException extends Exception { |
|||
GridException(String message) { super(message) } |
|||
} |
|||
def string2grid = { string -> |
|||
assert string.size() == 81 |
|||
(0..8).collect { i -> (0..8).collect { j -> string[9*i+j] } } |
|||
} |
|||
def gridRow = { grid, i, j -> grid[i] as Set } |
|||
def gridCol = { grid, i, j -> grid.collect { it[j] } as Set } |
|||
def gridBox = { grid, i, j -> |
|||
def tl = [i.intdiv(3)*3, j.intdiv(3)*3] |
|||
(0..2).collect { row -> (0..2).collect { col -> grid[tl[0]+row][tl[1]+col] } }.flatten() as Set |
|||
} |
|||
def nextEmpty = { grid -> |
|||
def jTries = grid.collect { row -> (0..8).find { ! (row[it] in CELL_VALUES) } } |
|||
def i = (0..8).find { jTries[it] != null } |
|||
i == null ? null : [i, jTries[i]] |
|||
} |
|||
def isSolved = { grid -> ! (grid.flatten().find { !(it in CELL_VALUES) }) } |
|||
def solve |
|||
solve = { grid -> |
|||
def ij = nextEmpty(grid) |
|||
if (! ij) { return grid } |
|||
def checkVals = (gridRow(grid, ij[0], ij[1]) + gridCol(grid, ij[0], ij[1]) + gridBox(grid, ij[0], ij[1])) as Set |
|||
CELL_VALUES.each { |
|||
if (! (it in checkVals || isSolved(grid))) { |
|||
try { |
|||
grid[ij[0]][ij[1]] = it |
|||
grid = solve(grid) |
|||
} catch (GridException ge) { |
|||
grid[ij[0]][ij[1]] = '.' |
|||
} |
|||
} |
|||
} |
|||
if (!isSolved(grid)) { |
|||
throw new GridException('Invalid Sudoku Grid') |
|||
} |
|||
grid |
|||
}</lang> |
|||
Test: |
|||
<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) |
|||
println 'PUZZLE' |
|||
grid.each { println it } |
|||
println '\nSOLUTION' |
|||
def start = System.currentTimeMillis() |
|||
def solution = solve(grid) |
|||
def elapsed = (System.currentTimeMillis() - start)/1000 |
|||
solution.each { println it } |
|||
println "\nELAPSED: ${elapsed} seconds"</lang> |
|||
Output: |
|||
<pre>PUZZLE |
|||
[4, ., ., ., ., ., ., 6, .] |
|||
[5, ., ., ., 8, ., 9, ., .] |
|||
[3, ., ., ., ., 1, ., ., .] |
|||
[., 2, ., 7, ., ., ., ., 1] |
|||
[., 9, ., ., ., ., ., 4, .] |
|||
[8, ., ., ., ., 3, ., 5, .] |
|||
[., ., ., 2, ., ., ., ., 7] |
|||
[., ., 6, ., 5, ., ., ., 8] |
|||
[., 1, ., ., ., ., ., ., 6] |
|||
SOLUTION |
|||
[4, 8, 2, 9, 7, 5, 1, 6, 3] |
|||
[5, 6, 1, 3, 8, 2, 9, 7, 4] |
|||
[3, 7, 9, 6, 4, 1, 8, 2, 5] |
|||
[6, 2, 5, 7, 9, 4, 3, 8, 1] |
|||
[1, 9, 3, 5, 6, 8, 7, 4, 2] |
|||
[8, 4, 7, 1, 2, 3, 6, 5, 9] |
|||
[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> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |