JSudoku

Yet another Sudoku program

Main interface

Down to the basics, here’s what I did:

  1. Generate the whole board with backtracking, randomizing the number I chose at each step and remember the choice, this assures that the board is random, while still keep the algorithm run in an acceptable time (it doesn’t have to regenerate a long track of numbers if it get into some sticky situation). Sudoku board have to keep up with a number of rules that make up a complex vector class, lost in there and you’re done. The other method to generate the board was to swap the rows/column/numbers, it’s safe and much faster but it took more time to implement, and it generates only a subclass of the possible Sudoku class, but it’s a good choice if you don’t want recursive calls in your program.
  2. Difficulty: I implemented a simple, but it’s not good for real application, I think. A good difficulty implementation should have taken humans’ deduction rules into consideration (you should know what are these these if you’ve played Sudoku before), and the algorithm should also make sure that with the given cells, only one solution is possible, this is a continuous generate-remove-check for solutions-remove loop and it’s complex to implement. So, I have only removed a number of cells based on difficulty, the more difficulty chosen, the less given cell there are. This implementation suffers from the above points.
  3. Build a usable Sudoku class’ interface: I deducted from coding that you need to store both the solution and the playing board in the class, provide board and solution get method, the set move method for the board should only accept valid moves, this way you only need to count the number of moves played to know if the player have won or not. This has the drawback that you can’t store invalid values in the board (to visually notify the player of their wrong moves), but it keeps your code clean of unnecessary checks.
  4. Build the interface: If you choose to manually generate the JFrame, JButton and uses a loop to create JTextField, it saves time to point-and-click creating the cells, but you will have to manually calculate the button and frame’s position to get a nice interface; the other way around, you’ll have to create JTextFields 81 times. I choose a hybrid approach: use the designer to design the form, add a JPanel to it, and then add the JTextField in the user interface’s constructor.
  5. Just for kicks: I add a key press handler into the text fields, the handler catches input, and if it’s not a valid number, not correct according to Sudoku rules or some other reason, the cell will be highlighted so the user can see it easily, the hint function is implemented in this way too: it compares what the user have to the solution and highlight the differences.

Creating text fields

    /** Creates new form SudokuInterface */
    public SudokuInterface() {
        initComponents();

        // Automatically arranges the cells into a grid-like layout
        jPanel1.setLayout(new GridLayout(Sudoku.ROWS, Sudoku.COLUMNS));
        fields = new JTextField[Sudoku.ROWS * Sudoku.COLUMNS];
        for (int i = 0; i < Sudoku.ROWS * Sudoku.COLUMNS; i++) {
            fields[i] = new JTextField(1);
            fields[i].setSize(66, 66);
            fields[i].setFont(cellFont);
            fields[i].setName(Integer.toString(i));
            fields[i].addKeyListener(cellInputHander);
            fields[i].setHorizontalAlignment(JTextField.CENTER);
            fields[i].setEnabled(false);
            jPanel1.add(fields[i]);
        }

        // First screen
        String intro = "JSudoku";
        for (int i = 1; i < intro.length() + 1; i++) {
            fields[4 * Sudoku.ROWS + i].setText(intro.charAt(i - 1) + "");
        }

    }

Handling key input

    private final KeyListener cellInputHander = new KeyListener() {

        /**
         * Controls, the user's input, let them input invalid data and display it
         * to avoid confusing the user (higher usability), but this won't be
         * reflected in the actual game, we have to keep track of which cells are
         * invalid, resulting in this complex implementation
         */
        public void keyTyped(KeyEvent e) {
            e.consume();
            int move = 0;
            String moveString = e.getKeyChar() + "";
            try {
                move = Integer.parseInt(moveString);
            } catch (Exception exception) {
                return;
            }
            // If the move is invalid, do nothing, the key won't appear
            int cellIndex = Integer.parseInt(e.getComponent().getName());
            if (!game.set(cellIndex, move)) {
                ((JTextField)e.getSource()).setForeground(cellIncorrectForeground);
                jLabel3.setText("You have just performed an invalid move");
                isInvalid[cellIndex] = true;
            } else {
                ((JTextField)e.getSource()).setForeground(cellEnabledForeground);
                jLabel3.setText("");
                isInvalid[cellIndex] = false;
            }
            ((JTextField)e.getSource()).setText(moveString);
            if (game.won()) {
                JOptionPane.showMessageDialog(rootPane, "You have solved the puzzle!", "Congratulation", JOptionPane.INFORMATION_MESSAGE);
                newGame(lastDifficulty);
            }
        }

        public void keyPressed(KeyEvent e) {

        }

        public void keyReleased(KeyEvent e) {

        }
    };

