# Programing a sudoku solver

Ashish Schottky

Ranch Hand

Posts: 93

posted 4 years ago

I am currently programing a sudoku solver in java which tries and implements using logical analysis to solve.

The basic steps that I am going to follow is

1:Find the candidates for all empty squares.

2:Eliminate them by comparing with numbers in row,column,block.

But I am having a mental block now,

to represent 81 candidates, I would require 81 arrays, hard-coding and mannual allocation of 81 arrays is inefficent.

How to do this automatically using for loops?

I have writen something like this

I thought of representing it in many ways, but jus couldnt find efficent implementation or perhaps having a mental block on how to represent the candidates array.

kindly help.

Thank you.

The basic steps that I am going to follow is

1:Find the candidates for all empty squares.

2:Eliminate them by comparing with numbers in row,column,block.

But I am having a mental block now,

to represent 81 candidates, I would require 81 arrays, hard-coding and mannual allocation of 81 arrays is inefficent.

How to do this automatically using for loops?

I have writen something like this

I thought of representing it in many ways, but jus couldnt find efficent implementation or perhaps having a mental block on how to represent the candidates array.

kindly help.

Thank you.

Stephan van Hulst

Bartender

Posts: 5334

48

posted 4 years ago

Maybe you can use sets instead. Sadly, you can't make arrays of generic types, but you can work around this by making a custom class:

Then just create an array like so:

Then just create an array like so:

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

posted 4 years ago

A Set is the logical choice, but I would just use a boolean array.

Ignore element 0 and just set the appropriate element to false as you cross it off.

Ashish Schottky wrote:I thought of representing it in many ways, but jus couldnt find efficent implementation or perhaps having a mental block on how to represent the candidates array.

A Set is the logical choice, but I would just use a boolean array.

Ignore element 0 and just set the appropriate element to false as you cross it off.

posted 4 years ago

I programmed multiple versions of my sudoku solver. I used a boolean[][][] to represent each possibility. Then you can search the array for certain patterns

to find numbers and solve the sudoku.

to find numbers and solve the sudoku.

"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." --- Martin Fowler

Please correct my English.

Ashish Schottky

Ranch Hand

Posts: 93

posted 4 years ago

thanks every one for replying.

I chose Wouter's method of using boolean[][][].

I have programed the sudoku program, which candidates by checking rows,columns and block. If there is a single candidate(naked single), it fills it on the board.

Now I am thinking of implementing hidden singles, but I donot know how to proceed or check.

Can someone help?

Pseudocode will help a lot.

I chose Wouter's method of using boolean[][][].

I have programed the sudoku program, which candidates by checking rows,columns and block. If there is a single candidate(naked single), it fills it on the board.

Now I am thinking of implementing hidden singles, but I donot know how to proceed or check.

Can someone help?

Pseudocode will help a lot.

posted 4 years ago

In case you're interested, here's a simple solver I wrote many years ago. Only 240 lines of code of which 1/3 contains hard coded board layouts. http://inasphere.com/files/SudokuJavaSrc.zip. - Cheers.

Ashish Schottky

Ranch Hand

Posts: 93

posted 4 years ago

@Carey Brown: Thanks for the reply.

I browsed through you code, it just brute-forces the things out.

I had programed a version of sudoku solver,which brute forced.Later on I got bored with it as it had no logic to come up to the solution, just sequentially checking things wont do any good as a solver.

So I decided to go for more human approach, that is to solve the puzzle by commonly used techniques of sudoku solver.

Very Easy puzzles which can be solved only by naked singles, are successfull solved by my program.

Now I am facing some difficulties to code for hidden singles.

Any hints or pseudocode??

I browsed through you code, it just brute-forces the things out.

I had programed a version of sudoku solver,which brute forced.Later on I got bored with it as it had no logic to come up to the solution, just sequentially checking things wont do any good as a solver.

So I decided to go for more human approach, that is to solve the puzzle by commonly used techniques of sudoku solver.

Very Easy puzzles which can be solved only by naked singles, are successfull solved by my program.

Now I am facing some difficulties to code for hidden singles.

Any hints or pseudocode??

Ulf Dittmer

Rancher

Posts: 42967

73

Ashish Schottky

Ranch Hand

Posts: 93

posted 4 years ago

@Ulf Dittmer: Thanks a lot for the same. I browsed through it and that is how I coded my version of brute-force program(All brute-forces are nearly the same I think, only they change on their approach and exiting the loops.)

But on then it doesnt include how to solve puzzles based on human methods of solving.

As far as my sudoku knowledge goes, I first try out for naked singles, then hidden singles. Most of the news-paper puzzles are solvable by only these two methods.

Later it goes on with naked pairs and hidden pairs, and so on. I have managed the code for naked singles, but hidden singles are something which bothers me a lot.

Manually, I can just view it, see which of the blank box has highest candidates, compare it with rows and columns and block, write it in, however I am unable to put this in code.

The main issue is, since i have boolean[][][] to check for the candidates,and then just put the index where ever the candidate is true. How to implement this for hidden singles.

But on then it doesnt include how to solve puzzles based on human methods of solving.

As far as my sudoku knowledge goes, I first try out for naked singles, then hidden singles. Most of the news-paper puzzles are solvable by only these two methods.

Later it goes on with naked pairs and hidden pairs, and so on. I have managed the code for naked singles, but hidden singles are something which bothers me a lot.

Manually, I can just view it, see which of the blank box has highest candidates, compare it with rows and columns and block, write it in, however I am unable to put this in code.

The main issue is, since i have boolean[][][] to check for the candidates,and then just put the index where ever the candidate is true. How to implement this for hidden singles.

Ralf PantfĂ¶rder

Greenhorn

Posts: 8

posted 4 years ago

My approach would be the following:

Represent the whole matrix by a 3x3x3x3 array of cells, instead of a 9x9 array, so that, e.g., cell[0, 1, 2, 0] represents the lower (2) left (0) cell in the upper (0) middle (1) block.

This way, the 27 constraints ("no double number in each row / column / block") are much easier to formulate. More precisely: The block constraints are formulated analogously to the row and column constraints, like: "keep two of the four indices fixed, and vary the two other indices." You will have much less arithmetics in your program. In fact, I think there will be no "

Represent the constraints by

Before filling a number into a cell, check whether this would violate any of the cell's three constraints, i.e., whether any of the three

Represent the whole matrix by a 3x3x3x3 array of cells, instead of a 9x9 array, so that, e.g., cell[0, 1, 2, 0] represents the lower (2) left (0) cell in the upper (0) middle (1) block.

This way, the 27 constraints ("no double number in each row / column / block") are much easier to formulate. More precisely: The block constraints are formulated analogously to the row and column constraints, like: "keep two of the four indices fixed, and vary the two other indices." You will have much less arithmetics in your program. In fact, I think there will be no "

`n / 3`" and no "`n % 3`".Represent the constraints by

`Set`s of`Integer`s. During initialization of the program, attach to each cell the pertinent constraints, so that each cell references three constraints, and each constraint is attached to nine cells.Before filling a number into a cell, check whether this would violate any of the cell's three constraints, i.e., whether any of the three

`Set`s already contains that number.