人間にとって難しい問題にするには、アルゴリズムで解いた場合にバックトラックのコストが高くなる配置にすればいいんじゃないかな

ちなみに gnome_sudoku では100回ランダムに問題を作成して、都度難易度が期待値を上回るかどうか測定している。
↓の generate_puzzle_for_difficulty()@173行目
http://gnome-sudoku.cvs.sourceforge.net/viewvc/gnome-sudoku/gnome-sudoku/src/lib/sudoku_maker.py?view=markup

難易度の測定方法は、何も考えずに埋めれるマスの数、考えられる組み合わせの中から外れを引く割合などを重み付けして定量化。
(経験則っぽい...)
↓の DifficultyRating クラス@597行目
http://gnome-sudoku.cvs.sourceforge.net/viewvc/gnome-sudoku/gnome-sudoku/src/lib/sudoku.py?view=markup