PHP实现数独破解(可以直接测试使用)

有时候会玩数独游戏，玩的多了会发现可以使用计算机来求解数独里的数字，使用递归进行进行遍历即可，所以就写了这么一个小功能，放在我的网站里，有兴趣的可以研究代码，或者也可以直接使用，要使用戳这里:数独破解测试使用

本功能使用两个php页面完成，sudoku_web.php是用来输入数据的，而sudoku_with.php是用来处理数据的，不要随意访问php页面，否则会被重定向。使用时要注意输入的数据正确，数独只有1-9,共9个数字，请不要输入其他字符，破解结果中，灰色输入框是使用者自己输入的数据，本功能作为测试，如有雷同，纯属巧合。

效果图

输入数据

破解结果

下面是代码

sudoku_web.php

&lt;!DOCTYPE html&gt;
&lt;html lang="en"&gt;
&lt;head&gt;
    &lt;meta charset="UTF-8"&gt;
    &lt;title&gt;Title&lt;/title&gt;
&lt;/head&gt;
&lt;body&gt;
&lt;style&gt;
    .form{
        width: 395px;
        height: 200px;
    }
    input{
        width: 30px;
        height: 30px;
        font-size: 18px;
        text-align: center;
    }
    td{

    }
&lt;/style&gt;
&lt;div align="center"&gt;
    &lt;h1&gt;数独破解&lt;/h1&gt;
    （请在对应文本框中输入已经提示的数字，请保证输入的只有数字，然后点击提交）
    &lt;form action="sudoku.php" method="post"&gt;
    &lt;table border="0" &gt;
        &lt;?php
            $sum = 0;
            for ($i=0;$i&lt;9;$i++){
                echo "&lt;tr&gt;";
                for ($j=0;$j&lt;9;$j++){
                    $sum = $sum + 1;
                    echo "&lt;td&gt;&lt;input type=\"text\" name=\"fig".$sum."\" max=\"9\" min=\"1\" maxlength=\"1\" size=\"1\" value=\"\"&gt;&lt;/td&gt;";
                    if($sum%3==0){
                        echo "&lt;td&gt;&lt;/td&gt;";
                    }
                }
                echo "&lt;/tr&gt;";
                if($sum%27==0){
                    echo "&lt;tr&gt;&lt;/tr&gt;&lt;tr&gt;&lt;/tr&gt;";
                }
            }

        ?&gt;
    &lt;/table&gt;
    &lt;input type="submit" value="提交" style="width: 50px;height: 30px;"&gt;   &lt;input type="reset" value="重置" style="width: 50px;height: 30px;"&gt;
    &lt;/form&gt;
&lt;/div&gt;
&lt;/body&gt;
&lt;/html&gt;

<!DOCTYPE html>

<head>

<title>Title</title>

</head>

<body>

<style>

.form{

width: 395px;

height: 200px;

}

input{

width: 30px;

height: 30px;

font-size: 18px;

text-align: center;

}

td{

}

</style>

（请在对应文本框中输入已经提示的数字，请保证输入的只有数字，然后点击提交）

<?php

$sum = 0;

