Lecture 8II SUDOKU PUZZLE SUDOKU New Play Check 軟體實作與計算實驗 1
4x4 Sudoku row column 3 2 } 4 } block 1 4 軟體實作與計算實驗 2
Sudoku Puzzle Numbers in the puzzle belong {1,2,3,4} Constraints Each column must contain four different numbers Each row must be filled with four different numbers Each block must be filled with four different numbers 軟體實作與計算實驗 3
9-by-9 Sudoku 軟體實作與計算實驗 4
Neural Computation 軟體實作與計算實驗 5
軟體實作與計算實驗 6
GUI Design 軟體實作與計算實驗 7
Open 軟體實作與計算實驗 8
A puzzle sudoku.fig Sudoku.m 軟體實作與計算實驗 9
Random permutation >> p1=randperm(4) p1 = 4 1 2 3 軟體實作與計算實驗 10
Flow Chart: New P1=randperm(4) P2=randperm(4) for i=1:4 row=p1(i); col=p2(i); C(row,col)=i; 軟體實作與計算實驗 11
Procedure : New Use randperm to generate two random permutations, p and q for i=1:4 j = p(i) d = q(i) C(i,j) = d Return C 軟體實作與計算實驗 12
New Randomly assign four different digits to four cells in the Puzzle such that one and only one cell in each row and column is assigned p= randperm(4);q=randperm(4); for each i Assign q(i) to the joint cell of column i and row p(i) Result One number in each row One number in each column All four numbers assigned are different 軟體實作與計算實驗 13
Press NEW 軟體實作與計算實驗 14
Press CHECK PLAY 軟體實作與計算實驗 15
Flow Chart : Row Checking N=size(S,2); Err=0; xx=1:4; for i=1:4 x=sort(s(i,:)); n=sum(x==xx); Err=Err+((N-n)>0); 軟體實作與計算實驗 16
Procedure : Row Checking Input a 4-by-4 matrix S; N=4; Set err to zero for i=1:4 A. Set n to the number of different digits in S(i,:) B. err =err +(N>n); Return err 軟體實作與計算實驗 17
Procedure : Column Checking Let S be a 4-by-4 matrix S; N=4 Set err to zero for i=1:4 A. Set n to the number of different digits in S(:,i) B. err =err +(N>n); Return err 軟體實作與計算實驗 18
block block } 3 } 4 } 2 } 1 4 } } block } } block 軟體實作與計算實驗 19
Indexing block Block 1: S(1:2,1:2) Block 2: S(1:2,3:4) Block 3: S(3:4,1:2) Block 4: S(3:4,3:4) 軟體實作與計算實驗 20
Indexing K=2; N=4=K 2 Block 1 is denoted by (a,b)=(1,1) S(1:2,1:2) Block 2 is denoted by (a,b)=(1,2) S(1:2,3:4) Block 3 is denoted by (a,b)=(2,1) S(3:4,1:2) Block 4 is denoted by (a,b)=(2,2) S(3:4,3:4) Block (a,b) S((a-1)*K+1:a*K, (b-1)*k+1:b*k) 軟體實作與計算實驗 21
Flow Chart: Block checking N=size(S,2);K=sqrt(N) Err=0; xx=1:4; for a=1:k for b=1:k Get the block (a,b) Reshape to a vector Sort the vector, x n=sum(x==xx); Err=Err+(N>n); 軟體實作與計算實驗 22
Procedure: Block Checking Input a 4x4 matrix S; N = 4; K=2; Set Err to zero for a=1:k for b=1:k B=S((a-1)*K+1:a*K, (b-1)*k+1:b*k); x=sort(reshape(b,1,n)); Set n to the number of different digits in x Err=Err+(N-n)>0 Return err 軟體實作與計算實驗 23
Get puzzle Get N 2 =16 digits in edit-cells of a puzzle Store 16 digits in a vector edit1 edit2 edit3 edit4 edit5 edit16 軟體實作與計算實驗 24
Get Puzzle function C=Get_Puzzle(hObject, eventdata, handles) C=zeros(1,16); for i=1:16 str=['get(handles.edit' int2str(i) ',''String'')']; z=eval(str); if length(z) > 0 C(i)=str2double(z); else C(i)=0; end end 軟體實作與計算實驗 25
Store a command to a string >> str=['get(handles.edit' int2str(i) ',''String'')'] str = get(handles.edit0,'string') 軟體實作與計算實驗 26
eval Two equivalent codes z=get(handles.edit0,'string') z=eval(str); 軟體實作與計算實驗 27
str=['get(handles.edit' int2str(i) ',''String'')']; z=eval(str); Get the content of the ith cell. Cell names: edit1, edit2,, edit16 軟體實作與計算實驗 28
Set Puzzle function Set_Puzzle(hObject, eventdata, handles,c) for i=1:16 str=['set(handles.edit' int2str(i) ',''FontSize'',' '20)']; eval(str); if C(i) > 0 str=['set(handles.edit' int2str(i) ',''ForegroundColor'',' '''Red''' ')']; eval(str); z=int2str(c(i)); str=['set(handles.edit' int2str(i) ',''String'',' z ')']; eval(str); end end 軟體實作與計算實驗 29
z=int2str(c(i)); str=['set(handles.edit' int2str(i) ',''String'',' z ')']; eval(str); Set the content of the ith cell to the number stored in C(i) 軟體實作與計算實驗 30
Exercise Download sudoku.m and sudoku.fig Implement the procedure for SUDOKU_New Implement procedures for row, column and block checking Revise sudoku.m New a sudoku game if the button NEW is pressed Calculate errors of row, column and block checking 軟體實作與計算實驗 31
Function calling Create a SUDOKU game Implement procedure SUDOKU_New function S=New_Sudoku() Call New_Sudoku at the beginning of pushbutton2_callback 軟體實作與計算實驗 32
function C=New_Sudoku() Function name New_Sudoku Input None Output C: a 4x4 matrix 軟體實作與計算實驗 33
function pushbutton2_callback(hobject, eventdata, handles) % hobject handle to pushbutton2 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) C=zeros(1,16); C(1)=1;C(2)=2;C(3)=3;C(4)=4; Set_Puzzle(hObject, eventdata, handles,c) 1. Call function New_Sudoku 2. The function output is a 4x4 matrix. 3. Reshape the output to a row vector before calling Set_Puzzle 軟體實作與計算實驗 34
Column-major reshape S=zeros(4,4); S(1,:)=[1 2 3 4]; C=reshape(S',1,16) 軟體實作與計算實驗 35
Function call S=New_Puzzle(); function Call to New_Puzzle() Store the return to S 軟體實作與計算實驗 36