# solving sudoku programmatically

satish bodas

Ranch Hand

Posts: 116

posted 7 years ago

Hello ,

I was bitten with the sudoku bug and was an avid solver of the daily sudo in the newspaper.

Thought would go about developing a program that would solve the puzzle once you feed it the problem .

I thought of two posible approaches

- apply brute force

- apply logic

Went with the apply logic approach ::

what I did was whenever I could deduce a solution to one of the sqaures manually - I listed down the steps / rules used to deduce the solution

I then converted these steps / rules into programmatic logic

That way whatever puzzles my mind could solve I put them down into code

I was able to solve simple / medium level puzzles

since I myself am not able to solve complex / difficult sudoku puzzles ( my limitation ) - couldnt write the code .

what are your thoughts ?

just curious - is this approach even remotely close to AI ?

Looking forward to your comments !

Thanks ,

~satish

I was bitten with the sudoku bug and was an avid solver of the daily sudo in the newspaper.

Thought would go about developing a program that would solve the puzzle once you feed it the problem .

I thought of two posible approaches

- apply brute force

- apply logic

Went with the apply logic approach ::

what I did was whenever I could deduce a solution to one of the sqaures manually - I listed down the steps / rules used to deduce the solution

I then converted these steps / rules into programmatic logic

That way whatever puzzles my mind could solve I put them down into code

I was able to solve simple / medium level puzzles

since I myself am not able to solve complex / difficult sudoku puzzles ( my limitation ) - couldnt write the code .

what are your thoughts ?

just curious - is this approach even remotely close to AI ?

Looking forward to your comments !

Thanks ,

~satish

Ulf Dittmer

Rancher

Posts: 42967

73

posted 7 years ago

No, that's not AI. Sudoku is a purely logical game - the fact that you can write down rules to solve it that always apply, no matter which state the game is in, is an indication of that. Putting a number down into a field is always either 100% correct or 100% wrong.

That's very different from a game like chess where, in any given position, there are multiple possible moves that lead to victory or defeat, some more likely than others to do so, and where the player needs to evaluate each move (or at least as many as possible).

There was a discussion on brute force solvers a while back: http://www.javaranch.com

[ October 11, 2008: Message edited by: Ulf Dittmer ]

That's very different from a game like chess where, in any given position, there are multiple possible moves that lead to victory or defeat, some more likely than others to do so, and where the player needs to evaluate each move (or at least as many as possible).

There was a discussion on brute force solvers a while back: http://www.javaranch.com

[ October 11, 2008: Message edited by: Ulf Dittmer ]

Geoffrey Falk

Ranch Hand

Posts: 171

1

posted 6 years ago

Here would be my approach:

The "3's" rule:

if box 1 has a number in row/col "x" and box2 has the same number in row/col "y", check the no of empty cells in row/col "z"

for each empty cell in "z", check in corresponding col/row [Note the order here, col/row not row/col] for same number.

if the number of cells that match is exactly 1, then that is the right number.

This is not an exhaustive rule, but this would solve some obvious parts of the puzzle.

I would suggest code:

you could also use special numbers for cells : eg -1 or 0 for an empty cell

if box 1 has a number in row/col "x" and box2 has the same number in row/col "y", check the no of empty cells in row/col "z"

for each empty cell in "z", check in corresponding col/row [Note the order here, col/row not row/col] for same number.

if the number of cells that match is exactly 1, then that is the right number.

This is not an exhaustive rule, but this would solve some obvious parts of the puzzle.

I would suggest code:

you could also use special numbers for cells : eg -1 or 0 for an empty cell

I agree. Here's the better link: Salvin.in

posted 6 years ago
The "entire row/col" rule

parse and check entire row/col and find out missing numbers.

check every empty cell for possiblity of a number occuring there, if the number of possibility is exactly one, there you go...

parse and check entire row/col and find out missing numbers.

check every empty cell for possiblity of a number occuring there, if the number of possibility is exactly one, there you go...

I agree. Here's the better link: Salvin.in

Ulf Dittmer

Rancher

Posts: 42967

73

posted 6 years ago

This subject has been discussed extensively (including programmatic solutions) in http://www.coderanch.com/t/35387/Programming-Diversions/SoDuko-puzzle

It is sorta covered in the JavaRanch Style Guide. |