Sudoku

K

K.I.L.E.R

Retarded moron
Veteran
http://en.wikipedia.org/wiki/Sudoku

My assignment is to create Sudoku and an AI that can play it.
I'm going to have a time attack mode between AI and Human.

Going to have to optimise a GA to think about as long as an average human Sudoku player.
One of my friends is good at it, so I will use him as a test. :)

I like this assignment.
 
K.I.L.E.R said:
http://en.wikipedia.org/wiki/Sudoku

My assignment is to create Sudoku and an AI that can play it.
I'm going to have a time attack mode between AI and Human.

Going to have to optimise a GA to think about as long as an average human Sudoku player.
One of my friends is good at it, so I will use him as a test. :)

I like this assignment.
Click to expand...
Isn't that a bit trivial? It's going to be no harder to program than, say, solving "the 8 queens" problem.
 
Well, to be fair, there are better algorithms to solve it than brute force/backtracking/branch&bound.

I don't think genetic algorithms are the right approach tho.
 
DemoCoder said:
Well, to be fair, there are better algorithms to solve it than brute force/backtracking/branch&bound..
Click to expand...
Well, obviously you'd immediately eliminate the impossible cases, eg (doing some of the solution work for Kruno) using a bit map per square to identify only the legal values, before launching into a recursive search. Even then you'd start with the one with the least number of possibilities.

FWIW, it seems the one I'm trying to solve (with pen and paper) at the moment will need a small amount of back tracking and can't just rely on a straightforward mechanical approach.
 
I spoke with my teacher today and she knows that using a GA isn't the best way to go.
She said that I can use any algorithm as long as I can justify it.

I'm confused.
 
K.I.L.E.R said:
I spoke with my teacher today and she knows that using a GA isn't the best way to go.
She said that I can use any algorithm as long as I can justify it.

I'm confused.
Click to expand...

For a bit of fun, last night I spent about 40 minutes writing part of a solver for Sudoku - I was curious to see how far you could get without using a recursive "what if" and just rely on having a "candidate set" per square.

I gave it the 3 examples from yesterday's "The Independent". The "Elementary" puzzle was solved trivially but the simple approach is not enough to solve the "Intermediate" nor "Advanced" puzzles. Ironically, it got further with the "Advanced" than the "Intermediate" so I'm wondering if they accidentally swapped them in the paper. :)

I might add the recursion aspect (about 10 mins work) at lunch today.

BTW: I don't think there's much chance your friend will outperform a computer... it took less than 1 millisecond to do the do the "elementary" puzzle. ;-)
 
Last edited by a moderator:
Well, I was thinking more along the lines of combinatoric approaches. Obviously, Sudoku bears some similarity and relation to Latin Squares/Steiner Triple Systems/Block Design. In fact, it's just a Latin Square with an additional constraint. That means it may possess combinatoric structure that permits a fast solution for some values of N. Whether or not that's be researched, I dunno.

I know, or atleast I heard it's been proven NP-hard. But that just means the general problem for Suduko with N symbols is NP-hard, and say nothing about particular values of N, e.g. maybe N = 1 mod 4 has trivial solution, but 3 mod 4 doesn't, etc.

Also, some graph color heuristic techniques may be feasible.
 
Last edited by a moderator:
DC: Hardly seems worth doing anything really clever. I added the necessary recursion and it solves the 'harder' puzzles in next-to-no time (i.e. under a millisecond which is the smallest unit for the "time" command on my Linux box).

On the recursion side, I always choose a square with the fewest possible number choices - it may not be the best approach, but it does work.

I know, or atleast I heard it's been proven NP-hard.
Click to expand...
It says that on the Wikipedia page that Kruno referenced.
 
Last edited by a moderator:
I have to ask, but what does "best solution" mean?
I'm having trouble understanding what a best solution would consist of.

Is it a performance factor or something else?
 
K.I.L.E.R said:
I have to ask, but what does "best solution" mean?
I'm having trouble understanding what a best solution would consist of.

