EI34031-Sudoku

sudoku.m

#{
INPUT = [0 0 0 8 1 0 0 0 0
         2 0 0 3 7 0 0 0 0 
         8 1 0 0 0 0 0 4 0
         0 0 1 0 0 0 0 7 2
         0 0 0 0 0 0 0 6 3
         0 7 3 0 6 0 0 0 0 
         0 0 9 2 0 0 6 0 0
         4 0 0 0 0 6 0 0 9
         0 0 0 0 0 1 7 0 0];
#}

% 输入数据
INPUT = [2 1 0 6 3 0 8 9 0
         0 4 0 0 0 7 0 0 5
         0 0 0 9 0 0 0 0 7
         0 0 2 0 0 0 0 4 0
         4 0 0 1 0 2 0 0 6
         0 6 0 0 0 0 1 0 0
         7 0 0 0 0 3 0 0 0
         8 0 0 7 0 0 0 6 0
         0 3 5 0 9 4 0 2 1];

function s=validate(sudoku)
  s=0;
  for i = 1:9 % 行
    for j = 1:9 % 1-9
      if(sum(j == sudoku(i,:)) > 1)
        return
      end
    end
  end
  for i = 1:9 % 列
    for j = 1:9 % 1-9
      if(sum(j == sudoku(:,i)) > 1)
        return
      end
    end
  end
  for i = 1:3:9 % 行
    for j = 1:3:9 % 列 
      for k = 1:9 % 1-9
        if(sum(k == sudoku([(j-1)*9+i (j-1)*9+i+1 (j-1)*9+i+2 j*9+i j*9+i+1 j*9+i+2 (j+1)*9+i (j+1)*9+i+1 (j+1)*9+i+2]))>1)
          return
        end
      end
    end
  end
  s=1;
  return
endfunction

function s=validate_single(sudoku, _i, _j, val)
  s = 0;
  if(sum(sudoku(_i,:)==val)>0)
    return
  end
  if(sum(sudoku(:,_j)==val)>0)
    return
  end
  % 找到方格的左上角
  i = ceil(_i/3)*3-2;
  j = ceil(_j/3)*3-2;
  % 对整个方格进行判断
  if(sum(val == sudoku([(j-1)*9+i (j-1)*9+i+1 (j-1)*9+i+2 j*9+i j*9+i+1 j*9+i+2 (j+1)*9+i (j+1)*9+i+1 (j+1)*9+i+2]))>0)
    return
  end
  s=1;
  return
endfunction

% 判断问题是否已经完全解决
function s=is_solved(sudoku)
  if(sum(sudoku==0)==0 & validate(sudoku)==1)
    s=1;
    return
  endif
  s=0;
endfunction

% 递归求解
function s=solve(_i, _j, sudoku)
  if(sudoku(_i,_j)==0)
    for k=1:9
      % 是否可填入
      if(validate_single(sudoku, _i, _j, k) == 1)
        sudoku(_i,_j)=k;
        % 找到可行解
        if(_i==9&&_j==9)
          s=sudoku;
          return
        % 换列
        elseif(_i==9)
          s = solve(1, _j+1, sudoku);
        else
          s = solve(_i+1, _j, sudoku);
        end
        % 递归找到解
        if(s != 0 && is_solved(s)==1)
          return
        end
        % 未找到解，继续
        sudoku(_i, _j)=0;
      end
    endfor
    s = 0;
    return
  else
    if(_i==9&&_j==9)
      s = sudoku;
      return
    elseif(_i==9)
      s = solve(1, _j+1, sudoku);
    else
      s = solve(_i+1, _j, sudoku);
    end
  end
endfunction

% 求可行集合
function ret=get_available(_i, _j, sudoku)
  x = sudoku(_i,:);
  y = sudoku(:,_j);
  i = ceil(_i/3)*3-2;
  j = ceil(_j/3)*3-2;
  z = sudoku([(j-1)*9+i (j-1)*9+i+1 (j-1)*9+i+2 j*9+i j*9+i+1 j*9+i+2 (j+1)*9+i (j+1)*9+i+1 (j+1)*9+i+2]);
  ret = 1:9;
  ret = setdiff(ret, x);
  ret = setdiff(ret, y);
  ret = setdiff(ret, z);
end

% 候选数优化
function s=prepare(sudoku)
  s=sudoku;
  for i=1:9
    for j=1:9
      if(sudoku(i,j)==0)
        x = get_available(i,j,s);
        if(length(x) == 1)
          s(i,j)=x(1);
        end
      end
    end
  end
endfunction

% 绘图
function draw(question, ans)
  one_to_ten = [1 10];
  clf
  hold on;
  for x=1:10
    if(mod(x, 3) == 1)
      plot([x x], one_to_ten, 'k', 'LineWidth', 8);
      plot(one_to_ten, [x x], 'k', 'LineWidth', 8);
    else
      plot([x x], one_to_ten, 'k:');
      plot(one_to_ten, [x x], 'k:');
    end
  end
  
  for i=1:9
    for j=1:9
      if(question(i,j)>0)
        text(j+0.5, 10.5-i, mat2str(question(i,j)), 'FontSize',24);
      else
        text(j+0.5, 10.5-i, mat2str(ans(i,j)), 'color', 'red', 'FontSize',24);
      end
    end
  end
  axis([0,11,0,11]);
  hold off;
endfunction


tic;
t1=toc;
% 回溯法
output = solve(1,1,INPUT);

t2=toc;

% 候选数优化
s = prepare(INPUT);
output = solve(1,1,s);
t3=toc;

% 时间
[t2-t1, t3-t2]
% 绘图
draw(INPUT, output);