这篇文章主要介绍了PHP实现的数独求解问题,涉及php数组与字符串的遍历、比较、判断、运算等相关操作技巧,需要的朋友可以参考下
本文实例讲述了PHP实现的数独求解问题。分享给大家供大家参考，具体如下：
一、数独问题描述：
对于给出的数字二维数组，要求每行每列的数字不能重复。
二、实现代码：
clear();
} else {
$this->matrix = $arr;
}
}
function clear() {
for($i=0; $i<9; $i++) {
for($j=0; $j<9; $j++) {
$this->matrix[$i][$j] = array();
for ($k = 1; $k <= 9; $k++) {
$this->matrix[$i][$j][$k] = $k;
}
}
}
}
function setCell($row,$col,$value){
$this->matrix[$row][$col] = array($value => $value);
//row
for($i = 0; $i < 9; $i++){
if($i != $col){
if(! $this->removeValue($row,$i,$value)) {
return false;
}
}
}
//col
for($i = 0; $i < 9; $i++){
if($i != $row){
if(! $this->removeValue($i,$value)) {
return false;
}
}
}
//square
$rs=intval($row / 3) * 3;
$cs=intval($col / 3) * 3;
for($i = $rs; $i < $rs + 3; $i++){
for($j = $cs; $j < $cs + 3; $j++){
if($i != $row && $j != $col){
if(! $this->removeValue($i,$j,$value))
return false;
}
}
}
return true;
}
function removeValue($row,$value) {
$count = count($this->matrix[$row][$col]);
if($count == 1){
$ret = !isset($this->matrix[$row][$col][$value]);
return $ret;
}
if (isset($this->matrix[$row][$col][$value])) {
unset($this->matrix[$row][$col][$value]);
if($count - 1 == 1) {
return $this->setCell($row,current($this->matrix[$row][$col]));
}
}
return true;
}
function set($arr) {
for ($i = 0; $i < 9; $i++) {
for ($j = 0; $j < 9; $j++) {
if ($arr[$i][$j] > 0) {
$this->setCell($i,$arr[$i][$j]);
}
}
}
}
function dump() {
for($i = 0; $i < 9; $i++){
for($j = 0; $j < 9; $j++){
$c = count($this->matrix[$i][$j]);
if($c == 1){
echo " ".current($this->matrix[$i][$j])." ";
} else {
echo "(".$c.")";
}
}
echo "\n";
}
echo "\n";
}
function dumpAll() {
for($i = 0; $i < 9; $i++){
for($j = 0; $j < 9; $j++){
echo implode('',$this->matrix[$i][$j]),"\t";
}
echo "\n";
}
echo "\n";
}
function calc($data) {
$this->clear();
$this->set($data);
$this->_calc();
$this->dump();
}
function _calc() {
for($i = 0; $i < 9; $i++){
for($j = 0; $j < 9; $j++){
if(count($this->matrix[$i][$j]) == 1) {
continue;
}
foreach($this->matrix[$i][$j] as $v){
$flag = false;
$t = new Sudoku($this->matrix);
if(!$t->setCell($i,$v)){
continue;
}
if(!$t->_calc()){
continue;
}
$this->matrix = $t->matrix;
return true;
}
return false;
}
}
return true;
}
}
$sd=new Sudoku;
$sd->calc(array(
array(0,5,6,9,0),array(0,4,7,8,2,2),array(7,1,3,6),array(2,4),array(4,));
$sd->calc(array(
array(1,5),3),array(3,1),array(9,7),array(5,));
$sd->calc(array(
array(7,array(1,));
$sd->calc(array(
array(0,array(6,array(8,));
?>
运行结果如下：
1 3 7 2 5 6 9 4 8
4 6 8 9 7 3 2 1 5
2 5 9 1 8 4 6 7 3
6 8 5 3 1 7 4 2 9
3 9 4 6 2 8 7 5 1
7 1 2 4 9 5 8 3 6
9 4 6 5 3 2 1 8 7
5 7 1 8 4 9 3 6 2
8 2 3 7 6 1 5 9 4
7 3 8 1 9 6 4 2 5
2 9 6 3 4 5 7 8 1
4 5 1 2 7 8 3 9 6
5 6 9 7 8 4 2 1 3
3 8 2 5 1 9 6 7 4
1 7 4 6 2 3 8 5 9
6 2 7 4 5 1 9 3 8
8 4 5 9 3 2 1 6 7
9 1 3 8 6 7 5 4 2
9 5 1 3 6 7 4 2 8
7 8 3 1 4 2 5 6 9
2 4 6 9 5 8 7 3 1
6 2 9 4 7 5 8 1 3
8 7 5 6 1 3 2 9 4
1 3 4 2 8 9 6 5 7
4 6 7 5 9 1 3 8 2
3 1 8 7 2 6 9 4 5
5 9 2 8 3 4 1 7 6
更多关于PHP相关内容感兴趣的读者可查看本站专题：《》、《》、《》、《》、《》、《》、《》及《》
希望本文所述对大家PHP程序设计有所帮助。
服务热线 19970861797
