How to Solve Sudoku using Hadoop ?

By ayalcinkaya | Updated: August 28, 2012

Viewed: 621 (+3 pv/w)

Tags: hadoop sudoku

Hadoop has provides an example jar file for test purposes. In this jar file there is an example to solve sudoku problems.

1. Input File

To use this example we need to make an input file for the sudoku problem. In this file each sudoku cell can be either a number or ‘?’ with spaces as separators.Like this one:

File : puzzle1.dta

8 5 ? 3 9 ? ? ? ?
? ? 2 ? ? ? ? ? ?
? ? 6 ? 1 ? ? ? 2
? ? 4 ? ? 3 ? 5 9
? ? 8 9 ? 1 4 ? ?
3 2 ? 4 ? ? 8 ? ?
9 ? ? ? 8 ? 5 ? ?
? ? ? ? ? ? 2 ? ?
? ? ? ? 4 5 ? 7 8

You can find this “puzzle1.dta” file in Hadoop directory :

hadoop-0.20.2/src/examples/org/apache/hadoop/examples/dancing/puzzle1.dta

or

hadoop-2.0.0-alpha-/src/hadoop-mapreduce-project/hadoop-mapreduce-examples/
	src/main/java/org/apache/hadoop/examples/dancing/puzzle1.dta

2. Hadoop Part

Now we need to save this input file in our local directory. And give this input to hadoop example jar. Start hadoop and run this command:

$hadoop-directory/bin/hadoop jar hadoop-examples-version.jar sudoku puzzle1.dta

Solving puzzle1.dta
8 5 1 3 9 2 6 4 7
4 3 2 6 7 8 1 9 5
7 9 6 5 1 4 3 8 2
6 1 4 8 2 3 7 5 9
5 7 8 9 6 1 4 2 3
3 2 9 4 5 7 8 1 6
9 4 7 2 8 6 5 3 1
1 8 5 7 3 9 2 6 4
2 6 3 1 4 5 9 7 8

Found 1 solutions

Hadoop give you the all possible solutions for the puzzle in a few seconds.( If there is more than one answer the time will be higher).

If you have questions,you can write a comment to me…

References

1. Apache Hadoop
2. Dancing Links algorithm