Anonymous user
Sudoku: Difference between revisions
Added a solution for this problem using MATLAB
(Added a solution for this problem using MATLAB) |
|||
Line 1,335:
}
}</lang>
=={{header|MATLAB}}==
This solution impliments a recursive, depth-first search of the possible values unfilled sudoku cells can take. The search tree is pruned using logical deduction rules and takes about a minute to solve some of the more difficult puzzles. This code can be cleaned by making the main code blocks, denoted by "%% [Block Title]," into their own separate functions. This can also be further improved by implementing a Sudoku class and making this solver a member function. There are also several lines of code that can be vectorized to improve efficiency, but at the expense of readability.
For this to work, this code must be placed in a file named "sudokuSolver.m"
<lang MATLAB>function solution = sudokuSolver(sudokuGrid)
%Define what each of the sub-boxes of the sudoku grid are by defining
%the start and end coordinates of each sub-box. The indecies represent
%the column and row of a grid coordinate on the actual sudoku grid.
%The contents of each cell with the same grid coordinates contain the
%information to determine which sub-box that grid coordinate is
%contained in on the sudoku grid. The array in position 1, i.e.
%subBoxes{row,column}(1), represents the row indecies of the subbox.
%The array in position 2, i.e. subBoxes{row,column}(2),represents the
%column indecies of the subbox.
subBoxes(1:9,1:9) = {{(1:3),(1:3)}};
subBoxes(4:6,:)= {{(4:6),(1:3)}};
subBoxes(7:9,:)= {{(7:9),(1:3)}};
for column = (4:6)
for row = (1:9)
subBoxes{row,column}(2)= {4:6};
end
end
for column = (7:9)
for row = (1:9)
subBoxes{row,column}(2)= {7:9};
end
end
%Generate a cell of arrays which contain the possible values of the
%sudoku grid for each cell in the grid. The possible values a specific
%grid coordinate can take share the same indices as the sudoku grid
%coordinate they represent.
%For example sudokuGrid(m,n) can be possibly filled in by the
%values stored in the array at possibleValues(m,n).
possibleValues(1:9,1:9) = { (1:9) };
%Filter the possibleValues so that no entry exists for coordinates that
%have already been filled in. This will replace any array with an empty
%array in the possibleValues cell matrix at the coordinates of a grid
%already filled in the sudoku grid.
possibleValues( ~isnan(sudokuGrid) )={[]};
%Iterate through each grid coordinate and filter out the possible
%values for that grid point that aren't alowed by the rules given the
%current values that are filled in. Or, if there is only one possible
%value for the current coordinate, fill it in.
solution = sudokuGrid; %so the original sudoku input isn't modified
memory = 0; %contains the previous iterations possibleValues
dontStop = true; %stops the while loop when nothing else can be reasoned about the sudoku
while( dontStop )
%% Process of elimination deduction method
while( ~isequal(possibleValues,memory) ) %Stops using the process of elimination deduction method when this deduction rule stops working
memory = possibleValues; %Copies the current possibleValues into memory, for the above conditional on the next iteration.
%Iterate through everything
for row = (1:9)
for column = (1:9)
if isnan( solution(row,column) ) %If grid coordinate hasn't been filled in, try to determine it's value.
%Look at column to see what values have already
%been filled in and thus the current grid
%coordinate can't be
removableValues = solution( ~isnan(solution(:,column)),column );
%If there are any values that have been assigned to
%other cells in the same column, filter those out
%of the current cell's possiblValues
if ~isempty(removableValues)
for m = ( 1:numel(removableValues) )
possibleValues{row,column}( possibleValues{row,column}==removableValues(m) )=[];
end
end
%If the current grid coordinate can only atain one
%possible value, assign it that value
if numel( possibleValues{row,column} ) == 1
solution(row,column) = possibleValues{row,column};
possibleValues(row,column)={[]};
end
end %end if
if isnan( solution(row,column) ) %If grid coordinate hasn't been filled in, try to determine it's value.
%Look at row to see what values have already
%been filled in and thus the current grid
%coordinate can't be
removableValues = solution( row,~isnan(solution(row,:)) );
%If there are any values that have been assigned to
%other cells in the same row, filter those out
%of the current cell's possiblValues
if ~isempty(removableValues)
for m = ( 1:numel(removableValues) )
possibleValues{row,column}( possibleValues{row,column}==removableValues(m) )=[];
end
end
%If the current grid coordinate can only atain one
%possible value, assign it that value
if numel( possibleValues{row,column} ) == 1
solution(row,column) = possibleValues{row,column};
possibleValues(row,column)={[]};
end
end %end if
if isnan( solution(row,column) ) %If grid coordinate hasn't been filled in, try to determine it's value.
%Look at sub-box to see if any possible values can be
%filtered out. First pull the boundaries of the sub-box
%containing the current array coordinate
currentBoxBoundaries=subBoxes{row,column};
%Then pull the sub-boxes values out of the solution
box = solution(currentBoxBoundaries{:});
%Look at sub-box to see what values have already
%been filled in and thus the current grid
%coordinate can't be
removableValues = box( ~isnan(box) );
%If there are any values that have been assigned to
%other cells in the same sub-box, filter those out
%of the current cell's possiblValues
if ~isempty(removableValues)
for m = ( 1:numel(removableValues) )
possibleValues{row,column}( possibleValues{row,column}==removableValues(m) )=[];
end
end
%If the current grid coordinate can only atain one
%possible value, assign it that value
if numel( possibleValues{row,column} ) == 1
solution(row,column) = possibleValues{row,column};
possibleValues(row,column)={[]};
end
end %end if
end %end for column
end %end for row
end %stop process of elimination
%% Check that there are no contradictions in the solved grid coordinates.
%Check that each row at most contains one of each of the integers
%from 1 to 9
if ~isempty( find( histc( solution,(1:9),1 )>1 ) )
solution = false;
return
end
%Check that each column at most contains one of each of the integers
%from 1 to 9
if ~isempty( find( histc( solution,(1:9),2 )>1 ) )
solution = false;
return
end
%Check that each sub-box at most contains one of each of the integers
%from 1 to 9
subBoxBins = zeros(9,9);
counter = 0;
for row = [2 5 8]
for column = [2 5 8]
counter = counter +1;
%because the sub-boxes are extracted as square matricies,
%we need to reshape them into row vectors so all of the
%boxes can be input into histc simultaneously
subBoxBins(counter,:) = reshape( solution(subBoxes{row,column}{:}),1,9 );
end
end
if ~isempty( find( histc( subBoxBins,(1:9),2 )>1 ) )
solution = false;
return
end
%Check to make sure there are no grid coordinates that are not
%filled in and have no possible values.
[rowStack,columnStack] = find(isnan(solution)); %extracts the indicies of the unsolved grid coordinates
if (numel(rowStack) > 0)
for counter = (1:numel(rowStack))
if isempty(possibleValues{rowStack(counter),columnStack(counter)})
solution = false;
return
end
end
%if there are no more grid coordinates to be filed in then the
%sudoku is solved and we can return the solution without further
%computation
elseif (numel(rowStack) == 0)
return
end
%% Use the unique relative compliment of sets deduction method
%Because no more information can be determined by the process of
%ellimination we have to try a new method of reasoning. Now we will
%look at the possible values a cell can take. If there is a value that
%that grid coordinate can take but no other coordinates in the same row,
%column or sub-box can take that value then we assign that coordinate
%that value.
keepGoing = true; %signals to keep applying rules to the current grid-coordinate because it hasn't been solved using previous rules
dontStop = false; %if this method doesn't figure anything out, this will terminate the top level while loop
[rowStack,columnStack] = find(isnan(solution)); %This will also take care of the case where the sudoku is solved
counter = 0; %makes sure the loop terminates when there are no more cells to consider
while( keepGoing && (counter < numel(rowStack)) ) %stop this method of reasoning when the value of one of the cells has been determined and return to the process of elimination method
counter = counter + 1;
row = rowStack(counter);
column = columnStack(counter);
gridPossibles = [possibleValues{row,column}];
coords = (1:9);
coords(column) = [];
rowPossibles = [possibleValues{row,coords}]; %extract possible values for everything in the same row except the current grid coordinate
totalMatches = zeros( numel(gridPossibles),1 ); %preallocate for speed
%count how many times a possible value for the current cell
%appears as a possible value for the cells in the same row
for n = ( 1:numel(gridPossibles) )
totalMatches(n) = sum( (rowPossibles == gridPossibles(n)) );
end
%remove any possible values for the current cell that have
%matches in other cells
gridPossibles = gridPossibles(totalMatches==0);
%if there is only one possible value that the current cell can
%take that aren't shared by other cells, assign that value to
%the current cell.
if numel(gridPossibles) == 1
solution(row,column) = gridPossibles;
possibleValues(row,column)={[]};
keepGoing = false; %stop this method of deduction and return to the process of elimination
dontStop = true; %keep the top level loop going
end
if(keepGoing) %do the same as above but for the current cell's column
gridPossibles = [possibleValues{row,column}];
coords = (1:9);
coords(row) = [];
columnPossibles = [possibleValues{coords,column}];
totalMatches = zeros( numel(gridPossibles),1 );
for n = ( 1:numel(gridPossibles) )
totalMatches(n) = sum( (columnPossibles == gridPossibles(n)) );
end
gridPossibles = gridPossibles(totalMatches==0);
if numel(gridPossibles) == 1
solution(row,column) = gridPossibles;
possibleValues(row,column)={[]};
keepGoing = false;
dontStop = true;
end
end
if(keepGoing) %do the same as above but for the current cell's sub-box
gridPossibles = [possibleValues{row,column}];
currentBoxBoundaries = subBoxes{row,column};
subBoxPossibles = [];
for m = currentBoxBoundaries{1}
for n = currentBoxBoundaries{2}
if ~((m == row) && (n == column))
subBoxPossibles = [subBoxPossibles possibleValues{m,n}];
end
end
end
totalMatches = zeros( numel(gridPossibles),1 );
for n = ( 1:numel(gridPossibles) )
totalMatches(n) = sum( (subBoxPossibles == gridPossibles(n)) );
end
gridPossibles = gridPossibles(totalMatches==0);
if numel(gridPossibles) == 1
solution(row,column) = gridPossibles;
possibleValues(row,column)={[]};
keepGoing = false;
dontStop = true;
end
end %end
end %end set comliment rule while loop
end %end top-level while loop
%% Depth-first search of the solution tree
%There is no more reasoning that can solve the puzzle so now it is time
%for a depth-first search of the possible answers, basically
%guess-and-check. This is implimented recursively.
[rowStack,columnStack] = find(isnan(solution)); %Get all of the unsolved cells
if (numel(rowStack) > 0) %If all of the above stuff terminates then there will be at least one grid coordinate not filled in
%Treat the rowStack and columnStack like stacks, and pop the top
%value off the stack to act as the current node whose
%possibleValues to search through, then assign the possible values
%of that grid coordinate to a variable that holds that values to
%search through
searchTreeNodes = possibleValues{rowStack(1),columnStack(1)};
keepSearching = true; %used to continue the search
counter = 0; %counts the amount of possible values searched for the current node
tempSolution = solution; %used so that the solution is not overriden until a solution hase been found
while( keepSearching && (counter < numel(searchTreeNodes)) ) %stop recursing if we run out of possible values for the current node
counter = counter + 1;
tempSolution(rowStack(1),columnStack(1)) = searchTreeNodes(counter); %assign a possible value to the current node in the tree
tempSolution = sudokuSolver(tempSolution); %recursively call the solver with the current guess value for the current grid coordinate
if ~islogical(tempSolution) %if tempSolution is not a boolean but a valid sudoku stop recursing and set solution to tempSolution
keepSearching = false;
solution = tempSolution;
elseif counter == numel(searchTreeNodes) %if we have run out of guesses for the current node, stop recursing and return a value of "false" for the solution
solution = false;
else %reset tempSolution to the current state of the board and try the next guess for the possible value of the current cell
tempSolution = solution;
end
end %end recursion
end %end if
%% End of program
end %end sudokuSolver</lang>
[http://www.menneske.no/sudoku/eng/showpuzzle.html?number=6903541 Test Input]:
All empty cells must have a value of NaN.
<lang MATLAB>sudoku = [NaN NaN NaN NaN 8 3 9 NaN NaN
1 NaN NaN NaN NaN NaN NaN 3 NaN
NaN NaN 4 NaN NaN NaN NaN 7 NaN
NaN 4 2 NaN 3 NaN NaN NaN NaN
6 NaN NaN NaN NaN NaN NaN NaN 4
NaN NaN NaN NaN 7 NaN NaN 1 NaN
NaN 2 NaN NaN NaN NaN NaN NaN NaN
NaN 8 NaN NaN NaN 9 2 NaN NaN
NaN NaN NaN 2 5 NaN NaN NaN 6]</lang>
[http://www.menneske.no/sudoku/eng/solution.html?number=6903541 Output]:
<lang MATLAB>solution =
7 6 5 4 8 3 9 2 1
1 9 8 7 2 6 4 3 5
2 3 4 9 1 5 6 7 8
8 4 2 5 3 1 7 6 9
6 1 7 8 9 2 3 5 4
3 5 9 6 7 4 8 1 2
9 2 6 1 4 7 5 8 3
5 8 1 3 6 9 2 4 7
4 7 3 2 5 8 1 9 6</lang>
=={{header|OCaml}}==
| |||