Sudoku game or humans vs. machines (computers in this case)

Few days ago, a friend of mine posted the following link on his wall on Facebook. The main question from that article was "how long will it take to crack ...the world's hardest Sudoku?". I felt like being challenged.

I am not a Sudoku fan, however my wife and my son are. Just to annoy them (not because I am a bad person :), but because I was looking for a way to sort the Sudoku puzzles in a quicker way, when being asked to assist them ... so, "I am lazy" is a more precise definition) and because I am a software engineer, I wrote a long time ago (of course I was inspired, it's not entirely my contribution) a little piece of Java code to resolve such puzzles. As a result, I decided to test it.

Here is the code:

import java.util.*;
import java.io.*;

public class ResolveSudoku {
 private static final int[] sudokuMatrix = {0,0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,0};

 // load the content from file
 public static void load(String file) throws Exception {
  String str = null;
  int line = 0;
  BufferedReader br = new BufferedReader(new FileReader(file));

  while ((str = br.readLine()) != null) {
   if (str.trim().length() == 0 || str.startsWith("#")) 
    continue;

   if (line >= 9) {
    line = 10;
    break;
   }

   String[] vls = str.split(",");
   if (vls.length != 9) {
    br.close();
    throw new Exception("Line " + (line + 1) + 
     " has illegal number of elements!");
   }

   for (int i = 0; i < 9; ++i) {
    int value = Integer.parseInt(vls[i].trim());
    if (value < 0 || value > 9) {
     br.close();
     throw new Exception("Line " + (line + 1) + 
      " position " + (i + 1) + " has illegal value!");
    }
    sudokuMatrix[line*9 + i] = value;
   }

   ++line;
  }

  br.close();
  if (line != 9) throw new Exception("File " + file + 
   " has illegal number of lines!");
 }

 // print the content of the sudoku matrix
 public static void printMatrix() {
  for (int i = 0; i < 81; ++i) {
   if (i != 0 && i % 3  == 0) System.out.print(" ");
   if (i != 0 && i % 9  == 0) System.out.println();
   if (i != 0 && i % 27 == 0) System.out.println();

   if (sudokuMatrix[i] == 0) System.out.print(".");
   else System.out.print(sudokuMatrix[i]);
  }
  System.out.println("\n");
 }

 private static boolean check(int row, int col, int value) {
  // check if row is ok
  int tmp = row * 9;
  for (int i = 0; i < 9; ++i) {
   if (sudokuMatrix[tmp + i] == value) 
    return false;
  }

  // check if column is ok
  for (int i = 0; i < 9; ++i) {
   if (sudokuMatrix[i*9 + col] == value) 
    return false;
  }

  // check if box is ok
  tmp = (row / 3)*27 + (col / 3)*3;
  if (sudokuMatrix[tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;

  tmp += 7;
  if (sudokuMatrix[tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;

  tmp += 7;
  if (sudokuMatrix[tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;

  return true;
 }

 public static boolean findSolution(int row, int col) {
  if (row == 9) {
   row = 0;
   if (++col == 9) return true;
  }

  int pos = row * 9 + col;
  if (sudokuMatrix[pos] != 0) return findSolution(row + 1, col);

  for (int i = 1; i <= 9; ++i) {
   if (check(row, col, i)) {
    sudokuMatrix[pos] = i;
    if (findSolution(row + 1, col)) return true;
   }
  }

  // reset the value back to zero 
  sudokuMatrix[pos] = 0; 
  return false;
 }

 public static void main(String[] args) throws Exception {
  load(args[0]);
  printMatrix();

  long start = System.currentTimeMillis();
  boolean res = findSolution(0, 0);
  long ex_time = System.currentTimeMillis() - start;

  if (res) printMatrix();
  else System.out.println("No solution!");

  System.out.println("Execution time: " + ex_time + "ms.");
 }
}

It's, basically, a routine that reads the puzzle's matrix from a file and another one that performs a brute force (i.e. analysing all the possible cases) in form of (I would say) an elegant recursive method call. Having the following input:

0,0,5,3,0,0,0,0,0
8,0,0,0,0,0,0,2,0
0,7,0,0,1,0,5,0,0
4,0,0,0,0,5,3,0,0
0,1,0,0,7,0,0,0,6
0,0,3,2,0,0,0,8,0
0,6,0,5,0,0,0,0,9
0,0,4,0,0,0,0,3,0
0,0,0,0,0,9,7,0,0

The problem was solved in ~30 milliseconds (after the byte code was JIT-ed on my "2.13Ghz, Core 2 Duo with SSD on board" laptop). And the answer was:

145 327 698
839 654 127
672 918 543

496 185 372
218 473 956
753 296 481

367 542 819
984 761 235
521 839 764

Is HTML5 going to replace Silverlight?

Is HTML5 going to replace Silverlight? Windows 8, facts and rumours from TechRepublic (with various links to other sources):

http://www.techrepublic.com/blog/programming-and-development/windows-8-native-apps-and-html5-facts-and-conjecture/4313

And, a quite unusual turn around from Microsoft ... C++ Renaissance, I guess as a reaction to Object C:

http://channel9.msdn.com/Shows/Going+Deep/Craig-Symonds-and-Mohsen-Agsen-C-Renaissance
http://channel9.msdn.com/Shows/Going+Deep/Mohsen-Agsen-C-Today-and-Tomorrow
http://blogs.msdn.com/b/somasegar/archive/2011/06/15/targeting-heterogeneity-with-c-amp-and-ppl.aspx

Regarding the square root of n

Have you ever caught yourself (assuming you like maths) proving that numbers like $\sqrt{2}$ or $\sqrt{5}$ etc. are irrationals. Here is, more or less, a general statement with the proof.

For $\forall n \in \mathbb{N}$ (natural numbers), either $\sqrt{n} \in \mathbb{N}$ or $\sqrt{n} \in \mathbb{I}$ (irrational numbers, i.e. real numbers minus rational numbers).

There are two possible cases:

1. If $n = p^2$, $p\in \mathbb{N}$ ⇒ $\sqrt{n}=p\in \mathbb{N}$

2. If $n \ne p^2$ or there is no such a $p \in \mathbb{N}$ that would satisfy $n = p^2$, then $\sqrt{n}$ is irrational.

Let's suppose the contrary, i.e. there $\exists p,q \in \mathbb{N}$ and $\gcd(p,q) = 1$ (greatest common divisor) so that
$$\sqrt{n}=\frac{p}{q}$$
This means that $n·q^2=p^2$. From $\gcd(p,q) = 1 \Rightarrow \gcd(p^2,q^2) = 1$.

From the Bézout’s theorem, there $\exists z,t \in \mathbb{Z}$ (integers) so that
$$z\cdot p^2 + t\cdot q^2 = 1 \iff\\ z\cdot n\cdot q^2 + t\cdot q^2 = 1 \iff\\ q^2 \cdot (z\cdot n + t) = 1$$ which means $q^2$ divides $1$, but this is possible only if $q = 1$. As a result $n = p^2$ - contradiction with our initial assumption.

This proves the statement.

System Analyst vs. Business Analyst

People tend to confuse these two terms, the purpose of this article is to clarify them. Business Analyst is a person that is part of the business (which isn't necessarily IT related), knows the business and can articulate what business wants in form of the business requirements. System Analyst is a person with IT background, who knows how IT systems work, how to translate business requirements into technical requirements/artefacts so that they are understandable by the technical team; system designers, developers and testers. I didn't include architects to the list, because system analysis, as a practise, is part of the system architecture.

So, what is typically (this isn't a firm rule) expected from a System Analyst to deliver?
- Functional Requirements
- Non-functional Requirements
- Use Cases
- Wireframes with descriptions of each UI element
- Entity diagrams.

Traceability is another important word for the System Analyst (and not only). It is a way of showing how various artefacts are implementing/realising each other (e.g. use cases realising requirements etc.). In order to produce all these artefacts, it is recommended to use one of the existing, industry recognized UML designing tools. This can be Rational Rose, Sparx Enterprise Architect or anything suitable.

A typical process looks like:

1. A new model is created using the design tool.

2. Business requirements are imported/added to the model.

3. Business requirements, if not detailed enough, are extended with more detailed functional and non-functional requirements, gathered during various sessions with SME (Subject Matter Experts).

4. Functional/Non-functional and business requirements are linked (typically using "association" connector) for traceability reasons.

5. Use cases are elaborated and added to the model. As per the industry standard (check with Google), each use case must have one Basic Path with up to ten sequences/events and zero or more Alternative Paths.

6. For traceability reasons, use cases are linked (typically using "realize" connector) with the requirements they are realising.

7. Wireframes are elaborated and added to the model (I must add, if the tool supports this, e.g. Sparx Enterprise Architect). Wireframes represent the draft versions of the User Interfaces required from the System. The detailed mock-ups are typically elaborated by the graphical designers from the wireframes.

8. Wireframes are linked (typically using "realize" connector) with the use cases they are realising.

9. High level entity diagrams are elaborated and added to the model.

10. Wireframes' UI form elements are mapped (typically using "realize" or "association" connectors) with the relevant attributes of the relevant entities. This is a great way to highlight the re-usable elements to the system designers.

11. All the acronyms, business terms and abbreviations are added to the Model Glossary, this is mandatory regardless of the fact that the tool supports this (e.g. Sparx Enterprise Architect) or not (in which case it can be a separate document).

The following picture is just an example of the expectation.

And don't forget, all these artefacts must be reviewed by SME!

Few remarks:

1. Mock-ups, elaborated by the graphical designers, must follow the User Interface functional/non-functional requirements. For instance DDA (Disability Discrimination Act) requirements/standards, if it is the case.

2. Entity diagrams, provided by the system analyst, aren't expected to be detailed class or database diagrams, this is an exercise for the system designers. They must be part of, what I call, the "requirements language".

For instance, if the business requirement says that "the super user must approve the document before it is published", then there will be an entity Document that will, probably, have a "status" attribute mapped (aggregation or composition) to an enumeration with the elements "DRAFT, READY, APPROVED". The relevant use case (or use cases) will operate with these terms.

Re Java final keyword, immutability and reflection

Few days ago, in a conversation ("Sun Certified Java Programmer " group at http://www.linkedin.com/) regarding Immutability pattern and Java Reflection, somebody came with the following code example (slightly adjusted by me in order to highlight the class attributes initialization order), which I found quite interesting and decided to post it.

So, execute the following code:

import java.lang.reflect.Field; 

class Test {
 public Test() {
  doIt();
 }
 public void doIt() {}
}

public class TestReflection extends Test { 
 private final String name = "Immutable";
 private String n = "n";
 public TestReflection() { } 

 public void doIt() {
  System.out.println("1 = " + name); 
  System.out.println(n); 
  System.out.println("-----");
 }

 public static void main(String[] args) throws Exception { 
  TestReflection abc = new TestReflection();
  Class c1 = Class.forName("TestReflection");
  Field field2 = c1.getDeclaredField("name"); 
  field2.setAccessible(true); 

  System.out.println("2 = " + abc.name); 
  field2.set(abc, "Mutable"); 
  System.out.println("3 = " + abc.name); 
 } 
}

Output: 
1 = Immutable
null
-----
2 = Immutable
3 = Immutable

And the following version of the code:

import java.lang.reflect.Field;

class Test {
 public Test() {
  doIt();
 }
 public void doIt() {}
}
public class TestReflection extends Test { 
 private final String name; 
 private String n = "n";

 public TestReflection() { 
  name = "Immutable"; 
 } 

 public void doIt() {
  System.out.println("1 = " + name); 
  System.out.println(n); 
  System.out.println("-----");
 }

 public static void main(String[] args) throws Exception { 
  TestReflection abc = new TestReflection();
  Class c1 = Class.forName("TestReflection"); 
  Field field2 = c1.getDeclaredField("name"); 

  field2.setAccessible(true); 
  System.out.println("2 = " + abc.name); 
  field2.set(abc, "Mutable"); 
  System.out.println("3 = " + abc.name); 
 } 
}

Output: 
1 = null
null
-----
2 = Immutable
3 = Mutable

The answer to this behaviour can be found in JLS (http://java.sun.com/docs/books/jls/third_edition/html/j3TOC.html), section 17.5.3,

"Even then, there are a number of complications. If a final field is initialized to a compile-time constant in the field declaration, changes to the final field may not be observed, since uses of that final field are replaced at compile time with the compile-time constant. "

Java 32bits vs. 64bits

I was playing recently with a recursive method for building all the possible routes via a set of nodes (with some predefined rules to link each pair of nodes) in Java. Rather than persisting the calculated routes into a file, I keep them in a HashSet.

Having about 138 nodes, this recursive method generates more than 5mln routes. This is quite an intensive calculation that consumes (and this is the point)
- about 1GB RAM with 32 bits JVM and
- about 2GB with 64 bits JVM.

Execution time, for building the routes, is like 17 seconds with 32 bits JVM and 21 seconds with 64 bits JVM.

Obvious question is "What the heck?". Apparently, here are the problems:
1. 64 bits systems are supposed to use (correct) 64 bits pointers (please allow me to use this C/C++ term) for accessing the process address space, thus allowing the process to use/access more (virtual) memory (i.e. 4GB with 32 bits vs. 16TB with 64 bits). But keeping an allocation table for 64 bits pointers (comparing to 32 bits) requires much more memory. So, 1GB vs. 2GB RAM isn't really a JVM problem.

Conclusion: if at some point you decide to use 64 bits JVM, don't forget to adjust the heap volume accordingly, in order to avoid unpleasant surprises.

2. Problem is also related to the way memory chips (DDR SDRAM) are made. Without diving into details (more details here http://lwn.net/Articles/250967/), accessing physical memory is a very slow operation and CPU tends to store frequently accessed data in its cache memory (L1, L2 and/or L3, which are far better memory chips, more expensive though). Modern compilers also tend to help developers from this point of view, if they follow some very well known rules (e.g. use arrays, stack is "cache-able", don't use "volatile" unless you really know what it is, etc.). But larger pointers require different memory alignment, thus 64 bits pointers aren't so cache efficient in the way 32 bits pointers are (e.g. when thinking about arrays). As a result, accessing physical RAM (or CPU cache miss) is the result of the 4 seconds difference.

To conclude: take care when deciding about using 32 bits or 64 bits Java.

And few online resources:
http://benjchristensen.com/2007/02/16/32-bit-versus-64-bit-jdk-memory-usage/
http://portal.acm.org/citation.cfm?id=1107407