I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Sudoku

05.16.2013
| 4788 views |
  • submit to reddit

It's Thursday already, so time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Sudoku Puzzle Solver

Given any sudoku  puzzle, write a method that can solve it. An example of a puzzle this method would be expected to handle follows:

Comments

sun east replied on Fri, 2013/05/17 - 4:21am

Here is my scala code:

/**
 * The puzzle is represented by an int array of size 81.
 * This method would modified the array to get a solution.
 */
def solve(p: Array[Int], start: Int = 0): Boolean = start match {
  case -1 => false
  case 81 => true
  case i  =>
    if(p(i) > 0) solve(p, i + 1)
    else {
      val cand = (0 until 81).filter(n => (n-i)%9*(n/9^i/9)*(n/27^i/27|n%9/3^i%9/3) == 0)
                             .map(n => 1 << p(n)).foldLeft(0)( _|_ )
      (9 to 0 by -1).exists{ n => p(i) = n; (cand >> n & 1) == 0 && solve(p, i+1) }
    }
}

sun east replied on Fri, 2013/05/17 - 4:39am

Here is a test case using the given puzzle:

scala> val puzz =
     |            """5 3 0  0 7 0  0 0 0
     |               6 0 0  1 9 5  0 0 0
     |               0 9 8  0 0 0  0 6 0
     |
     |               8 0 0  0 6 0  0 0 3
     |               4 0 0  8 0 3  0 0 1
     |               7 0 0  0 2 0  0 0 6
     |
     |               0 6 0  0 0 0  2 8 0
     |               0 0 0  4 1 9  0 0 5
     |               0 0 0  0 8 0  0 7 9"""
scala> val arr = puzz.replaceAll("""\s+""","").map(_.asDigit).toArray
scala> solve(arr)
res1: Boolean = true
scala> (0 until 81).grouped(9).map(_.map("%d" format arr(_)).mkString).mkString("\n")
res2: String =
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

Eliot Moss replied on Wed, 2013/05/22 - 7:15am

 I wrote one of these a while back. I converted the given puzzle into a satisfiability problem (essentially a big boolean formula where the variables are things like "this square contains a 3" and that expresses all the usual Sudoku rules) and tossed it at a Java SAT solver. This leverages the effort people have put into making SAT solvers fast and correct.  It is probably far from the smaller or even most elegant program to solve this problem, but it is straightforward and insures a solution is found quickly.

Jim Passmore replied on Wed, 2013/05/22 - 9:08am

 Credit where due, I recently saw this 162 character Sudoku solver in Python.

http://jakevdp.github.io/blog/2013/04/15/code-golf-in-python-sudoku/

Bean Duke replied on Wed, 2013/05/22 - 11:32am

That's implementation my fellow at Uni  showed me


:- use_module(library(clpfd)).
sudoku(Rows) :-
        length(Rows, 9), maplist(length_(9), Rows),
        append(Rows, Vs), Vs ins 1..9,
        maplist(all_distinct, Rows),
        transpose(Rows, Columns),
        maplist(all_distinct, Columns),
        Rows = [A,B,C,D,E,F,G,H,I],
        blocks(A,B,C),blocks(D,E,F),blocks(G,H,I).
length_(L, Ls) :- length(Ls, L).
blocks([], [], []).
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-
        all_distinct([A,B,C,D,E,F,G,H,I]),
        blocks(Bs1, Bs2, Bs3).

Yes, it's prolog

Paul Murray replied on Sun, 2014/01/26 - 7:49am

Put a random number in each empty cell, and check to see if the solution is valid. Loop until a solution is found.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.