Sudoku Generator - A Bug Fixing Patch

The Full Story

• How to write a Sudoku Solver
• Sudoku Solver - Part 2
• How to write a Sudoku Generator

The Problem

In the post "How to write a Sudoku Generator", the reader "vito kows" reported two issues.

1. There is a bug in solutionCount().
2. The generator takes too long for some seeds.

I am going to fix them below.

The Solution

1. Fix the bug in solutionCount()

Locate the original source code in solutionCount() :

Change it to:

Testing the Unique Solution Fix

Before proceeding to the next fix, you are suggested to compile and test it with :

javac *.java
java SudokuGenerator 28

2 Adding timeout in generate()

2.1 Locate source code in generate(int seed)

Change it to:

2.2 Locate source code in solveByRecursion()

Change it to

Final Testing

As a bonus for those who visited here, I am going to spend some CPU time to generate some puzzles with less than 30 open digits at the bottom of this post. And I will include the sample program that generates those puzzles.

Appendix - Puzzles with less than 30 open cells

String[] puzzles=new String[] {
"59......1..8..96.4.12.7.89.4.18..........6.17....2....8..24.....4....9...5.1.8...",
".2...7...5..2........68..3.7.5...6...4....5..69...3.8...1.6........7.842.3....176",
".621........75..4.5....6..274..6..3....5......5.....813.19...68.....34....561....",
"8...2...5.6.......9.73.1.4.6.5...9..7..9368...89.5....2.14...6....1....3....784..",
"....76...8.1....4...385............7...39.58.9...4.3.2...1.92..6...8..93.95...8..",
".....7..48.......31...46.8....19..........3.2.27...4.9..945...67..6.8....3...98.5",
"..3.87....1..4....8.7.....5.3..1.2..72...5.1.....6...467.....89.5.1......81..9.2.",
".2...98..7....1..6.68....1.....3...4..1........467..3......29..9168..32..839..4..",
".......93..971.8...6........3.124..6.7.59.48.942.......856.1............7.138....",
"7.......38...39......1.5.46...6.1..4.21...975.......6..82.9.6.....3.7.....3..81.9",
"......2.5.6..4.9..7.4.3......5..4...1..7...289......1..7......2.5.8.2.36....7....",
"..5....7...8.7....6..3.5..2..7.4..3638..5.1...9.1...2..4.761.....14...53.....3..7",
"..9..2.4...38....6.....3..23..65.7..9..4...63.2.3..1.5....8..7.69........7..1.4.8",
".5....23....4.......821.9........46.3........5..79...2..3....8..8.36..74.94..7..6",
"2....7.3.5..9.6.........8.11.64...873.58.........1.345..3....2.62.5.39.8.........",
"7...1.......586..164...3..5.3.7..1.44.8....2.....64.....7.3.9.85....1.6....29....",
".1...5......47.....6.3...8.......35..79.1.....2..58.6.6..7....48375....2.....6.3.",
"3.....4....8....63....27.185.67.2.89.2...3..1..3.6........3..5.7..9.1........692.",
"2...945.....2.......1..6....4.8.....1.2....73.6.1.2.89....1.3.47....3.5......97.6",
"7.326....8......695..19...3.3.....4...947...51.....6....8..13....5..2...3....729.",
"6.......5.9...6....47.536.2..43.2..71....78....61...2.2...4...1....39.8.5...2...3",
"..95...47.6..28.3...8.1....3.18.97....6...2....71...6...3.....8...6....58.53.....",
"2...3..966...948..4...15..2..6......9.5.....4....516...82...369....6..7.3..58....",
".3.4.......9..7..4.862.9....5..4..12...8...7...76...93.9....2.7.......6816.......",
"2...3..5.5..8.24........7.6.1..5.....6...3...3.2197...8.5...........1..493....2..",
".9...53...7..2.....4.38.5..3...41.6.....5.7.2..9.....84...9..71.8.1..64..6.8.....",
".....5.69..3..6.8.....78..23.....2...79......2.8.3....7.58.2.3.61.5...........19.",
"..93..7..85............63.221.6...5.7..8......4.....2.96.2.......75.8.4.5...6.93.",
".475....22..1.8.3....3..49.1.9.2.....2.4.........3..7.47....85.6..7.9.1....8.4..7",
"....24...4.3.5..7...2..3.........42...6.4..398..9........37961...916..45.7...5...",
".45....3..683.9......2.8..4.7..9......9..26......3..5..9....8.5.1.......3..415...",
"..8...92...6.32...5.....78...17..2...3....4...2...8..5....4..7175...1......27..69",
"..638....1.....3.98.71.....9..5......6.84.2.73.....6.545..1...66..4.3.....9.5..4.",
".8.35.9..7...81.....6....1....938.4...12....9.......3.4...932.7.9...2..16.....4.5",
".5......781.3.....2..7.415..8.2..4..4.....3.1..1.65..89..5..7.....63..8.......632",
"72..984...95...7......4..5.95..8...21......6.....7.3..3897..5......3.2.....8.1..9",
"...95.8.........4.341...7..19..7.2...2.5....3......4.5.5....124.74.9.3688..2.....",
};

