Một số ứng dụng của CTDL Stack
Giới thiệu
Cũng như queue, stack cũng là một array với một số tương tác đặc thù. Để dễ hình dung, bạn có thể tưởng tượng nó giống như … một ngón tay :) bạn có thể đeo vào và tháo ra các chiếc nhẫn, nhưng chiếc nhẫn cuối cùng đeo vào sẽ là chiếc đầu tiên phải gỡ ra (LIFO - Last In First Out). Hai phương thức chính của stack là push và pop mô tả cho các hành động này
Push(x) - Đưa phần tử x vào stack
Pop() - Lấy một phần tử ra khỏi stack
Ví dụ: stack S = {a,b,c,d} thì S.push(z) => S={x,a,b,c,d} và z=S.pop() thì z = x và S = {a,b,c,d}
Bài toán 8 quân hậu trên bàn cờ vua
Làm cách nào để sắp xếp 8 quân hậu lên một bàn cờ vua sao cho không quân nào ăn được quân nào?
Cơ sở để giải bài toán này là phương pháp thử - sai hay còn gọi là thuật toán quay lui (back tracking). Đơn giản là tại mỗi dòng, ta đặt tạm một quân hậu lên vị trí nào đó, cứ làm như vậy cho đến khi đặt hết tất cả quân hậu hoặc tại một dòng nào đó, không còn chỗ nào hợp lệ để đặt thì ta quay lại dòng trên, tìm một vị trí khác chưa thử để đặt thử quân hậu vào chỗ mới, cứ tiếp diễn như vậy…
Để dễ hiểu, bạn có thể xem hình dưới đây:
Với S là stack chứa vị trí của các quân hậu được đặt lần lượt trên từng dòng.
Hình 1: Khời đầu với bàn cờ trống, stack S rỗng S={}
Hình 2: Ta thử đặt quân hậu cho hàng đầu tiên ở cột 1, tiếp theo đến hàng thứ 2, ta không thể đặt quân hậu ở cột 1 và cột 2 nữa nên phải đặt ở cột 3, hàng thứ 3 cũng vậy, ta đặt ở cột 5, … cuối cùng ta ngừng ở hàng thứ 8, vì không còn một chỗ hợp lệ nào đặt quân hậu cho hàng 8 cả. Lúc này ta có trạng thái các quân hậu là S={1,3,5,7,2,4,6}
Hình 3: Vì không có chỗ đặt quân hậu cho hàng 8, ta thử quay lên hàng 7, đặt quân hậu vào cột khác, nhưng không còn cột nào hợp lệ nên ta gỡ bỏ quân hậu ở hàng 7, tiếp tục quay lên hàng 6. Hàng 6 cũng không có chỗ hợp lệ, lại tiếp tục gỡ quân hậu hàng 6 và quay lên hàng 5. Lúc đó S = {1,3,5,7,2}
Hình 4: Tại hàng 5 ta tìm kiếm một chỗ hợp lệ để đổi chỗ quân hậu ở hàng này, đó là cột 4. Lúc này vị trí các quân hậu là S={1,3,5,7,4}
… thuật toán cứ tiếp diễn như vậy cho đến khi tìm ra được giải pháp đặt toàn bộ 8 quân hậu.
Thuật toán
Stack s = {}, last = -1 là biến đánh dấu vị trí cột của quân hậu cuối cùng
Lặp
Tìm kiếm một chỗ đặt quân hậu vào hàng thứ s.length, cột thứ i từ last+1 đến 8:
Nếu kiếm được, đặt quân hậu lên bàn cờ, đưa i vào stack s.push(i), reset giá trị last = -1
Nếu không kiếm được chỗ, gỡ quân hậu ra khỏi bàn cờ, set last = s.pop()
return s
Code mẫu (không dùng đệ quy)
// 8 queens board
const board = [
[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]
];
function tryPlace(atRow, atColumn) {
// check if there is a queen in the same row
for(let i = 0; i < 8; i++){
if(board[atRow][i] === 1){
return false;
}
}
// check column
// ...
// check diagonals
// ...
// I would let you to do the rest as an excerise :)
return true;
}
function solve(board){
// stack to store the queens
const s = [];
// start from the first row
let last = -1;
do {
// try to place a queen in the next column
let canPlace = false;
// start from the last column
for (let i = last + 1; i < 8; i++){
if(tryPlace(s.length, i)){
// place the queen
board[s.length][i] = 1;
// push the column to the stack
s.push(i);
// reset the last column
last = -1;
canPlace = true;
break;
}
}
// if we can't place a queen in the current row
if(!canPlace){
if(s.length === 0) break;
// remove the last queen
last = s.pop();
// remove the queen from the board
board[s.length][last] = 0;
}
} while (s.length < 8);
console.log(s);
console.log(board);
}
Sudoku Solver
Dựa vào ý tưởng của bài 8 quân hậu ở trên, bạn có thể phát triển để giải bàn cờ Sudoku tương tự:
Tìm một ô trống và tìm một giá trị hợp lệ x để thử đặt vào ô trống đó
Nếu tìm thấy, đặt x vào board và lưu vào stack phần tử [row, col, x]
Nếu không tìm thấy, gỡ trong stack ra và kiếm giá trị khác
Code mẫu (không dùng đệ quy)
function isValid(board, row, col, num) {
return rowCheck(board, row, num) && colCheck(board, col, num) && boxCheck(board, row - row % 3, col - col % 3, num);
}
function findEmptyCell(board) {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] === 0) {
return [i, j];
}
}
}
return null;
}
function solve(board) {
const s = [];
let last = 0;
do {
const emptyCell = findEmptyCell(board);
if (emptyCell === null) {
return true;
}
const [row, col] = emptyCell;
let canFind = false;
for (let val = last + 1; val <= 9; val++) {
if (isValid(board, row, col, val)) {
board[row][col] = val;
s.push([row, col, val]);
canFind = true;
last = 0;
break;
}
}
if (!canFind) {
const lastElement = s.pop();
board[lastElement[0]][lastElement[1]] = 0;
last = lastElement[2];
}
} while (s.length < 81);
return false;
}
const board = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
];
solve(board);
console.log(board);