Move checking
Like I said, there’s plenty of room for improvement, so here’s the source code if you want to do just that 😉

Object oriented experiment

class Shape {
    // This method will be overridden by its children, even if it's not abstract
    // and its children have not specified @Override
    void draw() {
        System.out.println("Shape drawn");
    };

    @Override
    protected Object clone() {
        return null;
    }
}

class Rectangle extends Shape {
    void draw() {
        System.out.println("Draw rectangle!");
        super.draw();
    }

    // We can change the return type and access of a overridden method from its
    // parent class! Note that access modifier must be the same or more relaxing
    // like private -> protected -> public, but not the other direction
    @Override
    public Rectangle clone() {
        return null;
    }
}
class Triangle extends Shape {
    void draw() {
        System.out.println("Draw Triangle!");
    }
}
class Circle extends Shape {
    void draw() {
        System.out.println("Draw Circle!");
    }
}
public class AbstractClass {
    public static void main(String[] args) {
        Shape s = new Circle();
        s.draw();
        s = new Triangle();
        s.draw();
        s = new Rectangle();
        s.draw();
        
    }
}

First Android application

Or so… if numerous "hello world" applications doesn’t count. Well, time flies, it has been three weeks since the android class I was attending ended. Many thanks to MultiUni for organizing the event! I joined the class simply because of the boldness of whoever bring the idea of a learning community into motion, especially in Vietnam; and I know many share the same feeling with me. It’s a great opportunity to meet more people and get updates on what’s going on. One of my teachers wanted to do this years ago in the form of a university’s computing club but it seems the idea never saw the light of day – he is now a PhD or more accurately, Doctor of Science. He have had more important things to devote his time for 🙂

1.0 A half-user, half-programmer’s rant

Being short doesn’t stop the class from giving me a good head start on Android. Basically the Android’s application share much in common with J2ME, a cousin sharing the same root with Android in the Java family. However, Android have a more clearly defined framework – all naming are done according to convention, similar functions from different packages doesn’t have drastically different names like Java. The Dalvik debugging monitor server (with which you can interact through the DDMS view installed with Android Development Tools) is better integrated into the IDE and easier to use than its J2ME’s counterpart. All rounded up, Android is a fantastic platform to start mobile programming!

But being good doesn’t mean things are automatically going to be great for you. A while back I blogged about how frustrating Symbian programming is and predicted its demise. Well, that came true when the iPhone started to take up market share. Ironically that doesn’t mean I am good at predicting market trends but the exact opposite! Apparently hypes and marketing niches have more to do with the success of a product than technical feasibility.

smartphone_market_share_3Q09_trend

Smartphone market share trends, via Gartner and Arstechnica

The iPhone replaced Symbian’s complex model with an arcane platform! Did you know that you need a Mac to be able to program the iPhone? And while Apple started to dwarf Nokia on the mobile market, the first Android phones started to came out. Even a developer community such as the class I were in have only 3 Android phones and though so, they weren’t used for daily tasks like calling or texting :/

Technology takes time to be adapted, but Android just doesn’t have the "coolness" of the iPhone. You can’t impress your girlfriend telling her "I have the latest Google’s touch screen phone with fancy location based features" – she’ll simply ask "isn’t Google a search engine"?

That being said, the future is not bleak for Android. Google, after all is also a big company; and most importantly, they are driven by innovation in technology, just like Apple is driven by innovation in design and user interface. This is going to be an interesting battle and who knows? Maybe you are picking the winning side right now 😉

2.0 The application

Okay, as the title of this post have stated, it’s not an application that will make you coffee to impress your girl (or guy) but rather a demonstrative application on how easy it is to perform system tasks with Android.

The first objective is to make an application that displays pictures from a list. For simplicity’s sake, this will be an array of URLs; of course this can easily be replaced with an RSS feed. Secondly, when the user selects one of those pictures, the application will save it to the device and set it as the wallpaper.

2.1 Display

According to the instruction given, I should have made an application that displays one picture at a time and three buttons to flip between pages and set the wallpaper, like this:

ui1

But being such a busybody I took a scan on the Android samples that comes with the SDK. Fortunately there’s a gallery application using the ImageSwitcher control that looks substantially better:

android_api_imageswitcher

Besides the look, the ImageSwitcher interface also have a view initializing method, GetView so you can implement your own image generating procedure. This is especially useful for an advanced function: caching images.

public View getView(final int position, View convertView, ViewGroup parent)

