Sudoku: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 2,444: / Line 2,444: @@
 2 6 | 4 1 9 | 7 3 5
 </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}}==