for ($i=0;$i<9;$i++){

echo "<tr>";

for ($j=0;$j<9;$j++){

$sum = $sum + 1;

echo "<td><input type=\"text\" name=\"fig".$sum."\" max=\"9\" min=\"1\" maxlength=\"1\" size=\"1\" value=\"\"></td>";

if($sum%3==0){

echo "<td></td>";

}

echo "</tr>";

if($sum%27==0){

echo "<tr></tr><tr></tr>";

}

</table>

</form>

</div>

</body>

</html>

sudoku_with.php

&lt;!DOCTYPE html&gt;
&lt;html lang="en"&gt;
&lt;head&gt;
    &lt;meta charset="UTF-8"&gt;
    &lt;title&gt;Title&lt;/title&gt;
&lt;/head&gt;
&lt;body&gt;
&lt;style&gt;
    .form{
        width: 395px;
        height: 200px;
    }
    input{
        width: 30px;
        height: 30px;
        font-size: 18px;
        text-align: center;
    }
    td{

    }
&lt;/style&gt;
&lt;?php
/**
 * Created by PhpStorm.
 * User: Rain
 * Date: 2017/5/2
 * Time: 21:29
 */
//$old_host =  $_SERVER['HTTP_REFERER'];
//if($old_host != 'http://www.rain1024.com/more/sudoku_web.php'){
//    $url = 'http://www.rain1024.com/more/sudoku_web.php';
//    header("Locatio:$url");
//    exit();
//}
//$host = $_SERVER['HTTP_HOST'];
//if($host=='manage.rain1024.com'){
//    $url = 'manage.rain1024.com/manage/index.php';
//    header("Locatio:$url");
//    exit();
//}
$sudoku_arr = array();
for ($i = 0; $i &lt; 20; $i++) {
    for ($j = 0; $j &lt; 20; $j++) {
        $sudoku_arr[$i][$j] = 0;
    }
}
$sum = 0;
for ($i = 0; $i &lt; 9; $i++) {
    for ($j = 0; $j &lt; 9; $j++) {

        $sum = $sum + 1;
        /**
         * 要先判断输入的类型，只能是1-9的数字
         */
        if (empty($_POST['fig' . $sum])) {
            $sudoku_arr[$i][$j] = 0;
        } else {
            $sudoku_arr[$i][$j] = intval($_POST['fig' . $sum]);
        }
    }
}
$new_arr = $sudoku_arr;
//var_dump($sudoku_arr);
/* 数独求解程序
 * Created on 2017-4-18
 *
 */
class Sudoku {
    var $matrix;
    function __construct($arr = null) {
        if ($arr == null) {
            $this-&gt;clear();
        } else {
            $this-&gt;matrix = $arr;
        }
    }
    function clear() {
        for($i=0; $i&lt;9; $i++) {
            for($j=0; $j&lt;9; $j++) {
                $this-&gt;matrix[$i][$j] = array();
                for ($k = 1; $k &lt;= 9; $k++) {
                    $this-&gt;matrix[$i][$j][$k] = $k;
                }
            }
        }
    }
    function setCell($row, $col, $value){
        $this-&gt;matrix[$row][$col] = array($value =&gt; $value);
        //row
        for($i = 0; $i &lt; 9; $i++){
            if($i != $col){
                if(! $this-&gt;removeValue($row, $i, $value)) {
                    return false;
                }
            }
        }
        //col
        for($i = 0; $i &lt; 9; $i++){
            if($i != $row){
                if(! $this-&gt;removeValue($i, $col, $value)) {
                    return false;
                }
            }
        }
        //square
        $rs=intval($row / 3) * 3;
        $cs=intval($col / 3) * 3;
        for($i = $rs; $i &lt; $rs + 3; $i++){
            for($j = $cs; $j &lt; $cs + 3; $j++){
                if($i != $row &amp;&amp; $j != $col){
                    if(! $this-&gt;removeValue($i, $j, $value))
                        return false;
                }
            }
        }
        return true;
    }
    function removeValue($row, $col, $value) {
        $count = count($this-&gt;matrix[$row][$col]);
        if($count == 1){
            $ret = !isset($this-&gt;matrix[$row][$col][$value]);
            return $ret;
        }
        if (isset($this-&gt;matrix[$row][$col][$value])) {
            unset($this-&gt;matrix[$row][$col][$value]);
            if($count - 1 == 1) {
                return $this-&gt;setCell($row, $col, current($this-&gt;matrix[$row][$col]));
            }
        }
        return true;
    }
    function set($arr) {
        for ($i = 0; $i &lt; 9; $i++) {
            for ($j = 0; $j &lt; 9; $j++) {
                if ($arr[$i][$j] &gt; 0) {
                    $this-&gt;setCell($i, $j, $arr[$i][$j]);
                }
            }
        }
    }
    function dump() {
        for($i = 0; $i &lt; 9; $i++){
            for($j = 0; $j &lt; 9; $j++){
                $c = count($this-&gt;matrix[$i][$j]);
                if($c == 1){
                    echo " ".current($this-&gt;matrix[$i][$j])." ";
                } else {
                    echo "(".$c.")";
                }
            }
            echo "&lt;br&gt;";
        }
        echo "&lt;br&gt;";
    }
    function result() {
        global $new_arr;
        for($i = 0; $i &lt; 9; $i++){
            for($j = 0; $j &lt; 9; $j++){
                $c = count($this-&gt;matrix[$i][$j]);
                if($c == 1){
                    $new_arr[$i][$j] = current($this-&gt;matrix[$i][$j]);
                } else {
                    $new_arr[$i][$j] = $c;
                }
            }
//            echo "&lt;br&gt;";
        }
//        echo "&lt;br&gt;";
    }
    function dumpAll() {
        for($i = 0; $i &lt; 9; $i++){
            for($j = 0; $j &lt; 9; $j++){
                echo implode('', $this-&gt;matrix[$i][$j]), "  ";
            }
            echo "&lt;br&gt;";
        }
        echo "&lt;br&gt;";
    }
    function calc($data) {
        $this-&gt;clear();
        $this-&gt;set($data);
        $this-&gt;_calc();
        $this-&gt;result();
//        $this-&gt;dump();
    }
    function _calc() {
        for($i = 0; $i &lt; 9; $i++){
            for($j = 0; $j &lt; 9; $j++){
                if(count($this-&gt;matrix[$i][$j]) == 1) {
                    continue;
                }
                foreach($this-&gt;matrix[$i][$j] as $v){
                    $flag = false;
                    $t = new Sudoku($this-&gt;matrix);
                    if(!$t-&gt;setCell($i, $j, $v)){
                        continue;
                    }
                    if(!$t-&gt;_calc()){
                        continue;
                    }
                    $this-&gt;matrix = $t-&gt;matrix;
                    return true;
                }
                return false;
            }
        }
        return true;
    }
}
$sudoku = new Sudoku();
$sudoku-&gt;calc($sudoku_arr);
//for ($i = 0; $i &lt; 9; $i++) {
//    for ($j = 0; $j &lt; 9; $j++) {
//        echo $new_arr[$i][$j]."  ";
//    }
//    echo "&lt;br&gt;";
//}
?&gt;

&lt;div align="center"&gt;
    &lt;h1&gt;破解结果&lt;/h1&gt;
    （灰色输入框为自己输入的值，点击返回按钮可重新修改内容）
        &lt;table border="0" &gt;
            &lt;?php
            $sum = 0;
            for ($i=0;$i&lt;9;$i++){
                echo "&lt;tr&gt;";
                for ($j=0;$j&lt;9;$j++){
                    $sum = $sum + 1;
                    if($sudoku_arr[$i][$j]==0){
                        echo "&lt;td&gt;&lt;input  type=\"text\" value=\"".$new_arr[$i][$j]."\" max=\"9\" min=\"1\" maxlength=\"1\" size=\"1\" &gt;&lt;/td&gt;";
                    }else{
                        echo "&lt;td&gt;&lt;input style='background-color: #cac5c9' type=\"text\" max=\"9\" min=\"1\" maxlength=\"1\" size=\"1\" value=\"".$sudoku_arr[$i][$j]."\"&gt;&lt;/td&gt;";
                    }
                    if($sum%3==0){
                        echo "&lt;td&gt;&lt;/td&gt;";
                    }
                }
                echo "&lt;/tr&gt;";
                if($sum%27==0){
                    echo "&lt;tr&gt;&lt;/tr&gt;&lt;tr&gt;&lt;/tr&gt;";
                }
            }

            ?&gt;
        &lt;/table&gt;
        &lt;input type="button" value="返回" style="width: 50px;height: 30px;" onclick="goback()"&gt;
&lt;/div&gt;
&lt;script&gt;
    function goback(){
        history.go(-1);
    }
&lt;/script&gt;
&lt;/body&gt;
&lt;/html&gt;

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

<!DOCTYPE html>

<head>

<title>Title</title>

</head>

<body>

<style>

.form{

width: 395px;

height: 200px;

}

input{

width: 30px;

height: 30px;

font-size: 18px;

text-align: center;

}

td{

}

</style>

<?php

/**

* Created by PhpStorm.

* User: Rain

* Date: 2017/5/2

* Time: 21:29

//$old_host = $_SERVER['HTTP_REFERER'];

//if($old_host != 'http://www.rain1024.com/more/sudoku_web.php'){

// $url = 'http://www.rain1024.com/more/sudoku_web.php';

// header("Locatio:$url");

// exit();

//}

//$host = $_SERVER['HTTP_HOST'];

//if($host=='manage.rain1024.com'){

// $url = 'manage.rain1024.com/manage/index.php';

// header("Locatio:$url");

// exit();

//}

$sudoku_arr = array();

for ($i = 0; $i < 20; $i++) {

for ($j = 0; $j < 20; $j++) {

$sudoku_arr[$i][$j] = 0;

}

$sum = 0;

for ($i = 0; $i < 9; $i++) {

for ($j = 0; $j < 9; $j++) {

$sum = $sum + 1;

/**

* 要先判断输入的类型，只能是1-9的数字

if (empty($_POST['fig' . $sum])) {

$sudoku_arr[$i][$j] = 0;

} else {

$sudoku_arr[$i][$j] = intval($_POST['fig' . $sum]);

}

$new_arr = $sudoku_arr;

//var_dump($sudoku_arr);

/* 数独求解程序

* Created on 2017-4-18

class Sudoku {

var $matrix;

function __construct($arr = null) {

if ($arr == null) {

$this->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, $col, $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, $col, $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, $col, 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, $j, $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 "<br>";

}

echo "<br>";

}

function result() {

global $new_arr;

for($i = 0; $i < 9; $i++){

for($j = 0; $j < 9; $j++){

$c = count($this->matrix[$i][$j]);

if($c == 1){

$new_arr[$i][$j] = current($this->matrix[$i][$j]);

} else {

$new_arr[$i][$j] = $c;

}

// echo "<br>";

}

// echo "<br>";

}

function dumpAll() {

for($i = 0; $i < 9; $i++){

for($j = 0; $j < 9; $j++){

echo implode('', $this->matrix[$i][$j]), " ";

}

echo "<br>";

}

echo "<br>";

}

function calc($data) {

$this->clear();

$this->set($data);

$this->_calc();

$this->result();

// $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, $j, $v)){

continue;

}

if(!$t->_calc()){

continue;

}

$this->matrix = $t->matrix;

return true;

}

return false;

}

return true;

}

$sudoku = new Sudoku();

$sudoku->calc($sudoku_arr);

//for ($i = 0; $i < 9; $i++) {

// for ($j = 0; $j < 9; $j++) {

// echo $new_arr[$i][$j]." ";

// }

// echo "<br>";

//}

（灰色输入框为自己输入的值，点击返回按钮可重新修改内容）

<?php

$sum = 0;

for ($i=0;$i<9;$i++){

echo "<tr>";

for ($j=0;$j<9;$j++){

$sum = $sum + 1;

if($sudoku_arr[$i][$j]==0){

echo "<td><input type=\"text\" value=\"".$new_arr[$i][$j]."\" max=\"9\" min=\"1\" maxlength=\"1\" size=\"1\" ></td>";

}else{

echo "<td><input style='background-color: #cac5c9' type=\"text\" max=\"9\" min=\"1\" maxlength=\"1\" size=\"1\" value=\"".$sudoku_arr[$i][$j]."\"></td>";

}

if($sum%3==0){

echo "<td></td>";

}

echo "</tr>";

if($sum%27==0){

echo "<tr></tr><tr></tr>";

}

</table>

</div>

function goback(){

history.go(-1);

}

</script>

</body>

</html>

效果图

输入数据

破解结果

下面是代码

sudoku_web.php

sudoku_with.php

发表回复 取消回复

发表回复取消回复