ImageSwitcher is not a collection of images but rather a collection of ImageView controls, this allows for greater flexibility: you can customize how each image is rendered. For examples, odd images have a white border and even ones have a black border.

As you may have known, mobile devices have significantly tighter memory limit than full-pledged computing devices. Android phones is not an exception. You can only load like 10 640×480 pictures before hitting an “out of memory” exception. In this application I will cache eight images at a time. The caching algorithm is based on the priority queue principle: any time an image is used (get displayed either as the current image or in the preview line), it is moved to the top of the queue, images at the bottom of the queue are disposed to make room for new ones as necessary.

// 1 for view and 8 for scrolling
private final int cacheThreshold = 8;	
private LinkedList imageCache = new LinkedList();

The cache’s data structure 

It appears that all objects in Android have a Tag attribute so you can attach anything you want to them. I used that to attach the position of the image contained in the ImageView control in the list. By looking at this value you can easily determine when the ImageView is being displayed and move it up the queue.

		public View getView(final int position, View convertView,
				ViewGroup parent) {

			// Search if the cache already have the image,
			// this is better implemented as some kind of
			// comparison operator, but we don't have time
			// to look into that right now

			// Convert the queue to an array for easier iteration
			for (int i = 0; i < imageCache.size(); i++) {
				ImageView temp = imageCache.get(i);
				String imageTag = (String) temp.getTag();
				// Why string and not just position?
				// It will be easier to implement image loading
				// from the file system (images will be referred
				// to by path)
				if (imageTag.compareTo(imageLinks[position]) == 0) {
					// Increase priority for the returned item
					imageCache.remove(i);
					imageCache.addFirst(temp);
					return temp;
				}
			}

			// Load a new image if not cached
			while (imageCache.size() >= cacheThreshold)
			{
				imageCache.getLast().destroyDrawingCache();
				imageCache.removeLast();
			}
			final ImageView newView = new ImageView(mContext);

			newView.setAdjustViewBounds(true);
			newView.setLayoutParams(new Gallery.LayoutParams(
					LayoutParams.WRAP_CONTENT, LayoutParams.WRAP_CONTENT));

			// Load the first image with blocking routine to make sure it will display
			if (firstImage) {
				firstImage = false;
				BitmapInfo mResults = BitmapDownloader
					.downloadBitmap(imageLinks[position]);
				newView.setImageBitmap(mResults.getBitmap());
			}
			else
			{
				// Uses the asynchronous routine for other images
				Thread t = new Thread() {
					public void run() {
	
						BitmapInfo mResults = BitmapDownloader
								.downloadBitmap(imageLinks[position]);
						mResults.setToAssign(newView);
						Message downloadedMessage = new Message();
						downloadedMessage.setTarget(mHandler);
						downloadedMessage.what = MESSAGE_TYPE_WALLPAPER_DOWNLOAD_COMPLETE;
						downloadedMessage.obj = mResults;
						mHandler.sendMessage(downloadedMessage);
					}
				};
				t.start();
			}

			newView.setTag(imageLinks[position]);
			// Add the changed entry back to the cache
			imageCache.addFirst(newView);

			return newView;

		}

		private Context mContext;
		private Handler mHandler = new Handler(new Callback() {

			@Override
			public boolean handleMessage(Message msg) {
				if (msg.what == MESSAGE_TYPE_WALLPAPER_DOWNLOAD_COMPLETE) {
					final BitmapInfo downloaded = (BitmapInfo) msg.obj;
					// Fail? Try again, memory will be freed in a moment...
					if (downloaded.getBitmap() == null) {
						Thread t = new Thread() {
							public void run() {

								BitmapInfo mResults = BitmapDownloader
										.downloadBitmap(downloaded.getIdentifier());
								mResults.setToAssign(downloaded.getToAssign());
								Message downloadedMessage = new Message();
								downloadedMessage.setTarget(mHandler);
								downloadedMessage.what = MESSAGE_TYPE_WALLPAPER_DOWNLOAD_COMPLETE;
								downloadedMessage.obj = mResults;
								mHandler.sendMessage(downloadedMessage);
							}
						};
						t.start();
					}
					else
						downloaded.getToAssign().setImageBitmap(
							downloaded.getBitmap());
				}
				return true;
			}
		});

		// Control first image's loading
		private boolean firstImage = true;
		private static final int MESSAGE_TYPE_WALLPAPER_DOWNLOAD_COMPLETE = 3;

The full caching & downloading routine

