1
Я написал программу в SciLab, которая решает судоку. Но он может только решить sudoku, который всегда имеет квадрат с 1 возможным значением. Как легко и просто sudoku на brainbashers.com.Sudoku Solver - Scilab
Средняя судоку всегда достигают точки, что у них нет квадрата с одним возможным значением. Как я могу изменить свой код для решения этих, более сложных sudoku?
///////////////////////////////////////////////////////////////////////////
////////////////////////// Check Sudoku ///////////////////////////////
///////////////////////////////////////////////////////////////////////////
function r=OneToNine(V) // function checks if the given vector V contains 1 to 9
r = %T // this works
u = %F
index = 1
while r == %T & index < 10
for i=1 : length(V)
if V(i)==index then
u = %T
end
end
index=index+1
if u == %F then r = %F
else u = %F
end
end
if length(V) > 9 then r = %F
end
endfunction
function y=check(M) // Checks if the given matrix M is a solved sudoku
y = %T // this works too
if size(M,1)<>9 | size(M,2)<>9 then // if it has more or less than 9 rows and columns
y = %F // we return false
end
for i=1 : size(M,1) // if not all rows have 1-9 we return false
if OneToNine(M(i,:)) == %F then
y = %F
end
end
endfunction
function P=PossibilitiesPosition(board, x, y)
// this one works
// we fill the vector possibilites with 9 zeros
// 0 means empty, 1 means it already has a value, so we don't need to change it
possibilities = [] // a vector that stores the possible values for position(x,y)
for t=1 : 9 // sudoku has 9 values
possibilities(t)=0
end
// Check row f the value (x,y) for possibilities
// we fill the possibilities further by puttin '1' where the value is not possible
for i=1 : 9 // sudoku has 9 values
if board(x,i) > 0 then
possibilities(board(x,i))=1
end
end
// Check column of the value (x,y) for possibilities
// we fill the possibilities further by puttin '1' where the value is not possible
for j=1 : 9 // sudoku has 9 values
if board(j, y) > 0 then
possibilities(board(j, y))=1
end
end
// Check the 3x3 matrix of the value (x,y) for possibilities
// first we see which 3x3 matrix we need
k=0
m=0
if x >= 1 & x <=3 then
k=1
else if x >= 4 & x <= 6 then
k = 4
else k = 7
end
end
if y >= 1 & y <=3 then
m=1
else if y >= 4 & y <= 6 then
m = 4
else m = 7
end
end
// then we fill the possibilities further by puttin '1' where the value is not possible
for i=k : k+2
for j=m : m+2
if board(i,j) > 0 then
possibilities(board(i,j))=1
end
end
end
P = possibilities
// we want to see the real values of the possibilities. not just 1 and 0
for i=1 : 9 // sudoku has 9 values
if P(i)==0 then
P(i) = i
else P(i) = 0
end
end
endfunction
function [x,y]=firstEmptyValue(board) // Checks the first empty square of the sudoku
R=%T // and returns the position (x,y)
for i=1 : 9
for j=1 : 9
if board(i,j) == 0 & R = %T then
x=i
y=j
R=%F
end
end
end
endfunction
function A=numberOfPossibilities(V) // this checks the number of possible values for a position
A=0 // so basically it returns the number of elements different from 0 in the vector V
for i=1 : 9
if V(i)>0 then
A=A+1
end
end
endfunction
function u=getUniquePossibility(M,x,y) // this returns the first possible value for that square
pos = [] // in function fillInValue we only use it
pos = PossibilitiesPosition(M,x,y) // when we know that this square (x,y) has only one possible value
for n=1 : 9
if pos(n)>0 then
u=pos(n)
end
end
endfunction
///////////////////////////////////////////////////////////////////////////
////////////////////////// Solve Sudoku ///////////////////////////////
///////////////////////////////////////////////////////////////////////////
function G=fillInValue(M) // fills in a square that has only 1 possibile value
x=0
y=0
pos = []
for i=1 : 9
for j=1 : 9
if M(i,j)==0 then
if numberOfPossibilities(PossibilitiesPosition(M,i,j)) == 1 then
x=i
y=j
break
end
end
end
if x>0 then
break
end
end
M(x,y)=getUniquePossibility(M,x,y)
G=M
endfunction
function H=solve(M) // repeats the fillInValue until it is a fully solved sudoku
P=[]
P=M
if check(M)=%F then
P=fillInValue(M)
H=solve(P)
else
H=M
end
endfunction
//////////////////////////////////////////////////////////////////////////////
Так решает эту первую один
// Very easy and easy sudokus from brainbashers.com get solved completely
// Very Easy sudoku from brainbashers.com
M = [0 2 0 0 0 0 0 4 0
7 0 4 0 0 0 8 0 2
0 5 8 4 0 7 1 3 0
0 0 1 2 8 4 9 0 0
0 0 0 7 0 5 0 0 0
0 0 7 9 3 6 5 0 0
0 8 9 5 0 2 4 6 0
4 0 2 0 0 0 3 0 9
0 1 0 0 0 0 0 8 0]
Но doens't решить эту среду:
M2= [0 0 6 8 7 1 2 0 0
0 0 0 0 0 0 0 0 0
5 0 1 3 0 9 7 0 8
1 0 7 0 0 0 6 0 9
2 0 0 0 0 0 0 0 7
9 0 3 0 0 0 8 0 1
3 0 5 9 0 7 4 0 2
0 0 0 0 0 0 0 0 0
0 0 2 4 3 5 1 0 0]
Код ошибки при попытке решить среды судоку:
-->solve(M2)
!--error 21
Invalid index.
at line 14 of function PossibilitiesPosition called by :
at line 3 of function getUniquePossibility called by :
at line 20 of function fillInValue called by :
at line 182 of function solve called by :
at line 183 of function solve called by :
at line 183 of function solve called by :
at line 183 of function solve called by :
at line 183 of function solve called by :
solve(M2)
at line 208 of exec file called by :
_SCILAB-6548660277741359031.sce', 1
while executing a callback
Общий подход. Если есть несколько возможностей, выберите один и попытайтесь решить оставшуюся версию. Если это не сработает, выберите следующую опцию и т. Д. – Sirko
Вы написали функцию firstEmptyValue, но вы ее не используете; у вас все еще есть старая двойная петля внутри fillInValue –