Solving Combinatorial Problems: Knapsack and Sudoku in MATLAB

This assignment presents solutions to two distinct problems using MATLAB: the knapsack problem and Sudoku. For the knapsack problem, the objective is to maximize the benefit by selecting an optimal combination of items within a weight constraint, solved using BFS and DFS approaches. The MATLAB code for the knapsack problem is provided, along with the execution results showing the selected items and the computational time and memory usage. The second part of the assignment focuses on solving Sudoku puzzles using a MATLAB function that employs a backtracking algorithm. The code iterates through possible values, placing them and recursively calling the function until a valid solution is found. The provided MATLAB code efficiently solves the Sudoku puzzle, showcasing the final solved grid. Desklib provides access to this assignment and many others, offering students valuable resources for their studies.

Running head: ASSIGNMENT 1
ASSIGNMENT 1
Name of Student
Name of the University
Author Note

1Running head: ASSIGNMENT 1
Part 1:
The knapsack problem is one of the combinational optimization where the objective is to
maximize the benefit by choosing optimum number of items inside the bag.
ID b w
1 20 15
2 40 32
3 50 60
4 36 80
5 26 43
6 64 120
7 54 77
8 18 6
9 46 93
10 28 35
11 25 37
Max weight = 420.
Now, for solving the particular knapsack problem the BFS and DFS search methods are used
to find the items in the knapsack for maximum profit.
1. a) Now, the solution is given in array of 0s and 1s, where 0 means the item in that position
are not used in knapsack and 1 means that the item in that position is used in knapsack. The

2Running head: ASSIGNMENT 1
solution will be such that it gives maximum benefit without exceeding the maximum weight
that the knapsack can carry.
b) The objective function is
Maximize b
Where b = benefit = combination of items in 0 or 1 format.
c) The constraints of the problem are
sum(w) < = 420.
Item i = 0 or 1.
2. a.
The MATLAB program knapsack.m is executed which calculates the items to be used to gain
the maximum benefit in the knapsack.
MATLAB code:
function [max_profit quantity] = knapsack(weights, profits, max_w)
[M,N] = size(weights);
weights = weights(:);
profits = profits(:);
% initializing A matrix as the queue matrix
A = zeros(length(weights)+1,max_w+1);
% A(j+1,Y+1) is the optimum knapsack profit having maximum weight Y
% while using the 1st j terms in the sequence

3Running head: ASSIGNMENT 1
%%% applying the BFS and DFS algorithm
for j = 1:length(weights)
for Y = 1:max_w
if weights(j) > Y
A(j+1,Y+1) = A(j,Y+1);
else
A(j+1,Y+1) = ...
max( A(j,Y+1), profits(j) + A(j,Y-weights(j)+1));
end
end
end
max_profit = A(end,end);
%Finding the array of items that are used in knapsack in A(end,end)
quantity = zeros(length(weights),1);
a = max_profit;
j = length(weights);
Y = max_w;
while a > 0
while A(j+1,Y+1) == a
j = j - 1;

4Running head: ASSIGNMENT 1
end
j = j + 1;
quantity(j) = 1;
Y = Y - weights(j);
j = j - 1;
a = A(j+1,Y+1);
end
quantity = reshape(quantity,M,N);
end
Execution and Output
>> b =[20 40 50 36 26 64 54 18 46 28 25];
>> w =[15 32 60 80 43 120 77 6 93 35 37];
>> max_w = 420;
>> [max_profit quantity] = knapsack(w,b,max_w)
max_profit =
307
quantity =
1 1 1 0 1 1 1 0 0 1 1
Hence, the items that are used in the knapsack for maximum benefit are item 1, 2, 3,
5,6,7,10,11.

5Running head: ASSIGNMENT 1
The time consumed by the function is calculated by the inbuilt MATLAB function timeit
f = @() knapsack(w,b,max_w);
>> t = timeit(f)
t =
5.9146e-05
Hence, the time consumed for execution of knapsack.m is 5.9146e-05 secs.
b. Now, memory used by the function is calculated by subtracting the memory used after
executing the function and before execution of the function.
>> memory
Maximum possible array: 2398 MB (2.514e+09 bytes) *
Memory available for all arrays: 2398 MB (2.514e+09 bytes) *
Memory used by MATLAB: 1722 MB (1.806e+09 bytes)
Physical Memory (RAM): 8062 MB (8.453e+09 bytes)
memory
Maximum possible array: 2413 MB (2.530e+09 bytes) *
Memory available for all arrays: 2413 MB (2.530e+09 bytes) *
Memory used by MATLAB: 1723 MB (1.806e+09 bytes)
Physical Memory (RAM): 8062 MB (8.453e+09 bytes)
Hence, the memory used by the function is 1723- 1722 = 1 MB.

6Running head: ASSIGNMENT 1
Part 2:
The MATLAB function for solving Sudoku is shown below.
MATLAB code:
function M = sudoku(M)
% Cell is a cell array of candidate vectors for each cell.
% one is the first cell, if any, with one candidate.
% no is the first cell, if any, with no candidates.
[Cell,one,no] = entities(M);
while ~isempty(one) && isempty(no)
M(one) = Cell{one};
[Cell,one,no] = entities(M);
end
% when there is no solution return nothing
if ~isempty(no)
return
end
% Applying DFS algorithm
if any(M(:) == 0)
Y = M;
z = find(M(:) == 0,1); % find the cell with 0 value

7Running head: ASSIGNMENT 1
for r = [Cell{z}] % Iterating through the entities
M = Y;
M(z) = r; % placing a value
M = sudoku(M); % calling the output X matrix again
if all(M(:) > 0) % when all the zeros are filled then a solution is obtained
return
end
end
end
function [Cell,one,no] = entities(X)
Cell = cell(9,9);
three = @(k) 3*ceil(k/3-1) + (1:3);
for j = 1:9
for i = 1:9
if X(i,j)==0
z = 1:9;
z(nonzeros(X(i,:))) = 0;
z(nonzeros(X(:,j))) = 0;
z(nonzeros(X(three(i),three(j)))) = 0;
Cell{i,j} = nonzeros(z)';

8Running head: ASSIGNMENT 1
end
end
end
L = cellfun(@length,Cell); % total number of entities
one = find(X==0 & L==1,1);
no = find(X==0 & L==0,1);
end
end
Output:
M
M =
0 3 4 0 0 0 6 0 0
0 0 2 6 0 0 0 8 0
0 6 8 3 0 0 0 0 7
0 0 3 0 0 1 0 0 5
0 5 9 0 6 0 0 7 2
0 0 0 5 2 0 0 4 6
2 0 5 9 0 6 0 0 0

9Running head: ASSIGNMENT 1
0 0 0 4 0 8 0 5 0
0 0 0 0 0 7 0 0 4
>> M = sudoku(M)
M =
7 3 4 1 8 5 6 2 9
1 9 2 6 7 4 5 8 3
5 6 8 3 9 2 4 1 7
6 2 3 7 4 1 8 9 5
4 5 9 8 6 3 1 7 2
8 1 7 5 2 9 3 4 6
2 4 5 9 1 6 7 3 8
9 7 6 4 3 8 2 5 1
3 8 1 2 5 7 9 6 4