The Handler in Android is similar to the action or key press listener in java, it handles messages sent to it and have access to all the private variables inside the object it’s placed in. But unlike Java it’s not bound to the object and one object can have multiple handler. However it’s worth noting that Handler’s processing is blocking and it will halt the thread it’s running on so it’s not a good idea to use them for long activities like data transmission. In this case I:

  1. Send the download request to the Handler
  2. The handles process the download request and creates a new thread to download the image.
  3. When the thread is done, is sends a message back to the Handler. Note that I attached the image to that message using Message.obj
  4. Finally the Handler assigns the downloaded image back into the View

Oh, and accessing the internet requires permission from the user (so you won’t send out sensitive data). To get permission you’ll have to ask for it, add those to the manifest file:

<uses-permission android:name="android.permission.INTERNET" />
<uses-permission android:name="android.permission.SET_WALLPAPER" />
<uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE" />

 

2.2 Set wallpaper

In android, to make a button do something, you set its listener, like this

final Button btnSetWallpaper = (Button) findViewById(R.id.btnsetwallpaper);
		btnSetWallpaper.setOnClickListener(new OnClickListener() {

			@Override
			public void onClick(View arg0) {
				// Save dialog
				AlertDialog.Builder builder = new AlertDialog.Builder(arg0
						.getContext());
				builder.setMessage("Do you want to save this image?")
						.setCancelable(false).setPositiveButton("Yes",
								wallpaperDialogHandle).setNegativeButton(
								"Cancel", wallpaperDialogHandle)
						.setNeutralButton("No", wallpaperDialogHandle);
				AlertDialog alert = builder.create();
				alert.show();

			}
		});

And then define what the listener will do:

public DialogInterface.OnClickListener wallpaperDialogHandle = new DialogInterface.OnClickListener() {

		@Override
		public void onClick(DialogInterface dialog, int which) {
			switch (which) {
			case DialogInterface.BUTTON_POSITIVE: // Yes
			case DialogInterface.BUTTON_NEUTRAL: // No
				WindowManager mWinMgr = (WindowManager) getBaseContext()
						.getSystemService(Context.WINDOW_SERVICE);
				int displayWidth = mWinMgr.getDefaultDisplay().getWidth();
				int displayHeight = mWinMgr.getDefaultDisplay().getHeight();

				Bitmap newwallpaper = Bitmap.createBitmap(displayWidth,
						displayHeight, Config.ARGB_8888);
				Canvas myCanvas = new Canvas(newwallpaper);
				Gallery g = (Gallery) findViewById(R.id.gallery);
				// Draw the image to make sure the aspect ratio match
				((ImageView) g.getSelectedView()).getDrawable().draw(myCanvas);
				try {
					setWallpaper(newwallpaper);
				} catch (IOException e) {
					e.printStackTrace();
				}
				// Save file
				if (DialogInterface.BUTTON_POSITIVE == which) {
					Date date = new Date();
					java.text.DateFormat dateFormat = new java.text.SimpleDateFormat(
							"yyyyMMddhhmmss");
					String dateTimeString = dateFormat.format(date);
					try {
						FileOutputStream fos = new FileOutputStream(new File("/sdcard/" + dateTimeString + ".jpg"));

						newwallpaper.compress(CompressFormat.JPEG, 75, fos);

						fos.flush();
						fos.close();
					} catch (Exception e) {
						Log.e("MyLog", e.toString());
					}
				}
			default: // Cancel
				break;
			}
		}
	};

The important part is inside the try-catch block: setWallpaper(). I also added some image resizing (to make the wallpaper fit the screen) and save to device routine. I’m specifying “/sdcard/” in the FileOutputStream constructor to write to external storage. If you don’t specify this Android will write to your application’s private storage on device memory. Device memory is often much smaller than its external counterpart so it’s best to reserve it for sensitive data you want nobody else to read only.

2.3 Splash screen

Finally, to show tribute to the nice guidance given by the instructor, I have to add a splash screen with MultiUni logo eh? So I added the splash screen activity and change the startup activity to it

public class SplashScreenActivity extends Activity {
	public static final int HANDLER_MSG_WAIT = 1;
	
    /** Called when the activity is first created. */
    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.splash_screen);
        
        mHandler.sendEmptyMessageDelayed(HANDLER_MSG_WAIT, 2000);
    }
    
	Handler mHandler = new Handler() {

		@Override
		public void handleMessage(Message msg) {
			super.handleMessage(msg);
			Intent intent = new Intent(getApplicationContext(), 
					WallpaperTool.class);
			startActivity(intent);
			finish();
		}
    	
    };
    
}

See the Intent part? it’s used to call another activity. And that’s it!

You deserve something after all that reading, right? 😛 You can grab the source and compiled binary here (for Android 1.6)