frero-uni/TDT4136
0
0
Fork 0
Code Issues Pull Requests Releases Activity
Files
main
TDT4136/assignment2/delivery.md
fredrikr79 4451ef60e1 automate sudoku boards
2025-09-24 16:16:05 +02:00

14 KiB
Raw Permalink Blame History

title, author, date
title author date
TDT4136 Assignment 2 Erlend Ulvund Skaarberg and Fredrik Robertsen 2025-09-24

2a,c,d,e) Sudoku boards and backtrack statistics

These are the results of running our CSP solver on all four sudoku boards. It seems we get lucky on the hard board.

Additionally we calculate the time it takes for running backtracking search and AC-3 on each sudoku board.

$ for f in sudoku_*; do python3 sudoku.py $f; done

True
7 8 4 | 9 3 2 | 1 5 6
6 1 9 | 4 8 5 | 3 2 7
2 3 5 | 1 7 6 | 4 8 9
------+-------+------
5 7 8 | 2 6 1 | 9 3 4
3 4 1 | 8 9 7 | 5 6 2
9 2 6 | 5 4 3 | 8 7 1
------+-------+------
4 5 3 | 7 2 9 | 6 1 8
8 6 2 | 3 1 4 | 7 9 5
1 9 7 | 6 5 8 | 2 4 3
Backtrack failed 357 times out of 439 calls.
Running both AC-3 and backtracking search took 0.05711
Running only backtracking search took 0.04202
True
1 5 2 | 3 4 6 | 8 9 7
4 3 7 | 1 8 9 | 6 5 2
6 8 9 | 5 7 2 | 3 1 4
------+-------+------
8 2 1 | 6 3 7 | 9 4 5
5 4 3 | 8 9 1 | 7 2 6
9 7 6 | 4 2 5 | 1 8 3
------+-------+------
7 9 8 | 2 5 3 | 4 6 1
3 6 5 | 9 1 4 | 2 7 8
2 1 4 | 7 6 8 | 5 3 9
Backtrack failed 147 times out of 229 calls.
Running both AC-3 and backtracking search took 0.04713
Running only backtracking search took 0.03006
True
8 7 5 | 9 3 6 | 1 4 2
1 6 9 | 7 2 4 | 3 8 5
2 4 3 | 8 5 1 | 6 7 9
------+-------+------
4 5 2 | 6 9 7 | 8 3 1
9 8 6 | 4 1 3 | 2 5 7
7 3 1 | 5 8 2 | 9 6 4
------+-------+------
5 1 7 | 3 6 9 | 4 2 8
6 2 8 | 1 4 5 | 7 9 3
3 9 4 | 2 7 8 | 5 1 6
Backtrack failed 1225 times out of 1307 calls.
Running both AC-3 and backtracking search took 0.13033
Running only backtracking search took 0.11624
True
4 3 1 | 8 6 7 | 9 2 5
6 5 2 | 4 9 1 | 3 8 7
8 9 7 | 5 3 2 | 1 6 4
------+-------+------
3 8 4 | 9 7 6 | 5 1 2
5 1 9 | 2 8 4 | 7 3 6
2 7 6 | 3 1 5 | 8 4 9
------+-------+------
9 4 3 | 7 2 8 | 6 5 1
7 6 5 | 1 4 3 | 2 9 8
1 2 8 | 6 5 9 | 4 7 3
Backtrack failed 16016 times out of 16098 calls.
Running both AC-3 and backtracking search took 2.12073
Running only backtracking search took 2.10415

2b) domains

Here are the domains after running AC-3 on each sudoku puzzle:
(variable): {old domain} -> {new domain}

Running AC-3 on sudoku_easy.txt yields that the problem is solvable: True
AC-3 reduced the number of domain values from 473 to 294:
  X11: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 7, 8}
  X12: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 7, 8}
  X14: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 6, 7, 9}
  X16: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 6, 8}
  X17: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3}
  X19: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7}
  X22: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7, 8}
  X25: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 7, 8, 9}
  X26: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 5, 6, 8}
  X27: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 5}
  X28: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5, 6, 7}
  X29: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7}
  X31: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 6, 7}
  X32: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {3, 6, 7}
  X35: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7}
  X36: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6}
  X41: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 5, 7, 8}
  X42: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 7, 8}
  X43: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 5, 7, 8}
  X44: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5}
  X46: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5, 6}
  X49: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X52: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4}
  X53: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 5, 9}
  X55: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 8, 9}
  X57: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 8, 9}
  X58: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 6, 7, 8, 9}
  X61: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 5, 7, 8, 9}
  X64: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6, 7, 8, 9}
  X66: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6, 7, 8}
  X67: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 8, 9}
  X69: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 4, 6, 7, 8, 9}
  X74: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7, 8}
  X75: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7, 8}
  X78: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 8, 9}
  X79: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 8, 9}
  X81: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X82: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X83: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X84: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8, 9}
  X85: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8, 9}
  X88: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X91: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8}
  X93: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X94: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X96: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 6, 7, 8, 9}

