[PHP]Giải quyết bài SUDOKU sử dụng PHP

[Lucky_Star]

Dưới đây là các hàm xử lý giải quyết bài toán SUDOKU
Sau khi thêm giao diện để người dùng nhập dữ liệu đầu vào (input) ta có một trang ví dụ: http://www.g8soft.com/~anhtt/antiquizland.php

(Thank to Anhtt nhé ^_^)
<?php
// Đặt thời gian chạy tối đa là 300s
set_time_limit(300);

define(MAX,9); // điền các số từ 1..9
define(NUM,3); // kích thước ô vuông nhỏ 9=3×3

$found = false; // đã tìm thấy kết quả hay chưa?

$R = array(); // mảng lưu trữ kết quả điền được

/**
section: MAIN PROGRAM
**/

/**
section: FUNCTIONS
**/

// Functions

function sudoku_run() {


global $R, $found;
// Input - nhập dữ liệu
/* == có thể nhập từ FORM ==
for ($i = 0; $i < MAX; ++$i) {
$R[$i] = array();
for ($j = 0; $j < MAX; ++$j) {
$R[$i][$j] = fnumber($form_values[’SUDOKU_CELL_’.$i.’_’.$j]);
}
}
*/
// Process - xử lý duyệt
_sudoku_scan(0);

// Output - in kết quả
return _sudoku_output();
}

// Functions
function _sudoku_scan($n) {
global $R, $found;
$i = floor($n / MAX);
$j = $n % MAX;

if ($n >= MAX*MAX) {
$found = true;
//output();
return;
}

if ($R[$i][$j] > 0) {
_sudoku_scan($n+1);
return;
}

for ($k = 1; $k <= MAX; ++$k) {
if (_sudoku_canput($k, $i, $j)) {
$R[$i][$j] = $k;
_sudoku_scan($n+1);
if ($found && !$print_all) return;
$R[$i][$j] = 0;
}
}
}

function _sudoku_output() {
global $R, $found;
// — In ra kết quả
}

function _sudoku_canput($k, $i, $j) {
global $R, $found;
$ii = floor($i / 3) * 3;
$jj = floor($j / 3) * 3;
$good = true;
for ($p = 0; $p < MAX; ++$p) { // hang ngang, doc
if ($R[$i][$p] == $k) { // neu da co x tai o nao do
$good = false;
break;
}
if ($R[$p][$j] == $k) {
$good = false;
break;
}
if ($R[$ii+($p/3)][$jj+($p%3)] == $k) {
$good = false;
break;
}
}
return $good;
}

?>