How do Sudoku creators (the human kind) know that they’ve given enough clues to make a puzzle solvable while still making sure there are no errors?
In: 39
I made my own sudoku game with selectable 3 difficulty settings.
My first step was making a sudoku solver, a program that will solve any valid board. There are basically 2 ways of achieving this – brute-force / backtracking (just testing for every possible path to solution) and using common algorithms used by humans to solve. Of course – in reverse order.
First I try the easy elimination. From there, when it’s needed I use the backtracking algo. This is very slow, so it’s the last resort. It is slow, because there are many possible combinations to test. Also – I test if only ONE solution exist, if there’s more than one the board is invalid.
Let’s forget about backtracking. Sometimes a digit you can enter is obvious. This is the simples case. However – if there is only ONE such move and you must enter just that one number to proceed – this is called a bottleneck. It’s still easy to solve, but it’s tedious and unpleasant. So I discard the boards with too many bottle-necks. Then there are more advanced solving techniques and I try to solve the board using each of them counting how many times I had to use each of them to get the solution. Boards where advanced techniques were used I classify as “medium” difficulty. Then come the boards where I had to use backtracking / brute-force algorithm. It is my shortcut, because I’m too weak at Sudoku to implement better algorithms. That kind of boards I classify as “hard”.
BTW, backtracking / brute-force algo gives you a definitive answer if the board has exactly one solution. It also achieves it in reasonable time.
I tested my game on a good human player and it works exactly as expected. The “easy” boards were too easy for her, the “medium” was “not too tough” but “fun to play”, the “hard” were “challenging” to “frustrating”. Yet of course still solvable.
Latest Answers