Running AC-3 on sudoku_medium.txt yields that the problem is solvable: True
AC-3 reduced the number of domain values from 473 to 294:
  X11: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 7, 8}
  X12: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 7, 8}
  X14: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 6, 7, 9}
  X16: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 6, 8}
  X17: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3}
  X19: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7}
  X22: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7, 8}
  X25: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 7, 8, 9}
  X26: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 5, 6, 8}
  X27: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 5}
  X28: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5, 6, 7}
  X29: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7}
  X31: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 6, 7}
  X32: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {3, 6, 7}
  X35: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7}
  X36: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6}
  X41: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 5, 7, 8}
  X42: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 7, 8}
  X43: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 5, 7, 8}
  X44: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5}
  X46: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5, 6}
  X49: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X52: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4}
  X53: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 5, 9}
  X55: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 8, 9}
  X57: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 8, 9}
  X58: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 6, 7, 8, 9}
  X61: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 5, 7, 8, 9}
  X64: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6, 7, 8, 9}
  X66: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6, 7, 8}
  X67: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 8, 9}
  X69: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 4, 6, 7, 8, 9}
  X74: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7, 8}
  X75: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7, 8}
  X78: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 8, 9}
  X79: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 8, 9}
  X81: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X82: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X83: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X84: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8, 9}
  X85: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8, 9}
  X88: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X91: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8}
  X93: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X94: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X96: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 6, 7, 8, 9}

Running AC-3 on sudoku_hard.txt yields that the problem is solvable: True
AC-3 reduced the number of domain values from 473 to 294:
  X11: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 7, 8}
  X12: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 7, 8}
  X14: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 6, 7, 9}
  X16: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 6, 8}
  X17: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3}
  X19: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7}
  X22: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7, 8}
  X25: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 7, 8, 9}
  X26: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 5, 6, 8}
  X27: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 5}
  X28: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5, 6, 7}
  X29: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7}
  X31: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 6, 7}
  X32: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {3, 6, 7}
  X35: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7}
  X36: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6}
  X41: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 5, 7, 8}
  X42: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 7, 8}
  X43: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 5, 7, 8}
  X44: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5}
  X46: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5, 6}
  X49: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X52: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4}
  X53: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 5, 9}
  X55: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 8, 9}
  X57: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 8, 9}
  X58: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 6, 7, 8, 9}
  X61: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 5, 7, 8, 9}
  X64: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6, 7, 8, 9}
  X66: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6, 7, 8}
  X67: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 8, 9}
  X69: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 4, 6, 7, 8, 9}
  X74: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7, 8}
  X75: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7, 8}
  X78: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 8, 9}
  X79: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 8, 9}
  X81: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X82: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X83: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X84: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8, 9}
  X85: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8, 9}
  X88: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X91: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8}
  X93: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X94: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X96: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 6, 7, 8, 9}

Running AC-3 on sudoku_very_hard.txt yields that the problem is solvable: True
AC-3 reduced the number of domain values from 473 to 294:
  X11: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 7, 8}
  X12: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 7, 8}
  X14: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 6, 7, 9}
  X16: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 6, 8}
  X17: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3}
  X19: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7}
  X22: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7, 8}
  X25: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 7, 8, 9}
  X26: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 3, 5, 6, 8}
  X27: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 5}
  X28: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5, 6, 7}
  X29: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 7}
  X31: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {2, 6, 7}
  X32: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {3, 6, 7}
  X35: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7}
  X36: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6}
  X41: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 5, 7, 8}
  X42: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 7, 8}
  X43: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 5, 7, 8}
  X44: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5}
  X46: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 5, 6}
  X49: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X52: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4}
  X53: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 4, 5, 9}
  X55: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 6, 8, 9}
  X57: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 8, 9}
  X58: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 6, 7, 8, 9}
  X61: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 5, 7, 8, 9}
  X64: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6, 7, 8, 9}
  X66: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 5, 6, 7, 8}
  X67: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 8, 9}
  X69: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 4, 6, 7, 8, 9}
  X74: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7, 8}
  X75: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 7, 8}
  X78: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 8, 9}
  X79: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 8, 9}
  X81: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X82: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X83: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8}
  X84: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8, 9}
  X85: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 2, 3, 6, 8, 9}
  X88: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X91: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8}
  X93: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X94: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 6, 7, 8, 9}
  X96: {1, 2, 3, 4, 5, 6, 7, 8, 9} -> {1, 3, 4, 5, 6, 7, 8, 9}

2f) why does AC-3 drastically reduce the runtime for backtracking search?

AC-3 drastically reduces the runtime for backtracking search because it prunes the search space by eliminating inconsistent values from the domains of the variables before the backtracking search begins. By enforcing arc consistency, AC-3 ensures that many impossible assignments are removed early on, which means that the backtracking algorithm has fewer options to consider when trying to assign values to variables. This reduction in the number of potential assignments leads to fewer recursive calls and backtracks during the search process, which speeds up the backtracking search significantly. We've seen this in practice by printing the number of failures during backtracking search without AC-3. Using AC-3, we reach a few hundred failures, while without AC-3, we reach hundreds of thousands of failures within a few minutes of runtime.

Reference in New Issue View Git Blame Copy Permalink