Sound Programming - Part 5

Playing a Wave file

This is in response to a reader's comment in Sound Programming - Part 2.

I am going to show how to play a sound file using similar API as Beep.java and FadeBeep.java

This is part 5 of the series. If you are interested in the whole series, go to the Featured page.

Simple Wave Player

A wave file player with Fading out Effect

Since the comment is under FadeBeep.java, I would assume the reader wants a fading out effect while playing the sound file. Here is a sample that works for 16-bit wave file.

Java String Highlighter

Introduction

In Java Comment Highlighter, I have demonstrated how to highlight all Java comment in a text file, using the regular expression technique.

I am now going to use similar technique to write a String highlighter in Java, which will highlight all quoted string in a Java source file. The program will read a text file (a.txt) containing Java source code and convert it to a.html, with all String literals highlighted. We will use HtmlWriter.java as a starting point. You are recommended to read it first.

Replacement with Regular Expression

The regular expression of matching a quoted String in Java is :

It is not very obvious. I will try to explain it below.

Explaining the Regular Expression

Regular Expression	Explanation
"	Match a quote first
[^"\\]*	then repeatedly skipping characters until a quote or a stroke is read
(	if we read a stroke, then begin
\\.	skip one character following the stroke
[^"\\]*	once again, repeatedly skipping characters until a quote or a stroke is read
)	end if a storke is read
*	Repeat the above bracket group until no more stroke is found before the ending quote
"	Finally, match the ending quote

The regular expression is actually :

"[^"\\]*(\\.[^"\\]*)*"

Optionally, to optimize it a little bit, we may add a question mark and a colon to mark a non-capturing group.

"[^"\\]*(?:\\.[^"\\]*)*"

To store the regular expression in a Java String, we need to escape all the quote and stroke characters. Hence we have :

Deriving the regular expression from DFA

This is another way of deriving the regular expression of a quoted String. We will derive it by drawing a state diagram of a imaginary automatic machine that will match the quoted String. DFA stands for Deterministic Finite Automata. It is Finite because it has finite number of states. It is deterministic because for every input character it know where to go. DFA has a strict definition which is easy to be found on the web. Hence I will just draw the state diagram here.

State Transition

If we are in q0 and read a quote, we will go to q6
We represent the above transition by:

  q0" => q6

If we are in q6 and read a quote, we will go to q8

  q6" => q8 

If we are in q6 and read a stroke, we will go to q7

  q6\ => q7

f we are in q6 and read a char other than a quote or a stroke, then we will go back to q6

  q6[^"\] => q6

If we are in q7 and read any char, we will go to q6

  q7. => q6

The dot means any character in the alphabet. Let's define the alphabet to be the set of all ASCII characters excluding the new line character.

Full list of Transitions

(1)     q6" => q8 
(2)     q0" => q6
(3)     q7. => q6
(4) q6[^"\] => q6
(5)     q6\ => q7

We may combine (2), (3) and (4) to form a new transition by using the union character.

(6) q0"|q7.|q6[^"\] => q6

Looking at the third union, we are forming a loop. We will use the * character to represent the loop.

(7) (q0"|q7.)[^"\]* => q6

Rewriting it by distributing the star to each union, we have:

(8) q0"[^"\]*|q7.[^"\]* => q6

From (5), we may substitute q7 with q6\

(9) q0"[^"\]*|q6\.[^"\]* => q6

Now we have another loop, so we use the star to represent the loop again.

(10) q0"[^"\]*(\.[^"\]*)* => q6

We may now substitute (10) into (1)

(1)  q6" => q8  that means : 
(11) q0"[^"\]*(\.[^"\]*)*" => q8

That means starting from the initial state q0, we may arrive at the final state q8 by the regular expression:

  "[^"\\]*(\\.[^"\\]*)*"

Note that stroke is a meta character in regular expression and hence I have escaped all the stroke characters (become double strokes)

The expression derived by the DFA is the same as the one I explained above.

Highlighting the String

Once we have the regular expression ready, it is simple to implement a String highlighter. Since the implementation is very similar to the comment highlighter, I will not repeat here.

Base64 Encoder and Decoder in Java

Introduction

There are many third party libraries providing Base64 encoding and decoding functions. Many of them are open source solution. I am not going to say too much on the topic. I would just provide my implementation here. If you want to know more, go to the wiki page.


Source

The source contains over 200 lines, however about half of them are comments and unit test. Hence the encode() and decode() function are not really complex. In case you find reading other programmer code difficult. I would provide a typical way of how I read other people code.

Read the comment header first, then scroll down to the main program to see how to use the functions. Then read the functions following the flow in main().

Java Comment Highlighter

Introduction

I am going to demonstrate how to write a simple comment highlighter in Java, which will highlight all Java style comments. The program will read a text file (a.txt) containing Java source code and convert it to a.html, with all comments highlighted. We will use HtmlWriter.java as a starting point. You are recommended to read it first.

Replacement with Regular Expression

In HtmlWriter.java, we used the following to escape all special characters of the HTML output.

To highlight all comments, all we need to do is adding one more replace statement.

For example, the following statement will bold all comments in the source file.

The following is a typical output:

/***********************
*  A Simple Testing
************************/

class A
{
  public static void main(String[] args)
  {
    int b=10;    
    for (int i=0;i<b;i++)  // just a test
      System.out.print("Hello, \"world\"\n");
  }
}


/* End of File */

Painting the Comment in a Different Color

A little modification of the above replace statement would paint the comment in a different color.

The output will now become:

/***********************
*  A Simple Testing
************************/

class A
{
  public static void main(String[] args)
  {
    int b=10;    // just a test
    for (int i=0;i<b;i++)
      System.out.print("Hello, \"world\"\n");
  }
}


/* End of File */

Explaining the Regular Expression

First we will need to match a start tag /*

Note that * is a meta character in regular expression. If we really want to match a star, we need to escape it.

That completed the beginning and the ending of our regular expression

Regular Expression	Explanation
/\*(.|[\r\n])*?\*/	Match start of comment /*
/\*(.|[\r\n])*?\*/	Match end of comment */

Matching Anything

Between the begin tag and the end tag, anything is a valid comment.

Normally, to match anything in regular expression, we may use .*
The dot means "any characters", and the star means "any repetitions of the previous group".

However, in Java, the matching of regular expression is using single line mode by default. Hence the dot actually means "any character except linefeed".

Therefore we need to enhance the definition of anything :
(.|[\r\n])*
That actually means any repetitions (including zero repetition) of any characters (including linefeed).

Non-Greedy Match

In Java, the star operation is greedy by default. That is, it will try to match as much as possible.

In our previous example, if we are using greedy match, then the whole file would become a comment because there is a begin tag at the beginning of the file, and there is an end tag at the end of the file.

The problem can be solved by using non-greedy match. Just add a question mark after the star will make the star non-greedy. That completed the explanation of the regular expression.

Regular Expression	Explanation
/\*(.|[\r\n])*?\*/	Match start of comment /*
/\*(.|[\r\n])*?\*/	Match end of comment */
/\*(.|[\r\n])*?\*/	Any non-greedy repetitions of any characters

Finalizing the Regular Expression

1. We need to add single line comment support. //.*
2. We need to escape the stroke character inside a Java String, hence we have :

String comment="(/\\*(.|[\\r\\n])*?\\*/|//.*)";

Source Code

Note: You will need Reader.java and Writer.java

Converting a text file to HTML

We are going to write a simple program to convert a plain text file to HTML. To make life simpler, the program will assume the input file is a.txt and the output file is a.html. We will use Reader.java and Writer.java written previously. You may have a look at them first:

• Reading whole file into a String
• Write a String to file

Defining the Problem

Before writing the program, we would try to do a manual conversion first. This help us understand what should be implemented. The program will read the content of a.txt in memory, do the conversion, and then write the content to a.html. Sample input and output follows.

Sample input file: a.txt

class A
{
  public static void main(String[] args)
  {
    int b=10;    
    for (int i=0;i<b;i++)
      System.out.println("Hello World !\nHello again !");
  }
}

Sample output file: a.html

<html><body><pre style='font-family:monospace;font-size:12px'><code>
class A
{
  public static void main(String[] args)
  {
    int b=10;    
    for (int i=0;i&lt;b;i++)
      System.out.println(&quot;Hello World !\nHello again !&quot;);
  }
}
</code></pre></body></html>

Implementation Steps

1. Read the whole file a.txt into a String 2. Escape all special characters. That is :

  Replace & with &
  Replace < with &lt;
  Replace > with &gt;
  Replace " with &quot;

3. Surround the content with appropriate HTML tags. 4. Write the content to a.html Note that overwrite mode is turned off by default. If you wish to overwrite existing file, modify Writer.java

Source

The above steps lead to the following simple implementation.

Write a String to file

This is the reverse operation of Reading whole file into a String.

There are more than one ways of doing this. We may use FileWriter or FileOutputStream to achieve the purpose. The following sample wraps a FileWriter with a PrintWriter to print a String to the file.

Since this is only a demonstration and I don't want to do anything destructive, the program will NOT overwrite any existing file. You may turn on the overwrite mode following the comment below.

Reading whole file into a String

Reading a text file into a String object is a useful operation in many areas. For example, it can be used in text editor, syntax highlighter, "find and replace" tools and grep application.

Memory Constraints

For typical cases, most of the text files are less than 1MB in size. With today memory capacity, it is not a concern. However, we may still wish to limit the file size to avoid the user from using a 4GB movie file as input. Therefore, the first step in reading the whole file is to check the file size.

Getting the file size

The file size of a file can be read by the following code: where fileName is just a String containing the name of file, e.g. "a.txt".

Limiting the file size

I have arbitrarily chosen a file size limit of a million bytes, change it to what you need.

Buffer Allocation

Now we have the file size. It is convenient to allocate a buffer to hold the whole file.

Using DataInputStream for reading

The next step is to create a DataInputStream for reading the file.

Read the whole file into String

Now everything is ready and we may read the whole file into the byte array, and the create a String object from it.

Putting it all together

Related Posts

• Write a String to file
• How to add line number to text file ?
• How to display a text file on console