Is it a performance factor or something else?
Click to expand...
I presume by "best solution" you are refering to the code/algorithm used to solve sudoku puzzles (rather than the solution to an individual puzzle).

In this case "best" (assuming such a thing exists) would mean a program that uses either the least amount of time, memory space, or both to solve a puzzle. This is simpler if you only consider puzzles of a particular size.

You could also ask how do the time and memory space requirements change with n, where n is the dimension of the puzzle. (i.e. with standard sudoku, n is 9).

For example, I chose a simple algorithm that uses space that is O(n^2 * Max_recursion_depth) but that is insignificant for the size of these puzzles. If we had to solve a Sudoku puzzle with 1,000,000 x 1,000,000 squares... well, then, I'd have to rethink the algorithm and data structures. :)
 
http://members.optusnet.com.au/ksaho/work/intelligentSystem/assignment.zip

Whatcha think Simon?
I really didn't want to polish up on the graphics because it's using J2D.
After my assignment is handed in I'm going to transfer it over to GL and have real graphics.

Press a number on your keyboard (not keypad) to select a number.
1st mouse button places than number on a tile.
2nd mouse button clears a square.
 
Last edited by a moderator:
Simon F said:
I gave it the 3 examples from yesterday's "The Independent". The "Elementary" puzzle was solved trivially but the simple approach is not enough to solve the "Intermediate" nor "Advanced" puzzles. Ironically, it got further with the "Advanced" than the "Intermediate" so I'm wondering if they accidentally swapped them in the paper. :)
Click to expand...
This is good to know. My paper just started with these puzzles, and my rudimentary solver kept solving them day after day. I was beginning to doubt if it's even possible to design a solvable puzzle that required insight/backtracking/permuting, but this nulls those doubts.

I wonder how the puzzles are made? Pseudo guess and check and then binning them?
 
A good site for puzzles that are a bit more challenging than the usual newspaper-Sudoku is:
http://www.paulspages.co.uk/sudoku/index.htm
You can either generate new Sudoku with various difficulty levels, or pick one from the gallery. The gallery has a "outlaw" section with Sudoku that need testing and back-tracking.


And if you want to generate Sudoku disconnected from the web, Simple Sudoku is a nice program:
http://www.angusj.com/sudoku/index.php
It can also give hints and have different views to help various solving techniques. But it give you so much help that it would be rather boring to use it on easy problems. (Auto-candidates)
 
K.I.L.E.R said:
Sorry.
http://members.optusnet.com.au/ksaho/work/intelligentSystem/Soduko.zip

It was a wrong link.
I password protect my backup files so students who know I backup my stuff everywhere don't go through my work and use it in theirs.
Click to expand...
OK K,
I've had a quick look at the program and I was just wondering what exactly are you trying to achieve with it?
Is it to
  • Assist someone to solve puzzles (by saving them having to use a pencil and rubber)
  • Generate Puzzles or
  • something else
because it sort of confused me as to its aim.
 
You can play the game and it can assist you.
The AI is also supposed to play the game when you click on the "lazy" button.
 
K.I.L.E.R said:
You can play the game and it can assist you.
Click to expand...

Can I suggest that
  • you put heavy borders around the 3x3 blocks and
  • highlight the currenly chosen placement number in the display
. It'd make it easier to use.
The AI is also supposed to play the game when you click on the "lazy" button.
Click to expand...
Ahh. That's the only bit I did. I entered the board as an array of strings in "C" :D
 
You must log in or register to reply here.

Similar threads

P
GTC 2024
2 3
Replies
56
Views
5K
trinibwoy
T
mr.necturus
Project Elanda free download
Replies
5
Views
310
mr.necturus
mr.necturus
F
RDNA5 Speculation
Replies
2
Views
987
Erinyes
E
Cyan
Still Wakes the Deep (PS5, PC, XSX|S, Gamepass).
Replies
7
Views
1K
ZebMacahan
Z
P
AI Desktop Tools - Training and Inferencing
2
Replies
37
Views
5K
pharma
P
Back
Top