1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
| -module(sudoku4x4).
-include_lib("eunit/include/eunit.hrl").
-export([seed_matrix2/0]).
-export([run/0]).
-export([element/3, solve/1, take_row_and_column/4, pick_num/4, pos_to_xy/2]).
%% matrix representation
seed_matrix2() ->
[0, 0, 1, 0,
4, 0, 0, 0,
0, 0, 0, 2,
0, 4, 0, 0].
matrix2_ans() ->
[3, 2, 1, 4,
4, 1, 2, 3,
1, 3, 4, 2,
2, 4, 3, 1].
element(X, Y, _) when X < 0; Y < 0 ->
nil;
element(X, Y, Matrix) ->
% make sure it is zero-indexed
lists:nth(X*9 + Y - 1, Matrix).
pos_to_xy(Pos, Len) when Pos rem Len =:= 0 ->
{(Pos div Len), Len};
pos_to_xy(Pos, Len) ->
{(Pos div Len) + 1, Pos rem Len}.
take_row_and_column(R, C, AnsMatrix) ->
SideLen = round(math:sqrt(length(AnsMatrix))),
take_row_and_column(R, C, AnsMatrix, SideLen).
take_row_and_column(R, C, AnsMatrix, SideLen) ->
% io:format("take_row_and_column: ~p~n", [AnsMatrix]),
RowVector = [ lists:nth((R-1)*SideLen+X, AnsMatrix) || X <- lists:seq(1, SideLen)],
ColVector = [ lists:nth((X-1)*SideLen+C, AnsMatrix) || X <- lists:seq(1, SideLen)],
{RowVector, ColVector}.
%% pick a number to test for coordinate x,y
pick_num(R, C, AnsMatrix, StartFromThisNum) ->
SideLen = round(math:sqrt(length(AnsMatrix))),
{RV, CV} = take_row_and_column(R, C, AnsMatrix, SideLen),
pick_num2(R, C, RV, CV, StartFromThisNum, SideLen).
pick_num2(R, C, RV, CV, Num, Bound) when Num =< Bound ->
F = fun(X) -> X == Num end,
InRow = lists:any(F, RV),
InCol = lists:any(F, CV),
case { InRow, InCol } of
{false, false} -> {ok, Num};
_ -> pick_num2(R, C, RV, CV, Num+1, Bound)
end;
pick_num2(_R, _C, _RV, _CV, _Num, _Bound) ->
{err, 0}.
solve(Seed) ->
%% round() is needed to convert it to integer
solve(Seed, 1, [], Seed, 1, round(math:sqrt(length(Seed))), []).
solve_backtrack(Seed, PosInSeed, _Begin, Rest, LastNum, SideLen, []) ->
solve(Seed, 1, [], Seed, 1, SideLen, []); % initial step
solve_backtrack(Seed, _PosInSeed, Ans, _Rest, _LastNum, SideLen, [LastStep|Tail]) ->
{LasPosInSeed, LastPosInSeedNum} = LastStep,
PrevAns = lists:sublist(Ans, 1, LasPosInSeed-1),
Rest = lists:sublist(Seed, LasPosInSeed, length(Seed)-LasPosInSeed+1),
solve(Seed, LasPosInSeed, PrevAns, Rest, LastPosInSeedNum, SideLen, Tail).
is_check_point(6, 4) ->
{yes, [{1, 6}]};
is_check_point(8, 4) ->
{yes, [{1, 6}, {3, 8}]};
is_check_point(14, 4) ->
{yes, [{1, 6}, {3, 8}, {9, 14}]};
is_check_point(16, 4) ->
{yes, [{1, 6}, {3, 8}, {9, 14}, {11, 16}]};
is_check_point(_,_) ->
{no, []}.
is_well_formed(M, Pts) when is_list(Pts) ->
F = fun({X, Y}) -> is_well_formed(M, X, Y) end,
lists:all(F, Pts).
is_well_formed(M, 1, 6) ->
case lists:nth(1, M) + lists:nth(2, M) + lists:nth(5, M) + lists:nth(6, M) of
10 -> true;
_ -> false
end;
is_well_formed(M, 3, 8) ->
case lists:nth(3, M) + lists:nth(4, M) + lists:nth(7, M) + lists:nth(8, M) of
10 -> true;
_ -> false
end;
is_well_formed(M, 9, 14) ->
case lists:nth(9, M) + lists:nth(10, M) + lists:nth(13, M) + lists:nth(14, M) of
10 -> true;
_ -> false
end;
is_well_formed(M, 11, 16) ->
case lists:nth(11, M) + lists:nth(12, M) + lists:nth(15, M) + lists:nth(16, M) of
10 -> true;
_ -> false
end;
is_well_formed(_, _, _) ->
false.
solve(Seed, PosInSeed, Ans, [H|Remain], LastNum, SideLen, Steps) when H =:= 0
->
{R, C} = pos_to_xy(PosInSeed, SideLen),
CurrentMatrix = lists:sublist(Ans, 1, PosInSeed-1) ++ lists:sublist(Seed, PosInSeed, length(Seed)-PosInSeed+1),
case pick_num(R, C, CurrentMatrix, LastNum+1) of
{ok, NewH} ->
case is_check_point(PosInSeed, SideLen) of
{yes, Pts} ->
ProposedMatrix = lists:sublist(Ans, 1, PosInSeed-1) ++ [NewH] ++ lists:sublist(Seed, PosInSeed+1, length(Seed)-PosInSeed+1),
case is_well_formed(ProposedMatrix, Pts) of
true -> %% move on
solve(Seed, PosInSeed+1, Ans++[NewH], Remain, 0, SideLen, [{PosInSeed, NewH}]++Steps);
false -> %% backtraked
solve_backtrack(Seed, -1, Ans, [H]++Remain, -1, SideLen, Steps)
end;
{no, _} -> % continue
solve(Seed, PosInSeed+1, Ans++[NewH], Remain, 0, SideLen, [{PosInSeed, NewH}]++Steps)
end;
_ -> %% backtracked
solve_backtrack(Seed, -1, Ans, [H]++Remain, -1, SideLen, Steps)
end;
solve(Seed, PosInSeed, Begin, [H|Remain], _TriedNumAtThisPos, SideLen, Steps) ->
%% seeded value, move on
solve(Seed, PosInSeed+1, Begin ++ [H], Remain, 0, SideLen, Steps);
solve(_Seed, EndPos, Ans, _, _, SideLen, _Steps) when EndPos == SideLen*SideLen+1 ->
Ans.
run() ->
Ans = solve(seed_matrix2()),
io:format("Ans ~p~n", [Ans]).
unit_test() ->
[?assert(pos_to_xy(1, 4) =:= {1, 1}),
?assert(pos_to_xy(4, 4) =:= {1, 4}),
?assert(pos_to_xy(7, 4) =:= {2, 3}),
?assert(pick_num2(1, 1, [1,0], [0,0], 1, 2) =:= {ok, 2}),
?assert(pick_num2(1, 1, [1,0], [1,2], 1, 2) =:= {err, 0}),
?assert(pick_num2(1, 1, [1,0], [1,2], 5, 2) =:= {err, 0})
].
|