本文同步分享於個人Blog → InformisTry - HankLee

前言

講了27天的演算法，好像一直都沒有在一個實際的場合下使用，實在是有點無聊，現在已經進入倒數最後三天了，我們來講一個比較不一樣的，而這三天都會圍繞在一個腦力激盪遊戲上面，這個遊戲就是數獨(Sudoku)。

再接下來的三天裡，我會來講如何用程式來計算出數獨的解答，我們會講三種解法，各有各的特色，那我們就開始吧。

數獨(Sudoku)是什麼遊戲？

我相信應該是很多人都有玩過這個遊戲，有一陣子每天水果日報上面都會有一到兩題數獨讓讀者玩，仿間也有很多整本數獨題目的書可以去購買，現在更方便了，無論是Apple的App Store或是Google的Google Play裡面，都有很多人寫數獨遊戲來給大家玩，那數獨這個遊戲到底怎麼玩？

數獨是一個正方形矩陣，基本上一個矩陣的大小，長寬的值會是某一個數字的二次方；另外，矩陣中每一個位置都可以填入數子，填入的數字範圍與長或寬的值相同，若現在是一個4 x 4的矩陣，則填入的數值就是1, 2, 3, 4，下圖為4x4和9x9的矩陣範例。

而一般數獨這個遊戲的規則是：

1. 同一個區塊中，所填入的數字不可重複。（紅色框）
2. 同一行中填入的數字不可重複。（綠色框）
3. 同一列中填入的數字不可重複。（黃色框）

數獨基本上都會有難度上的分別，依據難度的不同，在欄位中可能會預先提供的數值位置及數量就會不同，但不管如何，在利用程式去算答案之前，我們必須要牢記這三條規則。

解法一：Backtracking

今天主要要講的解法是利用Backtracking的方式，Backtracking其實就是『回朔』的一個過程，用Backtracking的方式也很像是一種Brute Force，而其流程如下（用4x4的數獨為例）：

1. 先找出第一個空的欄位。
2. 在這個欄位中填入1。
3. 檢查上面提到的三個條件，如果三個條件都符合，則找下一個空的欄位，反覆2, 3步；但是如果有一個條件不符合，則填入下一個數字，再檢查條件是否符合。
4. 如果全部的數字(1~4)都填入都沒有辦法符合條件，則回到『上一個』欄位，改變『上一個』欄位的值，再檢查條件有沒有符合。
5. 反覆上述步驟直到整個數獨陣列都填入值。

看看下面GIF：

這又是一個很長的GIF了，所以如果有認真看的話，可以看到當1~4的值都試過，卻都無法符合三個條件的話，就會去更改『上一個』欄位的值。

Code如下（GitHub-Sudoku-Backtracking)：

/**
 * @author Hank Lee
 * Shared in InformisTry -- https://jumperc2p.github.io/InformisTry/
 *
 */
public class SudokuGrid {
	
	public Integer size = 0;
	public Integer[] symbols = null;
	public Integer[][] grid = null;
	public Integer sqrt = 0;
	
	public boolean validate() {
    	
    	for (int currentY = 0; currentY < size; currentY++) {
    		for (int currentX = 0; currentX < size; currentX++) {
    			int currentNumber = grid[currentY][currentX];
    			if (!this.basicValidate(this, currentNumber, currentX, currentY))
    				return false;
    		}
    	}
		
		return true;
    }

	
	/**
	 * To do the basic validation of sudoku grid.
	 * In the method, it only checks basic 3 constraints, 
	 * which are box-value constraints, row-value constraints and column-value constraints
	 * 
	 * @param sudokuGrid the sudoku grid
	 * @param currentNumber the current number to check
	 * @param currentX the current column of the cell
	 * @param currentY the current row of the cell
	 * @return true: valid, false: invalid
	 */
	public boolean basicValidate(SudokuGrid sudokuGrid, int currentNumber, int currentX, int currentY) {
		

		// compare each number in one row
		for (int x = 0; x < sudokuGrid.size; x++) {
			if (currentX != x && sudokuGrid.grid[currentY][x] != null && currentNumber == sudokuGrid.grid[currentY][x])
				return false;
		}
		
		// compare each number in one column
		for (int y = 0; y < sudokuGrid.size; y++) {
			if (currentY != y && sudokuGrid.grid[y][currentX] != null && currentNumber == sudokuGrid.grid[y][currentX])
				return false;
		}
		
		// compare each number in one sub-grid
		int modX = currentX / sudokuGrid.sqrt;
		int modY = currentY / sudokuGrid.sqrt;
		
		for (int y = (modY*sudokuGrid.sqrt); y<((modY+1)*sudokuGrid.sqrt); y++) {
			for (int x = (modX*sudokuGrid.sqrt); x<((modX+1)*sudokuGrid.sqrt); x++) {
				if (currentX != x && currentY != y && sudokuGrid.grid[y][x] != null && sudokuGrid.grid[y][x] == currentNumber)
					return false;
			}
		}
		
		return true;
		
	}
}

import java.util.HashMap;
import java.util.Map;

/**
 * @author Hank Lee
 * Shared in InformisTry -- https://jumperc2p.github.io/InformisTry/
 *
 */
public class BackTrackingSolver {
	
	/**
	 * Find the blank cell and return with a map object
	 * @param sudokuGrid the sudoku grid
	 * @return two sets of data: 
	 * 			x : column
	 * 			y : row
	 */
	public Map<String, Integer> findBlankPosition(SudokuGrid sudokuGrid){
		
		Map<String, Integer> map = new HashMap<>();
		for (int y = 0; y < sudokuGrid.size; y++) {
			for (int x = 0; x < sudokuGrid.size; x++) {
				if (sudokuGrid.grid[y][x] == null) {
					map.put("y", y);
					map.put("x", x);
					return map;
				}
			}
		}
		return null;
	}
	
	public boolean solve(SudokuGrid sudokuGrid) {
    	
    	// find a blank cell to work on.
    	Map<String, Integer> currentPosition = this.findBlankPosition(sudokuGrid);
    	
    	if (currentPosition == null) {
    		return true;
    	}
    	
    	// get the current row and column values
    	int currentX = currentPosition.get("x");
    	int currentY = currentPosition.get("y");
    	
    	// try all the symbols one by one
    	for (int currentNumber : sudokuGrid.symbols) {
    		
    		// if the current number is valid, put it into the cell
    		if(sudokuGrid.basicValidate(sudokuGrid, currentNumber, currentX, currentY)) {
    			sudokuGrid.grid[currentY][currentX] = currentNumber;
    			
    			// recursively to find solutions
    			if (this.solve(sudokuGrid)) {
    				return true;
    			}
    			
    			// Once there is no symbol which is valid, recover the value of the value to null
    			sudokuGrid.grid[currentY][currentX] = null;
    		}
    	}
    	
        return false;
    }
}

小結

Sudoku的Backtracking其實滿消耗時間的，因為他會把數值都試過一遍，所以如果在進行的過程中，都無法符合三個條件的話，就會去一直更改『上一個』欄位的值，最壞的情況就是重新回到『最一開始』的欄位去調整，這樣等於又需要重新開始了。

預告

明天我們來介紹另外一種方式來解數獨，而且這個方式的速度會比Backtracking還要快喔。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin
2. Python Sudoku Solver Tutorial with Backtracking p.1