1
$\begingroup$

With a blank grid, I put and number (1-9) any cell, the Sudoku has n solutions. I continue filling any blank cells with numbers that satisfy the constraints, so the Sudoku still has many solutions, but less than n. I keep filling in cell,s so the total solutions will become less and less, until all the cells are either filled or I've hit a dead end (the Sudoku is unsolvable).

While I am doing this, I want to make sure that the current number I am filling into a cell will not produce an unsolvable Sudoku.

Is there any method/algorithm to check the solvability (has at least one solution) of an uncompleted Sudoku without actually solve it? The reason is I am doing it on paper, solve a sudoku with more than one solution need backtracing algorithm that beyond anyone's caluculation limitation to solve it without computer.

Improve this question
$\endgroup$
6
  • $\begingroup$ there are algorithms to solve sudoku, use one of them. $\endgroup$
    – Jasen
    May 9, 2016 at 8:48
  • $\begingroup$ Dancing Links is generally accepted as being the best one. en.wikipedia.org/wiki/Dancing_Links $\endgroup$
    – Dennis_E
    May 9, 2016 at 9:28
  • $\begingroup$ @Dennis_E I know how to solve a sudoku, I want to check the solvability without solve it. $\endgroup$
    – xfx
    May 9, 2016 at 10:25
  • $\begingroup$ @Jasen I know how to solve a sudoku, I want to check the solvability without solve it. $\endgroup$
    – xfx
    May 9, 2016 at 10:25
  • $\begingroup$ @xfx I have implemented this years ago, using Dancing Links. I also implemented a Sudoku generator that does exactly what you describe. Dancing Links doesn't just solve Sudoku's. If a Sudoku has 0 solutions, it will discover that during the solving process (a column in the matrix has a size of 0). The only way to discover if a Sudoku has 1 or more than 1 solutions is to solve it. $\endgroup$
    – Dennis_E
    May 9, 2016 at 10:31

1 Answer 1

Reset to default
2
$\begingroup$

As far as I know, there is no way to do it as you describe without actually solving the Sudoku.

There is however a slightly different approach to creating a Sudoku that should work: Instead of starting with an empty grid and adding numbers, start with a full grid and remove numbers. If you only remove a number that you know could be deduced from the numbers that remain, then the Sudoku obviously still has a unique solution. This way you only have to check one solving step at a time.

The problem with this method is that you need a full grid to start with. One obvious source for these is any previously completed Sudoku. You can do certain permutations of the rows, columns, or digits to generate further variations. It is actually very difficult to find a simple way of generating a random filled grid if you want every legal filled grid to be possible, especially if you want them all to be equally likely. Thankfully however, for most practical purposes a few dozen (with their permutations) would probably be enough.

I created a Sudoku generating program years ago. My first method it used was starting with the grid empty, and this took a long time. I switched to removing numbers from a full grid, and it was much faster. The reason is that it can be quite hard to solve a Sudoku which is mostly empty, and very easy to solve a Sudoku that is mostly full. Even though more solves were needed (one for each of the 50-60 numbers removed as opposed to one for the 20-30 numbers placed), it was much faster.

Improve this answer
$\endgroup$
3
  • $\begingroup$ One may permute the numbers, the in-band-rows, the in-stack-columns, the bands and the stacks. Welcome to puzzling Jaap - thanks for your website!! $\endgroup$
    – Jonathan Allan
    May 10, 2016 at 2:53
  • $\begingroup$ I am not generate a sudoku puzzle, I am solving a puzzle. The puzzle is different from standard sudoku, it starts with with few numbers filled, usually less than 5, than complete the sudoku. The puzzle itself will has more than one solution, so common techniques won't work. $\endgroup$
    – xfx
    May 11, 2016 at 0:15
  • $\begingroup$ @xfx could you update your question to specify exactly what it is that you are attempting to achieve? An example may help. I understand you don't want a solver, but for what it's worth my dancing links solver will yield all possible completions for a given sudoku whether it has 1 solution or many. Edit: The question says you are checking the constraints as you go, so you should never hit a dead end :/ $\endgroup$
    – Jonathan Allan
    May 11, 2016 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.