Solver written in PHP

gaby · Posted: Sun Jul 03, 2005 12:13 am Post subject: Solver written in PHP

Hi,

I've been lurking here for the past few days, absorbing as much as I can. I've been working on a PHP sudoku solver, with some success. From the information found on these boards, I've successfully implemented the swordfish/jellyfish/n-fish algorithm, along with many other types of analysis. My solver currently handles:

try_single_candidate: Look for cells that only have one candidate number

try_candidate_appears_once: Look for rows/columns/blocks in which a candidate number appears once

try_candidate_in_specific_row_col: If a number appears as candidates for two cells in two different blocks, but both cells are in the same column, it is possible to remove that number as a candidate for other cells in that column.

try_num_only_in_one_block: If a number appears in a single row or column in a block, remove that candidate from other cells in that row or column

try_matched_pairs: Look for cells in a row/column/block that have only two numbers. If there are 2 cells, and they contain only the same numbers, remove those candidates from other cells in the row/column/block.

try_x_wing: From * http://www.simes.clara.co.uk/programs/sudokutechnique6.htm, which is effectively a swordfish where N=2.

try_number_chains: Look at a row/column/block for a set of N cells that contains N different numbers between them, and no other numbers. Remove these numbers from other cells in the row/column/block. Also referred to as naked chains.

try_number_chains_inverse: Look at a row/column/block for a set of N cells that contain a set of N numbers. Remove other candidates not in the set of numbers from the cells that make up the set. Also referred to as hidden chains.

try_nishio: Implementation of the nishio limited T+E technique.

try_swordfish: Implementation of the swordfish, jellyfish, going to (N-1)-fish where N is the number of rows/columns with number pairs in

try_sledgehammer: Last resort, brute force approach. Look for the number that has least candidates, then pick a cell that it is in that has the fewest number of candidates in. Try that number as a start point for brute force.

The code tries all the methods in that order. It it manages to add some numbers or remove some candidates, then it loops back round and starts at the top of the list again, until it either solves the puzzle or gets stuck. If I disable brute force, it solves a large number of sudoku, especially now I have finally implemented the swordfish algorithm.

If anyone is interested in the code, I am happy to send a copy, and I would welcome any help or suggestions on missing algorithms or solving methods, as I don't particularly want to leave the brute force in there, and would rather just make the script smarter.

The code is mostly written with respect to converting to run on a NxN sudoku, rather than a 3x3 one, but I haven't retrofitted all the functions to work properly with it, and I haven't tested it on anything other than a 3x3 sudoku.

I would also be interested in sudokou generation, using this to solve it and guess the difficulty. Once I've taken this code as far as I can I'll be coming at it from the other end, trying to generate loads of sudoku for public consumption.

If anyone's interested in the code, pelase let me know Smile

Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

lennaz · Posted: Tue Jul 05, 2005 10:28 pm Post subject:

im really interested in it... especially the algorithms for swordfish, brute force; im workin on a php sudoku to play online, with time trial.... maybe we can exchange some knowledge

gaby · Posted: Thu Jul 07, 2005 5:30 pm Post subject: PHP Solver

Sure, if you go to my website and drop me an email, I'll get a copy over to you when I've got it nice and tidy.

http://www.vanhegan.net/contact.php
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/