Giải ô số Sudoku

Trò này quá quen thuộc, nhưng tớ chưa tự tay chơi bao giờ nên ko biết khó hay dễ, chỉ biết khi code cho máy mò cực nhanh: thuật toán đơn giản là sử dụng đệ quy quay lui, vét cạn mọi trường hợp.

Viết bằng Pascal, Java đã lâu, nay viết lại bằng JavaScript, nhân thể test cái Aptana Studio (IDE ko thể thiếu cho Web Developer).

Chú ý: trong trường hợp ô số bạn điền vào có nhiều hơn 1 kết quả thì chương trình sẽ đưa ra 1 kết quả bất kì.

Yêu cầu: trình duyệt FireFox hoặc Internet Explorer (tớ ko cài Safari với Opera nên chưa test).

Ai quan tâm đến khía cạnh lập trình có thể download mã nguồn và xem cụ thể thuật toán.

Lớp quan trọng nhất: lớp Algorithms:

/**
 * @author Kata
 */

function Algorithms() {
    this.zone = [
        [0, 0, 0, 1, 1, 1, 2, 2, 2],
        [0, 0, 0, 1, 1, 1, 2, 2, 2],
        [0, 0, 0, 1, 1, 1, 2, 2, 2],
        [3, 3, 3, 4, 4, 4, 5, 5, 5],
        [3, 3, 3, 4, 4, 4, 5, 5, 5],
        [3, 3, 3, 4, 4, 4, 5, 5, 5],
        [6, 6, 6, 7, 7, 7, 8, 8, 8],
        [6, 6, 6, 7, 7, 7, 8, 8, 8],
        [6, 6, 6, 7, 7, 7, 8, 8, 8]
    ];
    this.cxh = [[], [], [], [], [], [], [], [], []];
    this.cxc = [[], [], [], [], [], [], [], [], []];
    this.cxv = [[], [], [], [], [], [], [], [], []];
    this.a = [[], [], [], [], [], [], [], [], []];
    this.result = [[], [], [], [], [], [], [], [], []];
}

Algorithms.prototype.filter = function(matrix, col, row){
    var b = [];
    for (var i = 0; i < 9; i++)
        b[i] = true;

    for (var i = 0; i < 9; i++)
        if (matrix[i][row] >= 0)
            b[matrix[i][row]] = false;
    for (var j = 0; j < 9; j++)
        if (matrix[col][j] >= 0)
            b[matrix[col][j]] = false;

    var myZone = this.zone[col][row];
    for (var i = 0; i < 9; i++)
        for (var j = 0; j < 9; j++)
            if (this.zone[i][j] == myZone && matrix[i][j] >= 0)
                b[matrix[i][j]] = false;

    var list = [];
    for (var i = 0; i < 9; i++)
        if (b[i])
            list.push(i);
    return list;
}

Algorithms.prototype.solve = function(matrix) {
    this.copyArr(this.a, matrix);
    var i, j, x;
    this.stopbtr = false;
    for (i = 0; i < 9; i++)
        for (j = 0; j < 9; j++) {
            this.cxc[i][j] = true;
            this.cxh[i][j] = true;
            this.cxv[i][j] = true;
        }
    for (i = 0; i < 9; i++)
        for (j = 0; j < 9; j++)
            if (this.a[i][j] >= 0) {
                x = this.a[i][j];
                this.cxc[i][x] = false;
                this.cxh[j][x] = false;
                this.cxv[this.zone[i][j]][x] = false;
            }
    this.backtracking(0, 0);
}

Algorithms.prototype.backtracking = function(i, j) {
    if (this.stopbtr)
        return;
    if (this.a[i][j] == -1) {
        for (var k = 0; k < 9; k++)
            if (this.cxc[i][k] & this.cxh[j][k] &
                    this.cxv[this.zone[i][j]][k]) {
                this.a[i][j] = k;
                this.cxc[i][k] = false;
                this.cxh[j][k] = false;
                this.cxv[this.zone[i][j]][k] = false;
                if (i == 8 & j == 8) {
                    this.stopbtr = true;
                    this.copyArr(this.result, this.a);
                }
                else
                    if (j == 8)
                        this.backtracking(i + 1, 0);
                    else
                        this.backtracking(i, j + 1);
                this.a[i][j] = -1;
                this.cxc[i][k] = true;
                this.cxh[j][k] = true;
                this.cxv[this.zone[i][j]][k] = true;
            }
    }
    else {
        if (i == 8 & j == 8) {
            this.stopbtr = true;
            this.copyArr(this.result, this.a);
        }
        else
            if (j == 8)
                this.backtracking(i + 1, 0);
            else
                this.backtracking(i, j + 1);
    }
}

Algorithms.prototype.copyArr = function(a, b){
    for (var i = 0; i < 9; i++)
        for (var j = 0; j < 9; j++)
            a[i][j] = b[i][j];
}

Thuật toán rất đơn giản, ta tổ chức dữ liệu như sau:

int[][] a = new int[10][10];
Đây là bảng Sudoku, nếu ô trống thì a[i][j] = 0 còn không a[i][j] = 1..9 (1 <= i, j <= 9)

boolean[][] cxh = new boolean[10][10];
Dùng để kiểm tra xem ở hàng i đã tồn tại số j hay chưa, nếu có cxh[i][j] = true còn không thì cxh[i][j] = false. (1 <= i, j <= 9)

boolean[][] cxc = new boolean[10][10];
Dùng để kiểm tra xem ở cột i đã tồn tại số j hay chưa, nếu có cxc[i][j] = true còn không thì cxc[i][j] = false. (1 <= i, j <= 9)

boolean[][] cxv = new boolean[10][10];
Dùng để kiểm tra xem ở vùng i đã tồn tại số j hay chưa, nếu có cxv[i][j] = true còn không thì cxv[i][j] = false. (1 <= i, j <= 9)

int zone[][] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
{0, 7, 7, 7, 8, 8, 8, 9, 9, 9}
};
Dùng để xét xem ô [i][j] sẽ thuộc vùng thứ mấy, mảng này dùng để phục vụ cho mảng cxv.

Ví dụ khi ta quyết định thử điền số 3 vào ô [7][4] thì sau đó:

  • Hàng 7 tồn tại số 3 nên cxh[7][3] = false;
  • Cột 4 tồn tại số 3 nên cxc[4][3] = false;
  • Vùng 8 tồn tại số 3 nên cxv[8][3] = false; (Thực chất là vùng zone[7][4] tồn tại số 3 nên
    cxv[zone[7][4]][3] = false, ở đây zone[7][4] == 8);

Dĩ nhiên trước khi quyết định thử điến số 3 vào ô [7][4] ta phải chắc chắn rằng các biến
cxh[7][3], cxc[4][3], cxv[zone[7][4]][3] đều true.

boolean stopbtr;
dùng để kết thúc đệ quy khi tìm ra kết quả.

Cuối cùng là kĩ thuật đệ quy quay lui để duyệt hết tất cả các trường hợp có thể có.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s